一種基于決策樹ID3的改進算法

王子京 劉毓

摘 要： 針對傳統ID3算法無法處理屬性值連續的數據集，設計了一種新的改進算法用于連續評價數據的處理。改進算法先用聚類算法對連續屬性值進行離散化，再計算屬性的粗糙度作為屬性分裂的標準，最后用改進的ID3算法生成決策樹。通過仿真驗證了該方法的預測正確率，并探討其應用條件。實驗結果表明，在不降低正確率的情況下，該算法可處理屬性值連續的數據且具有更好的可讀性及更低的運算量。

關鍵詞： 數據挖掘； 決策樹； 粗糙集； ID3算法； 大數據； 算法改進

中圖分類號： TN911.1?34； TP181 文獻標識碼： A 文章編號： 1004?373X（2018）15?0039?04

An improved ID3 algorithm for decision tree

WANG Zijing， LIU Yu

（School of Communications and Information Engineering， Xian University of Posts & Telecommunications， Xian 710121， China）

Abstract： The traditional ID3 algorithm can′t process the dataset with continuous attribute value. Therefore， an improved ID3 algorithm is designed to process the continuous evaluation data. The clustering algorithm is used in the improved algorithm to discrete the continuous attribute values， and then the roughness of the attribute is calculated as the divisive standard of the attribute. The improved ID3 algorithm is adopted to generate the decision tree. The prediction accuracy of the method is verified with simulation， and its application condition is discussed. The experimental result shows that the improved algorithm can process the data with continuous attribute value， and has high readability and less computational amount while maintaining the accuracy.

Keywords： data mining； decision tree； rough set； ID3 algorithm； big data； algorithm improvement

0 引 言

ID3算法是數據挖掘中一個重要的分類算法[1]，該算法用信息增益作為分裂屬性算擇的標準，生成的決策樹結構簡單，結果可讀性好。然而，ID3算法并不適用于連續數據，且傾向于選擇多值屬性分裂。文獻[2?4]提出基于模糊集和粗糙集的改進方案，用條件屬性的粗糙度代替屬性的信息熵作為分裂的標準，以解決ID3算法傾向選擇多值屬性的問題。而對于ID3無法處理連續值的問題，文獻[5?6]提出C4.5和CART（Classification and Regression Tree）算法。C4.5算法對連續屬性進行分割并使分割信息熵最小，采用信息增益率作為分裂屬性的標準。而CART算法在屬性值連續的情況下，使用最小剩余方差來判定回歸樹的最優劃分，生成回歸樹。但是C4.5和CART算法的輸出結果帶有連續屬性值的具體范圍，不易于理解。因此，仍需在優化結果的可讀性上做進一步的工作。客觀世界中，存在這樣一類數據，在采樣時是連續的，在決策時，需用具有較好可讀性的離散指標代替原連續值。因此，有必要對連續量進行離散化并深入挖掘該連續量反映的評價等級信息，如在某種對學生的評價中，需將其連續成績轉化為“優”“良”“中”“差”的評價指標。對于這些數據，設計一種高效、可讀性強的決策方法是非常必要的。文獻[7]提出對于決策樹中的連續屬性值用聚類算法進行離散化的思路，但是對于這種方法的具體實施、預測正確率、應用場合及局限的研究上仍有待進一步分析探討。本文提出用K?means++算法離散化連續屬性值的思想，并且結合粗糙集的研究成果，改進原有的ID3算法，減少傳統ID3算法的運算量。本文在具體數據集中應用改進的ID3算法，通過實驗仿真得出改進ID3算法的預測正確率，最后對改進算法的應用場合以及局限作出明確探討。實驗結果表明，本文提出的改進ID3算法在不降低預測正確率的情況下，具有更好的可讀性，更少的運算量，適用于需離散化為等級指標的連續數據。

信息增益越大，再劃分時所需要的信息量就越小。一般情況下，存在數個條件屬性，分別計算每一個條件屬性的信息增益，選擇信息增益最大的一個屬性作為分裂節點。假如存在一個多值屬性，這個屬性往往會被優先選擇作為分裂節點。但是取值最多的屬性有可能是在實踐中沒有意義的甚至是不相關的屬性。另外，計算各條件屬性的信息熵時，要進行大量的對數運算。在數據集較大的情況下，運算量陡增。因此，有必要針對這兩個問題作出改進。

2 基于粗糙集的ID3算法原理

對于上述運算量大和偏向選擇多值屬性的問題，文獻[8?9]提出一種基于粗糙集的改進算法。它的核心思想是用條件屬性的粗糙度作為選擇分裂屬性的標準，無需進行對數運算，減少了運算量，避免了優先選擇多值屬性。

2.1 決策系統

四元組[S=U，A，V，f]為一個信息系統。其中，[U]為所要驗究對象的非空有限集合，為論域；[A]是屬性集合；[V=a∈AVa]是屬性[a]的值域；[f：U×A→V]是信息函數，其為論域中的每一個對象賦予屬性值。若[A=C∪D]，其中，C為條件屬性集合，D為決策屬性集合，則該信息系統稱為決策系統。

2.2 不可區分關系

對于一個決策系統[S=U，A，V，f]，[?B?A]是屬性集合的一個子集，稱等價關系[IndB]為[S]的不可區分關系，即：

[IndB=x，y∈U×U?a∈B，fx，a=fy，a]

它的含意是僅僅通過屬性集[B]無法區分對象[x]和對象[y]，即兩者的屬性取值相同。

2.3 上近似與下近似

對于一個決策系統[S=U，A，V，f]，[IndB]是等價關系，[X∈U]是一個樣例集，它是粗糙的，那么[X]的某些子集可以完全被定義，稱為下近似集；可能屬于[X]的集合稱為上近似集。數學表達式如下：

[BX=xi∈UBxi?X] （5）

[BX=xi∈UBxi∩X≠?] （6）

式中：[BX]為[X]的下近似集；[BX]為[X]的上近似集；[Bxi]為等價關系[IndB]下包含[xi]的等價類。

2.4 屬性重要性

設[P，Q∈R]，其中[R]是論域中等價關系的集合。那么[γPQ]表示[P]的分類能力：

[γPQ=cardPXcardX] （7）

式中：card是求模運算；[X]是屬于等價關系[Q]下的等價類非空集合。對于[P]下的屬性[a]，分別計算[a]加入[P]與未加入[P]時的[γPQ]，可以得出屬性[a]的重要性。表達式如下：

[SGAa，P，Q=γPQ-γP-{a}Q] （8）

3 K?means算法及改進

K?means是一種聚類算法，流程如下：在數據集中隨機選擇k個不同的值作為聚類中心。計算數據集中每一個樣本與k個分類中心的距離，并將其歸入最臨近的一個中心所在的一類。得到一個聚類結果后，再次計算各分類結果的中心，計算樣本與中心之間的距離，反復迭代，以至得到一個聚類誤差收斂的結果或根據實際情況設定迭代次數。

K?means聚類的結果以及迭代次數與初始值選擇有很大關系。為了提高效率、改善聚類結果，必須優化初始值的選擇。文獻[10]提出K?Means++算法，它的思想是在選擇初始值時盡可能地使各初始值的距離最大，可減少迭代的次數，提高聚類效率。

4 改進的ID3算法原理

改進算法的主要思想是首先將數據集中連續的屬性取值應用K?means++算法進行離散化，然后計算各條件屬性的重要性[SGAa，P，Q]，選擇重要性大的屬性作為分裂節點。反復迭代，直至所有條件屬性均被用作分裂節點。最后剪枝生成決策樹。

改進的ID3算法主要步驟如下：

1） 數據初始化。

2） 判斷屬性值是否離散。若離散，則執行步驟3）。否則，確定離散化后取值的個數，應用K?means++算法離散化，并用離散值代替原連續值。

3） 計算活躍的條件屬性的重要性，即根據式（8）計算[SGAa，P，Q]的值。

4） 分割樣本集，選擇重要性最大的條件屬性作為分裂節點。

5） 繼續分割樣本集，重復步驟3）和步驟4）選擇剩余的條件屬性分割樣本集，直至所有條件屬性均被用作分裂結點。

6） 剪枝，生成決策樹。

5 實驗以及結果分析

本文通過分析督導專家對授課教師的聽課評價記錄，應用改進的ID3算法生成評判授課教師教學水平高低的決策規則。目前本文提出的算法已應用于西安郵電大學的本科教學評估實踐中。

5.1 實驗數據

本文的數據為近年西安郵電大學督導專家對本校教師的聽課評價記錄，該數據可在西安郵電大學官網下載。數據集的結構如表1所示，樣本的數量為325個。樣本中包含4個條件屬性和1個決策屬性。決策屬性是連續的；而條件屬性即教師的教學態度、教學內容、教學能力和教學效果，是離散的。所有條件屬性下的取值均為“一般”和“良好”兩個評價等級。改進算法對連續的決策屬性值進行離散化。在離散化過程中，需根據評價體系的不同，確定相應的聚類中心個數。一般而言，二值評價和三值評價體系較為常見。本文采用二值評價體系，將待評教師分為“良好”和“一般”兩類。

5.2 實驗過程

將樣本分為4等份，前3份用作訓練數據，最后1份用作測試集。所有仿真均在Matlab 2012軟件中完成。本文在二值評價體系中應用改進算法，生成的決策樹如圖1所示。本文也應用了CART算法分析數據集，作為參照對象。最后分別測試生成的決策樹的準確性。測試結果及決策樹復雜度如表2所示，其中CART算法的準確率是指在預測值的區間[-0.5，0.5]之內的實際值與所有實際值的比例。

5.3 實驗結果分析

二值評價體系下改進算法生成的決策樹更為簡潔。改進算法的葉子節點已經是教師的評價結果，可讀性更好。這是因為CART算法在用條件屬性分割樣本集后，僅僅對樣本作回歸分析，并未對樣本所反映的評價等級信息進行深入挖掘。而改進算法通過對樣本集作聚類，充分挖掘了隱藏的評價等級信息，得出的決策樹的可讀性更好。另外，改進算法只計算條件屬性的重要性，而CART算法生成回歸樹時，需要對樣本實施分割并進行回歸分析。因此，改進的ID3算法的計算量比CART算法小，運行時間更短。綜上所述，改進的ID3算法適用于本文的教學督導評價數據，具有良好的可讀性以及較少的計算量。

6 結 語

ID3算法是數據挖掘中的一種重要算法。針對具體的關于評價體系的數據，本文提出的改進ID3算法用K?means離散連續屬性值，通過計算屬性的重要性選擇分裂節點，生成決策樹。實驗證明具有更好的可讀性及較低的計算量。然而，本文只在二值評價體系下應用了改進算法，對于其他評價體系下的應用仍需做進一步研究。另外，本文提出的改進ID3算法在其他類型數據的應用上也有必要做進一步探討。

參考文獻

[1] 李泓波，白勁波，楊高明，等.決策樹技術研究綜述[J].電腦知識與技術，2015，11（24）：1?4.

LI Hongbo， BAI Jinbo， YANG Gaoming， et al. Review on decision tree technology research [J]. Computer knowledge and technology， 2015， 11（24）： 1?4.

[2] 翟俊海，翟夢堯，李勝杰.基于相容粗糙集技術的連續值屬性決策樹歸納[J].計算機科學，2012，39（11）：183?186.

ZHAI Junhai， ZHAI Mengyao， LI Shengjie. Induction of decision tree for continuous?valued attributes based on tolerance rough sets technique [J]. Computer science， 2012， 39（11）： 183?186.

[3] 朱付保，霍曉齊，徐顯景.基于粗糙集的ID3決策樹算法改進[J].鄭州輕工業學院學報（自然科學版），2015，30（1）：50?54.

ZHU Fubao， HUO Xiaoqi， XU Xianjing. Improved ID3 decision tree algorithm based on rough set [J]. Journal of Zhengzhou University of Light Industry （natural science）， 2015， 30（1）： 50?54.

[4] 翟俊海，王華超，張素芳.一種基于模糊熵的模糊分類算法[J].計算機工程與應用，2010，46（20）：176?180.

ZHAI Junhai， WANG Huachao， ZHANG Sufang. Fuzzy classification algorithm based on fuzzy entropy [J]. Computer engineering and applications， 2010， 46（20）： 176?180.

[5] 鞏固，呂俊懷，黃永青，等.有效改進C5.0算法的方法[J].計算機工程與設計，2009，30（22）：5197?5199.

GONG Gu， L? Junhuai， HUANG Yongqing， et al. Effective method of improving C5.0 algorithm [J]. Computer engineering and design， 2009， 30（22）： 5197?5199.

[6] 張亮，寧芊.CART決策樹的兩種改進及應用[J].計算機工程與設計，2015，36（5）：1209?1213.

ZHANG Liang， NING Qian. Two improvements on CART decision tree and its application [J]. Computer engineering and design， 2015， 36（5）： 1209?1213.

[7] 王小巍，蔣玉明.決策樹ID3 算法的分析與改進[J].計算機工程與設計，2011，32（9）：3069?3072.

WANG Xiaowei， JIANG Yuming. Analysis and improvement of ID3 decision tree algorithm [J]. Computer engineering and design， 2011， 32（9）： 3069?3072.

[8] LIU X W， WANG D H， JIANG L X. A novel method for inducing ID3 decision trees based on variable precision rough set [C]// 2011 the Seventh International Conference on Natural Computation. Shanghai， China： IEEE， 2011： 494?497.

[9] 翟俊海，侯少星，王熙照.粗糙模糊決策樹歸納算法[J].南京大學學報（自然科學版），2016，52（2）：306?312.

ZHAI Junhai， HOU Shaoxing， WANG Xizhao. Induction of rough fuzzy decision tree [J]. Journal of Nanjing University （natural sciences）， 2016， 52（2）： 306?312.

[10] 周潤物，李智勇，陳少淼，等.面向大數據處理的并行優化抽樣聚類K?means算法[J].計算機應用，2016，36（2）：311?315.

ZHOU Runwu， LI Zhiyong， CHEN Shaomiao， et al. Parallel optimization sampling clustering K?means algorithm for big data processing [J]. Journal of computer applications， 2016， 36（2）： 311?315.

[11] 李曉瑜，俞麗穎，雷航，等.一種K?means改進算法的并行化實現與應用[J].電子科技大學學報，2017，46（1）：61?68.

LI Xiaoyu， YU Liying， LEI Hang， et al. The parallel implementation and application of an improved K?means algorithm [J]. Journal of University of Electronic Science and Technology of China， 2017， 46（1）： 61?68.