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

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

多種屬性選取標準“多數表決”優(yōu)化決策樹研究

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

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

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

屬性選取標準；多數表決；決策樹

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

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

1 測試屬性選擇標準簡介

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

1.1 信息增益標準

經典的ID3算法使用該標準，對要學習的一個訓練樣本集，類別屬性的信息熵由下式給出：

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

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

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

根據屬性A的值劃分訓練樣本集的信息增益是：

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

1.2 信息增益率標準

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

1.3 Gini-index標準

Gini-index是一種度量不純度的函數，CART算法變形使用該標準，在Gini-index標準中用Gini-index指數來度量訓練數據集中各侯選屬性劃分類別屬性的“純度”。

若訓練樣本集中各個類別是均勻的，則該訓練數據集具有最大的不純度，否則，如果訓練樣本在各類別中數量差距很大，則訓練數據集的不純度就較?。蝗绻柧殬颖就瑢傩砸粋€類別，則為0。

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

由于根據各屬性的不同取值對訓練數據集進行劃分，數據集合變的越來越小，這將導致平均訓練數據集的不純度的減?。醇兌仍黾樱Ｔ谠摌藴手?，作為不純度函數形式如下：

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

把Gini-index應用在決策樹中，則節(jié)點t的不純度函數為：

其中，假定結點t所對應的候選屬性有m個取值，則根據該候選屬性值劃分訓練數據集，則對應的得到m個數據子集t1,t2,…,tm，而每個數據子集所占訓練數據集的比例分別為p(t1),p(t2),…,p(tm)。

在具有Gini-index標準的算法中，首先計算并比較各候選屬性劃分樣本帶來的純度增量；選取使純度增量最大的候選屬性作為測試屬性，并據此劃分訓練數據集；最后在每個劃分后的子集中，遞歸進行上面的純度增量計算并劃分。

1.4 χ2統(tǒng)計標準

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

假設一個訓練數據集中含有候選屬性A和類別屬性C，由它們所構成的列聯表如表1所示，其中，xij表示訓練數據集中候選屬性A取值Ai類別屬性C取值Cj的訓練樣本的個數；xoj表示類別屬性C取值Cj的訓練樣本總數，統(tǒng)計量xio表示候選屬性A取值Ai的訓練樣本總數。

表1 屬性A和分類屬性C的列聯表

χ2統(tǒng)計標準通過計算并比較類別屬性與各候選屬性的關聯程度，選取關聯程度最大的候選屬性作為測試屬性或分裂屬性。

2 多種屬性選取標準多數表決決策樹算法

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

算法：Gen_Multi_Sta_Dec_Tree由給定訓練數據集產生一棵多種屬性選取標準多數表決決策樹。

輸入：由離散屬性表示的訓練數據集S，和用于構建決策樹的候選屬性集合A。

輸出：一棵多種屬性選取標準多數表決決策樹。

步驟：

①采用ID3標準計算并比較各候選屬性的信息增益值，并使信息增益最大的候選屬性被選次數增一。

②采用C4.5標準計算并比較各候選屬性的信息增益率，并使信息增益率最大的候選屬性的被選次數增一。

③采用Gini_index標準計算并比較各候選屬性的純度增量，并使純度增量最大的候選屬性的被選次數增一。

④采用χ2統(tǒng)計標準計算并比較各候選屬性與類別屬性關聯程度，并使關聯程度最大的候選屬性的被選次數增一。

3 具體示例

本文給出了取自AllElectronics顧客數據庫數據元組訓練集（數據取自[Qui86]）如表2，對構建多決策判定樹過程如下：

表2 給出了取自AllElectronics顧客數據庫數據元組訓練集（數據取自[Qui86]）

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

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

圖1 根據age劃分樣本

圖2 根據由樣本集創(chuàng)建的決策樹

同樣對每個劃分的樣本集采用上述同樣的算法構建決策樹，最終得決策樹如圖2。

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

3 結束語

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

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

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

[3]Soman K P,Diwakar S,Ajay V.數據挖掘基礎教程[M].北京：機械工業(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]謝妞妞，劉於勛.決策樹屬性選擇標準的改進[J]．計算機工程與應用，2010，46（34）：115-118,139．

[7]喻金平，黃細妹，李康順.基于一種新的屬性選擇標準的ID3改進算法[J].計算機應用研究，2012，29（8）：2895-2898,2908．

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

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

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

[11]王小巍，蔣玉明.決策樹ID3算法的分析與改進[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 Anhui236037,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

安徽省科技攻關項目（5101031114）資助。

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