王 森，趙發(fā)勇，陳曙光

（阜陽師范學(xué)院 物理與電子工程學(xué)院，安徽 阜陽 236037）

多種屬性選取標(biāo)準(zhǔn)“多數(shù)表決”優(yōu)化決策樹研究

王 森，趙發(fā)勇，陳曙光

（阜陽師范學(xué)院 物理與電子工程學(xué)院，安徽 阜陽 236037）

測(cè)試屬性的選取即屬性選擇標(biāo)準(zhǔn)是構(gòu)建決策樹的關(guān)鍵及核心，對(duì)于同樣的數(shù)據(jù)集，不同的屬性選取標(biāo)準(zhǔn)構(gòu)建的決策樹有可能差別很大。對(duì)于不知采用何種屬性選擇標(biāo)準(zhǔn)或者沒有一種標(biāo)準(zhǔn)適合所處理的數(shù)據(jù)集，本文提出了一種解決的方法，即多種屬性選取標(biāo)準(zhǔn)多數(shù)表決優(yōu)化決策樹算法，該算法利用“專家會(huì)診”的思想，構(gòu)建決策樹，具有更廣的適應(yīng)性和更可能高的準(zhǔn)確率。

屬性選取標(biāo)準(zhǔn)；多數(shù)表決；決策樹

在創(chuàng)建決策樹過程中，測(cè)試屬性選取標(biāo)準(zhǔn)非常重要，可以說處于核心和最重要的地位，而如何選擇好的測(cè)試屬性或?qū)傩灾档倪壿嬇袛嗍菢?gòu)建好的決策樹的關(guān)鍵。對(duì)于相同的訓(xùn)練數(shù)據(jù)集，可以采用不同的算法構(gòu)建符合這個(gè)訓(xùn)練數(shù)據(jù)集決策樹。不同的算法構(gòu)建的決策樹可能相同，也可能不同。研究表明，一般情況下，構(gòu)建的決策樹越簡單，預(yù)測(cè)能力越強(qiáng)[1]。要構(gòu)造盡可能簡單的決策樹，關(guān)鍵在于選擇合適的測(cè)試屬性或產(chǎn)生合適的邏輯判斷式的標(biāo)準(zhǔn)。針對(duì)不同特性的數(shù)據(jù)集，人們提出了多種不同測(cè)試屬性選擇標(biāo)準(zhǔn)（如信息增益標(biāo)準(zhǔn)[2]、信息增益率標(biāo)準(zhǔn)[3]、基于距離度量的標(biāo)準(zhǔn)、G統(tǒng)計(jì)標(biāo)準(zhǔn)、Gini-index標(biāo)準(zhǔn)[4]、基于χ2統(tǒng)計(jì)的標(biāo)準(zhǔn)[4]、最小描述長度標(biāo)準(zhǔn)、基于相關(guān)度的標(biāo)準(zhǔn)等等）。不同的度量標(biāo)準(zhǔn)，有不同的效果，特別是對(duì)于多值屬性，選擇不同的度量標(biāo)準(zhǔn)對(duì)于結(jié)果的影響很大，也有許多學(xué)者提出一些改進(jìn)的方法[5-11]來選取測(cè)試屬性。對(duì)于用戶來說，選擇哪種標(biāo)準(zhǔn)確實(shí)比較困難，往往要根據(jù)經(jīng)驗(yàn)或領(lǐng)域知識(shí)來確定，或經(jīng)過多種標(biāo)準(zhǔn)的構(gòu)建的決策樹進(jìn)行比較（如預(yù)測(cè)的準(zhǔn)確率、構(gòu)建決策樹的效率等方面），選擇最符合實(shí)際的需要的決策樹，用于未來的決策。

在面對(duì)一個(gè)數(shù)據(jù)集時(shí)，不知采用何種屬性選擇標(biāo)準(zhǔn)對(duì)分類比較準(zhǔn)確、或者哪種屬性選取標(biāo)準(zhǔn)都不理想時(shí)，就像同一病人，不同的醫(yī)生可能診斷結(jié)果不同，或者任何一個(gè)醫(yī)生治療的效果都不好時(shí)，可能要專家會(huì)診，這樣不同的醫(yī)生可以從不同的角度對(duì)病人提出不同的治療意見，為了達(dá)成一致的意見，往往要進(jìn)行多數(shù)表決，在票數(shù)相同時(shí)，聽取有名專家的意見。受這種思想的啟發(fā)，我們?cè)跇?gòu)建決策樹時(shí)，在進(jìn)行屬性選擇時(shí)，采用多個(gè)不同屬性選擇標(biāo)準(zhǔn)來選擇測(cè)試屬性，最終采用多數(shù)表決方法來決定哪個(gè)是最終的測(cè)試屬性，即票數(shù)最多的作為測(cè)試屬性（或分裂屬性），若票數(shù)最多的屬性有多個(gè)時(shí)，采用最有影響的屬性選擇標(biāo)準(zhǔn)（如ID3的信息增益或者C4.5系統(tǒng)的信息增益率標(biāo)準(zhǔn)）所選擇的屬性作為測(cè)試屬性。文中選擇信息增益標(biāo)準(zhǔn)、信息增益率標(biāo)準(zhǔn)、Gini-index標(biāo)準(zhǔn)和χ2統(tǒng)計(jì)標(biāo)準(zhǔn)作為屬性選擇標(biāo)準(zhǔn)，采用多數(shù)表決的方式來優(yōu)化構(gòu)建決策樹，在票數(shù)相同時(shí)采用信息增益率標(biāo)準(zhǔn)選擇的測(cè)試屬性作為最終要選取的測(cè)試屬性來構(gòu)建決策樹。

1 測(cè)試屬性選擇標(biāo)準(zhǔn)簡介

這里，假設(shè)訓(xùn)練數(shù)據(jù)樣本的集合S中有s個(gè)數(shù)據(jù)樣本。假定類別屬性C，有m個(gè)不同值，即Ci(i=1,2,…,m)。在類Ci中有數(shù)據(jù)樣本si個(gè)。

1.1 信息增益標(biāo)準(zhǔn)

經(jīng)典的ID3算法使用該標(biāo)準(zhǔn)，對(duì)要學(xué)習(xí)的一個(gè)訓(xùn)練樣本集，類別屬性的信息熵由下式給出：

其中，pi是任意樣本屬于類Ci的概率，并用sis近似估計(jì)。

根據(jù)屬性A劃分成子集的熵由下式給出：

其中，m是類別屬性值的個(gè)數(shù)，n是候選屬性A的取值個(gè)數(shù)；熵值越小，說明訓(xùn)練樣本集根據(jù)屬性A劃分的子集純度越高。

根據(jù)屬性A的值劃分訓(xùn)練樣本集的信息增益是：

計(jì)算并比較各候選屬性的信息增益，選取信息增益最大的候選屬性作為測(cè)試屬性，并以該測(cè)試屬性創(chuàng)建一個(gè)結(jié)點(diǎn)并標(biāo)記此結(jié)點(diǎn)，再根據(jù)該測(cè)試屬性的每個(gè)值劃分樣本并為每一個(gè)劃分產(chǎn)生一個(gè)分枝。算法以遞歸的方法自上而下在每個(gè)被劃分的數(shù)據(jù)樣本集中進(jìn)行同上操作，直到被劃分的每個(gè)集合屬于同一個(gè)類別為止；否則算法選擇具有不同類的子集遞歸進(jìn)行同上操作。

1.2 信息增益率標(biāo)準(zhǔn)

C4.5系統(tǒng)使用該標(biāo)準(zhǔn)，信息增益率是在信息增益的基礎(chǔ)之上發(fā)展起來的，它避免信息增益的多值趨向，是對(duì)信息增益的優(yōu)化。通過計(jì)算并比較各候選屬性的信息增益率，信息增益率最大候選屬性被選擇作為測(cè)試屬性。具體過程：首先，通過公式（1）、（2）和（3）計(jì)算各侯選屬性的信息增益，然后根據(jù)如下公式（4），計(jì)算各候選屬性的信息增益率。用于對(duì)候選屬性A的信息增益率計(jì)算的函數(shù)定義如下：

1.3 Gini-index標(biāo)準(zhǔn)

Gini-index是一種度量不純度的函數(shù)，CART算法變形使用該標(biāo)準(zhǔn)，在Gini-index標(biāo)準(zhǔn)中用Gini-index指數(shù)來度量訓(xùn)練數(shù)據(jù)集中各侯選屬性劃分類別屬性的“純度”。

若訓(xùn)練樣本集中各個(gè)類別是均勻的，則該訓(xùn)練數(shù)據(jù)集具有最大的不純度，否則，如果訓(xùn)練樣本在各類別中數(shù)量差距很大，則訓(xùn)練數(shù)據(jù)集的不純度就較??；如果訓(xùn)練樣本同屬性一個(gè)類別，則為0。

假設(shè)不純度函數(shù) φ定義在一個(gè) k元組((p(c1),p(c2),…,p(ck))上，則不純度函數(shù)φ滿足下列條件：

a)p(ci)≥0其中i∈{1,2,…,k}，

由于根據(jù)各屬性的不同取值對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行劃分，數(shù)據(jù)集合變的越來越小，這將導(dǎo)致平均訓(xùn)練數(shù)據(jù)集的不純度的減?。醇兌仍黾樱?。在該標(biāo)準(zhǔn)中，作為不純度函數(shù)形式如下：

其中，p(ci)≥0（i∈{1,2,…,k}）表示每個(gè)類別在訓(xùn)練數(shù)據(jù)集中的概率。

把Gini-index應(yīng)用在決策樹中，則節(jié)點(diǎn)t的不純度函數(shù)為：

其中，假定結(jié)點(diǎn)t所對(duì)應(yīng)的候選屬性有m個(gè)取值，則根據(jù)該候選屬性值劃分訓(xùn)練數(shù)據(jù)集，則對(duì)應(yīng)的得到m個(gè)數(shù)據(jù)子集t1,t2,…,tm，而每個(gè)數(shù)據(jù)子集所占訓(xùn)練數(shù)據(jù)集的比例分別為p(t1),p(t2),…,p(tm)。

在具有Gini-index標(biāo)準(zhǔn)的算法中，首先計(jì)算并比較各候選屬性劃分樣本帶來的純度增量；選取使純度增量最大的候選屬性作為測(cè)試屬性，并據(jù)此劃分訓(xùn)練數(shù)據(jù)集；最后在每個(gè)劃分后的子集中，遞歸進(jìn)行上面的純度增量計(jì)算并劃分。

1.4 χ2統(tǒng)計(jì)標(biāo)準(zhǔn)

CHILD算法變形使用該標(biāo)準(zhǔn)，χ2統(tǒng)計(jì)是用基于統(tǒng)計(jì)學(xué)的方法，通過統(tǒng)計(jì)分析各侯選屬性與類別屬性關(guān)聯(lián)程度，選取關(guān)聯(lián)程度最大的屬性作為測(cè)試屬性。一般步驟如下：首先用列聯(lián)表表示侯選屬性與類別屬性的取值頻率；其次比較它們實(shí)際觀察到的頻率與假設(shè)在沒有關(guān)聯(lián)的情況下的頻率，得到近似于χ2統(tǒng)計(jì)的統(tǒng)計(jì)量的分布。χ2統(tǒng)計(jì)標(biāo)準(zhǔn)的基本方程為：

其中，xij表示類別屬性取第j個(gè)值，候選屬性取第i個(gè)值時(shí)訓(xùn)練樣本的個(gè)數(shù)；表示在假定類別屬性與候選屬性沒有關(guān)聯(lián)時(shí)xij的期望值。該期望值越大，表示候選屬性與類別屬性的關(guān)系程度越大；統(tǒng)計(jì)量xio表示候選屬性A取值A(chǔ)i的樣本總數(shù)，而統(tǒng)計(jì)量xoj表示類別屬性C取值Cj的樣本總數(shù)；N表示訓(xùn)練數(shù)據(jù)集中的樣本總數(shù)。

假設(shè)一個(gè)訓(xùn)練數(shù)據(jù)集中含有候選屬性A和類別屬性C，由它們所構(gòu)成的列聯(lián)表如表1所示，其中，xij表示訓(xùn)練數(shù)據(jù)集中候選屬性A取值A(chǔ)i類別屬性C取值Cj的訓(xùn)練樣本的個(gè)數(shù)；xoj表示類別屬性C取值Cj的訓(xùn)練樣本總數(shù)，統(tǒng)計(jì)量xio表示候選屬性A取值A(chǔ)i的訓(xùn)練樣本總數(shù)。

χ2統(tǒng)計(jì)標(biāo)準(zhǔn)通過計(jì)算并比較類別屬性與各候選屬性的關(guān)聯(lián)程度，選取關(guān)聯(lián)程度最大的候選屬性作為測(cè)試屬性或分裂屬性。

2 多種屬性選取標(biāo)準(zhǔn)多數(shù)表決決策樹算法

由基本理論基礎(chǔ)，構(gòu)建多種屬性選取策略優(yōu)化決策樹算法如下：

算法：Gen_Multi_Sta_Dec_Tree由給定訓(xùn)練數(shù)據(jù)集產(chǎn)生一棵多種屬性選取標(biāo)準(zhǔn)多數(shù)表決決策樹。

輸入：由離散屬性表示的訓(xùn)練數(shù)據(jù)集S，和用于構(gòu)建決策樹的候選屬性集合A。

輸出：一棵多種屬性選取標(biāo)準(zhǔn)多數(shù)表決決策樹。

步驟：

①采用ID3標(biāo)準(zhǔn)計(jì)算并比較各候選屬性的信息增益值，并使信息增益最大的候選屬性被選次數(shù)增一。

②采用C4.5標(biāo)準(zhǔn)計(jì)算并比較各候選屬性的信息增益率，并使信息增益率最大的候選屬性的被選次數(shù)增一。

③采用Gini_index標(biāo)準(zhǔn)計(jì)算并比較各候選屬性的純度增量，并使純度增量最大的候選屬性的被選次數(shù)增一。

④采用χ2統(tǒng)計(jì)標(biāo)準(zhǔn)計(jì)算并比較各候選屬性與類別屬性關(guān)聯(lián)程度，并使關(guān)聯(lián)程度最大的候選屬性的被選次數(shù)增一。

3 具體示例

本文給出了取自AllElectronics顧客數(shù)據(jù)庫數(shù)據(jù)元組訓(xùn)練集（數(shù)據(jù)取自[Qui86]）如表2，對(duì)構(gòu)建多決策判定樹過程如下：

根據(jù)ID3標(biāo)準(zhǔn)，

由于Gain(age)最大，所以根據(jù)信息增益標(biāo)準(zhǔn)屬性age劃分樣本。

根據(jù)信息增益標(biāo)準(zhǔn)，

GainRatio(credit_rating)=0.049 3。

由于GainRatio(age)最大，所以根據(jù)屬性age劃分樣本。

根據(jù)Gini-Index標(biāo)準(zhǔn),

由于gini(age)最大，所以用屬性age劃分樣本。

根據(jù)χ2統(tǒng)計(jì)標(biāo)準(zhǔn)

由于χ2(age)最大，所以由屬性age劃分樣本。

由于上述各標(biāo)準(zhǔn)都選擇屬性age劃分樣本（可能是舉例的樣本集不合適的原因或樣本量太小的原因，四種選擇測(cè)試屬性的標(biāo)準(zhǔn)都選擇age屬性作為分裂屬性），所以據(jù)此劃分樣本得圖1。

同樣對(duì)每個(gè)劃分的樣本集采用上述同樣的算法構(gòu)建決策樹，最終得決策樹如圖2。

從上面過程可以看出，相比單獨(dú)屬性選擇標(biāo)準(zhǔn)，通過多種屬性選擇標(biāo)準(zhǔn)來確定測(cè)試屬性，是一種“多數(shù)表決”構(gòu)建決策樹。它適用于在給定數(shù)據(jù)集不知采用什么樣的屬性選擇標(biāo)準(zhǔn)時(shí)或者使用每種屬性選擇標(biāo)準(zhǔn)都不理想時(shí)，這種情況的數(shù)據(jù)集在實(shí)際應(yīng)用中可能最多，因此，多屬性選擇標(biāo)準(zhǔn)構(gòu)建決策樹的方法，具有更好和更廣的適應(yīng)性。同“專家會(huì)診”的效果一樣，通常情況下效果會(huì)很好，但也有例外的情況。這種方法計(jì)算量很大，構(gòu)建決策樹的效率低，但一旦建立好決策樹，準(zhǔn)確率要高，其準(zhǔn)確率也有待用實(shí)際的數(shù)據(jù)集來驗(yàn)證。當(dāng)然這種構(gòu)建決策樹的算法，是一種折中方法，實(shí)際應(yīng)用也有通過測(cè)試集的測(cè)試，有較高的準(zhǔn)確率后才用于以后的推測(cè)或估計(jì)。

3 結(jié)束語

本文介紹了構(gòu)建決策樹常用的四種測(cè)試屬性選擇標(biāo)準(zhǔn)：信息增益標(biāo)準(zhǔn)、信息增益率標(biāo)準(zhǔn)、Gini-Index標(biāo)準(zhǔn)和χ2統(tǒng)計(jì)標(biāo)準(zhǔn)。對(duì)于同一數(shù)據(jù)集，由于屬性選擇標(biāo)準(zhǔn)不同，構(gòu)建的決策樹可能不同；本文提出一種基于“多數(shù)表決”的思路，即采用“多數(shù)表決”選擇測(cè)試屬性構(gòu)建決策樹；設(shè)計(jì)并實(shí)現(xiàn)了相應(yīng)的算法，給出了從一個(gè)具體的示例介紹基于多種屬性選擇標(biāo)準(zhǔn)“多數(shù)表決”構(gòu)建決策樹的過程。在給定數(shù)據(jù)集不知采用什么樣的屬性選擇標(biāo)準(zhǔn)時(shí)或者使用任一一種屬性選擇標(biāo)準(zhǔn)都不理想時(shí)，采用“多數(shù)表決”構(gòu)建決策樹是一種合適的選擇。

[1]張 琳，陳 燕，李桃迎，等.決策樹分類算法研究[J]．計(jì)算機(jī)工程，2011，37（13）：66-67,70．

[2]Han J W,Kamber M.數(shù)據(jù)挖掘(概念與技術(shù))[M]．北京：機(jī)械工業(yè)出版社，2006．

[3]Soman K P,Diwakar S,Ajay V.數(shù)據(jù)挖掘基礎(chǔ)教程[M].北京：機(jī)械工業(yè)出版社，2011．

[4]L Breiman J H,Stone C J.Classification and regression trees[Z].1984.

[5]M.Mehta,R.Agrawal.SLIQ:A fast scalable classifier for data mining.int.conf.EDBT’96 28.

[6]謝妞妞，劉於勛.決策樹屬性選擇標(biāo)準(zhǔn)的改進(jìn)[J]．計(jì)算機(jī)工程與應(yīng)用，2010，46（34）：115-118,139．

[7]喻金平，黃細(xì)妹，李康順.基于一種新的屬性選擇標(biāo)準(zhǔn)的ID3改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（8）：2895-2898,2908．

[8]孫淮寧，胡學(xué)鋼.一種基于屬性貢獻(xiàn)度的決策樹學(xué)習(xí)算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，32（8）：1137-1141．

[9]屈志毅，周海波.決策樹算法的一種改進(jìn)算法[J]．計(jì)算機(jī)應(yīng)用，2008，28（z1）：141-143．

[10]鄒永貴，范程華.基于屬性重要度的ID3改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用，2008，28（z1）：144-145,149．

[11]王小巍，蔣玉明.決策樹ID3算法的分析與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（9）：3069-3072,3076．

Majority voting optimization of decision tree with multiple attributes selection criteria

WANG Sen,ZHAO Fa-yong,CHEN Shu-guang
(School of Physics and Electronic Engineering,Fuyang Normal University,Fuyang Anhui 236037,China)

The selection of test attributes is the key and core of constructing the decision tree.For the same data set,the decision trees constructed by different attribute selection criteria may vary greatly.Not to know which attribute selection criteria is good or not a standard suitable for handling data sets,this paper presents a solution,namely the majority voting optimization of decision tree with multiple attributes selection criteria algorithm,which uses the idea of“expert consultation”to construct the decision tree,with a wider adaptability and higher accuracy in the practical application.

attribute selection criteria;majority voting;decision tree

A

1004-4329（2017）01-061-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）01-061-05

2017-01-10

安徽省科技攻關(guān)項(xiàng)目（5101031114）資助。

王 森（1973- ）男，碩士，講師，研究方向：軟件工程、數(shù)據(jù)挖掘。