基于C4.5算法的移動手機客戶應用*

劉歡 蘇勇

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

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

2 C4.5算法

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

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

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

v兩個樣本子集，這樣的劃分能夠將連續屬性c上的最終信息增益率求解出來。

算法構造決策樹過程如下所示：

1）設樣本訓練集為T；

2）首先要進行的是判斷T是否為空。如果為空的話，就返回一個失敗的值現設為A（A是一個單節點）；

3）如果T是由具有相同的屬性類B的數據集構成的話，就返回帶有B類標記的單節點；

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

5）將集合C中所有的元素都進行遍歷；

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

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

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

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

11）最后就是根據上面一個步驟中Y的結合的數值建立節點，并且將節點標記為 y1，y2，y3，y4，…，ym；

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

3 改進型的C4.5算法

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

1）按照已經存在的分類標準，訓練集將會被劃分為連續型數值類或離散型數值類輸出。

2）再根據待分類預測的樣本來遍歷整個訓練數據集：

（1）設置近鄰閾值K。

（2）對于訓練數據集中的每個樣本尋找最近鄰的K個數據點。

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

3）針對分類子集采用C4.5算法構造決策樹的方法來執行。

4）終止算法。

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

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

4 實驗結果

圖1 數據集為1500時的實驗數據

圖2 數據集為2500時的實驗數據

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

經過對比，可以看到本文改進的C4.5算法相對于經典的C4.5算法具有較為準確的分類效果。

5 移動客戶預測

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

6 結語

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