杜麗英

（吉林建筑大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，長春 130118）

0 引言

隨著數(shù)據(jù)庫技術(shù)的廣泛應(yīng)用和數(shù)據(jù)庫管理系統(tǒng)的普及，現(xiàn)在各行業(yè)使用的信息系統(tǒng)尤其是國內(nèi)金融部門使用的大多數(shù)業(yè)務(wù)處理系統(tǒng)都是基于數(shù)據(jù)庫的，能夠?qū)崿F(xiàn)業(yè)務(wù)數(shù)據(jù)的錄入、查詢、更新、統(tǒng)計(jì)等功能，并將與業(yè)務(wù)相關(guān)的數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫中。數(shù)據(jù)庫存儲(chǔ)中的這些大量數(shù)據(jù)往往隱含著重要信息，如果對(duì)其進(jìn)行深入的分析，挖掘數(shù)據(jù)背后隱藏的信息，發(fā)現(xiàn)大量客戶數(shù)據(jù)中潛在的關(guān)聯(lián)和規(guī)則，以此對(duì)未來的發(fā)展趨勢做出預(yù)測，從而在企業(yè)的管理和決策中發(fā)揮重要作用。數(shù)據(jù)挖掘就是從大量的數(shù)據(jù)中提取出隱藏在其中的，有應(yīng)用價(jià)值的信息和規(guī)則的過程。

客戶關(guān)系管理（Customer Relationship Management，CRM）是一種以客戶為核心的經(jīng)營理念，通過不斷完善客戶的服務(wù)來實(shí)現(xiàn)企業(yè)利潤的增長。即通過客戶信息的分析處理，不斷改進(jìn)客戶業(yè)務(wù)流程，滿足客戶需求，為客戶提供所需要的服務(wù)等手段來實(shí)現(xiàn)客戶和企業(yè)利潤的增加，提高對(duì)客戶的營銷能力，從而實(shí)現(xiàn)客戶和企業(yè)的相互的利益滿足?？蛻舴诸愂荂RM中一個(gè)重要方面，而決策樹方法是分類分析的常用工具。

決策樹是數(shù)據(jù)挖掘技術(shù)中常用的分類方法，將挖掘的結(jié)果以樹形結(jié)構(gòu)的圖形方式體現(xiàn)出來，具有結(jié)構(gòu)簡單，易于理解，效率高等優(yōu)點(diǎn)。決策樹分類挖掘技術(shù)廣泛應(yīng)用于各行業(yè)的客戶關(guān)系管理系統(tǒng)中，通過對(duì)客戶相關(guān)信息的分析，對(duì)客戶所屬的類別進(jìn)行預(yù)測，從而采取相應(yīng)的措施和服務(wù)策略，提高服務(wù)水平和工作效率，從而得到較大的收益。

1 決策樹C4.5算法

1.1 C4.5算法

決策樹在數(shù)據(jù)挖掘領(lǐng)域因其分類預(yù)測的準(zhǔn)確率較高、直觀易于理解等特點(diǎn)，廣泛應(yīng)用在各領(lǐng)域。決策樹算法比較多，不同算法創(chuàng)建的決策樹的性能也各有所不同，ID3和C4.5算法是決策樹方法中最有影響力的算法，主要進(jìn)行數(shù)據(jù)分類劃分的處理。C4.5算法是ID3算法的改進(jìn)和擴(kuò)充。ID3算法只能對(duì)連續(xù)型屬性數(shù)據(jù)進(jìn)行處理，而C4.5算法既可以處理離散型屬性數(shù)據(jù)，也能夠?qū)B續(xù)性屬性數(shù)據(jù)進(jìn)行處理。

C4.5算法構(gòu)造決策樹時(shí)選擇分支節(jié)點(diǎn)屬性的依據(jù)是信息增益率。ID3算法中節(jié)點(diǎn)屬性的選擇標(biāo)準(zhǔn)是信息增益的大小，因?yàn)橛休^多取值的屬性具有較大的信息增益的特點(diǎn)，ID3算法節(jié)點(diǎn)屬性的選擇側(cè)重于取值較多的屬性[1]。而C4.5算法以信息增益率為屬性節(jié)點(diǎn)的選擇依據(jù)，克服了ID3算法的傾向于選擇取值較多的屬性的不足。

1.2 C4.5算法的處理過程

C4.5算法的詳細(xì)步驟如下：

步驟1：若數(shù)據(jù)集中的有連續(xù)型屬性，需要離散化處理。進(jìn)行離散化數(shù)據(jù)預(yù)處理后，進(jìn)行根節(jié)點(diǎn)屬性的選擇。計(jì)算數(shù)據(jù)集中所有屬性的信息增益率，選擇其中的最大值的屬性作為根節(jié)點(diǎn)屬性。

1）計(jì)算數(shù)據(jù)集分類的信息期望I。設(shè)S為有n個(gè)實(shí)例的數(shù)據(jù)集合，依據(jù)實(shí)例所屬的類別，集合S有m種劃分{S1,S2,…,Si,…Sm}，每種劃分的實(shí)例數(shù)目為ni，pi=ni/n是Si類出現(xiàn)的概率。將集合S劃分為m個(gè)類別的信息熵或信息期望[2]為：

2）計(jì)算非類別屬性A的信息期望I(A=aj)，j=1,2,…,v，即屬性A有v個(gè)取值，將S劃分為v個(gè)子集{D1,D2,…,Dv}，Dj為A=aj時(shí)的子集，Dj的實(shí)例數(shù)為dj，Dj子集中屬于Si類的實(shí)例數(shù)為dij，屬于第i類的概率為pij，pij=dij/ dj，信息期望I(A=aj)為：

當(dāng)A=aj時(shí)的概率為pj=dj/n，利用屬性A的取值進(jìn)行劃分子集的期望信息，即A的熵為：

屬性A在進(jìn)行分類劃分時(shí)提供的信息量，稱作屬性A的信息增益，記為Gain(A)：

3）屬性A的信息增益率：

其中I(A)為屬性A的取值劃分集合S的信息期望的比值

步驟2：確定節(jié)點(diǎn)屬性后，根據(jù)節(jié)點(diǎn)屬性不同取值建立不同的分支，而屬性值的不同取值對(duì)應(yīng)不同的數(shù)據(jù)子集。依此類推，對(duì)各數(shù)據(jù)子集，仍然以信息增益率最大值的屬性作為作為子節(jié)點(diǎn)屬性的選擇標(biāo)準(zhǔn)[3]，直到各子集的實(shí)例都屬于同一類別為止，由此就能構(gòu)造一棵決策樹。

步驟3：提取決策規(guī)則。生成決策樹后，就可以依據(jù)各分支上屬性的取值獲取決策規(guī)則，新數(shù)據(jù)集就可以根據(jù)決策規(guī)則進(jìn)行分類預(yù)測。

1.3 C4.5算法對(duì)連續(xù)屬性的處理

C4.5算法既能處理離散型屬性數(shù)據(jù)，也能夠?qū)B續(xù)性屬性數(shù)據(jù)進(jìn)行處理[4]。若數(shù)據(jù)集中有連續(xù)型屬性時(shí)，需要對(duì)連續(xù)屬性的值進(jìn)行離散化處理，選擇分支節(jié)點(diǎn)屬性以信息增益率作為標(biāo)準(zhǔn)。

如果某節(jié)點(diǎn)中數(shù)據(jù)集合T的實(shí)例中有連續(xù)型屬性A，C4.5算法需進(jìn)行離散化處理[5]。首先可對(duì)連續(xù)屬性值進(jìn)行排序，確定連續(xù)屬性的最大值和最小值，采用一定的算法將整個(gè)區(qū)間劃分成多個(gè)相等的子區(qū)間或以排序后的連續(xù)型屬性的相鄰值的均值設(shè)定子區(qū)間，然后計(jì)算該屬性的信息增益率，以信息增益率的最大值為標(biāo)準(zhǔn)找到連續(xù)屬性的分割點(diǎn)，對(duì)連續(xù)型屬性的實(shí)際取值進(jìn)行順序查找確定實(shí)際的分割點(diǎn)[6]。具體步驟如下：

1）對(duì)節(jié)點(diǎn)對(duì)應(yīng)的T集合上的所有實(shí)例中連續(xù)型描述屬性的取值，按從小到大的順序進(jìn)行排列，得到屬性A的取值的順序排列{a1,a2,…,av}。

2）計(jì)算信息增益率。屬性A的取值ai，其中1≤i≤v-1，按值a=(ai+ai+1)／2將集合T劃分為兩個(gè)子集：T1={ai| ai≤a}和T2={aj| aj＞a}，然后計(jì)算屬性A按照a值劃分的信息增益率。a值用區(qū)間[a1，ai]，[ai,ai+1]來描述屬性A的取值。

3）確定連續(xù)屬性的分割點(diǎn)。屬性A的每個(gè)v-1種劃分，ai和ai+1都可看作該連續(xù)屬性的2個(gè)離散取值的情況進(jìn)行處理，計(jì)算每種a值劃分的信息增益率，選擇v-1種劃分中具有信息增益率最大值的a作為連續(xù)屬性的分割點(diǎn)。

4）確定實(shí)際分割點(diǎn)。在屬性A的取值序列{a1，a2,…,av}中找出最接近分割點(diǎn)a，但又不超過它的屬性A的取值ai，將ai作為屬性A的實(shí)際分割點(diǎn)，完成對(duì)連續(xù)型屬性A的離散化處理。

2 連續(xù)屬性處理過程的改進(jìn)

將數(shù)據(jù)集合T以屬性A的值按照升序排序后，在離散化的處理過程中進(jìn)行信息增益率的計(jì)算時(shí)，可將通過比較得到的信息增益率最大值和對(duì)應(yīng)的分割點(diǎn)的序列值分別保存到變量GainMax和IndexMax中，變量的初值可設(shè)為零。當(dāng)計(jì)算完所有的v-1個(gè)區(qū)間的信息增益率值時(shí)，就得到了GainMax和IndexMax值，這樣能夠提高效率，節(jié)省運(yùn)算時(shí)間，也省略了多次順序查找，因?yàn)槿绻谟?jì)算出的v-1個(gè)信息增益率中找出最大的信息增益率，又在連續(xù)型屬性取值中查找最接近但又不超過屬性分割點(diǎn)的屬性A的取值ai，多次的查找會(huì)使算法的執(zhí)行效率降低。

當(dāng)數(shù)據(jù)集較大且連續(xù)屬性值比較多時(shí)，在離散化處理時(shí)，對(duì)所有劃分計(jì)算信息增益率會(huì)占用較多的時(shí)間，如何快速找到最佳劃分點(diǎn)，即屬性分割點(diǎn)成為解決問題的關(guān)鍵。根據(jù)Fayyad的研究，無論數(shù)據(jù)集類別有多少種，連續(xù)型屬性所屬類別分布如何，最佳劃分點(diǎn)總是在類別邊界點(diǎn)處，實(shí)際的分割點(diǎn)總是出現(xiàn)在邊界處，因此對(duì)離散化方法可做進(jìn)一步優(yōu)化。具體步驟如下：

1）將該節(jié)點(diǎn)上的數(shù)據(jù)集合按照連續(xù)型屬性的取值從小到大進(jìn)行順序排列，即A屬性的取值的順序序列{a1，a2,…，av}。

2）計(jì)算信息增益率。假設(shè)數(shù)據(jù)集合T分成兩個(gè)類別,以A屬性ai為邊界處，即分割點(diǎn)，其中1≤i≤v-1，得到兩個(gè)子集：T1={aj|1≤j≤i}和T2={aj| i＜j≤v}，計(jì)算按ai劃分的信息增益率。

3）確定連續(xù)屬性的分割點(diǎn)。假設(shè)數(shù)據(jù)集合T分成多個(gè)類別，通過類別邊界處找到分割點(diǎn)。這里分割點(diǎn)可選為相鄰不同類別的兩個(gè)屬性值中較小的一個(gè)。例如，當(dāng)排序后的實(shí)例屬性值為(a1，a2,…,a8)，其中前2個(gè)屬于類別1，中間3個(gè)屬于類別2，最后3個(gè)屬于類別3，a2與a3分別屬于類別1與類別2，邊界點(diǎn)在a2與a3之間，選擇屬性值較小的a2為分割點(diǎn)，因此只需考察兩個(gè)分割點(diǎn)a2與a5而無需檢查其余6個(gè)分割點(diǎn)。

4）確定實(shí)際分割點(diǎn)。計(jì)算按照屬性分割點(diǎn)的值劃分得到的信息增益率，選擇信息增益率最大的屬性值作為最佳分割點(diǎn)。

3 改進(jìn)的處理過程與原處理過程的分析比較

在處理連續(xù)屬性的離散化時(shí)，需要將數(shù)據(jù)集合T以連續(xù)屬性A的值從小到大排序，減少了后續(xù)處理過程中排序和查找的次數(shù)，提高了確定分割點(diǎn)的效率。在原C4.5算法中數(shù)據(jù)集合T中屬性A的值為ai(1≤i≤v-1)，按值a=(ai+ai+1)／2將T劃分為兩個(gè)子樣本集，改進(jìn)的C4.5算法中直接用ai將T劃分為兩個(gè)子樣本集，由于{a1，a1,…，av}是有序序列，用ai將T劃分為兩個(gè)子樣本集與用a劃分的效果相同。同樣在計(jì)算信息增益率的過程中得到最大信息增益率和分割點(diǎn)序號(hào)，節(jié)省了兩次順序查找的時(shí)間，因此改進(jìn)后的C4.5算法并沒有改變原C4.5算法構(gòu)造的決策樹性質(zhì)。

改進(jìn)的分割點(diǎn)選擇方法可以有效地減少信息增益率的計(jì)算次數(shù)，從而提高效率，當(dāng)屬性的取值越多，而所屬的類別越少，性能會(huì)有明顯的提高。當(dāng)屬性的每個(gè)取值都屬于一種類別這種極端的情況出現(xiàn)時(shí)，改進(jìn)算法與未改進(jìn)算法運(yùn)行次數(shù)相同，運(yùn)行效率也不會(huì)降低。在未改進(jìn)的算法中，需要計(jì)算所有劃分的信息增益率，而在改進(jìn)后的算法中，只計(jì)算邊界點(diǎn)處的屬性值的信息增益率，降低了計(jì)算復(fù)雜度。當(dāng)連續(xù)型屬性所屬的類別較少時(shí)如只有2種類別時(shí)，改進(jìn)后的算法計(jì)算效率有明顯提高。當(dāng)遇到極端情況時(shí)，每個(gè)屬性值分別屬于不同類別，改進(jìn)算法的與C4.5的計(jì)算復(fù)雜度相同。

4 實(shí)驗(yàn)分析對(duì)比

選取UCI機(jī)器學(xué)習(xí)庫中的有14條記錄的weather數(shù)據(jù)集創(chuàng)建決策樹，根據(jù)天氣的情況判斷是否適合打球（yes為適合，no為不適合），使用C4.5算法和改進(jìn)的C4.5算法構(gòu)造的決策樹相同(如圖1)，由此可知，改進(jìn)的C4.5算法與原算法有大致相同的準(zhǔn)確率。

圖1 C4.5算法與C4.5改進(jìn)算法構(gòu)造的決策樹

在UCI機(jī)器學(xué)習(xí)庫中選取4個(gè)數(shù)據(jù)集，這4個(gè)數(shù)據(jù)集中都有連續(xù)型屬性值，通過數(shù)據(jù)集的測試將改進(jìn)前后的算法在運(yùn)算時(shí)間上進(jìn)行分析比較。其中各數(shù)據(jù)集如表1所示。

表1 數(shù)據(jù)集的屬性及實(shí)例數(shù)

C4.5算法與改進(jìn)的C4.5算法運(yùn)算時(shí)間的對(duì)比如圖2所示。

圖2 C4.5算法與C4.5改進(jìn)算法運(yùn)算時(shí)間比較

使用數(shù)據(jù)集構(gòu)造決策樹所用時(shí)間，與數(shù)據(jù)集的大小及連續(xù)型屬性值的多少有關(guān)。通過上述4個(gè)數(shù)據(jù)集進(jìn)行測試的結(jié)果可以看出，使用改進(jìn)的C4.5算法構(gòu)造決策樹所用的時(shí)間比未改進(jìn)的算法要快，尤其在數(shù)據(jù)量較大時(shí)較為明顯，對(duì)相同規(guī)模的數(shù)據(jù)集，改進(jìn)的C4.5算法構(gòu)造決策樹所用的時(shí)間較少。

5 結(jié)束語

本文詳細(xì)的分析了決策樹分類算法C4.5，針對(duì)C4.5算法的連續(xù)屬性離散化處理過程中需要處理所有劃分情況的特點(diǎn)，根據(jù)Fayyad邊界點(diǎn)判別定理，提出了盡快找到最佳劃分的改進(jìn)方法，算法運(yùn)算速度得到了提高，改進(jìn)的C4.5算法與原算法相比，在構(gòu)造決策樹時(shí)具有相同的準(zhǔn)確率和較高的計(jì)算速度。

[1]姚亞夫,邢留濤.決策樹C 4.5 連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,42(12)：3772-3776.

[2]黃文.決策樹的經(jīng)典算法：ID3與C4.5 [J].四川文理學(xué)院學(xué)報(bào)(自然科學(xué)),2007,17(5)：16-18.

[3]劉耀男.C4.5算法的分析及應(yīng)用[J].東莞理工學(xué)院學(xué)報(bào),2012,19(5)：47-52.

[4]馮帆,徐俊剛.C4.5決策樹改進(jìn)算法研究[J].電子技術(shù),2012,39(6)：1-4.

[5]喬曾偉,孫衛(wèi)祥.C4.5算法的兩點(diǎn)改進(jìn)[J].江蘇工業(yè)學(xué)院學(xué)報(bào),2008,20(4)：56-59.

[6]李慧慧,萬武族.決策樹分類算法C4.5中連續(xù)屬性過程處理的改進(jìn)[J].計(jì)算機(jī)與現(xiàn)代化,2010(8)：8-10.