基于聚類提取訓練集的預測分析

楊懷珍，李玲華

（桂林電子科技大學 管理學院，廣西 桂林 541004）

0 引言

在決策樹研究應用中，有學者側重于研究產生決策樹的訓練和檢驗數據的大小及特性與決策樹特性之間的關系，即著重于產生決策樹的數據。眾所周知，數據挖掘中的原始數據集通常存在以下問題：屬性值不完整；多數據源集合造成的數據定義、內涵不一致；異常、錯誤、孤立值造成的噪聲數據；數據記錄或屬性的重復造成的數據冗余等。這類數據的增加并沒有都帶來決策樹準確性的提高，一些專家認為，在產生決策樹前盡量減少訓練數據量比在決策樹產生后再簡化決策樹更能夠提高決策樹的性能，實際上，這就是經常提起的數據預處理技術，與決策樹修剪技術相對應，也稱為數據減少技術。聚類技術可以將同一個聚類“簇”中的物理或抽象對像盡可能地彼此相似，不同聚類“簇”中的對象彼此相異，基于原始數據的缺陷及聚類的特性，將聚類應用于分類預測前的數據預處理中，可以刪除冗余、相似、噪聲數據，從而減少訓練數據并提高訓練數據的質量，進而改進單個決策樹的性能。

本文以某區有線電視用戶數據作為研究對象，根據K-means聚類分析結果抽取訓練樣本，在訓練樣本的支持下，建立基于C5.0的決策樹模型，對用戶訂制交互服務的意愿進行預測，探索一種新的預測思路。

1 研究方法

1.1 K-means聚類算法

K-means聚類算法又稱為K均值聚類算法，其優點是原理簡單、算法速度快，伸縮性好。

K-means聚類算法的工作流程是：首先隨機選取K個樣本作為初始聚類中心，然后計算各個樣本到聚類中心的距離，把樣本歸到離它最近的聚類中心所在的類中，重新計算調整后的新類的聚類中心，重復這個過程，直到相鄰2次的聚類中心沒有任何變化，這時樣本調整結束，算法已經收斂。該算法的描述如下：

(1)給定大小為N的數據集，令I=1，選取k個初始聚類中心 zj(I),j=1,2,3,…，k。

(2)計算每個數據對象與聚類中心的距離D(Xi，Zj(I))。其中 i=1,2,3,…，k，j=1,2,3,…，k 如果滿足(1)式：

(4)判斷：若 Zi(I+1)≠Zj(I)，j=1,2,3,…，k，則 I=I+1。 返回（2）。否則該算法結束。

從上面的算法思想和算法框架，不難看出，K個初始聚類中心點的選取對聚類結果具有較大的影響，因為在該算法中是隨機地選取任意K個點作為初始聚類中心。如果有先驗知識，可以選取具有代表性的點作為初始中心點。

1.2 決策樹及C5.0算法

決策樹算法的起源是概念學習系統，是應用較廣的歸納推理算法之一，它對噪聲數據有很好的健壯性。決策樹通過把實例從根節點排列到某個葉子節點來分類，葉子節點即為實例所屬的分類。一般情況下，樹越小則樹的預測能力越強。具體來說，決策樹是對一組數據進行分類的樹形結構，要求這組數據存在于一個二維的表形結構中，表中每行數據對應一個訓練樣本并包括若干個屬性值，這些值中包含一個表征數據類別的屬性，稱類別屬性，其它屬性稱非類別屬性。根據二維表數據生成的決策樹的每個非葉子節點都對應一個非類別屬性，其分支對應于該屬性的可能取值。葉子節點則代表某記錄對應的類別屬性值。對一個新的待預測數據，生成的決策樹在每個非葉子節點上都對其屬性進行提問，確定進入哪一個分支，最后到達決定其類別屬性的葉子節點，從而獲得預測值。

C5.0決策樹算法由C4.5算法改進而成，根據提供最大信息增益的字段分割樣本數據，并對決策樹各葉子進行裁剪或合并來提高分類精度，最后確定各葉子的最佳閾值。通常不需花費大量的訓練時間即可建立決策樹，且生成的決策樹容易進行解釋。C5.0增加了強大的Boosting算法以提高分類精度，Boosting算法依次建立一系列決策樹，后建立的決策樹重點考慮以前被錯分和漏分的數據，最后生成更準確的決策樹。下面以計算評價屬性A為例計算信息增益率GainRatio(A)，S表示一組樣本，Pi是任意樣本屬于Bi的概率，用Si/s表示。假定類別屬性具有n個不同的值，定義n個不同類Bi(i=1,…，n)。設Si是類B中的樣本數。lnfo(s)表示當前樣本中的信息熵，計算如下：

設屬性A具有n個不同值{A1,A2,…，An}，利用A將S劃分為 n個子集{S1,S2,…，Sn}，其中 Sj為 S中在 A中具有 Aj的樣本，sij是子集sj中類Bi樣本數。ijfo(S,A)表示利用屬性A劃分S中所需要信息熵，計算如下：

分裂信息Splitlnfo(A)是S關于屬性A的各值的熵，用以消除具有大量屬性值屬性的偏差，計算如下：

1.3 研究方法

基于以上分析，本文的研究方法具體如圖1所示：

抽取主要過程描述如下：

樣本數據組織與預處理：數據預處理包括數據的過濾篩選和數據的規范化、離散化處理等。

建模前導處理：基于K-means聚類技術對客戶樣本進行分群，抽取各個簇中心附近的一個樣本組合成為K個訓練樣本集。

利用訓練樣本訓練決策分類器。

構建預測模型。

利用測試樣本檢驗模型。

2 實例：某區有線電視服務交互服務訂制預測建模與應用

有線電視服務交互服務是指有線電視臺可利用現有的寬帶網絡和衛星傳輸系統，將海量的數據信息加密后廣播出去，用戶可按照自己的需要，通過無線遙控器、機頂盒、IC卡等設備，在電視上自由地點播遠程節目庫中的視頻節目和信息，以及股票信息接收、交互式娛樂、電子商務、電視購物、遠程教育等增值業務服務，令人們的生活將更加快捷、豐富多彩。隨著人們消費觀念的轉變，“有償服務”也將成為未來信息服務產業的核心，付費電視業務將成為電視發展的動力和結構變化的方向，基于此的交互服務訂制與否的用戶預測具有廣闊的市場前景。

圖1 基于K-means聚類與決策樹的有線電視交互服務訂制預測建模框架與應用方法

2.1 數據準備與預處理

本文數據來源于某區有線電視網絡的442名用戶一定歷史時期市場研究資料，文中將K-means聚類分析與C5.0算法應用于有線電視交互服務的訂制預測分析中，從中找出訂制響應率較高的客戶群，分析工具采用SPSS Clementine 11.1。影響目標變量交互服務訂制與否的因素很多，根據實際操作經驗來看，通常包括：①教育程度；②性別；③年齡；④每天看電視時長；⑤所屬行業；⑥子女數目；⑦月收入等級等。預處理過程中包含對收入缺失值的補充，對月收入等級、所屬行業進行離散化處理等。

2.2 抽取學習樣本與建立決策樹模型

決策樹算法是從樣本中學習規則，屬于監督分類方法，因此學習樣本的好壞對決策樹模型的性能影響較大。本文依據漸進抽樣原則，采用聚類分析中K-means算法對原始數據進行聚類抽樣。將采集的某區的442個樣本記錄在Clementine11.1軟件中進行數據抽樣。為了保證評價模型的學習精度，學習樣本的確定采用試驗的方法，即根據建立的模型評價精度高低來選擇合適規模的學習樣本。本次試驗開始聚50個類，分別從每個聚類中心附近抽取一條記錄，得到50個訓練樣本。通過建立評價模型來檢驗評價模型的精度，若滿足實際情況的要求，表示該模型建立合理；如果所建立的評價模型精度不高，需要重新增加學習樣本對模型進行訓練，直至滿足實際工作需要為止。抽樣流程中，C5.0節點采用專家模式，修剪嚴重性設為20，修剪嚴重性高低的不同會影響生成的決策樹或規則集的修剪程度，增加該值可獲得一個更簡潔的小型樹，減小該值可獲得一個更精確的樹。經多次訓練，在設為20時精確度與樹的復雜度得到較好的平衡。為了能體現評價的模型的實用性，檢驗模型的泛化能力，采用測試樣本是全部的樣本記錄，即442個測試樣本。

在聚50個類的數據集來看，得到模型的預測精度為76.39%，預測結果誤差較大，不能完全反映接受交互服務訂制的用戶分布情況，故50個學習樣本建立模型試驗失敗。主要原因是50個聚類中各個聚類的數據之間距離過大，樣本分布不太合理，決策樹模型沒有得到充分學習，因此50個樣本不能有效地代表用戶群分布情況。為了實現評價目的，需要增大學習樣本的范圍，重新建立決策樹評價模型。依據試驗設計的路線，結合孫微微等研究成果，本次采用遞增的方式來抽取學習樣本。當采用聚80類來抽取學習樣本，重新訓練決策樹評價模型，并檢驗得到此時的模型預測精度為81.76%。從80個學習樣本建立模型的效果看出，隨著學習樣本的增加，評價模型精度有所提高，但精度依然不是很理想，需要再增大學習樣本規模，以下操作與之前相同。當選擇200個學習樣本時，與150個樣本建立的模型精度差別不明顯，停止繼續擴大樣本規模。圖2表示在六種不同的學習樣本支持下所表現出評價模型預測精度的變化曲線。

從圖2可以看出，150個樣本比120個樣本評價模型準確率提高了4.16個百分點，而200個和180個學習樣本模型的準確率只比120個樣本模型提高了0.56個百分點和0.38個百分點。從這些數據可以看出在150個樣本基礎上每增加30左右的樣本，模型精度提高的很少，表明在150個樣本點模型準確率趨于穩定。因此確定150個學習樣本建立的決策樹模型作為有線電視交互服務訂制預測模型，該樣本所建立的模型預測精度為87.35%。

表1 基于K-means與決策樹預測的誤分類損失

表2 基于決策樹預測的誤分類損失

2.3 試驗結果與分析

(1)基于K-means與決策樹C5.0預測的誤分類損失

最后，用442個樣本替代流程圖中的數據源，檢驗用150個訓練樣本建立的決策樹評價模型，其模型測試的準確率為84.84%，表明該模型的泛化能力較好，能有效地用典型性樣本推理出大量未知樣本的類別。誤分類損失如表1所示，字段NEWSCHAN表示實際的訂制意愿，字段$CNEWSCHAN則表示預測的訂制意愿，0表示不愿意接受訂制，1表示愿意接受訂制。

表1表明，442名用戶中，共預測有204名用戶會訂制有線電視交互服務，其中準確預測176名，即愿意接受訂制的預測準確率達86.27%。預測有234名用戶將不愿意訂制有線電視交互服務，其中準確預測199名，即不愿意訂制有線電視交互服務的預測準確率為83.61%。

(2)本文研究方法與基于決策樹預測的誤分類損失比較

同樣的樣本不經過聚類抽取學習樣本而直接用決策樹C5.0進行預測，誤分類損失如表2所示，該模型的預測準確率僅達70.14%，其中愿意接受訂制的預測準確率為77.48%，該精度與基于K-means與決策樹進行預測所得的同類精度86.27%低了8.79個百分點。

(3)基于K-means與決策樹C5.0預測所產生的部分決策規則描述

在生成決策樹之后，可以方便地提取決策樹描述的知識，沿著根結點到葉結點的每一條對應一條決策規則。

抽取部分響應率較高的節點列如表3所示。

指數值大于 1的節點表示，通過從這些節點中選擇記錄而不是從整個樣本中隨機選擇記錄，能夠有更多的機會找到愿意接受訂制的用戶。抽取表3第三條規則描述如下：

該用戶群為40歲以上的女性，每天看電視3小時以內，這類用戶在442名樣本用戶中共存在63位，占總體樣本的14.25%（14.25%=63*100%/442），63位用戶中有44位用戶愿意接受交互服務的訂制，即響應率為69.84%（69.84%=44*100%/63），這44位用戶數目占總體愿意接受訂制數目（如圖 3， 39+176=215名）的 20.47%(20.47%=44*100%/215)，從這些記錄中獲得積級響應的可能性是隨機選擇用戶的1.43倍 (總體響應率=215*100%/442=48.64%，1.43=69.84%/48.64%)。故可對響應指數＞1的用戶群進行有針對性的營銷。

實驗結果表明，決策樹建模前的樣本抽樣采用聚類抽樣方法，以漸進抽樣的原則，有效地減少了學習樣本數量，降低了評價模型的復雜度，并提高了模型的精度。

3 結論

本文運用聚類方法抽取決策樹模型的學習樣本，有效地減少了學習樣本空間，在試驗精度不高時增加選擇樣本，所獲得的模型的預測精度相對于僅運用決策樹進行處理有所增高，并且該模型的可解釋性較好，提取的規則能有效地識別高響應率的客戶群。進一步的工作包括對該方法進行完善和改進，以及進行深入的理論上的分析和嚴格論證，在回歸任務、神經網絡、粗集等其他一些學習方法和其他集成學習方法的基礎上進行評測。

[1]Sebbanm,Nock R,Chauchat J H,et al.Impact of Learning Set Quality and Size on Decision Tree Performances[J].IJCSS,2000,1(1).

[2]饒秀琪,張國基.基于KPCA的決策樹方法及其應用[J].計算機工程與設計,2007,28(7).

[3]Durkin J,蔡競峰,蔡自興.決策樹技術及其當前研究方向[J].控制工程,2005,12(1).

[4]Brodley C E,Friedlm A.Identifying and Eliminating Mislabeled Training Instances[C].Proceeding of the 13th National Conference on Artificial Intelligence，,1996.

[5]Uinlan J R.C4.5:Programs for Machine Learning[M].San Mateo,CA:Morgan Kaufmann,1993.

[6]葛宏偉,楊鏡非.決策樹在短期電力負荷預測中的應用[J].華中電力,2009,(1).

[7]孫微微,劉才興,田緒紅.訓練集容量對決策樹分類錯誤率的影響研究[J].計算機工程與應用,2005,(10).