基于分類矩陣的決策樹算法

陶道強，馬良荔＋，彭 超

（1.海軍工程大學 計算機工程系，湖北 武漢430033；2.海軍工程大學 校務部，湖北 武漢430033）

0 引 言

分類分析是數據挖掘中的一項重要任務，具有廣泛的應用領域［1－2］。分類的關鍵在于如何構建分類模型，不同分類方法的選擇導致分類結果的各異，其中的一種特別有效的方法是決策樹算法［3］。決策樹以其結構簡單，便于理解，模型效率和分類精度高，分類速度快的優點不斷的應用到許多規則的提取方法中［4－5］，許多人也不斷的改進決策樹算法，從而在很多方面得到更好的應用，比如ID3算法的改進［6－7］。

ID3算法是決策樹算法中最為典型的算法，于1986年由Quinlan提出。該算法采用自頂向下的策略，搜索全部空間的一部分，確保所做的測試次數較少，但是ID3算法也存在著不足［7－8］：

（1）這種基于信息熵的計算方法容易產生多值偏向問題，即偏向于選擇屬性取值較多的非類別屬性，而屬性值較多的非類別屬性并不總是最優的；

（2）數據集越大，非類別屬性越多，需要的計算時間就會急劇增加。

（3）ID3算法對噪聲比較敏感。

1 基本概念

1.1 ID3算法理論基礎

Quinlan把Shannon的信息論引入到了決策樹算法中，并依據信息熵對訓練集進行分類。關于信息熵的定義［9］如下：

定義1 若給定的概率分布P＝（p1，p2，…，pn），則由該分布傳遞的信息量稱為P的熵，即

定義2 若一個記錄的集合T根據類別屬性的值分成互相獨立的類C1，C2，…，Cn，其概率分布為P，定義T的一個元素屬于那個類所需要的信息量為

定義3 若屬性X的值將T 分為集合T1，T2，…，Tn，則確定T中的一個元素類的信息量可通過確定Ti的加權平均值得到，Info（Ti）的加權平均值為

定義4 屬性X對分類提供的信息量，即增益為

1.2 預剪枝

在決策樹的生成過程中，會同時產生一些冗余分支，這些冗余的分支嚴重影響了算法的效率而且還會產生 “過擬合”效應［10］。預剪枝就是在完全正確分類訓練集之前，較早地停止樹的生長［11］。具體什么時候停止生長，有多種不同的方法，比如：當決策樹達到一定高度時；當到達結點的實例個數小于某一個閾值時；當每次擴張對系統性能的增益小于某個閾值時；當然，到達結點的實例具有相同的特征向量時，也可以停止生長。本文所指的預剪枝是指到達結點的實例個數小于某個閾值時決策樹停止生長。

2 分類矩陣

2.1 分類矩陣的定義

定義5在給定的一個訓練集T中，若按照一個非類別屬性X＝｛X1，X2，…，Xm｝將T分為集合T1，T2，…，Tm，同時集合Ti（i＝1，2，…，m）又按照類別屬性C＝｛C1，C2，…，Cn｝分為了m＊n個部分，形成了X到C的映射，本文將這種映射定義為分類矩陣，記為分類矩陣AX，C，且

AX，C中的元素aij（i＝1，2，…，m；j＝1，2，…，n；aij是非負整數）表示在訓練集T中，同時對應屬性值Xi和屬性值Cj的實例個數，而所有元素之和就是訓練集T的總個數。屬性X和屬性C的各個屬性值可以是無序的，因此任意對分類矩陣AX，C進行行交換或列交換，得到的矩陣仍然屬性X到屬性C的映射矩陣，只不過交換后矩陣元素對應的屬性值應做相應的交換。

應當指出，若訓練集T的總個數為零，即AX，C中的各個元素全部為零時，分類將失去意義，本文中不予考慮。本文定義的分類矩陣所需要的條件是矩陣的各個元素為非負整數，且至少有一個不為零。

2.2 基于分類矩陣的增益計算

根據上述定義1～5，本文用Gain（AX，C）代替增益Gain（X，T），經推算基于分類矩陣的增益可表示為如下

2.3 基于分類矩陣增益的性質

性質1增益非負性。根據增益的定義我們可知信息量恒為非負值，即在任意非空的訓練集T中，對于任意非類別屬性X都存在Gain（X，T）≥0。結合本文的定義，若存在任意矩陣Q

式中：r，c——任意正整數，只要其滿足分類矩陣的條件，都存在

性質2矩陣擴展后增益不變。對于上述矩陣Q，根據式（6）可知若存在任意矩陣U

（其中O為相應維數的零矩陣）都有

性質3無序性。任意對分類矩陣AX，C進行行交換或列交換，得到的新的分類矩陣，其基于分類矩陣的增益仍不變，即

2.4 ID3算法多值偏向性分析

許多文獻［8，12－15］都提到了ID3算法的多值偏向性，但文獻 ［12］僅指出了ID3算法多值偏向，文獻 ［8，13］簡單提出了多值偏向性的證明方法但未給出證明，文獻 ［14］利用粗糙集理論給出了證明，而 文獻 ［15］利用平均歐式距離證明了其改進的 AED（average euclidean distance）算法不具有多值偏向性。本文旨在利用分類矩陣給出證明。

首先，根據文獻 ［8，13］，非類別屬性X創建另外一個新屬性X＇，它與屬性X唯一的區別：其中一個已知屬性值Xm分解為s個值，Xm＋1，Xm＋2，…，Xm＋s，其余值和X中的完全一樣，即形成了新的映射（根據性質3可知，在不使增益改變的條件下，為便于表達，可以認為上述Xm就是X屬性的最后一個屬性值）

根據文獻 ［8，13］可知，如果有

恒成立，則說明該決策樹算法在建樹過程中具有多值偏向。

當amj（j＝1，2，…，n）全部為零時，根據性質2可知式（13）的△值為0；否則，結合式（6）可推出

觀察式（14）可知

其中矩陣

由假設條件可知，B矩陣中至少存在一個元素為正整數，而其余均為非負整數，滿足分類矩陣的條件，根據性質1可知，Gain（B）≥0，故有△≥0。綜合可知，式（13）恒成立，從而證明了ID3算法具有多值偏向性。

3 改進方案

3.1 多值偏向性的克服

為克服ID3算法的多值偏向，基于分類矩陣的決策樹算法引入一個權重因子t，將增益與權重因子的乘積暫時作為屬性選擇標準，其中t＝1∕log2m，m為屬性X的取值個數，即屬性的選擇標準暫時修改如下

引入權重因子t原因如下：

（1）對于任意訓練集，其增益都為非負且不會大于log2m，而且log2m是定值，其計算速度相對與增益的計算可忽略。

由定義1，2，5可知，對于任意一個給定的訓練集，其非類別屬性X的信息量是一定的，即為

再由本文的定義可知，增益在數值上也可表述為

其中互信息Info（C，T）的數值可從式（6）（18）和（19）中導出。

由信息量的非負性可知，增益Gain（AX，C）、信息量Info（X）、互信息量Info（C，T）的值均為非負數。而由信息論和式（6）（8）（19）可證明Gain（AX，C）的取值范圍為

引入權重因子t，并將因子值定為t＝1∕log2m，可以使增益縮放到 ［0，1］范圍內進行比較，從而使比較更固定，更準確，同時又基本保持了其原有的計算速度。

（2）引入權重因子t，克服了ID3算法的多值偏向性。

對照式（13），根據文獻 ［8］［13］可知，引入權重因子t＝1∕log2m后，對于式（12）給出的新映射，如果有

恒成立，則說明改進的決策樹算法在建樹過程中仍具有多值偏向。當然若式（21）非恒成立，則該算法不具有多值偏向性。由新映射的變化可以看出，若s＝1，新映射與原來的映射不存在任何變化，那么△≡0，討論將失去意義，現令s＞1。下面給出使式（21）不成立的特例，從而說明算法不具有多值偏向性。

由性質1可知，對于任意分類矩陣AX，C，都有Gain（AX，C）都是非負的，那么必然存在任意m＊n階的分類矩陣AX，C，使Gain（AX，C）＞0，現假設 AX，C就是這樣的矩陣（一般情況下，在屬性選擇時將不會選擇增益為0的非類別屬性，因此討論增益為0的情況也是沒必要的），同時令新映射

式中：O——s＊n階的零矩陣，s＞1，那么由性質2可知

同時m＋s－1＞m，那么有

以上假設說明，引入權重因子t后，新映射的增量存在小于0的情況，式（21）非恒成立，因此避免了算法的多值偏向，從而使分類時，尤其是在各個非類別屬性取值個數差別較大時，能更加準確的選擇非類別屬性，提高分類準確率，即降低了分類的噪聲敏感。

3.2 分類速率的改進

當數據集越來越大，非類別屬性越來越多時，分類時間問題就凸現了出來。而分類的時間大部分用于了增益的計算上，觀察基于分類矩陣的增益公式，即式（6）可知：

（1）算法的計算環節需要不斷的進行形式為xlog2x的計算（x為0到訓練集總個數之間的整數），而這種對數計算的時間復雜度相對與從數組中讀取是很高的。

（2）對于任意給定的一個訓練集T，其類別屬性的信息量Info（T）即

是不變的，那么對應于式（6）則其前兩項是不變的。

（3）對于任意給定的一個訓練集T，式（6）的除數項都是不變的。

因此若要加快分類速率，減少分類時間就必須針對以上問題改進，本文改進的方案是：

（1）在實際的應用過程中，我們可以事先利用數組來存放形式為xlog2x的對數值，計算過程中只需要不斷的從數組中讀取即可。例如本文在MATLAB仿真中利用數組arr（1）～arr（sum＋1）來存放0log20～sumlog2sum的數值（sum表示訓練集的總個數），從而大大縮短了計算的時間。

（2）在非類別屬性個數較多時，只計算一次式（6）的前兩項。

（3）去除式（6）的除數項，從而減少不必要的計算開支。

因此，綜合以上改進方法，引入權重因子t后，式（6）可以更改為

利用式（26），用imGain（AX，C）代替Gain（X，T）作為非類別屬性的選擇標準來對數據集進行分類，明顯的將克服多值偏向性并且能提高分類的速率。

4 實例驗證

為測試本文方案的改進程度，本文采用UCI機器學習數據庫（其 網 址 為：http：//archive.ics.uci.edu/ml/datasets.html）中的Car Evaluation數據集和Nursery數據集進行對比驗證。驗證的方法是采用對較小數據集Car Evaluation從第一個數據開始每四個進行一次抽樣，得到432條數據集作為訓練集，其余作為測試集，而對于較大數據集Nursery從第一個數據開始每八個進行一次抽樣，得到的1620條數據作為訓練集，其余作為測試集（上述兩個數據集的特點見表1）。

表1 所選數據集的特點

在同一臺電腦上，利用MATLAB對以上數據集各進行50次實驗，每次實驗都對訓練集經行1000次連續重復分類，而且每次分類都讓決策樹完全生長。求其單次分類平均值、得到的葉子節點個數和利用測試集測試出分類的精確率，得到的實驗數據見表2。

表2 決策樹完全生長的實驗結果

由于上述實驗得到的決策樹是完全生長的，很多葉子節點都只有一個或兩個實例，相對于訓練集的樣本個數是可以忽略不計的，而且適量的減少節點可以使決策樹得到簡化，從而使分類規則更容易理解。本文使用預剪枝的方法，設定其閾值為3，即實例個數小于3時，將停止相應樹枝的生長。在此情況下，再次對上述數據集進行比較，得到的實驗數據見表3。

對比表2和表3的葉子結點數可知，設定閾值后葉子節點數，即分類規則，將大大減小，從而更能說明分類方案的優劣。對比表3的各項可以說明，決策樹規則生成過程中，相比于ID3算法，使用本文方案：分類速率大大提高；生成規則個數有所減少；分類精確率有所提高。從而達到了對原有算法改進的目的。

表3 閾值設為3時的實驗結果

5 結束語

本文就引言中提出的ID3算法的三點不足進行改進。研究中定義了一種分類矩陣，給出了基于分類矩陣增益的計算公式，并針對其特點提出了改進方案。本文利用分類矩陣從理論證明了原有算法的多值偏向性和改進后方案對多值偏向缺點的克服，并利用MATLAB從實驗上證明：引入權重因子后，基于分類矩陣的決策樹算法有助于減少決策樹分類的時間，提高了分類的精確率，同時通過預剪枝的方法可以看出該方案適度減少了主要分類規則的生成個數。

［2］Noor Elmitiny，YAN Xuedong，Essam Radwan，et al.Classification analysis of driver＇s stop/go decision and red－light running violation ［J］.Accident Analysis and Prevention，2010，42（1）：101－111.

［3］CHEN Yenliang，Lucas Tzu－Hsuan Hung.Using decision trees to summarize associative classification rules ［J］.Expert Systems With Applications，2009，36（2）：2338－2351.

［4］Arun Kumar M，Gopal M.Fast multiclass SVM classification using decision tree based one－against－all method ［J］.Neural Processing Letters，2010，32（3）：311－323.

［5］Chandra B，Paul Varghese P.On improving efficiency of SLIQ decision tree algorithm ［C］.Proceedings of International Joint Conference on Neural Networks，Orlando，Florida，USA，2007.

［6］ZHU Haodong.Research on improvement and simplification of ID3algorithm ［J］.Journal of Shanghai Jiaotong University，2010，44（7）：883－886（in Chinese）. ［朱顥東.ID3算法的改進 和 簡 化 ［J］.上 海 交 通 大 學 學 報，2010，44（7）：883－886.］

［7］ZHANG Fenglian，LIN Jianliang.New method of building decision tree ［J］ .Computer Engineering and Applications，2009，45（10）：141－143（in Chinese）.［張鳳蓮，林健良.新的決策樹構造方法 ［J］.計算機工程與應用，2009，45（10）：141－143.］

［8］WU Xianyu，WANG Jianfen，XIE Jinlong.The research of ID3 decision tree algorithm and its optimization ［J］.Microcomputer ＆Its Applications，2010，29（21）：7－9（in Chinese）.［武獻宇，王建芬，謝金龍.決策樹ID3算法研究及其優化 ［J］.微型機與應用，2010，29（21）：7－9.］

［9］YAO Jiayi.The theory and application of data warehouse and data mining ［M］.Beijing：Pubulishing House of Electronics Industry，2009（in Chinese）.［姚家奕.數據倉庫與數據挖掘技術原理及應用 ［M］.北京：電子工業出版社，2009.］

［10］DING Xiangwu，WANG Bin.An improved pre－pruning algorithm based on ID3［J］.Computer and Modernization，2008，24（9）：47－50（in Chinese）.［丁祥武，王斌.一種基于ID3的前剪枝改進算法 ［J］.計算機與現代化，2008，24（9）：47－50.］

［11］DU Jun，CAI Zhihua，Charles X Ling.Cost－senstive decision trees with pre－pruning ［G］.LNCS 4509：Proceedings of the 20th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence 2007：171－179.

［12］DI Wenhui，LI Qing，LOU Xinyuan.Decision tree classification algorithm based on modified degree［J］.Computer Engineering and Design，2008，29（24）：6344－6346（in Chinese）.［狄文輝，李卿，樓新遠.基于修正系數的決策樹分類算法 ［J］. 計 算 機 工 程 與 設 計，2008，29（24）：6344－6346.］

［13］HAN Songlai，ZHANG Hui，ZHOU Huaping.A brief survey of decision tree attributes selection strategy ［J］.Microcomputer Applications，2007，28（8）：785－790（in Chinese）.［韓松來，張輝，周華平.決策樹的屬性選取策略綜述 ［J］.微計算機應用，2007，28（8）：785－790.］

［14］YE Mingquan，HU Xuegang.Heuristic algorithm for reduction based on attribute significance［J］.Journal of Henan Normal University（Natural Science），2008，36（5）：163－165（in Chinese）.［葉明全，胡學鋼.一種基于屬性重要性的屬性約簡啟發式算法 ［J］.河南師范大學學報（自然科學版），2008，36（5）：163－165.］

［15］LIU Quan，HU Daojing，YAN Qicui.Decision tree algorithm based on average euclidean distance ［C］.2nd International Conference on Future Computer and Communication，2010：507－511.