劉歡 蘇勇

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

1 引言

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

2 C4.5算法

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

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

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

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

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

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

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

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

4）如果碰到的是一個(gè)集合C為空值而這個(gè)值是無類別分類的并且含有連續(xù)屬性的，那么返回T中一個(gè)樣本數(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ù)上面一個(gè)步驟中Y的結(jié)合的數(shù)值建立節(jié)點(diǎn)，并且將節(jié)點(diǎn)標(biāo)記為 y1，y2，y3，y4，…，ym；

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

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

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

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

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

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

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

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

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

4）終止算法。

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

其中歐氏距離的計(jì)算公式為

4 實(shí)驗(yàn)結(jié)果

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

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

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

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

5 移動(dòng)客戶預(yù)測(cè)

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

6 結(jié)語

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