馬　源

(福州大學(xué) 物理與信息工程學(xué)院，福州　350108)

?

基于隨機(jī)化屬性選擇和決策樹(shù)的組合分類(lèi)器

馬源

(福州大學(xué) 物理與信息工程學(xué)院，福州350108)

摘要：針對(duì)決策樹(shù)泛化能力差，容易產(chǎn)生過(guò)擬合問(wèn)題，提出基于隨機(jī)化屬性選擇和決策樹(shù)組合分類(lèi)器。首先運(yùn)用隨機(jī)化鄰域?qū)傩约s減產(chǎn)生多個(gè)分類(lèi)較高的屬性子集；其次每個(gè)屬性子集作為分類(lèi)回歸樹(shù)(CART)的輸入，訓(xùn)練多個(gè)基分類(lèi)器；最后對(duì)得到的多個(gè)分類(lèi)精度結(jié)果進(jìn)行投票融合的方式獲得最后的分類(lèi)結(jié)果。實(shí)驗(yàn)表明，提出的隨機(jī)屬性選擇和決策樹(shù)集成算法有效性。

關(guān)鍵詞：過(guò)擬合；隨機(jī)化；決策樹(shù)；分類(lèi)器；融合

0引言

經(jīng)典粗糙集理論[1]是波蘭華沙理工大學(xué)教授Pawlak1982年，在研究不完整和不精確知識(shí)的表達(dá)時(shí)提出的。粗糙集有以下優(yōu)點(diǎn)：能夠客觀地挖掘出數(shù)據(jù)內(nèi)部的消息，也就是可以找到數(shù)據(jù)的本質(zhì)信息；可以將數(shù)據(jù)通過(guò)一定的原則進(jìn)行提煉，得到數(shù)據(jù)的內(nèi)涵信息。由于上述作用，粗糙集理論在數(shù)據(jù)挖掘中得到廣泛應(yīng)用，鄰域粗糙集[2]是為了解決經(jīng)典粗糙集便于處理數(shù)值型屬性的數(shù)據(jù)集合而提出的。鄰域粗糙集約減可以對(duì)樣本數(shù)據(jù)集進(jìn)行屬性選擇，選擇出分類(lèi)能力強(qiáng)的屬性，達(dá)到去噪和降維的功能，從而減少分類(lèi)計(jì)算復(fù)雜度，提高分類(lèi)效果。

決策樹(shù)[3]是一種非常適合數(shù)據(jù)挖掘的算法。相比較神經(jīng)網(wǎng)絡(luò)、貝葉斯、支持向量機(jī)等分類(lèi)器，其主要優(yōu)點(diǎn)是模型具有可解釋性，容易被人們所理解，且構(gòu)建速度快。同時(shí)決策樹(shù)生成算法不需要附加信息，例如數(shù)據(jù)和類(lèi)別分布的先驗(yàn)知識(shí)。然而其主要缺點(diǎn)是分類(lèi)結(jié)果準(zhǔn)確率不高，容易產(chǎn)生過(guò)擬合問(wèn)題，當(dāng)數(shù)據(jù)集中的屬性過(guò)多，用決策樹(shù)分類(lèi)容易出現(xiàn)結(jié)構(gòu)性差等問(wèn)題。

目前，數(shù)據(jù)挖掘主要的研究方向由單一的方法逐漸發(fā)展成為多種方法結(jié)合。粗糙集在化簡(jiǎn)訓(xùn)練樣本，消除冗余信息，處理大數(shù)據(jù)量的時(shí)候具有一定優(yōu)勢(shì)。但粗糙集分類(lèi)精度不高，往往結(jié)果不太穩(wěn)定。研究表明[4]粗糙集和決策樹(shù)具有很高的優(yōu)勢(shì)互補(bǔ)性，因此可以將兩者結(jié)合。在實(shí)際應(yīng)用中，粗糙集理論結(jié)合決策樹(shù)分類(lèi)器發(fā)揮兩者的優(yōu)越性，取得了較好的效果。

針對(duì)決策樹(shù)構(gòu)造中存在抗噪聲能力差、選擇最優(yōu)屬性困難的問(wèn)題，文獻(xiàn)[5]提出一種基于變精度粗糙集模型的決策樹(shù)構(gòu)建。文獻(xiàn)[6]提出一種鄰域粗糙集快速約減算法，從中選擇最大屬性重要度的屬性加入約減集合中，直到所有剩余屬性重要度為0，并將此應(yīng)用在CART分類(lèi)器上驗(yàn)證了該約減算法的可以提高分類(lèi)效果。然而實(shí)際數(shù)據(jù)中約減是種NP問(wèn)題，存在多個(gè)保持原始樣本數(shù)據(jù)具有區(qū)分能力的屬性子集，因此為了盡可能利用不同子空間的分類(lèi)能力，文獻(xiàn)[7]提出WADF方法和文獻(xiàn)[8]提出一種隨機(jī)屬性約減算法尋求多個(gè)約減。本文將鄰域粗糙集隨機(jī)屬性選擇與CART決策樹(shù)相結(jié)合，設(shè)計(jì)出一種集成學(xué)習(xí)分類(lèi)器。通過(guò)隨機(jī)化鄰域約減產(chǎn)生的多個(gè)約減，作為CART的輸入，最后對(duì)分類(lèi)結(jié)果進(jìn)行加權(quán)投票的方式融合不同的結(jié)果做出決策，提高泛化能力和減少過(guò)擬合問(wèn)題。從實(shí)驗(yàn)數(shù)據(jù)測(cè)試結(jié)果可以看出，本文提出方法的有效性。

1鄰域粗糙集模型基本概念

鄰域粗糙集模型不需要像經(jīng)典粗糙集事先要屬性離散化，它可以對(duì)數(shù)值形屬性直接處理，直接用于知識(shí)約減。下面介紹鄰域粗糙集模型相關(guān)概念[1]。

定理1給定實(shí)數(shù)空間Ω上的非空有限集合U={x1,x2,…xn}，對(duì)于?xi的鄰域δ定義為：δ(xi)={x|x∈U,Δ(x,xi)≤δ}，其中δ≥0，Δ(x,xi)為距離函數(shù)，表示x與xi之間的距離。常見(jiàn)的距離計(jì)算函數(shù)例如：曼哈頓距離函數(shù)、歐式距離函數(shù)等。

定理2假設(shè)有一鄰域決策系統(tǒng)NDS=(U,A,D)，其中U為全部樣本構(gòu)成的集合，A為樣本的屬性子集，D為分類(lèi)決策屬性。決策屬性D將U劃分為N個(gè)等價(jià)類(lèi)(x1,x2,…xN)，?B∈A，D關(guān)于B的上下近似定義為：

定理3決策屬性D對(duì)于條件屬性B的依賴度定義為：

其中PosB(D)為決策鄰域決策系統(tǒng)的下近似。

定理4屬性重要度定義為：條件屬性對(duì)決策屬性的影響程度，若屬性a∈B，那么條件屬性a對(duì)于決策屬性D的重要度公式為：

Sig(a,B,D)=γB(D)-γB-{a}(D)

定理5對(duì)于決策系統(tǒng)NDS=(U,A,D)，B∈A，a∈B，如果滿足：

(1)γB(D)=γA(D)

(2)?a∈B:γB-{a}(D)<γB(D)

則稱B是一個(gè)屬性約減。

2CART分類(lèi)算法

2.1CART分類(lèi)算法簡(jiǎn)介

CART是在給定輸入隨機(jī)變量X條件下輸出隨機(jī)變量Y的條件概率分布的方法，假設(shè)決策樹(shù)是二叉樹(shù)，內(nèi)部節(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹(shù)等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測(cè)的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。CART主要由決策樹(shù)生成和決策樹(shù)剪枝組成[9]。

2.2CART決策樹(shù)生成

CART決策樹(shù)的生成就是遞歸地構(gòu)建二叉決策樹(shù)的過(guò)程。構(gòu)建回歸樹(shù)和分類(lèi)樹(shù)采用不同的準(zhǔn)則，對(duì)回歸樹(shù)用平方誤差最小準(zhǔn)則，對(duì)分類(lèi)樹(shù)用基尼系數(shù)最小化準(zhǔn)則，進(jìn)行特征選擇，生成二叉樹(shù)。由于篇幅有限，只介紹分類(lèi)樹(shù)的生成。

分類(lèi)樹(shù)用基尼指數(shù)選擇最優(yōu)特征，基尼系數(shù)計(jì)算公式為：

其中，K為樣本類(lèi)的個(gè)數(shù)，pk為樣本點(diǎn)屬于第k類(lèi)的概率。

假設(shè)訓(xùn)練數(shù)據(jù)集為D，根據(jù)訓(xùn)練數(shù)據(jù)集，從根節(jié)點(diǎn)開(kāi)始，遞歸地對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建二叉決策樹(shù)：

1)計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的基尼系數(shù)，對(duì)于每個(gè)特征A，對(duì)其可能取的每個(gè)值a，根據(jù)樣本點(diǎn)對(duì)A=a的測(cè)試為“是”或“否”將D分割成D1和D2兩部分，計(jì)算A=a的基尼系數(shù)。

2)在所有可能的特征A以及它們所有可能的切分點(diǎn)a中，選擇基尼系數(shù)最小的特征極其對(duì)應(yīng)的切分點(diǎn)作為最有特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)節(jié)點(diǎn)生成兩個(gè)子節(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個(gè)子節(jié)點(diǎn)中去。

3)對(duì)2個(gè)子節(jié)點(diǎn)遞歸地調(diào)用1)和2)，直至滿足停止條件。

4)生成CART決策樹(shù)。

算法停止計(jì)算的條件是節(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閥值，或樣本集的基尼系數(shù)小于預(yù)定閥值，或者沒(méi)有更多特征。

2.3CART決策樹(shù)剪枝

當(dāng)決策樹(shù)生成時(shí)，需要從完全生長(zhǎng)的決策樹(shù)的底端剪去一些子樹(shù)，目的是為了使決策樹(shù)變小，模型變簡(jiǎn)單，減少過(guò)擬合問(wèn)題，從而能夠?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測(cè)。CART剪枝算法首先從生成算法產(chǎn)生的決策樹(shù)T0底端開(kāi)始不斷剪枝，知道T0的根節(jié)點(diǎn)，形成一個(gè)子樹(shù)序列{T0,T1,…,Tn}；然后通過(guò)交叉驗(yàn)證在獨(dú)立的驗(yàn)證數(shù)據(jù)集上對(duì)子樹(shù)序列進(jìn)行測(cè)試，從而選擇最優(yōu)子樹(shù)。CART剪枝算法如下：

1)設(shè)k=0，T=T0。

2)設(shè)a=+∞。

4)自上而下地訪問(wèn)內(nèi)部節(jié)點(diǎn)t，如果有g(shù)(t)=a，進(jìn)行剪枝，并對(duì)葉節(jié)點(diǎn)t以多數(shù)表決法決定其類(lèi)，得到樹(shù)T。

5)設(shè)k=k+1，ak=a，Tk=T。

6)如果T不是由根節(jié)點(diǎn)單獨(dú)構(gòu)成的樹(shù)，則回到步驟4)

7)采用交叉驗(yàn)證法在子樹(shù)序列T0,T1,…,Tn中選取最優(yōu)子樹(shù)Ta。

3基于隨機(jī)屬性選擇和決策樹(shù)的集成學(xué)習(xí)分類(lèi)器

3.1基本思想

本文提出的集成學(xué)習(xí)分類(lèi)器結(jié)構(gòu)圖如圖1所示。給定一個(gè)鄰域決策系統(tǒng)NDS=(U,A,D)，多次運(yùn)用鄰域隨機(jī)化屬性約減算法可以得到多個(gè)屬性約簡(jiǎn)子集(a1,a2,…an)，每個(gè)約減子集作為CART分類(lèi)器的輸入，采用十字交叉驗(yàn)證得到一組決策，最后對(duì)每組決策通過(guò)加權(quán)投票的方式最終可以得到每個(gè)樣本的類(lèi)標(biāo)號(hào)。

圖1　結(jié)構(gòu)圖Fig.1　Structure chart

3.2算法描述

本文提出的一種隨機(jī)屬性選擇和CART的集成學(xué)習(xí)分類(lèi)器，利用鄰域隨機(jī)化屬性產(chǎn)生多個(gè)約減的屬性子集，從而產(chǎn)生對(duì)樣本數(shù)據(jù)進(jìn)行特征選擇的多個(gè)子集，具體過(guò)程如算法1所示，然后利用CART進(jìn)行分類(lèi)學(xué)習(xí)。本文采用了10折交叉驗(yàn)證方法，在對(duì)每一個(gè)子集進(jìn)行分類(lèi)學(xué)習(xí)時(shí)，將該子集劃分為10等份，利用其中的9份作為訓(xùn)練集用于構(gòu)建一個(gè)CART分類(lèi)器，剩余的1份作為測(cè)試集進(jìn)行測(cè)試。在10折交叉驗(yàn)證之后，該子集將會(huì)產(chǎn)生一個(gè)決策輸出，同理對(duì)于剩下的子集采用同種方法，每個(gè)子集產(chǎn)生的決策輸出最后通過(guò)投票融合的方法最終決策輸出。具體算法如算法2。

算法1(基于鄰域粗糙集隨機(jī)化屬性約減)：

輸入：NDS=(U,A,D)，參數(shù)δ和隨機(jī)數(shù)N

輸出：約減reduce={a1,a2,…an}

1)屬性約減初始化reduce為空集

2)對(duì)任意的ai∈A-reduce計(jì)算屬性ai的重要度SIG(ai,reduce,D)

3)選擇ak，ak為屬性集{A-reduce}中重要度SIG(ai,reduce,D)前F個(gè)最大中的一個(gè)

4)如果SIG(ai,reduce,D)>0，則reduce∪ak→reduce

5)回到第二步

6)否則返回約減reduce，約減完成。

算法2(基于鄰域粗糙集隨機(jī)化屬性約減和決策樹(shù)的集成學(xué)習(xí))：

輸入：原始數(shù)據(jù)集通過(guò)約減的屬性集{a1,a2,…an}

輸出：驗(yàn)證集上的分類(lèi)正確率

步驟：

1)初始化

①讀入原始數(shù)據(jù)集{a1,a2,…an}

2)For(iin 1∶10)

①將原始數(shù)據(jù)集{a1,a2,…an}中的每個(gè)子集劃分成10等份

②在訓(xùn)練集上運(yùn)行CART創(chuàng)建分類(lèi)器

③在測(cè)試集上執(zhí)行分類(lèi)預(yù)測(cè)

3)對(duì)于每個(gè)子集的預(yù)測(cè)采用投票，輸出分類(lèi)正確率

3.3時(shí)間復(fù)雜度分析

鄰域隨機(jī)屬性約減在選定隨機(jī)數(shù)F后，每次運(yùn)行即可以得到1個(gè)隨機(jī)化約減。這個(gè)算法的時(shí)間復(fù)雜度為(2n-k)(k+1)×(k+1)×mlogm/2，其中n和m分別為樣本和特征的數(shù)據(jù)，k為約減中屬性的個(gè)數(shù)。約減后的各個(gè)屬性子集作為CART分類(lèi)器的輸入，設(shè)約減后的數(shù)據(jù)集維數(shù)為m*，訓(xùn)練樣本個(gè)數(shù)為n*。在構(gòu)建CART樹(shù)的過(guò)程中，訓(xùn)練1個(gè)不進(jìn)行剪枝的樹(shù)，訓(xùn)練每一個(gè)基分類(lèi)器的計(jì)算時(shí)間小于O(m*n*(logn*)2)，對(duì)于k個(gè)基分類(lèi)器的時(shí)間復(fù)雜度近似為O(km*n*(logn*)2)，本實(shí)驗(yàn)采用10折交叉驗(yàn)證，需運(yùn)行CART算法10次，最終k個(gè)基分類(lèi)器的時(shí)間復(fù)雜度約為10×O(km*n*(logn*)2)。

在進(jìn)行實(shí)驗(yàn)時(shí)，我們?cè)O(shè)置運(yùn)行隨機(jī)屬性約減算法10次，這樣將會(huì)產(chǎn)生10個(gè)約減結(jié)果，然后利用CART分類(lèi)器學(xué)習(xí)。實(shí)驗(yàn)表明，提出的集成學(xué)習(xí)運(yùn)行時(shí)間上是可以接受的，算法具有較好的擴(kuò)展性。

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

4.1實(shí)驗(yàn)數(shù)據(jù)與方法

從UCI數(shù)據(jù)庫(kù)中下載4個(gè)數(shù)據(jù)集，分別是zoo、heart 、wdbc、soy、wine、wpbc數(shù)據(jù)集描述如表1所示。算法采用matlab2014a實(shí)現(xiàn)

表1　數(shù)據(jù)描述

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

在分類(lèi)學(xué)習(xí)之前對(duì)數(shù)據(jù)進(jìn)行了預(yù)處理，首先剔除缺省值和無(wú)關(guān)屬性，然后歸一化處理，使得每個(gè)屬性的取值在[0,1]之間。本文提出的設(shè)計(jì)方法分類(lèi)精度如表2所示。

表2　提出方法的分類(lèi)精度

為了進(jìn)一步說(shuō)明本設(shè)計(jì)的優(yōu)越性，比較本文提出的設(shè)計(jì)方法和基于快速約減的貪心算法的CART、使用原始特征的CART的分類(lèi)精度，比較結(jié)果如圖2所示。3種分類(lèi)方法在6個(gè)不同數(shù)據(jù)集分類(lèi)準(zhǔn)確度的平均值柱狀圖如圖3所示。

圖2　3種分類(lèi)方法比較Fig.2　Comparison of classification among three methods

圖3　3種分類(lèi)方法平均值比較Fig.3　Comparison of average classification among three methods

從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)提出基于隨機(jī)屬性選擇和決策樹(shù)的組合分類(lèi)器可以較大的提高CART分類(lèi)器的準(zhǔn)確度，準(zhǔn)確度優(yōu)于基于快速約減的貪心算法的CART分類(lèi)器。從繪出的分類(lèi)曲線可以看出，快速貪心約減算法并不完全可以使CART分類(lèi)效果提高，在有些數(shù)據(jù)集上分類(lèi)效果差于直接使用原始數(shù)據(jù)集的CART。從平均值柱狀圖可以看出，提出的方法在6個(gè)數(shù)據(jù)集的平均準(zhǔn)確度相比較直接使用原始數(shù)據(jù)集的CART提高了4.93%，比基于快速約減算法的CART提高了4.95%。

5結(jié)語(yǔ)

目前CART決策樹(shù)分類(lèi)穩(wěn)定性差，易產(chǎn)生過(guò)擬合，分類(lèi)精度有待提高。本文提出的基于隨機(jī)屬性選擇和決策樹(shù)的組合分類(lèi)器，首先利用鄰域粗糙集的隨機(jī)屬性選擇方法，得到多個(gè)保持原始樣本數(shù)據(jù)具有區(qū)分能力的屬性子集，在不同屬性集上分別構(gòu)建CART決策樹(shù)，最后通過(guò)加權(quán)融合的方法得到判決。通過(guò)實(shí)驗(yàn)結(jié)果表明可以較大改善CART分類(lèi)器準(zhǔn)確度不高和過(guò)擬合問(wèn)題，以后將使用此方法應(yīng)用到實(shí)際數(shù)據(jù)中。

參考文獻(xiàn)：

[1] 楊啟賢.粗糙集及其應(yīng)用簡(jiǎn)介[J].貴州師范大學(xué)學(xué)報(bào)(自然科學(xué)版),1988,6(2):4-9.

[2] HU Q,YU D,XIE Z.Neighborhood classifiers[J]. Expert Systems with Applications,2008,34(2):866-876.

[3] PONKIYA P.A Review on Tree Based Incremental Classification[J].International Journal of Computer Science and Information Technologies,2014,5(1):306-309.

[4] PAL P,MOTWANI D.The Based on Rough Set Theory Development of Decision Tree after Redundant Dimensional Reduction[C]// Advanced Computing & Communication Technologies (ACCT), 2015 Fifth International Conference on IEEE, 2015:278-282.

[5] WANG F.Improved Algorithm of Decision Trees Construction Based on Variable Precision Rough Set[J].Computer & Digital Engineering, 2013，41(3):337-339.

[6] 胡清華,于達(dá)仁,謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡(jiǎn)[J].軟件學(xué)報(bào),2008,19(3):640-64.

[7] WU Q X,BELL D,MCGINNITY M.Multiknowledge for decision making[J].Knowledge & Information Systems, 2005,7(2):246-266.

[8] 朱鵬飛,胡清華,于達(dá)仁.基于隨機(jī)化屬性選擇和鄰域覆蓋約簡(jiǎn)的集成學(xué)習(xí)[J].電子學(xué)報(bào),2012,40(2):273-279.

[9] 李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,2012:67-73.

文章編號(hào)：1004—5570(2016)01-0098-05

收稿日期：2015-08-12

作者簡(jiǎn)介：馬源(1991-)，男，碩士研究生，研究方向：數(shù)據(jù)挖掘，圖像處理與通信，E-mail：251394667@qq.com.

中圖分類(lèi)號(hào)：TP391.4

文獻(xiàn)標(biāo)識(shí)碼：A

Ensemble classifier based on randomized attribute selection and decision tree

MA Yuan

(Institute of Physics and Information Engineering,Fuzhou University,Fuzhou,Fujian 350108,China)

Abstract:Aiming at the problems of poor generalization ability and easy to overfitting in decision tree.We introduce an ensemble classifier based on randomized attribute selection and combination of decision tree.Firstly,multiple subsets with higher accuracy are produced by use of randomization adjacent attribute reduction;Secondly each attribute subset as classification and regression tree’s input;Finally the final classification result is obtained by multiple classification results fusion.The experiment result shows that the proposed random attribute selection and decision tree integration algorithm is effective.

Key words:overfitting；randomization;decision tree;classifier; fusion