路 翀，徐 輝，楊永春

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

基于決策樹分類算法的研究與應用

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

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

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

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

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

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

1 決策樹的分類算法

決策樹分類方法將搜索空間劃分為一些矩形區(qū)域，然后根據(jù)元組（或對象，實例）落入的區(qū)域對元組進行分類。給定一個數(shù)據(jù)庫

其中元組

其屬性空間為

其中ai為每個內部節(jié)點。同時，給定類別集合

其中cj被標記為每個葉節(jié)點，且記cj中的樣本數(shù)為tl。每個弧都被標記一個謂詞，這個謂詞可應用于相應父節(jié)點的屬性。

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

其中則熵的定義為：

若給定一個數(shù)據(jù)狀態(tài)D，以及該狀態(tài)被分裂為j個新狀態(tài)

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

其增益比率定義[1]

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

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

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

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

則定義強分裂屬性集

其中

2 粗糙集理論

粗糙集理論[7-9]的核心就是將知識和分類結合在一起，并用等價類關系形式化構造商集合U/R={X1，X2，…，Xm}，其中Xi就是U/R的一個等價類。

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

3 本文提出的分類算法

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

4 基于客戶流失實例分析

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

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

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

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

結構化后數(shù)據(jù)樣本如表2所示。

4.2 生成決策樹

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

表2 結構化樣本數(shù)據(jù)

圖1 ID3算法模型圖

圖2 ID3改進算法模型圖

4.3 分 析

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

5 結束語

文中提出的優(yōu)化算法與ID3算法的分析比較，得出此方法生成的決策樹結構更簡單，時間復雜度更優(yōu)。盡管如此，改進后的算法仍有待完善，主要體現(xiàn)在以下的幾方面：1）簡單的優(yōu)化目前之限于多維的數(shù)據(jù)庫，對高維的數(shù)據(jù)庫，比如上萬維的生物基因信息數(shù)據(jù)庫，需要更多的優(yōu)化；2）由于本文的數(shù)據(jù)與結果存在著一定的相關性，所以在很多情況下，需要對屬性進行刪減，其目的與算法剪枝類似，防止決策樹過擬合；3）其準確性在不同的樣本中表現(xià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]劉小虎，李生.決策樹的優(yōu)化算法[J].軟件學報，1998，9（10）:797-800.

[3]馮少榮.決策樹算法的研究與改進[J].廈門大學學報：自然科學版，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]于海平，朱玉金，陳耿.一種基于粗糙集理論的決策樹構造方法[J].計算機應用與軟件，2011，28（2）:80-84.

[7]王國胤，姚一豫，于洪.粗糙集理論與應用研究綜述[J].計算機學報，2011，7（32）：1229-1246.

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

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

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

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

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

[13]張清華，王國胤，肖雨.粗糙集的近似集[J].軟件學報，2012，7（23）:1745-1759.

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

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

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

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

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

[19]王江榮，羅資琴，文暉，等.基于粗糙集的多項logistic回歸模型在油層識別中的應用[J].工業(yè)儀表與自動化裝置，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 稿件編號：201601207

國家自然科學基金項目（61363066）；新疆高校項目（XJEDU2014I043）

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