基于決策樹(shù)分類算法的研究與應(yīng)用

路 翀，徐 輝，楊永春

（1.新疆交通職業(yè)技術(shù)學(xué)院 新疆 烏魯木齊 831401；2.伊犁師范學(xué)院 電子與信息工程學(xué)院，新疆 伊寧 835000）

基于決策樹(shù)分類算法的研究與應(yīng)用

路 翀1，徐 輝2，楊永春1

（1.新疆交通職業(yè)技術(shù)學(xué)院 新疆 烏魯木齊 831401；2.伊犁師范學(xué)院 電子與信息工程學(xué)院，新疆 伊寧 835000）

首先采用企業(yè)的客戶數(shù)據(jù)作為樣本數(shù)據(jù)進(jìn)行客戶的穩(wěn)定性分析,然后，提出了一種基于ID3算法的改進(jìn)分類算法,該分類新的算法是在經(jīng)典ID3算法基礎(chǔ)上引入粗糙組合屬性的思想，使得期望非葉節(jié)點(diǎn)到各葉節(jié)點(diǎn)的平均路徑最短，從而提升分類的速度和準(zhǔn)確率。通過(guò)實(shí)例對(duì)改進(jìn)算法生成決策樹(shù)產(chǎn)生的結(jié)果分析，表明了該算法生成的決策樹(shù)結(jié)構(gòu)更簡(jiǎn)單，時(shí)間復(fù)雜度更優(yōu),算法更有效。

決策樹(shù)；ID3算法；分裂屬性；粗糙集理論

決策樹(shù)（Decision Tree，DT）是一種用于分類，聚類和預(yù)測(cè)的建模方法。決策樹(shù)采用“分而治之”的方法將問(wèn)題的搜索空間分為若干子集，這些子集由決策樹(shù)的根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)表示。每個(gè)節(jié)點(diǎn)引出的弧代表了該節(jié)點(diǎn)相關(guān)聯(lián)的問(wèn)題的可能答案。每個(gè)葉節(jié)點(diǎn)代表對(duì)問(wèn)題解決方案的一個(gè)預(yù)測(cè)輸出[1]。

決策樹(shù)分類算法的關(guān)鍵問(wèn)題在于選擇一個(gè)恰當(dāng)?shù)姆诸悓傩砸?guī)則，利用恰當(dāng)?shù)囊?guī)則產(chǎn)生的分支可加快決策樹(shù)的生長(zhǎng)以及產(chǎn)生較優(yōu)化結(jié)構(gòu)的決策樹(shù)，從而獲得較準(zhǔn)確的知識(shí)。隨著訓(xùn)練樣本的規(guī)模不斷擴(kuò)大，尤其訓(xùn)練樣本的屬性空間不斷擴(kuò)大。訓(xùn)練樣本獨(dú)立分散在主存中不僅費(fèi)時(shí)，而且影響算法效率。同時(shí)，分析數(shù)據(jù)的算法往往由于數(shù)據(jù)的多構(gòu)化不規(guī)則性，且需要跨學(xué)科跨領(lǐng)域的研究。因此，優(yōu)化算法使其有效地處理各種大規(guī)模的數(shù)據(jù)已經(jīng)成為決策樹(shù)分類算法的重要研究方向[2-3]，也是目前國(guó)內(nèi)對(duì)決策樹(shù)分類算法研究的熱點(diǎn)。

1 決策樹(shù)的分類算法

決策樹(shù)分類方法將搜索空間劃分為一些矩形區(qū)域，然后根據(jù)元組（或?qū)ο?，?shí)例）落入的區(qū)域?qū)υM進(jìn)行分類。給定一個(gè)數(shù)據(jù)庫(kù)

其中元組

其屬性空間為

其中ai為每個(gè)內(nèi)部節(jié)點(diǎn)。同時(shí)，給定類別集合

其中cj被標(biāo)記為每個(gè)葉節(jié)點(diǎn)，且記cj中的樣本數(shù)為tl。每個(gè)弧都被標(biāo)記一個(gè)謂詞，這個(gè)謂詞可應(yīng)用于相應(yīng)父節(jié)點(diǎn)的屬性。

1984年，Quinlan在《Introduction of decision trees》中提出了著名的ID3算法[4]，其關(guān)鍵思想是利用信息熵原理，選擇信息增益（Gain）最大的屬性作為分類屬性，遞歸地構(gòu)造決策樹(shù)的分枝，最大限度地減少正確分類所需要的信息。之后，Quinlan提出ID3優(yōu)化算法C4.5[5]，在幾個(gè)方面的不足上進(jìn)行了改進(jìn)，提出信息增益率（GainRatio）的概念，其定義如下，給定概率：

其中則熵的定義為：

若給定一個(gè)數(shù)據(jù)狀態(tài)D，以及該狀態(tài)被分裂為j個(gè)新?tīng)顟B(tài)

則分裂屬性的信息增益定義

其增益比率定義[1]

則分裂屬性的信息增益定義其增益比率定義[1]。

本文對(duì)客戶的穩(wěn)定性分析所提出的分類算法在經(jīng)典ID3算法基礎(chǔ)上引入粗糙組合屬性的思想[6]，期望非葉節(jié)點(diǎn)到各葉節(jié)點(diǎn)的平均路徑最短，提升分類的速度和準(zhǔn)確率。

假設(shè)在給定數(shù)據(jù)庫(kù)D中，屬性au∈A（1≤u≤h）是分類決策樹(shù)中決定分裂屬性的Gain的值較大的，稱為強(qiáng)分裂屬性。屬性av∈A（1≤u≤h，u≠v），相應(yīng)地，每次遞歸計(jì)算中Gain值較小的，稱為弱分裂屬性。若對(duì)象的非空有限集合U中任意的子集V，不能夠?qū)⒎强沼邢藜疷中的某些對(duì)象區(qū)分開(kāi)，則記作Dim（V）。若刪除屬性，

則定義弱分裂屬性集AV:=Uav；同樣地，

則定義強(qiáng)分裂屬性集

其中

2 粗糙集理論

粗糙集理論[7-9]的核心就是將知識(shí)和分類結(jié)合在一起，并用等價(jià)類關(guān)系形式化構(gòu)造商集合U/R={X1，X2，…，Xm}，其中Xi就是U/R的一個(gè)等價(jià)類。

由于不可分關(guān)系計(jì)算的時(shí)間復(fù)雜度直接影響到算法的復(fù)雜度，Rough集理論中利用求等價(jià)類劃分的算法。基于基數(shù)排序的思想可以將求等價(jià)類劃分的時(shí)間復(fù)雜度降低到O(|P|| U|），其中P位屬性子集中屬性的數(shù)量，U為論域[10-13]。所以這就解釋了結(jié)合粗糙集理論的分類算法在速度和準(zhǔn)確性上會(huì)有一定程度的提升。

3 本文提出的分類算法

經(jīng)典ID3算法是選取Gain值最大的屬性作為優(yōu)先分裂屬性。本文提出的結(jié)合粗糙集理論的分類算法首先是組合強(qiáng)分裂屬性，然后生成決策樹(shù)，具體優(yōu)化后的算法如下：

4 基于客戶流失實(shí)例分析

下文采用某企業(yè)的客戶數(shù)據(jù)（共計(jì)600條記錄），作為樣本數(shù)據(jù)進(jìn)行分析，如表1所示。

表1 原始樣本數(shù)據(jù)

4.1 數(shù)據(jù)預(yù)處理

由于樣本數(shù)據(jù)存在結(jié)構(gòu)差異，故需要對(duì)原始數(shù)據(jù)作定義處理。屬性：

結(jié)構(gòu)化后數(shù)據(jù)樣本如表2所示。

4.2 生成決策樹(shù)

首先由經(jīng)典ID3算法，根據(jù)結(jié)構(gòu)化數(shù)據(jù)樣本建立客戶流失分析的決策樹(shù)模型，如圖1所示。為了改進(jìn)算法的時(shí)間復(fù)雜性與準(zhǔn)確性，將訓(xùn)練樣本也采用結(jié)合粗糙集組合屬性的算法建立決策樹(shù)，如圖2所示。

表2 結(jié)構(gòu)化樣本數(shù)據(jù)

圖1 ID3算法模型圖

圖2 ID3改進(jìn)算法模型圖

4.3 分 析

結(jié)果中葉節(jié)點(diǎn)0表示常駐客戶，1表示非常駐客戶，2表示極有可能流失客戶。從時(shí)間復(fù)雜度方向的評(píng)價(jià)，粗糙集組合屬性構(gòu)建的決策樹(shù)擁有更簡(jiǎn)潔的樹(shù)結(jié)構(gòu)，所花費(fèi)的時(shí)間優(yōu)于經(jīng)典ID3算法，有利于決策者做出決策，尤其在遇到較多維屬性的樣本時(shí)，采用粗糙集組合屬性的思想結(jié)合分類算法對(duì)數(shù)據(jù)進(jìn)行處理時(shí)十分有必要的。另一方面，解決了ID3算法常見(jiàn)的問(wèn)題，即在整個(gè)搜索過(guò)程中出現(xiàn)的局部最優(yōu)而非全局最優(yōu)。

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

文中提出的優(yōu)化算法與ID3算法的分析比較，得出此方法生成的決策樹(shù)結(jié)構(gòu)更簡(jiǎn)單，時(shí)間復(fù)雜度更優(yōu)。盡管如此，改進(jìn)后的算法仍有待完善，主要體現(xiàn)在以下的幾方面：1）簡(jiǎn)單的優(yōu)化目前之限于多維的數(shù)據(jù)庫(kù)，對(duì)高維的數(shù)據(jù)庫(kù)，比如上萬(wàn)維的生物基因信息數(shù)據(jù)庫(kù)，需要更多的優(yōu)化；2）由于本文的數(shù)據(jù)與結(jié)果存在著一定的相關(guān)性，所以在很多情況下，需要對(duì)屬性進(jìn)行刪減，其目的與算法剪枝類似，防止決策樹(shù)過(guò)擬合；3）其準(zhǔn)確性在不同的樣本中表現(xiàn)不一樣，若追求既快速又準(zhǔn)確地算法有待更進(jìn)一步完善[14-19]。

[1]Margaret H.Dunham Data Mining Introductory and Advanced Topics[D].Arrangement with the original publisher，Pearson Education，Inc，2003：51-102.

[2]劉小虎，李生.決策樹(shù)的優(yōu)化算法[J].軟件學(xué)報(bào)，1998，9（10）:797-800.

[3]馮少榮.決策樹(shù)算法的研究與改進(jìn)[J].廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，7（46）：496-500.

[4]Ouinlan JR.Induction of decision trees[J].Machine Learning，1998（1）:81-106.

[5]Ouinlan JR.C4.5:Programsformachine learning[M].California:Morgan Kaufmann Publishers Inc.，1993.

[6]于海平，朱玉金，陳耿.一種基于粗糙集理論的決策樹(shù)構(gòu)造方法[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（2）:80-84.

[7]王國(guó)胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2011，7（32）：1229-1246.

[8]馬文萍，黃媛媛，李豪，等.基于粗糙集與差分免疫模糊聚類算法的圖像分割[J].軟件學(xué)報(bào)，2014，11（25）:2675-2689.

[9]李華雄，劉盾，周獻(xiàn)中.決策粗糙集模型研究綜述[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2010，5（22）:624-630.

[10]唐瑞春，張肖南，郭雙樂(lè).一種基于粗糙集和歐式距離的手機(jī)故障案例匹配算法[J].中國(guó)海洋大學(xué)學(xué)報(bào):自然科學(xué)版，2015，12（45）:125-130.

[11]張瓊.基于粗糙集的改進(jìn)Leader聚類算法[J].江蘇師范大學(xué)學(xué)報(bào):自然科學(xué)版，2015，4（33）:50-53.

[12]鮑新中，張建斌，劉澄.基于粗糙集條件信息熵的權(quán)重確定方法[J].中國(guó)管理科學(xué)，2009，3（17）:131-135.

[13]張清華，王國(guó)胤，肖雨.粗糙集的近似集[J].軟件學(xué)報(bào)，2012，7（23）:1745-1759.

[14]張明，程科，楊習(xí)貝，等.基于加權(quán)粒度的多粒度粗糙集[J].控制與決策，2015，2（30）:222-228.

[15]羅彬，邵培基，羅盡堯，等.基于粗糙集理論-神經(jīng)網(wǎng)絡(luò)-蜂群算法集成的客戶流失研究[J].管理學(xué)報(bào)，2011，2（8）:265-272.

[16]徐巖，陳昕.基于貝葉斯決策樹(shù)的電網(wǎng)報(bào)警信息去噪方法研究[J].陜西電力，2014（6）：38-41.

[17]吳恩英，呂佳.基于二叉樹(shù)支持向量機(jī)多類分類算法的研究[J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2016（3）：102-106.

[18]徐國(guó)浪，魏延.基于二叉樹(shù)結(jié)構(gòu)雙優(yōu)化的SVM多分類算法研究[J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2013（6）：109-113.

[19]王江榮，羅資琴，文暉，等.基于粗糙集的多項(xiàng)logistic回歸模型在油層識(shí)別中的應(yīng)用[J].工業(yè)儀表與自動(dòng)化裝置，2015（3）：28-32.

The research and application of classification algorithm based on decision tree

LU Chong1，XU Hui2，YANG Yong-chun1
（1.Xinjiang Vocational and Technical College of Communication，Wulumuqi，831401，China；2.Electronics and Information Engineering College，Yili Normal College，Yining 835000，China）

In this paper,we analysed the stability by enterprise customer data as the sample data,and then,we proposed an improved algorithm based on the ID3 algorithm via combining with rough set theory.The new classification algorithm is based on the classical ID3 algorithm to introduce the concept of rough combination attribute,which makes the average path of the expected non leaf nodes to the nodes of the shortest path,so as to improve the speed and accuracy of classification.The structure of decision trees which are constructed by the improved algorithm becomes very exact and simple,the time complexity is betterthantheID3algorithm.Experimentalresultsonthedecisiontreealsoshow theimprovedalgorithm iseffective.

decision tree；ID3 algorithm；splitting attribute；rough set theory

TP301

A

1674－6236（2016）18-0001-03

2016-01-22 稿件編號(hào)：201601207

國(guó)家自然科學(xué)基金項(xiàng)目（61363066）；新疆高校項(xiàng)目（XJEDU2014I043）

路 翀(1966—)，男，江蘇江都人，教授。研究方向：模式識(shí)別。