劉 毓, 劉 陸, 高 尹, 楊 柳

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

隨機(jī)森林算法[1]具有較低泛化誤差和較好收斂性，可解決決策樹(shù)的局部最優(yōu)解和過(guò)度擬合問(wèn)題，已成為數(shù)據(jù)分析、圖像處理、知識(shí)管理等眾多領(lǐng)域的研究熱點(diǎn)之一。

隨機(jī)森林算法的基分類器為決策樹(shù)[2]，改進(jìn)單個(gè)基分類器的分類準(zhǔn)確率可以提高整個(gè)隨機(jī)森林算法的分類準(zhǔn)確率。通過(guò)遺傳算法尋找參數(shù)最優(yōu)組合的方法，提高了算法的分類性能，但算法的收斂速度依賴于初值設(shè)定[3-4]。給抽樣結(jié)果增加約束條件，非平衡數(shù)據(jù)的分類性能有所提高，但是算法訓(xùn)練速度較慢[5]。采用決策協(xié)調(diào)度作為劃分規(guī)則分裂節(jié)點(diǎn)，根據(jù)條件屬性與目標(biāo)屬性等價(jià)類模的比值衡量該屬性的分類能力，雖然基分類器的性能有一定的提升，但仍然存在模糊問(wèn)題[6]。因此，針對(duì)上述問(wèn)題，本文以決策協(xié)調(diào)度為基礎(chǔ)，從條件屬性與目標(biāo)屬性間的邏輯關(guān)系入手，引入粗糙集理論[7]中屬性相容性[8]，以條件屬性的相容度作為基分類器分裂節(jié)點(diǎn)的準(zhǔn)則，用寬相容度輔助嚴(yán)相容度構(gòu)建基分類器，以期提高基分類性能，進(jìn)而改善隨機(jī)森林算法性能。

1 隨機(jī)森林算法基本原理

隨機(jī)森林算法根據(jù)Bagging抽樣模型[9]，采用有放回的隨機(jī)采樣方式進(jìn)行采樣，生成K個(gè)子訓(xùn)練集，再?gòu)拿總€(gè)子訓(xùn)練集的所有屬性中選取特征子空間[10]。特征子空間的大小影響了隨機(jī)性的引入程度，一般取值為 log2M+1，M為特征總數(shù)。將選取特征子空間后的K個(gè)子訓(xùn)練集建立K個(gè)基分類器，從而形成隨機(jī)森林，如圖1所示。每個(gè)基分類器任其生長(zhǎng)，不需要剪枝[11]?；诸惼饕话悴捎肐D3[12]或C4.5[13]算法。當(dāng)輸入測(cè)試樣本時(shí)，隨機(jī)森林輸出的分類結(jié)果由每個(gè)基分類器的輸出結(jié)果進(jìn)行簡(jiǎn)單投票決定。

圖1 隨機(jī)森林示意圖

設(shè)隨機(jī)森林模型為{h(X,θk),k=1,2,…,K}，其中，h(·)為單個(gè)基分類器，K為基分類器的總個(gè)數(shù)，X為樣本條件屬性集，θk為基分類器參數(shù)。樣本集為T={(xi,yi):xi∈X,yi∈Y,i=1,2,…,N}，其中N為樣本容量，Y為決策屬性。

輸入樣本X對(duì)應(yīng)的正確分類結(jié)果Y的得票數(shù)，超過(guò)其他錯(cuò)誤分類別中得票數(shù)最多者的程度可用余量函數(shù)表示為

(1)

其中，I(·)為指示函數(shù)，當(dāng)·為真時(shí)，取值為1;當(dāng)·為假時(shí)，取值為0。

根據(jù)隨機(jī)森林投票的特點(diǎn)，對(duì)給定樣本分類的錯(cuò)誤率的度量，利用泛化誤差[14]表示為

e=P[m(X,Y)<0]。

(2)

其中，P(·)為概率質(zhì)量函數(shù)。

式(2)結(jié)合Hoeffding不等式[15]與Chebyshev不等式[16]，得到隨機(jī)森林的泛化誤差界[13]

(3)

2 屬性相容度基礎(chǔ)理論

對(duì)于基分類器偏向選擇多值屬性的問(wèn)題，可根據(jù)屬性相容度進(jìn)行改進(jìn)，屬性相容度以決策協(xié)調(diào)度為基礎(chǔ)。

2.1 信息系統(tǒng)

決策表{U,A∪D,V,f}為一個(gè)信息系統(tǒng)[17]，其中U為全部對(duì)象的集合，為論域；A為條件屬性集合；D為目標(biāo)屬性集合；V=∪a∈AVa是屬性a的值域，即條件屬性所有取值的集合；f:U×A→V為信息函數(shù)，它的作用是將U中所有對(duì)象的每個(gè)元素都映射為屬性值，即?a∈A,x∈U,f(x,a)∈Va。

2.2 等價(jià)關(guān)系與不可區(qū)分關(guān)系

信息系統(tǒng)可以簡(jiǎn)化表示為(U,R)，R為等價(jià)關(guān)系[18]，一個(gè)屬性可以作為一個(gè)等價(jià)關(guān)系，信息系統(tǒng)可以看作是一個(gè)等價(jià)關(guān)系族。U/R表示一個(gè)等價(jià)類集，即所有元素在等價(jià)關(guān)系構(gòu)成的集合。

設(shè)存在非空等價(jià)關(guān)系Z，Z是等價(jià)關(guān)系R的子集，各個(gè)子集Z的交集也是等價(jià)關(guān)系，此關(guān)系為不可區(qū)分關(guān)系，用O(Z)表示。在O(Z)下的等價(jià)類是信息系統(tǒng)中最小的單元。

2.3 決策協(xié)調(diào)度

等價(jià)類U/(A,D)表示條件屬性集與目標(biāo)屬性集的交集，它的模用|A∪D|表示，作為一個(gè)測(cè)度顯示A→D的邏輯關(guān)系強(qiáng)弱，也是決策規(guī)則出現(xiàn)的次數(shù)，即頻度。決策協(xié)調(diào)度[17]的表達(dá)式為

(4)

其中，X是A的非空屬性子集，|·|是求模運(yùn)算。

屬性決策協(xié)調(diào)度的值越大，則表示該屬性重要程度越高。

3 基于屬性相容度的改進(jìn)算法

隨機(jī)森林的性能取決于基分類器性能，基分類器的性能越高，隨機(jī)森林的性能越強(qiáng)。改進(jìn)算法以決策協(xié)調(diào)度為基礎(chǔ)，從隨機(jī)森林的基分類器入手。決策協(xié)調(diào)度只在宏觀上做了處理，各個(gè)決策規(guī)則在相容關(guān)系上還有待提高，當(dāng)各個(gè)條件屬性間的協(xié)調(diào)度距離較小時(shí)，決策依據(jù)不足。因此，需先計(jì)算主決策集與次決策集，再構(gòu)建屬性相容度[18]，利用屬性相容度作為劃分規(guī)則。

3.1 主決策集與次決策集

設(shè)在決策表中存在條件屬性集C∈A,O(C)={c1,c2,…,cm}與決策屬性集D，O(D)={d1,d2,…,dL}，則在O(C,D)中，與決策規(guī)則C→di矛盾的集合是∪i≠jC→dj。依次對(duì)O(C,D)下的集合求模運(yùn)算，模值最大集合為主決策集，記作W；模值次大的集合為次決策集，記作B。

3.2 屬性相容度

設(shè)主決策集的模為|W|，次決策集的模為|B|，定義屬性相容度的表達(dá)式為

(5)

其中，X為C的非空子集。B對(duì)W的影響為嚴(yán)相容度。

W與B間呈矛盾關(guān)系。當(dāng)|W|與|B|的值相等時(shí)，將式(5)中次決策集舍去，屬性相容度又可表示為

(6)

將次決策集舍去，只考慮主決策集的影響，則為寬相容度。

在比較屬性相容度時(shí)，若嚴(yán)相容度相同且同為最大值，則需要進(jìn)一步計(jì)算寬相容度并進(jìn)行比較，從而將條件屬性的性能嚴(yán)格區(qū)分。屬性相容度也可以用決策規(guī)則出現(xiàn)的概率度量該規(guī)則邏輯關(guān)系的強(qiáng)弱，概率值越大，表示該條件屬性與目標(biāo)屬性間的邏輯關(guān)系就越強(qiáng)，則該屬性就越重要。主決策集與次決策集的定義都是與一個(gè)條件屬性下的某個(gè)決策規(guī)則出現(xiàn)的頻度有關(guān)。然而，這兩個(gè)決策相互矛盾。在度量條件屬性與目標(biāo)屬性邏輯關(guān)系強(qiáng)弱時(shí)，有必要將矛盾的規(guī)則剔除或是計(jì)算兩者之差。對(duì)于一個(gè)條件屬性而言，屬性相容度越大，決策規(guī)則邏輯關(guān)系越強(qiáng)，分類能力越好。

3.3 改進(jìn)算法步驟

通過(guò)嚴(yán)相容度與寬相容度的計(jì)算，能夠區(qū)分不同條件屬性，從而提高基分類器的分類能力。通過(guò)嚴(yán)相容度計(jì)算條件屬性的分類能力就可以選擇分裂節(jié)點(diǎn)。在特殊情況下，會(huì)出現(xiàn)條件屬性嚴(yán)相容度相同的情形，且這些條件屬性的相容度都大于其他條件屬性相容度，此時(shí)計(jì)算寬相容度可將其區(qū)分。

算法的具體步驟如下。

步驟1 采用有放回的隨機(jī)采樣方式進(jìn)行訓(xùn)練集采樣，生成K個(gè)子訓(xùn)練集。

步驟2 取出1個(gè)子訓(xùn)練集，對(duì)該子集選取特征子空間，以此作為1個(gè)基分類器的訓(xùn)練集。

步驟3 基分類器訓(xùn)練開(kāi)始，對(duì)訓(xùn)練集的數(shù)據(jù)初始化操作，將所有條件屬性進(jìn)行標(biāo)記。

步驟4 分別計(jì)算出各個(gè)條件屬性的主決策集的模值與次決策集的模值。

步驟5 利用式(5)計(jì)算所有條件屬性的相容度。若存在兩個(gè)的屬性相容度的值近似且為最大值，則利用式(6)進(jìn)行計(jì)算。

步驟6 選出分類性能最強(qiáng)的條件屬性，并將該屬性的標(biāo)記去除，將該屬性作為分裂節(jié)點(diǎn)加入生成模型來(lái)分隔樣本集。

步驟7 重復(fù)步驟5和步驟6，直到所有屬性都去除標(biāo)記或達(dá)到葉子節(jié)點(diǎn)。

步驟8 生成并存儲(chǔ)該基分類器模型。

步驟9 重復(fù)步驟2～步驟8，直至K個(gè)基分類器全部生成完畢，結(jié)束。

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

4.1 數(shù)據(jù)集選取

選取UCI公開(kāi)數(shù)據(jù)集[19]中的Monks數(shù)據(jù)集、House-votes-84數(shù)據(jù)集、Credit-A數(shù)據(jù)集、Tic-tac-toe數(shù)據(jù)集和Kr-vs-kp數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。其中，Monks數(shù)據(jù)集的樣本數(shù)為432個(gè)，條件屬性個(gè)數(shù)為6個(gè)。House-votes-84數(shù)據(jù)集的樣本數(shù)為435個(gè)，條件屬性個(gè)數(shù)為16個(gè)。Credit-A數(shù)據(jù)集的樣本數(shù)為690個(gè)，條件屬性個(gè)數(shù)為15個(gè)。Tic-tac-toe數(shù)據(jù)集的樣本數(shù)為958個(gè)，條件屬性個(gè)數(shù)為9個(gè)。Kr-vs-kp數(shù)據(jù)集的樣本數(shù)為3 196個(gè)，條件屬性個(gè)數(shù)為36個(gè)。以上5個(gè)數(shù)據(jù)集所有屬性的取值均為離散值。

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

實(shí)驗(yàn)運(yùn)行環(huán)境為中央處理器Intel (R) Core (TM) i3-3217U,主頻1.8 GHz,內(nèi)存4 GB的PC機(jī), Win7 64位操作系統(tǒng), Matlab版本9.0 (R2016b)。根據(jù)上述5種數(shù)據(jù)集，分別對(duì)比改進(jìn)算法、隨機(jī)森林算法[1]與文獻(xiàn)[5]算法的準(zhǔn)確率和運(yùn)行時(shí)間，準(zhǔn)確率對(duì)比結(jié)果如表1所示，運(yùn)行時(shí)間對(duì)比結(jié)果如表2所示。

表1 準(zhǔn)確率對(duì)比結(jié)果/%

從表1可以看出，改進(jìn)算法對(duì)5種數(shù)據(jù)集的決策準(zhǔn)確率均高于其他兩種算法。在Monks數(shù)據(jù)集上，改進(jìn)算法提高了近11%，比文獻(xiàn)[5]算法提高了3.2%；在House-votes-84數(shù)據(jù)集上，改進(jìn)算法提高5.5%，比文獻(xiàn)[5]算法提高了2.7%。表明在訓(xùn)練數(shù)據(jù)量較少時(shí)，改進(jìn)算法有明顯的優(yōu)勢(shì)。這是由于改進(jìn)算法充分利用了條件屬性與目標(biāo)屬性的邏輯關(guān)系，采用屬性的相容度作為分裂節(jié)點(diǎn)判決依據(jù)，從而得到更高的準(zhǔn)確率。對(duì)于大數(shù)據(jù)集，改進(jìn)算法的準(zhǔn)確率也有所提高。

表2 運(yùn)行時(shí)間對(duì)比結(jié)果/s

從表2可以看出，改進(jìn)算法的計(jì)算復(fù)雜度均低于其它兩種算法。改進(jìn)算法繼承了隨機(jī)森林處理高維數(shù)據(jù)、特征遺失數(shù)據(jù)和不平衡數(shù)據(jù)的優(yōu)點(diǎn)。

除了準(zhǔn)確率外，查準(zhǔn)率、查全率以及綜合分類率以也是衡量算法性能的重要指標(biāo)[20]。計(jì)算以上性能指標(biāo)需要將樣例的真實(shí)類別與預(yù)測(cè)類別的組合劃分為真正例、假正例、真反例和假反例等4種情形[21]。

以Monks數(shù)據(jù)為例，3種算法對(duì)真實(shí)類別與預(yù)測(cè)類別組合劃分的統(tǒng)計(jì)結(jié)果如表3所示。

表3 3種算法統(tǒng)計(jì)結(jié)果

真正例與假反例的數(shù)量越多，算法的性能越好，從表3中可以看出不同算法分類結(jié)果的個(gè)數(shù)。但僅憑個(gè)數(shù)，無(wú)法準(zhǔn)確描述算法的優(yōu)劣，還需要進(jìn)一步對(duì)比查準(zhǔn)率、查全率和綜合分類率等3種性能，結(jié)果如表4所示。

表4 3種算法性能對(duì)比結(jié)

從表4可以看出，改進(jìn)算法綜合性能最好，在查準(zhǔn)率保持一定的情況下，查全率得到很大的提升，95%有用信息被留下。對(duì)于處理海量數(shù)據(jù)時(shí)，引入粗糙集的改進(jìn)隨機(jī)森林算法只需要計(jì)算各個(gè)等價(jià)類交集的模值，省去大量對(duì)數(shù)運(yùn)算，降低計(jì)算的復(fù)雜度，提高訓(xùn)練速度，從而提高學(xué)習(xí)效率。

5 結(jié)語(yǔ)

基于屬性相容度的隨機(jī)森林算法，重新構(gòu)建了用以度量條件屬性的重要程度數(shù)學(xué)表達(dá)式，引入了屬性相容性，并用屬性的相容度代替?zhèn)鹘y(tǒng)算法中的信息增益作為新的劃分規(guī)則，從而提高了基分類性能，改善了隨機(jī)森林算法性能。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法對(duì)數(shù)據(jù)量較少時(shí)具有更高的準(zhǔn)確率，并且弱化了多值偏向問(wèn)題，此外也不需要進(jìn)行對(duì)數(shù)運(yùn)算；在處理海量數(shù)據(jù)時(shí)，具有更快的訓(xùn)練速度。改進(jìn)算法在繼承了隨機(jī)森林優(yōu)點(diǎn)的前提下，不僅提高了預(yù)測(cè)準(zhǔn)確率而且降低了計(jì)算復(fù)雜度。