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

陶道強(qiáng)，馬良荔＋，彭 超

（1.海軍工程大學(xué) 計(jì)算機(jī)工程系，湖北 武漢430033；2.海軍工程大學(xué) 校務(wù)部，湖北 武漢430033）

0 引 言

分類分析是數(shù)據(jù)挖掘中的一項(xiàng)重要任務(wù)，具有廣泛的應(yīng)用領(lǐng)域［1－2］。分類的關(guān)鍵在于如何構(gòu)建分類模型，不同分類方法的選擇導(dǎo)致分類結(jié)果的各異，其中的一種特別有效的方法是決策樹算法［3］。決策樹以其結(jié)構(gòu)簡(jiǎn)單，便于理解，模型效率和分類精度高，分類速度快的優(yōu)點(diǎn)不斷的應(yīng)用到許多規(guī)則的提取方法中［4－5］，許多人也不斷的改進(jìn)決策樹算法，從而在很多方面得到更好的應(yīng)用，比如ID3算法的改進(jìn)［6－7］。

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

（1）這種基于信息熵的計(jì)算方法容易產(chǎn)生多值偏向問(wèn)題，即偏向于選擇屬性取值較多的非類別屬性，而屬性值較多的非類別屬性并不總是最優(yōu)的；

（2）數(shù)據(jù)集越大，非類別屬性越多，需要的計(jì)算時(shí)間就會(huì)急劇增加。

（3）ID3算法對(duì)噪聲比較敏感。

1 基本概念

1.1 ID3算法理論基礎(chǔ)

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

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

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

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

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

1.2 預(yù)剪枝

在決策樹的生成過(guò)程中，會(huì)同時(shí)產(chǎn)生一些冗余分支，這些冗余的分支嚴(yán)重影響了算法的效率而且還會(huì)產(chǎn)生 “過(guò)擬合”效應(yīng)［10］。預(yù)剪枝就是在完全正確分類訓(xùn)練集之前，較早地停止樹的生長(zhǎng)［11］。具體什么時(shí)候停止生長(zhǎng)，有多種不同的方法，比如：當(dāng)決策樹達(dá)到一定高度時(shí)；當(dāng)?shù)竭_(dá)結(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某一個(gè)閾值時(shí)；當(dāng)每次擴(kuò)張對(duì)系統(tǒng)性能的增益小于某個(gè)閾值時(shí)；當(dāng)然，到達(dá)結(jié)點(diǎn)的實(shí)例具有相同的特征向量時(shí)，也可以停止生長(zhǎng)。本文所指的預(yù)剪枝是指到達(dá)結(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某個(gè)閾值時(shí)決策樹停止生長(zhǎng)。

2 分類矩陣

2.1 分類矩陣的定義

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

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

應(yīng)當(dāng)指出，若訓(xùn)練集T的總個(gè)數(shù)為零，即AX，C中的各個(gè)元素全部為零時(shí)，分類將失去意義，本文中不予考慮。本文定義的分類矩陣所需要的條件是矩陣的各個(gè)元素為非負(fù)整數(shù)，且至少有一個(gè)不為零。

2.2 基于分類矩陣的增益計(jì)算

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

2.3 基于分類矩陣增益的性質(zhì)

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

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

性質(zhì)2矩陣擴(kuò)展后增益不變。對(duì)于上述矩陣Q，根據(jù)式（6）可知若存在任意矩陣U

（其中O為相應(yīng)維數(shù)的零矩陣）都有

性質(zhì)3無(wú)序性。任意對(duì)分類矩陣AX，C進(jìn)行行交換或列交換，得到的新的分類矩陣，其基于分類矩陣的增益仍不變，即

2.4 ID3算法多值偏向性分析

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

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

根據(jù)文獻(xiàn) ［8，13］可知，如果有

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

當(dāng)amj（j＝1，2，…，n）全部為零時(shí)，根據(jù)性質(zhì)2可知式（13）的△值為0；否則，結(jié)合式（6）可推出

觀察式（14）可知

其中矩陣

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

3 改進(jìn)方案

3.1 多值偏向性的克服

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

引入權(quán)重因子t原因如下：

（1）對(duì)于任意訓(xùn)練集，其增益都為非負(fù)且不會(huì)大于log2m，而且log2m是定值，其計(jì)算速度相對(duì)與增益的計(jì)算可忽略。

由定義1，2，5可知，對(duì)于任意一個(gè)給定的訓(xùn)練集，其非類別屬性X的信息量是一定的，即為

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

其中互信息Info（C，T）的數(shù)值可從式（6）（18）和（19）中導(dǎo)出。

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

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

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

對(duì)照式（13），根據(jù)文獻(xiàn) ［8］［13］可知，引入權(quán)重因子t＝1∕log2m后，對(duì)于式（12）給出的新映射，如果有

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

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

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

同時(shí)m＋s－1＞m，那么有

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

3.2 分類速率的改進(jìn)

當(dāng)數(shù)據(jù)集越來(lái)越大，非類別屬性越來(lái)越多時(shí)，分類時(shí)間問(wèn)題就凸現(xiàn)了出來(lái)。而分類的時(shí)間大部分用于了增益的計(jì)算上，觀察基于分類矩陣的增益公式，即式（6）可知：

（1）算法的計(jì)算環(huán)節(jié)需要不斷的進(jìn)行形式為xlog2x的計(jì)算（x為0到訓(xùn)練集總個(gè)數(shù)之間的整數(shù)），而這種對(duì)數(shù)計(jì)算的時(shí)間復(fù)雜度相對(duì)與從數(shù)組中讀取是很高的。

（2）對(duì)于任意給定的一個(gè)訓(xùn)練集T，其類別屬性的信息量Info（T）即

是不變的，那么對(duì)應(yīng)于式（6）則其前兩項(xiàng)是不變的。

（3）對(duì)于任意給定的一個(gè)訓(xùn)練集T，式（6）的除數(shù)項(xiàng)都是不變的。

因此若要加快分類速率，減少分類時(shí)間就必須針對(duì)以上問(wèn)題改進(jìn)，本文改進(jìn)的方案是：

（1）在實(shí)際的應(yīng)用過(guò)程中，我們可以事先利用數(shù)組來(lái)存放形式為xlog2x的對(duì)數(shù)值，計(jì)算過(guò)程中只需要不斷的從數(shù)組中讀取即可。例如本文在MATLAB仿真中利用數(shù)組arr（1）～arr（sum＋1）來(lái)存放0log20～sumlog2sum的數(shù)值（sum表示訓(xùn)練集的總個(gè)數(shù)），從而大大縮短了計(jì)算的時(shí)間。

（2）在非類別屬性個(gè)數(shù)較多時(shí)，只計(jì)算一次式（6）的前兩項(xiàng)。

（3）去除式（6）的除數(shù)項(xiàng)，從而減少不必要的計(jì)算開(kāi)支。

因此，綜合以上改進(jìn)方法，引入權(quán)重因子t后，式（6）可以更改為

利用式（26），用imGain（AX，C）代替Gain（X，T）作為非類別屬性的選擇標(biāo)準(zhǔn)來(lái)對(duì)數(shù)據(jù)集進(jìn)行分類，明顯的將克服多值偏向性并且能提高分類的速率。

4 實(shí)例驗(yàn)證

為測(cè)試本文方案的改進(jìn)程度，本文采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)（其 網(wǎng) 址 為：http：//archive.ics.uci.edu/ml/datasets.html）中的Car Evaluation數(shù)據(jù)集和Nursery數(shù)據(jù)集進(jìn)行對(duì)比驗(yàn)證。驗(yàn)證的方法是采用對(duì)較小數(shù)據(jù)集Car Evaluation從第一個(gè)數(shù)據(jù)開(kāi)始每四個(gè)進(jìn)行一次抽樣，得到432條數(shù)據(jù)集作為訓(xùn)練集，其余作為測(cè)試集，而對(duì)于較大數(shù)據(jù)集Nursery從第一個(gè)數(shù)據(jù)開(kāi)始每八個(gè)進(jìn)行一次抽樣，得到的1620條數(shù)據(jù)作為訓(xùn)練集，其余作為測(cè)試集（上述兩個(gè)數(shù)據(jù)集的特點(diǎn)見(jiàn)表1）。

表1 所選數(shù)據(jù)集的特點(diǎn)

在同一臺(tái)電腦上，利用MATLAB對(duì)以上數(shù)據(jù)集各進(jìn)行50次實(shí)驗(yàn)，每次實(shí)驗(yàn)都對(duì)訓(xùn)練集經(jīng)行1000次連續(xù)重復(fù)分類，而且每次分類都讓決策樹完全生長(zhǎng)。求其單次分類平均值、得到的葉子節(jié)點(diǎn)個(gè)數(shù)和利用測(cè)試集測(cè)試出分類的精確率，得到的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表2。

表2 決策樹完全生長(zhǎng)的實(shí)驗(yàn)結(jié)果

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

對(duì)比表2和表3的葉子結(jié)點(diǎn)數(shù)可知，設(shè)定閾值后葉子節(jié)點(diǎn)數(shù)，即分類規(guī)則，將大大減小，從而更能說(shuō)明分類方案的優(yōu)劣。對(duì)比表3的各項(xiàng)可以說(shuō)明，決策樹規(guī)則生成過(guò)程中，相比于ID3算法，使用本文方案：分類速率大大提高；生成規(guī)則個(gè)數(shù)有所減少；分類精確率有所提高。從而達(dá)到了對(duì)原有算法改進(jìn)的目的。

表3 閾值設(shè)為3時(shí)的實(shí)驗(yàn)結(jié)果

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

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

［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，F(xiàn)lorida，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ìn) 和 簡(jiǎn) 化 ［J］.上 海 交 通 大 學(xué) 學(xué) 報(bào)，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）.［張鳳蓮，林健良.新的決策樹構(gòu)造方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，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）.［武獻(xiàn)宇，王建芬，謝金龍.決策樹ID3算法研究及其優(yōu)化 ［J］.微型機(jī)與應(yīng)用，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）.［姚家奕.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)原理及應(yīng)用 ［M］.北京：電子工業(yè)出版社，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ìn)算法 ［J］.計(jì)算機(jī)與現(xiàn)代化，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）.［狄文輝，李卿，樓新遠(yuǎn).基于修正系數(shù)的決策樹分類算法 ［J］. 計(jì) 算 機(jī) 工 程 與 設(shè) 計(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）.［韓松來(lái)，張輝，周華平.決策樹的屬性選取策略綜述 ［J］.微計(jì)算機(jī)應(yīng)用，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）.［葉明全，胡學(xué)鋼.一種基于屬性重要性的屬性約簡(jiǎn)啟發(fā)式算法 ［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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.