基于聚類提取訓(xùn)練集的預(yù)測(cè)分析

楊懷珍，李玲華

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

0 引言

在決策樹(shù)研究應(yīng)用中，有學(xué)者側(cè)重于研究產(chǎn)生決策樹(shù)的訓(xùn)練和檢驗(yàn)數(shù)據(jù)的大小及特性與決策樹(shù)特性之間的關(guān)系，即著重于產(chǎn)生決策樹(shù)的數(shù)據(jù)。眾所周知，數(shù)據(jù)挖掘中的原始數(shù)據(jù)集通常存在以下問(wèn)題：屬性值不完整；多數(shù)據(jù)源集合造成的數(shù)據(jù)定義、內(nèi)涵不一致；異常、錯(cuò)誤、孤立值造成的噪聲數(shù)據(jù)；數(shù)據(jù)記錄或?qū)傩缘闹貜?fù)造成的數(shù)據(jù)冗余等。這類數(shù)據(jù)的增加并沒(méi)有都帶來(lái)決策樹(shù)準(zhǔn)確性的提高，一些專家認(rèn)為，在產(chǎn)生決策樹(shù)前盡量減少訓(xùn)練數(shù)據(jù)量比在決策樹(shù)產(chǎn)生后再簡(jiǎn)化決策樹(shù)更能夠提高決策樹(shù)的性能，實(shí)際上，這就是經(jīng)常提起的數(shù)據(jù)預(yù)處理技術(shù)，與決策樹(shù)修剪技術(shù)相對(duì)應(yīng)，也稱為數(shù)據(jù)減少技術(shù)。聚類技術(shù)可以將同一個(gè)聚類“簇”中的物理或抽象對(duì)像盡可能地彼此相似，不同聚類“簇”中的對(duì)象彼此相異，基于原始數(shù)據(jù)的缺陷及聚類的特性，將聚類應(yīng)用于分類預(yù)測(cè)前的數(shù)據(jù)預(yù)處理中，可以刪除冗余、相似、噪聲數(shù)據(jù)，從而減少訓(xùn)練數(shù)據(jù)并提高訓(xùn)練數(shù)據(jù)的質(zhì)量，進(jìn)而改進(jìn)單個(gè)決策樹(shù)的性能。

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

1 研究方法

1.1 K-means聚類算法

K-means聚類算法又稱為K均值聚類算法，其優(yōu)點(diǎn)是原理簡(jiǎn)單、算法速度快，伸縮性好。

K-means聚類算法的工作流程是：首先隨機(jī)選取K個(gè)樣本作為初始聚類中心，然后計(jì)算各個(gè)樣本到聚類中心的距離，把樣本歸到離它最近的聚類中心所在的類中，重新計(jì)算調(diào)整后的新類的聚類中心，重復(fù)這個(gè)過(guò)程，直到相鄰2次的聚類中心沒(méi)有任何變化，這時(shí)樣本調(diào)整結(jié)束，算法已經(jīng)收斂。該算法的描述如下：

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

(2)計(jì)算每個(gè)數(shù)據(jù)對(duì)象與聚類中心的距離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）。否則該算法結(jié)束。

從上面的算法思想和算法框架，不難看出，K個(gè)初始聚類中心點(diǎn)的選取對(duì)聚類結(jié)果具有較大的影響，因?yàn)樵谠撍惴ㄖ惺请S機(jī)地選取任意K個(gè)點(diǎn)作為初始聚類中心。如果有先驗(yàn)知識(shí)，可以選取具有代表性的點(diǎn)作為初始中心點(diǎn)。

1.2 決策樹(shù)及C5.0算法

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

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

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

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

1.3 研究方法

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

抽取主要過(guò)程描述如下：

樣本數(shù)據(jù)組織與預(yù)處理：數(shù)據(jù)預(yù)處理包括數(shù)據(jù)的過(guò)濾篩選和數(shù)據(jù)的規(guī)范化、離散化處理等。

建模前導(dǎo)處理：基于K-means聚類技術(shù)對(duì)客戶樣本進(jìn)行分群，抽取各個(gè)簇中心附近的一個(gè)樣本組合成為K個(gè)訓(xùn)練樣本集。

利用訓(xùn)練樣本訓(xùn)練決策分類器。

構(gòu)建預(yù)測(cè)模型。

利用測(cè)試樣本檢驗(yàn)?zāi)Ｐ汀?/p>

2 實(shí)例：某區(qū)有線電視服務(wù)交互服務(wù)訂制預(yù)測(cè)建模與應(yīng)用

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

圖1 基于K-means聚類與決策樹(shù)的有線電視交互服務(wù)訂制預(yù)測(cè)建?？蚣芘c應(yīng)用方法

2.1 數(shù)據(jù)準(zhǔn)備與預(yù)處理

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

2.2 抽取學(xué)習(xí)樣本與建立決策樹(shù)模型

決策樹(shù)算法是從樣本中學(xué)習(xí)規(guī)則，屬于監(jiān)督分類方法，因此學(xué)習(xí)樣本的好壞對(duì)決策樹(shù)模型的性能影響較大。本文依據(jù)漸進(jìn)抽樣原則，采用聚類分析中K-means算法對(duì)原始數(shù)據(jù)進(jìn)行聚類抽樣。將采集的某區(qū)的442個(gè)樣本記錄在Clementine11.1軟件中進(jìn)行數(shù)據(jù)抽樣。為了保證評(píng)價(jià)模型的學(xué)習(xí)精度，學(xué)習(xí)樣本的確定采用試驗(yàn)的方法，即根據(jù)建立的模型評(píng)價(jià)精度高低來(lái)選擇合適規(guī)模的學(xué)習(xí)樣本。本次試驗(yàn)開(kāi)始聚50個(gè)類，分別從每個(gè)聚類中心附近抽取一條記錄，得到50個(gè)訓(xùn)練樣本。通過(guò)建立評(píng)價(jià)模型來(lái)檢驗(yàn)評(píng)價(jià)模型的精度，若滿足實(shí)際情況的要求，表示該模型建立合理；如果所建立的評(píng)價(jià)模型精度不高，需要重新增加學(xué)習(xí)樣本對(duì)模型進(jìn)行訓(xùn)練，直至滿足實(shí)際工作需要為止。抽樣流程中，C5.0節(jié)點(diǎn)采用專家模式，修剪嚴(yán)重性設(shè)為20，修剪嚴(yán)重性高低的不同會(huì)影響生成的決策樹(shù)或規(guī)則集的修剪程度，增加該值可獲得一個(gè)更簡(jiǎn)潔的小型樹(shù)，減小該值可獲得一個(gè)更精確的樹(shù)。經(jīng)多次訓(xùn)練，在設(shè)為20時(shí)精確度與樹(shù)的復(fù)雜度得到較好的平衡。為了能體現(xiàn)評(píng)價(jià)的模型的實(shí)用性，檢驗(yàn)?zāi)Ｐ偷姆夯芰?，采用測(cè)試樣本是全部的樣本記錄，即442個(gè)測(cè)試樣本。

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

從圖2可以看出，150個(gè)樣本比120個(gè)樣本評(píng)價(jià)模型準(zhǔn)確率提高了4.16個(gè)百分點(diǎn)，而200個(gè)和180個(gè)學(xué)習(xí)樣本模型的準(zhǔn)確率只比120個(gè)樣本模型提高了0.56個(gè)百分點(diǎn)和0.38個(gè)百分點(diǎn)。從這些數(shù)據(jù)可以看出在150個(gè)樣本基礎(chǔ)上每增加30左右的樣本，模型精度提高的很少，表明在150個(gè)樣本點(diǎn)模型準(zhǔn)確率趨于穩(wěn)定。因此確定150個(gè)學(xué)習(xí)樣本建立的決策樹(shù)模型作為有線電視交互服務(wù)訂制預(yù)測(cè)模型，該樣本所建立的模型預(yù)測(cè)精度為87.35%。

表1 基于K-means與決策樹(shù)預(yù)測(cè)的誤分類損失

表2 基于決策樹(shù)預(yù)測(cè)的誤分類損失

2.3 試驗(yàn)結(jié)果與分析

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

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

表1表明，442名用戶中，共預(yù)測(cè)有204名用戶會(huì)訂制有線電視交互服務(wù)，其中準(zhǔn)確預(yù)測(cè)176名，即愿意接受訂制的預(yù)測(cè)準(zhǔn)確率達(dá)86.27%。預(yù)測(cè)有234名用戶將不愿意訂制有線電視交互服務(wù)，其中準(zhǔn)確預(yù)測(cè)199名，即不愿意訂制有線電視交互服務(wù)的預(yù)測(cè)準(zhǔn)確率為83.61%。

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

同樣的樣本不經(jīng)過(guò)聚類抽取學(xué)習(xí)樣本而直接用決策樹(shù)C5.0進(jìn)行預(yù)測(cè)，誤分類損失如表2所示，該模型的預(yù)測(cè)準(zhǔn)確率僅達(dá)70.14%，其中愿意接受訂制的預(yù)測(cè)準(zhǔn)確率為77.48%，該精度與基于K-means與決策樹(shù)進(jìn)行預(yù)測(cè)所得的同類精度86.27%低了8.79個(gè)百分點(diǎn)。

(3)基于K-means與決策樹(shù)C5.0預(yù)測(cè)所產(chǎn)生的部分決策規(guī)則描述

在生成決策樹(shù)之后，可以方便地提取決策樹(shù)描述的知識(shí)，沿著根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條對(duì)應(yīng)一條決策規(guī)則。

抽取部分響應(yīng)率較高的節(jié)點(diǎn)列如表3所示。

指數(shù)值大于 1的節(jié)點(diǎn)表示，通過(guò)從這些節(jié)點(diǎn)中選擇記錄而不是從整個(gè)樣本中隨機(jī)選擇記錄，能夠有更多的機(jī)會(huì)找到愿意接受訂制的用戶。抽取表3第三條規(guī)則描述如下：

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

實(shí)驗(yàn)結(jié)果表明，決策樹(shù)建模前的樣本抽樣采用聚類抽樣方法，以漸進(jìn)抽樣的原則，有效地減少了學(xué)習(xí)樣本數(shù)量，降低了評(píng)價(jià)模型的復(fù)雜度，并提高了模型的精度。

3 結(jié)論

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

[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]饒秀琪,張國(guó)基.基于KPCA的決策樹(shù)方法及其應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(7).

[3]Durkin J,蔡競(jìng)峰,蔡自興.決策樹(shù)技術(shù)及其當(dāng)前研究方向[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]葛宏偉,楊鏡非.決策樹(shù)在短期電力負(fù)荷預(yù)測(cè)中的應(yīng)用[J].華中電力,2009,(1).

[7]孫微微,劉才興,田緒紅.訓(xùn)練集容量對(duì)決策樹(shù)分類錯(cuò)誤率的影響研究[J].計(jì)算機(jī)工程與應(yīng)用,2005,(10).