姚亞夫，邢留濤

(中南大學(xué) 機(jī)電工程學(xué)院，湖南 長(zhǎng)沙，410083)

分類問(wèn)題是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一。近年來(lái)，分類問(wèn)題在許多行業(yè)和領(lǐng)域都有廣泛的應(yīng)用[1]，如何更精確、更有效地分類一直是廣大科研工作者的目標(biāo)。決策樹(shù)以其預(yù)測(cè)準(zhǔn)確率高、穩(wěn)定性好、直觀易懂等特點(diǎn)[2-4]，得到廣泛的應(yīng)用。目前，構(gòu)造決策樹(shù)的算法比較多[5-6]，用不同的算法可以構(gòu)造出不同的決策樹(shù)，其性能也不盡相同，決策樹(shù)的構(gòu)造通常包含 2個(gè)重要步驟[7]：生成決策樹(shù)和決策樹(shù)的剪枝。每個(gè)步驟都有不同的方法，相應(yīng)地就有各種不同的決策樹(shù)生成和剪枝算法，最早的決策樹(shù)算法是由 Hunt等[8]于 1966年提出的 CLS(concept learning system)。ID3算法[9]和C4.5算法[10]是目前最具影響的決策樹(shù)算法,已廣泛應(yīng)用于數(shù)據(jù)分類領(lǐng)域。C4.5算法是在ID3算法的基礎(chǔ)上改進(jìn)過(guò)來(lái)的，不僅可以處理離散型描述屬性，還可以處理連續(xù)性屬性。C4.5算法采用信息增益率作為選擇分枝屬性的標(biāo)準(zhǔn)，彌補(bǔ)了 ID3算法在使用信息增益選擇分枝屬性時(shí)偏向于取值較多的屬性的缺陷，但C4.5算法也有一些缺陷[11]。本文作者研究C4.5算法中的連續(xù)性屬性離散化技術(shù)，并提出了改進(jìn)算法—局部擇優(yōu)法。將改進(jìn)C4.5算法應(yīng)用于行人和車輛模式識(shí)別，并對(duì)改進(jìn)C4.5分類器與K-均值分類器以及傳統(tǒng)C4.5分類器的分類性能進(jìn)行比較。

1 C4.5算法

作為ID3算法的改進(jìn)算法，C4.5算法克服了ID3算法的兩大缺點(diǎn)：(1) ID3算法使用信息增益作為評(píng)價(jià)標(biāo)準(zhǔn)來(lái)選擇根節(jié)點(diǎn)和各內(nèi)部節(jié)點(diǎn)中的分枝屬性，信息增益的缺點(diǎn)是傾向于選擇取值較多的屬性，在某些情況下這類屬性可能不會(huì)提供太多有價(jià)值的信息，而C4.5算法采用信息增益率作為評(píng)價(jià)標(biāo)準(zhǔn)，克服了ID3算法的這點(diǎn)不足；(2) ID3算法只能處理描述屬性為離散型的數(shù)據(jù)集，而C4.5算法既可以處理離散型描述屬性，又可以處理連續(xù)型描述屬性。C4.5算法也是一種基于信息論[12]的機(jī)器學(xué)習(xí)方法，其核心思想是通過(guò)分析訓(xùn)練數(shù)據(jù)集，在整個(gè)數(shù)據(jù)集上遞歸地建立一個(gè)決策樹(shù)，其詳細(xì)過(guò)程如下。

Step 1 對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，若數(shù)據(jù)集為連續(xù)型描述屬性，需將數(shù)據(jù)集離散化，并計(jì)算所有屬性的信息增益率，選擇信息增益率最大的描述屬性作為根節(jié)點(diǎn)的分枝屬性。

(1) 設(shè)整個(gè)數(shù)據(jù)集為T，類別集為{C1，C2，…，Ck}，總共分為k個(gè)類，每個(gè)類對(duì)應(yīng) 1個(gè)數(shù)據(jù)子集Ti(1≤i≤k)。令|T|為數(shù)據(jù)集T的樣本數(shù)，|Ci|為數(shù)據(jù)集T中屬于類別Ci的樣本數(shù)，則各類別的先驗(yàn)概率為Pi=|Ci|/|T|，對(duì)數(shù)據(jù)集T進(jìn)行分類所需要的信息熵[13]為：

(2) 設(shè)描述屬性Ak(k=1，2，…，m)有q個(gè)不同的取值{a1k，a2k，…，aqk}，用描述屬性Ak可將數(shù)據(jù)集T劃分為q個(gè)子集{T1，T2，…，Tq}，Tj(j=1，2，…，q)中的樣本在屬性Ak上具有相同的取值為子集Tj中的樣本數(shù)，為子集Tj中屬于類別Ci的樣本數(shù)，則由描述屬性Ak劃分?jǐn)?shù)據(jù)集T所得信息熵為：

(3) 屬性Ak的信息熵為：

由式(4)和(5)可得信息增益率的計(jì)算公式：

式中：k=1，2，…，m，此式即為描述屬性Ak劃分?jǐn)?shù)據(jù)集T的信息增益率。

Step 2 根據(jù)根節(jié)點(diǎn)屬性不同取值所對(duì)應(yīng)的數(shù)據(jù)子集，采用與Step1相同的方法遞歸地建立樹(shù)的分枝，選擇分枝中信息增益率最大的屬性作為子節(jié)點(diǎn)，如此循環(huán)下去，直到所有分枝節(jié)點(diǎn)中的樣本屬于同一類別，即葉節(jié)點(diǎn)中所有樣本屬性取值相同時(shí)為止。

Step 3 對(duì)生成的決策樹(shù)進(jìn)行剪枝，消除噪聲和孤立點(diǎn)等隨機(jī)因素的影響，以得到簡(jiǎn)化的決策樹(shù)，C4.5采用的是后剪枝算法[14]。

Step 4 提取決策規(guī)則[15]。在C4.5算法中，對(duì)于生成的決策樹(shù)，可以直接獲得決策規(guī)則，無(wú)論是決策樹(shù)還是決策規(guī)則都可以對(duì)新的數(shù)據(jù)集進(jìn)行分類預(yù)測(cè)。

C4.5算法在ID3算法的基礎(chǔ)上增加了處理連續(xù)型屬性的功能。在選擇某節(jié)點(diǎn)上的分枝屬性時(shí)，對(duì)于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對(duì)于某一連續(xù)型的描述屬性Ak(本文所處理的屬性即為連續(xù)型屬性)，如果某節(jié)點(diǎn)中數(shù)據(jù)集的樣本數(shù)量為Tj，C4.5算法進(jìn)行如下處理：

(1) 將該節(jié)點(diǎn)上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體取值，由小到大進(jìn)行排列，得到屬性值的取值序列 {A1k,A2k,…,ATjk}。

(2) 在描述屬性序列 {A1k,A2k,…,ATjk}中共生成Tj-1個(gè)分割點(diǎn)，共有Tj-1種對(duì)數(shù)據(jù)集的劃分方式。設(shè)第i(1≤i≤Tj)個(gè)分割點(diǎn)的取值為：

它將該節(jié)點(diǎn)上的數(shù)據(jù)集劃分為2個(gè)數(shù)據(jù)子集，可用區(qū)間[A1k,ai]，(ai,ATjk]的數(shù)據(jù)樣本來(lái)表示描述屬性Ak的取值。

(3) 屬性Ak的Tj-1種分割中的每一種情況，都可作為該屬性的2個(gè)離散取值，重新構(gòu)造該屬性的離散值，按照上述公式計(jì)算每一種分割所對(duì)應(yīng)的信息增益率Gain_Ratio(Ak)，選擇其中信息增益率最大的分割閾值作為屬性Ak的最佳分割閾值，即

Gain_Ratio(ak) = max{Gain_Ratio(ai)}，即ak是ai中信息增益率最大者。

2 C4.5算法的改進(jìn)

作為ID3算法的改進(jìn)算法，C4.5在算法功能上增強(qiáng)了不少，但也存在一些不足之處[11]：C4.5算法采用信息增益率作為最佳分裂屬性的評(píng)判標(biāo)準(zhǔn)，計(jì)算描述屬性的信息增益率，并選擇其中信息增益率最大的描述屬性作為節(jié)點(diǎn)分裂屬性。在連續(xù)型屬性離散化時(shí)，由上述C4.5算法連續(xù)型屬性離散化方法可知，算法要在任一屬性的不同取值中插入若干個(gè)分割點(diǎn)，再計(jì)算所有分割點(diǎn)的信息增益率，選擇其中信息增益率最大的分割閾值作為連續(xù)型屬性的最佳分割閾值。當(dāng)決策樹(shù)的節(jié)點(diǎn)數(shù)量比較多、連續(xù)型屬性數(shù)量比較多、連續(xù)型屬性中任一屬性取值又比較多時(shí)，算法的計(jì)算量是相當(dāng)大的，這將會(huì)在很大程度上影響決策樹(shù)的生成效率。本文針對(duì)C4.5算法中連續(xù)型屬性最佳分割閾值選擇算法的計(jì)算復(fù)雜性問(wèn)題提出了一些改進(jìn)，以提高決策樹(shù)的效率。

2.1 連續(xù)型屬性處理算法的改進(jìn)

C4.5算法在連續(xù)屬性離散化過(guò)程中，要對(duì)所有劃分情況進(jìn)行預(yù)測(cè)，這將占用很多時(shí)間。如何快速選擇一個(gè)最佳的劃分閾值已成為亟待解決的問(wèn)題。Fayyad等[16]證明：無(wú)論用于學(xué)習(xí)的數(shù)據(jù)集有多少個(gè)類別，不管類別的分布如何，連續(xù)型屬性的最佳分割點(diǎn)總在邊界點(diǎn)處。

本文根據(jù) Fayyad邊界點(diǎn)原理[16]將連續(xù)型描述屬性按升序排列，選取排序后某一連續(xù)型屬性的相鄰兩類邊界點(diǎn)處的 6個(gè)屬性取值ai-2，ai-1，ai，ai+1，ai+2和ai+3(ai-2＜ai-1＜ai＜ai+1＜ai+2＜ai+3)作為測(cè)試屬性值。其中：ai是類1中的最大值，ai+1是類2中的最小值。計(jì)算相應(yīng)的信息增益率，選擇信息增益率最大的屬性值作為最佳分割閾值進(jìn)行劃分。改進(jìn)后的算法只需計(jì)算邊界點(diǎn)處6個(gè)屬性值的信息增益率，相對(duì)于傳統(tǒng)C4.5算法遍歷所有的屬性值的信息增益率，其計(jì)算復(fù)雜度降低了許多。當(dāng)連續(xù)型屬性只有2個(gè)類別時(shí)，簡(jiǎn)化后算法的計(jì)算效率則更高，本文的所要處理的應(yīng)用對(duì)象的實(shí)驗(yàn)數(shù)據(jù)就屬于這種情況；當(dāng)遇到特殊情況即每個(gè)屬性值僅代表1個(gè)類別時(shí)，改進(jìn)算法的計(jì)算復(fù)雜度與C4.5算法的相當(dāng)。

2.2 改進(jìn)決策樹(shù)C4.5算法描述

算法：決策樹(shù) C4.5算法，F(xiàn)unction Tree=Create_C4.5(T,A,target)。

輸入：訓(xùn)練集T,描述屬性A,描述測(cè)試樣本的類標(biāo) target。

輸出：決策樹(shù)Tree，預(yù)測(cè)分類準(zhǔn)確率。

步驟：

(1) 在訓(xùn)練集T中創(chuàng)建根節(jié)點(diǎn)N；

(2) 若訓(xùn)練集T中的樣本屬于同一類別C，則以C標(biāo)記節(jié)點(diǎn)N，并以節(jié)點(diǎn)N作為葉節(jié)點(diǎn)，返回；

(3) 如果描述屬性為空，那么以數(shù)據(jù)集中占多數(shù)的描述類別C標(biāo)記節(jié)點(diǎn)N并將N作為葉節(jié)點(diǎn)，返回；

(4) 從描述屬性A中選出信息增益率最大的描述屬性Ak作為節(jié)點(diǎn)N的分裂屬性，轉(zhuǎn)入下一步；

(5) 若描述屬性是離散型，設(shè)屬性Ak有v種取值a1，a2，…，av，則數(shù)據(jù)集T將被Ak分為v個(gè)樣本子集，每個(gè)子集都是由屬性取值相同的樣本組成的；

(6) 若描述屬性是連續(xù)型，則用改進(jìn)的連續(xù)型屬性分割算法選擇最佳分割閾值，并對(duì)屬性集A進(jìn)行劃分，用離散化后屬性集對(duì)數(shù)據(jù)集T進(jìn)行步驟(5)同樣的操作，返回；

(7) 選擇剩余描述屬性中最佳分裂屬性在數(shù)據(jù)子集上創(chuàng)建子節(jié)點(diǎn)，返回；

(8) 對(duì)進(jìn)一步劃分的數(shù)據(jù)子集，即新建各內(nèi)部節(jié)點(diǎn)，遞歸調(diào)用步驟(2)～步驟(7)，繼續(xù)選擇最佳分枝屬性作為內(nèi)部節(jié)點(diǎn)，直到所有的樣本都?xì)w類于相應(yīng)的葉節(jié)點(diǎn)為止。

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)由 2個(gè)部分組成：(1) 經(jīng)處理的數(shù)字視頻圖像中行人和車輛的特征數(shù)據(jù)；(2) 從標(biāo)準(zhǔn)數(shù)據(jù)集UCI中采集的部分?jǐn)?shù)據(jù)。

3.1 實(shí)驗(yàn)Ⅰ及結(jié)果分析

實(shí)驗(yàn)Ⅰ的內(nèi)容是對(duì)改進(jìn)C4.5算法與傳統(tǒng)C4.5算法的分類性能進(jìn)行比較。實(shí)驗(yàn)1所用的部分?jǐn)?shù)據(jù)如表1所示。

為了降低分類器的誤判率，對(duì)部分人車特征數(shù)據(jù)進(jìn)行了歸一化處理。實(shí)驗(yàn)1主要在決策樹(shù)生成效率和預(yù)測(cè)能力方面對(duì)改進(jìn)C4.5算法與傳統(tǒng)C4.5算法進(jìn)行了比較。實(shí)驗(yàn)數(shù)據(jù)由訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)2部分組成。實(shí)驗(yàn)采用10重交叉驗(yàn)證決策樹(shù)的分類準(zhǔn)確率，各組實(shí)驗(yàn)數(shù)據(jù)的數(shù)量不同，逐組均勻增加。實(shí)驗(yàn)數(shù)據(jù)(m,n)分別代表訓(xùn)練集和測(cè)試集的樣本數(shù)量。在各組實(shí)驗(yàn)數(shù)據(jù)上分別訓(xùn)練測(cè)試10次，求其平均分類準(zhǔn)確率作為本實(shí)驗(yàn)的記錄值，結(jié)果如表2所示。分類準(zhǔn)確率定義為測(cè)試集中被正確識(shí)別出類別的樣本數(shù)占總樣本數(shù)的比例。實(shí)驗(yàn)結(jié)果表明：改進(jìn)C4.5分類器與傳統(tǒng)C4.5分類器的平均分類準(zhǔn)確率相當(dāng)，但在決策樹(shù)生成時(shí)間方面，改進(jìn)C4.5分類器有很大的改進(jìn)，減少了很大一部分用時(shí)，在一定程度上提高了 C4.5分類器的生成效率。

表1 人車特征數(shù)據(jù)(部分訓(xùn)練特征)Table 1 People and vehicle feature data(part of raining feature)

3.2 實(shí)驗(yàn)Ⅱ及結(jié)果分析

實(shí)驗(yàn)Ⅱ的內(nèi)容是對(duì)改進(jìn)C4.5分類器與K-均值分類器以及傳統(tǒng)C4.5分類器的分類性能比較。所采用的實(shí)驗(yàn)數(shù)據(jù)如表3所示，數(shù)據(jù)取自標(biāo)準(zhǔn)數(shù)據(jù)集UCI，每組數(shù)據(jù)包含數(shù)據(jù)名稱、實(shí)例個(gè)數(shù)、類個(gè)數(shù)以及屬性個(gè)數(shù)等信息，共11組。實(shí)驗(yàn)采用10重交叉驗(yàn)證法在標(biāo)準(zhǔn)數(shù)據(jù)集上對(duì)改進(jìn)C4.5分類器的預(yù)測(cè)能力進(jìn)行測(cè)試。各分類器分別在每組數(shù)據(jù)上測(cè)試10次，每次測(cè)試采用不同的數(shù)據(jù)劃分方法，采用10次測(cè)試分類準(zhǔn)確率的平均值作為實(shí)驗(yàn)記錄結(jié)果，最終以各分類器在總數(shù)據(jù)集上的平均分類準(zhǔn)確率為依據(jù)，進(jìn)行分類性能比較。

由實(shí)驗(yàn)Ⅱ的結(jié)果可知：改進(jìn)C4.5分類器的平均分類準(zhǔn)確率為85.011 0%，比傳統(tǒng)C4.5分類器的平均分類準(zhǔn)確率高約2.4%，比K-均值分類器高約5.7%。實(shí)驗(yàn)結(jié)果表明：無(wú)論是改進(jìn) C4.5分類器還是傳統(tǒng)C4.5分類器都有較強(qiáng)的穩(wěn)定性；改進(jìn)C4.5分類器和傳統(tǒng) C4.5分類器均比 K-均值分類器的分類性能要好；在某些數(shù)據(jù)集上，改進(jìn)C4.5分類器的分類準(zhǔn)確率更高。

表2 實(shí)驗(yàn)Ⅰ的結(jié)果Table 2 Results of experiment Ⅰ %

表3 實(shí)驗(yàn)Ⅱ的數(shù)據(jù)集Table 3 Data set of experiment Ⅱ

實(shí)驗(yàn)Ⅰ和實(shí)驗(yàn)Ⅱ的結(jié)果表明；改進(jìn)C4.5分類器比傳統(tǒng)C4.5 分類器的分類準(zhǔn)確率略高，但改進(jìn)C4.5分類器的計(jì)算量要比傳統(tǒng) C4.5分類器的計(jì)算量減少近20%，大大提高了決策樹(shù)的生成效率。無(wú)論是改進(jìn)C4.5分類器還是傳統(tǒng)C4.5分類器，都比K-均值分類器的分類準(zhǔn)確率要高，在算法穩(wěn)定性方面，前兩者也比K-均值分類器要好，由實(shí)驗(yàn)結(jié)果可知：改進(jìn)C4.5分類器和傳統(tǒng) C4.5分類器的分類準(zhǔn)確率對(duì)決策樹(shù)的節(jié)點(diǎn)容錯(cuò)率(同一節(jié)點(diǎn)中允許存在的錯(cuò)誤樣本數(shù)占總樣本數(shù)的比例)較穩(wěn)定；當(dāng)節(jié)點(diǎn)容錯(cuò)率在0～8%的范圍內(nèi)調(diào)整時(shí)，改進(jìn)的與傳統(tǒng)的C4.5分類器的分類準(zhǔn)確率不變；當(dāng)容錯(cuò)率繼續(xù)調(diào)大時(shí)，二者的分類準(zhǔn)確率均緩慢下降；當(dāng)容錯(cuò)率超過(guò)12%時(shí)，分類準(zhǔn)確率則大幅度下降。分類器的穩(wěn)定性較差，而K-均值分類器其分類準(zhǔn)確率受錯(cuò)誤樣本的影響較大，如有少量錯(cuò)誤樣本，K-均值分類器的分類準(zhǔn)確率就會(huì)明顯降低。

表4 實(shí)驗(yàn)Ⅱ的結(jié)果Table 4 Results of experiment Ⅱ %

4 結(jié)論

(1) 對(duì)傳統(tǒng) C4.5分類器處理連續(xù)型屬性的算法進(jìn)行改進(jìn)，提出了一種局部最佳分割閾值選擇算法，該算法在很大程度上減少了原算法的計(jì)算量，提高了決策樹(shù)的生成效率，特別是當(dāng)預(yù)測(cè)數(shù)據(jù)集的類別數(shù)目比較少時(shí)，改進(jìn)算法的效果更明顯。改進(jìn)的算法可行，決策樹(shù)的生成效率提高了近20%，改進(jìn)C4.5分類器具有較好的應(yīng)用價(jià)值。

(2) 在最佳分割閾值選擇算法中，如何確定邊界點(diǎn)處連續(xù)屬性的取值個(gè)數(shù)是關(guān)鍵，取不同的屬性個(gè)數(shù)對(duì)算法的計(jì)算量影響很大，是否有更好的方法確定邊界點(diǎn)處連續(xù)屬性的取值個(gè)數(shù)有待進(jìn)一步研究。

[1]Haykin S. Neural networks and learning machines[M]. Beijing:China Machine Press,2009: 1-7.

[2]ZHU Xiao-liang,WANG Jian,YAN Hong-can,et al. Research and application of the improved algorithm C4.5 on decision tree[C]//IEEE International Conference on Test and Measurement,Hongkong,2009: 184-187.

[3]de Toledo P,Rios P M,Ledezma A,et al. Predicting the outcome of patients with subarachnoid hemorrhage using machine learning techniques[J]. IEEE Trans on Information Technology in Biomedicine,2009,13(5): 794-801.

[4]Tsang S,Kao B,Yip K Y et al. Decision trees for uncertain data[C]//IEEE International Conference on Data Engineering,Shanghai,2009: 441-444.

[5]LI Fa-chao,LI Ping,JIN Chen-xia. Summary of decision tree algorithm and its application in attribute reduction[R].Shijiazhuang: Hebei Univ of Sci and Technol,2009: 313-317.

[6]謝金梅,王艷妮. 決策樹(shù)算法綜述[J]. 軟件導(dǎo)報(bào),2008,7(11):83-85.XIE Jin-mei,WANG Yan-ni. Summary of decision tree algorithms[J]. Software Guide,2008,7(11): 83-85.

[7]王闐,佘光輝. 決策樹(shù) C4.5算法在森林資源二類調(diào)查中的應(yīng)用[J]. 南京林業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版,2007,31(3): 115-118.WANG Tian,SHE Guang-hui. Application of C4.5 based decision tree algorithm about investigation and analysis of forestry resources[J]. Journal of Nanjing Forestry University:Natural Sciences Edition,2007,31(3): 115-118.

[8]Hunt E B,Marin J,Stone P T. Experiments in induction[M]. San Diego: Academic Press,1966: 77-89.

[9]CHEN Jin,LUO De-Lin,MU Fen-xiang. An improved ID3 decision tree algorithm[C]//4th International Conference on IEEE Computer Science and Education. Chengdu,2009:127-130.

[10]Quinlan J R. C4.5: Programs for machine learning[M]. San Mateo: Morgan Kaufmann Publishers Inc,1993: 17-42.

[11]楊學(xué)兵,張俊. 決策樹(shù)算法及其核心技術(shù)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(1): 44-46.YANG Xue-bing,ZHANG Jun. Decision tree algorithm and its key techniques[J]. Computer Technology and Development,2007,17(1): 44-46.

[12]Roiger R J,Geatz M W. 數(shù)據(jù)挖掘教程[M]. 翁敬農(nóng),譯. 北京:清華大學(xué)出版社,2008: 60-85.Roiger R J,Geatz M W. Data mining tutorial[M]. WENG Jing-mong,trans. Beijing: Tsinghua University Press,2008:60-85.

[13]Maszczyk T,Duch W. Comparison of Shannon,Renyi and Tsallis entropy used in decision trees[J]. Artificial Intelligence and Soft Computing,2008,5097: 643-651.

[14]Kantardzic M. Data mining: Concepts,models,and algorithms[M]. New York: John Wiley and IEEE Press,2003:139-164.

[15]ZHOU Chi,XIAO Wei-min,Tirpak T M,et al. Evolving accurate and compact classification rules with gene expression programming[J]. IEEE Transactions on Evolutionary Computation,2003,7(6): 519-531.

[16]Fayyad U M,Irani K B. On the handling of continuous-value attributes in decision tree generation[J]. Machine Learning,1992,8(1): 87-102.