劉歡 蘇勇

（江蘇科技大學(xué)計算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

數(shù)據(jù)挖掘［1］實質(zhì)上就是一種在超級多的數(shù)據(jù)中得到重要信息的技術(shù)。到目前為止，通信流量業(yè)務(wù)的發(fā)展變得高速化而且多樣化，經(jīng)營競爭是越來越激烈，對移動的服務(wù)需求提出了更高、更新的要求。當(dāng)前，智能手機(jī)的遍及使用使得用戶的流量消費(fèi)行為更加靈活、更加粘稠。那么如何充分挖掘這些數(shù)據(jù)中隱含的規(guī)律，提高移動公司對于手機(jī)客戶流量的具體策劃，有效拉攏到更多的客戶以及保留更多的老客戶，而不是僅僅進(jìn)行一些基礎(chǔ)的查詢和統(tǒng)計制定出一個籠統(tǒng)的套餐給所有人。利用數(shù)據(jù)挖掘［2～3］在這些超級多的數(shù)據(jù)中及時的來發(fā)現(xiàn)有用的知識，提升流量的信息利用率，來滿足不同類型的客戶需求，實現(xiàn)精細(xì)化營銷［3］變得十分重要。對于在數(shù)據(jù)挖掘技術(shù)當(dāng)中分類分析是一項首要的技術(shù)，該方式的目標(biāo)就是能夠準(zhǔn)確有效地獲取這些信息，分類的主要方法是建立分類模型或分類函數(shù)。這些分類模型或者函數(shù)必須要具有數(shù)據(jù)集的特點，而這些模型則是可以從某個已知的類別中反映出某個未知的類別。C4.5算法是一種基于分類的算法，該算法易于理解、算法復(fù)雜度較低［5］。經(jīng)典的C4.5算法在運(yùn)行的的過程當(dāng)中因為各種緣由，會致使以下一些缺點：1）準(zhǔn)確率不高。2）在構(gòu)造樹的過程當(dāng)中，對于數(shù)據(jù)集有必要要進(jìn)行屢次的按照次序的掃描和排序，這樣也就導(dǎo)致了算法效率不高。3）當(dāng)內(nèi)存不能被容納時，訓(xùn)練將不能運(yùn)行［6］。很多C4.5得優(yōu)化算法為了削弱這些缺點而相繼產(chǎn)生，如文獻(xiàn)［7］提出的為改進(jìn)C4.5算法的準(zhǔn)確率而引進(jìn)了一個平衡度系數(shù)，該值是由決策者依賴先驗學(xué)問或是專業(yè)內(nèi)知識來確定的，在特定的情況之下人為妥協(xié)了各屬性信息的增益率，利用改良之后的算法來對構(gòu)造出的決策樹進(jìn)行分類變得是更加的確切且合理。改進(jìn)前后的算法再通過實例分析來進(jìn)行了比較，證實了改進(jìn)算法的有效性。文獻(xiàn)［8～10］提出的對算法上計算每個屬性中的元素的信息熵的時候進(jìn)行重新的比較來改進(jìn)C4.5算法，將多余的屬性給去除掉，從而減少了算法的復(fù)雜度，進(jìn)而提高了算法的準(zhǔn)確率，但是同時也存在著建樹的時候比較信息的時候?qū)е滤惴ǖ托б约懊鎸B續(xù)的數(shù)據(jù)處理起來比較困難。在此基礎(chǔ)上進(jìn)行改進(jìn)的一個算法為懶散式分類算法，該算法將訓(xùn)練和學(xué)習(xí)的階段合并，只有在明確分類要求時才進(jìn)行學(xué)習(xí)建立分類模型，相對而言時間消耗非常短以及時效性比較高，但是如果在分類的過程中數(shù)據(jù)規(guī)模比較大的話，就會導(dǎo)致時間開銷增加。本文中采用的改進(jìn)型的C4.5算法結(jié)合了懶散式分類算法時效性強(qiáng)、運(yùn)算時間快的特點和C4.5分類算法的預(yù)測精確度的特點設(shè)計了一個新的算法，最后為決策者得出一個準(zhǔn)確的趨勢，保證結(jié)果的客觀性。

2 C4.5算法

對于分類算法來講C4.5算法是一種比較重要的算法，是決策樹的核心算法，它的做法是用信息增益率取代了信息增益來對屬性進(jìn)行測試，這不僅支持了離散的屬性，而且還支持了連續(xù)的屬性，除此之外還對決策樹進(jìn)行了一些必須的的剪枝。

對于決策樹來講，信息增益率就是其的核心，它是在信息增益的基礎(chǔ)上發(fā)展而來的，信息增益率的公式如下所示：

C4.5的處理過程如下：設(shè)T為樣本集，c為連續(xù)型屬性。首先是通過屬性c的取值將樣本集T從小到大進(jìn)行排序，并且取到的值是互不相同的。將值進(jìn)行排序后得到的序列為v1，v2，…，vn，i∈［1，n-1］，同時還按照v=（vi+vi+1）/2和v進(jìn)行劃分的兩個樣本子集，其中，此時用gainv記錄劃分所得的信息增益。在序列v1，v2，…，vn中找出使得信息增益gainv最大的v。根據(jù)連續(xù)屬性c劃分的樣本集T的信息增益為gainv，此時樣本集H被劃分為H1v和H2

v兩個樣本子集，這樣的劃分能夠?qū)⑦B續(xù)屬性c上的最終信息增益率求解出來。

算法構(gòu)造決策樹過程如下所示：

1）設(shè)樣本訓(xùn)練集為T；

2）首先要進(jìn)行的是判斷T是否為空。如果為空的話，就返回一個失敗的值現(xiàn)設(shè)為A（A是一個單節(jié)點）；

3）如果T是由具有相同的屬性類B的數(shù)據(jù)集構(gòu)成的話，就返回帶有B類標(biāo)記的單節(jié)點；

4）如果碰到的是一個集合C為空值而這個值是無類別分類的并且含有連續(xù)屬性的，那么返回T中一個樣本數(shù)量最多的屬性值；

5）將集合C中所有的元素都進(jìn)行遍歷；

6）如果集合C中的元素Ci為連續(xù)的屬性，那么令Ci中最大值為D1，最小值為D2；

7）執(zhí)行For循環(huán)，j初始值為2，每次執(zhí)行完畢i加1，循環(huán)到i=n-2；

8）Dh=D1+i*（D1Dn）/n；

9）將Cj元素中最大的信息增益屬性值賦值到D中，再設(shè)集合A元數(shù)中的信息增益最大的屬性值為Y；

11）最后就是根據(jù)上面一個步驟中Y的結(jié)合的數(shù)值建立節(jié)點，并且將節(jié)點標(biāo)記為 y1，y2，y3，y4，…，ym；

12）其余的子樹也通過上述過程建立起來。

3 改進(jìn)型的C4.5算法

C4.5分類算法通過之前所有的數(shù)據(jù)集建立一個全局模型，其中得到的分類結(jié)果也是非常容易理解的，在決策樹中關(guān)于每一條從根節(jié)點到葉節(jié)點的路徑都對應(yīng)一種預(yù)測分類結(jié)果，由此可以看得出來算法精確度相對很高，但同時也增加了時間復(fù)雜度。結(jié)合之前分類法的優(yōu)點，我們可以設(shè)計出一種算法，不但能夠確保時效性強(qiáng)、運(yùn)算時間快，而且還可以保證C4.5分類算法的預(yù)測精確度。該算法主要步驟如下：

1）按照已經(jīng)存在的分類標(biāo)準(zhǔn)，訓(xùn)練集將會被劃分為連續(xù)型數(shù)值類或離散型數(shù)值類輸出。

2）再根據(jù)待分類預(yù)測的樣本來遍歷整個訓(xùn)練數(shù)據(jù)集：

（1）設(shè)置近鄰閾值K。

（2）對于訓(xùn)練數(shù)據(jù)集中的每個樣本尋找最近鄰的K個數(shù)據(jù)點。

（3）輸出K個近鄰作為分類子集。

3）針對分類子集采用C4.5算法構(gòu)造決策樹的方法來執(zhí)行。

4）終止算法。

在第2）步中的訓(xùn)練集的K個近鄰點是通過計算歐氏距離而度量到的。如果求出來的距離越小的話，那么就表明訓(xùn)練集的數(shù)據(jù)對象相似度越大，越為近鄰關(guān)系。對于劃分的兩個數(shù)值類型采取了不同的輸出結(jié)果：首先是當(dāng)類為連續(xù)性數(shù)值時，測試樣本的最終輸出為近鄰的平均值。同樣，當(dāng)類是離散值的時候，測試樣本的最終輸出是在特征空間中最近鄰樣本中、同類別樣本個數(shù)最多的那一個。

其中歐氏距離的計算公式為

4 實驗結(jié)果

圖1 數(shù)據(jù)集為1500時的實驗數(shù)據(jù)

圖2 數(shù)據(jù)集為2500時的實驗數(shù)據(jù)

在某個時間段上某些方面流量使用情況的人工模擬數(shù)據(jù)集上的分類準(zhǔn)確率如圖1～2所示（圖1和圖2分別是數(shù)據(jù)集為1500，2500時的實驗數(shù)據(jù)）。

經(jīng)過對比，可以看到本文改進(jìn)的C4.5算法相對于經(jīng)典的C4.5算法具有較為準(zhǔn)確的分類效果。

5 移動客戶預(yù)測

根據(jù)上述方法，并且結(jié)合以往上網(wǎng)時間段、上網(wǎng)偏好等因素，我們可以得到不同的人群在不同的時間段的不同的上網(wǎng)偏好，移動公司的相關(guān)部門可以根據(jù)曲線圖的趨勢做出對應(yīng)的決策，為客戶提供個性化的服務(wù)，這樣能夠拉攏更多的客戶，將會為移動公司帶來巨大的利潤。

6 結(jié)語

文中著重的是對算法上計算每個屬性中的元素的信息熵的時候進(jìn)行重新的比較來改進(jìn)C4.5算法，去掉了不必要的屬性，降低了算法的復(fù)雜度，進(jìn)而提高了算法的準(zhǔn)確率。研究的主要的目標(biāo)是為了公司相關(guān)部門人員分配的參考，所以這邊的分類中心就只需要幾個。下一步的研究方向是針對本算法中的不足，研究如何將每個屬性中的元素的信息熵重新的比較，并優(yōu)化算法分類的準(zhǔn)確率，以便為相關(guān)部門提供有力的參考依據(jù)。