決策樹C4.5算法的應(yīng)用研究

摘 要：決策樹技術(shù)是數(shù)據(jù)挖掘的重要方法，廣泛應(yīng)用于客戶分類和預(yù)測(cè)。本文對(duì)決策樹的C4.5算法的基本思想和特點(diǎn)進(jìn)行了介紹，并結(jié)合實(shí)例說(shuō)明了構(gòu)造決策樹的具體實(shí)現(xiàn)過(guò)程。

關(guān)鍵詞：決策樹；客戶分類；C4.5算法

中圖分類號(hào)：TP311.13

隨著計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫(kù)技術(shù)的不斷普及，在各應(yīng)用領(lǐng)域的業(yè)務(wù)系統(tǒng)中積累了大量的數(shù)據(jù)，如何從這些數(shù)據(jù)中提煉出隱藏在其中的有價(jià)值的信息，已經(jīng)成為一個(gè)廣泛關(guān)注和深入研究的問(wèn)題。數(shù)據(jù)挖掘就是對(duì)這些大量的數(shù)據(jù)進(jìn)行分析和推理，從中提取出有用的、有潛在應(yīng)用價(jià)值的信息或規(guī)則的過(guò)程，進(jìn)而對(duì)未來(lái)的活動(dòng)進(jìn)行分類和預(yù)測(cè)。

決策樹技術(shù)是數(shù)據(jù)挖掘的重要分支，決策樹具有簡(jiǎn)單直觀，易于理解，分類效率高等特點(diǎn)，適合對(duì)大規(guī)模訓(xùn)練數(shù)據(jù)集合進(jìn)行分析處理，在越來(lái)越多的領(lǐng)域得到了廣泛應(yīng)用，取得了很好的效果。構(gòu)造決策樹的算法有很多，如著名的ID3算法、C4.5算法等。ID3算法在構(gòu)造決策樹確定節(jié)點(diǎn)屬性時(shí)以信息增益的最大值作為選擇標(biāo)準(zhǔn)，傾向于取值較多的屬性，而在很多時(shí)候?qū)傩灾递^多的并一定是最佳的。另外ID3算法適于比較小的數(shù)據(jù)集，并且對(duì)噪聲較為敏感，而當(dāng)訓(xùn)練數(shù)據(jù)集較大時(shí)，構(gòu)建的決策樹有可能會(huì)改變等。因此針對(duì)ID3 算法的不足缺點(diǎn)，提出了改進(jìn)的C4.5算法[1]。

1 決策樹C4.5算法

C4.5算法采用信息增益率[2]作為選擇分支節(jié)點(diǎn)屬性的標(biāo)準(zhǔn)。C4.5算法在構(gòu)造決策樹過(guò)程中，計(jì)算所有屬性的信息增益率，即選擇信息增益率最大的屬性作為節(jié)點(diǎn)，依據(jù)節(jié)點(diǎn)屬性的不同取值建立不同的分支。采用遞歸的方法，對(duì)各分支的子集仍然選擇信息增益率最大的屬性作為當(dāng)前節(jié)點(diǎn)，直到子集中的實(shí)例類別相同為止。由此構(gòu)造的決策樹，其中每一個(gè)節(jié)點(diǎn)屬性都是當(dāng)前具有最大增益率的屬性，通過(guò)決策樹獲取的知識(shí)和規(guī)則可以對(duì)新的數(shù)據(jù)或已有數(shù)據(jù)進(jìn)行分類。C4.5算法涉及的相關(guān)理論知識(shí)[3]定義如下：

（1）信息熵。設(shè)S為含有n個(gè)訓(xùn)練樣本的數(shù)據(jù)集，將其劃分為m個(gè)不同的類，pi是類別i出現(xiàn)的概率。將S劃分為m個(gè)類的信息熵為：

（2）屬性A的信息增益為： （A的取值為a ，a ，…a ）

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

2 C4.5算法實(shí)例

根據(jù)如下的客戶信息基本表中數(shù)據(jù)樣本信息。應(yīng)用C4.5算法構(gòu)造決策樹，根據(jù)年齡、收入等數(shù)據(jù)信息分析判斷是客戶否購(gòu)買理財(cái)產(chǎn)品。具體步驟如下：

表1 客戶基本數(shù)據(jù)表

客戶號(hào)年齡收入穩(wěn)定工作信用購(gòu)買理財(cái)產(chǎn)品

1青年高no低no

2青年高no高no

3中年高no低yes

4老年中no低yes

5老年低yes低yes

6老年低yes高no

7中年低yes高yes

8青年中no低no

9青年低yes低yes

10老年中yes低yes

11青年中yes高yes

12中年中no高yes

13中年高yes低yes

14老年中no高no

2.1 計(jì)算屬性的信息增益率，選取信息增益率最大的屬性作為當(dāng)前節(jié)點(diǎn)。

（1）依據(jù)訓(xùn)練數(shù)據(jù)集的實(shí)例所屬類別，計(jì)算信息熵為： I=-（9/14）log（9/14）-（5/14）log（5/14）=0.94bit

（2）計(jì)算屬性的信息增益

Entropy（青年）=-（3/5）log（3/5）-（2/5）log（2/5）=0.917bit

同理：Entropy（中年）=0bit Entropy（老年）=0.971bit

Gain（年齡）=I-5/14Entropy（青年）-4/14Entropy（中年）-5/14Entropy（老年）=0.246bit

（3）計(jì)算屬性的信息增益率

I（年齡）=-（5/14）log（5/14）-（4/14）log（4/14）-（5/14）log（5/14）=1.577bit

則GainRatio（年齡）=0.246/1.577=0.507 同理，其他屬性的信息增益率為：GainRatio（收入）=0.106 GainRatio（信用狀況）=0.049 GainRatio（穩(wěn)定工作）=0.156

選取各屬性中信息增益率最大的屬性作為分支節(jié)點(diǎn)，即選擇年齡為根節(jié)點(diǎn)。

2.2 根據(jù)當(dāng)前節(jié)點(diǎn)的屬性不同取值建立不同分支，不同分支對(duì)應(yīng)不同數(shù)據(jù)子集。采用遞歸算法，在每個(gè)子集中計(jì)算屬性的信息增益率，選擇其中信息增益率最大的為當(dāng)前節(jié)點(diǎn)屬性，建立決策樹[4]。

在本例中按照年齡屬性的不同取值對(duì)應(yīng)不同子集。在各個(gè)子集中，以每條記錄的客戶號(hào)代表該記錄數(shù)據(jù)。年齡為青年子集{1，2，8，9，11}，中年{3，7，12，13}，老年{4，5，6，10，14}。其中中年子集的例子都屬于同一個(gè)類，因此對(duì)應(yīng)分枝的類別標(biāo)記為yes，對(duì)其余兩個(gè)子集的實(shí)例將繼續(xù)使用最大信息增益率的節(jié)點(diǎn)屬性確定方法。

例如對(duì)年齡為青年子集{1，2，8，9，11}，對(duì)年齡除外的屬性求信息增益率，選擇具有最大信息增益率的穩(wěn)定工作為當(dāng)前節(jié)點(diǎn)屬性，穩(wěn)定工作為no時(shí)所有記錄類別為不購(gòu)買理財(cái)產(chǎn)品，該節(jié)點(diǎn)標(biāo)記為no。穩(wěn)定工作為yes時(shí)記錄的類別為購(gòu)買理財(cái)產(chǎn)品，該節(jié)點(diǎn)標(biāo)記yes。最后構(gòu)造的決策樹如下：

圖1 建立決策樹

3 結(jié)束語(yǔ)

決策樹是數(shù)據(jù)挖掘技術(shù)中常用方法。決策樹具有直觀易于理解、效率等特點(diǎn)，除了廣泛應(yīng)用在客戶分類劃分和預(yù)測(cè)方面，決策樹在金融風(fēng)險(xiǎn)、客戶關(guān)系管理等領(lǐng)域也有著廣闊的前景。C4.5算法作為決策樹中經(jīng)典的算法，構(gòu)造決策樹是以信息增益率為選擇標(biāo)準(zhǔn)。本文著重介紹了C4.5算法的主要思想和特點(diǎn)，并通過(guò)實(shí)例數(shù)據(jù)說(shuō)明了使用C4.5算法構(gòu)造決策樹的過(guò)程。由于使用C4.5算法構(gòu)造的決策樹分類準(zhǔn)確率較高，解決了實(shí)際應(yīng)用的客戶分類劃分等問(wèn)題，得到了普遍肯定。

參考文獻(xiàn)：

[1]劉耀南.C4.5 算法的分析及應(yīng)用[J].東莞理工學(xué)院學(xué)報(bào)，2012（05）：47-52.

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

[3]張炳明，畢學(xué)慧.C4.5算法在客戶關(guān)系管理中的應(yīng)用研究[J].阜陽(yáng)師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2009，26（2）27-30.

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

作者簡(jiǎn)介：杜麗英（1969-），女，吉林長(zhǎng)春人，講師，碩士，主要從事計(jì)算機(jī)應(yīng)用方面的研究。

作者單位：吉林建筑大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，長(zhǎng)春 130118

基金項(xiàng)目：吉林省教育廳“十二五”科學(xué)技術(shù)研究項(xiàng)目（吉教科合字[2012]第198號(hào)）