集成學習思想預擬合分類算法

張 躍,趙 佳,胡 明

(長春工業大學 計算機科學與工程學院，吉林 長春 130012)

0 引 言

隨著大數據技術的發展，大數據時代已經到來[1-3]。而大數據的分類一直是大數據研究的熱點問題[4-6]，常用的分類算法有：樸素貝葉斯(naive bayes)、支持向量機(SVM)、k-近鄰算法(KNN)、神經網絡(ANN)和決策樹，其中決策樹憑借結構簡單、計算復雜度低、對數據缺值不敏感等優點被廣泛應用。它主要依靠每個節點上的屬性對劃分到該節點中的樣本集合進行繼續劃分，最終落到對應各個決策結果的葉子節點中。即每一個決策樹的根節點都包含了所有的樣本，每個葉子結點對應著一個類別。但是傳統的決策樹也有不足之處，主要由于其過于簡單，容易發生過擬合，以及不容易感知到特征之間的相互關聯，各屬性樣本數量的平衡情況也會嚴重影響其分類效果，且判定特征的準則會對結果產生很大影響。

隨機森林就是為了解決其中容易過擬合的問題，在2001年被LeoBreiman提出[7]。通過將多個決策樹進行有機結合，改變了之前生成決策樹時固定的選擇樣本方式，通過隨機采樣方法從原始數據樣本集中選擇多個特征樣本，即有放回的抽取樣本構建一個樣本子集，再使用多個由樣本子集構建的決策樹分別進行分類，最后將分類結果進行融合。

目前，已經有許多研究者在此基礎上進行了改進[8-11]。文獻[9]提出使用MapReduce將過采樣、欠采樣和對成本敏感的學習應用于大數據，以便這些技術能夠管理所需的、盡可能大的數據集，從而正確識別樣本代表性不足的類別，但是對于直接處理樣本代表性不平衡的數據和對特征較少的情況并未多作考慮；文獻[12]提出文中一種在65 nm CMOS中的隨機森林(RF)機器學習分類器的集成電路(IC)實現。通過利用源自RF分類器整體性質的固有錯誤恢復能力，對算法、體系結構和電路進行了共同優化，以實現積極的能量和延遲優勢。確定性子采樣(DSS)和泛化決策樹降低了互連復雜性，并避免了不規則的內存訪問模式和計算，最終降低了能量延遲積(EDP);文獻[13]提出使用隨機森林(RF)技術來搜索與糖尿病相關的最重要屬性(SNP)。通過使用RF獲得的屬性相關性用于根據屬性與RF的相關性在相似性度量中使用k最近鄰加權方法對屬性進行預測;文獻[14]引入相似度矩陣，使用有關交互對的直接和間接信息從訓練集中構造一個隨機森林(決策樹的集合)。生成的森林用于確定蛋白質對之間的相似性，再使用這種相似性對蛋白質對進行分類，但是算法的時間復雜度較高。

針對以上問題，文中提出一種基于集成的學習器和深度學習的分類方法，分為預擬合階段和泛化擬合兩個階段:

1)預擬合階段。借助神經網絡強大的提煉效果，進行簡單的初步擬合，并將特征進行融合提煉。

2)泛化擬合階段。利用增強模型泛化能力的隨機森林算法進一步擬合，最終得到一個更加具有魯棒性和泛化能力的分類模型。

實驗結果表明，PF-RF算法能夠有效擬合特征，準確進行分類，最終得到更好的分類效果，且可以感知到特征之間的相互關聯，對平衡數據也有更好的效果。

1 理論基礎

定義1屬性間的信息熵

(1)

為當前樣本集合，pk(k=1,2,…,|y|)為當前樣本種類k所占比例，信息熵越小，樣本集合的純度就越高。然后對于信息熵有下面的信息增益指標。

定義2信息增益

(2)

式中：a----離散屬性的V個可能取值{a1,a2,…,an}，信息增益越大,代表屬性a對樣本進行分類后的樣本純度越有提升。

定義3增益率

(3)

定義4基尼指數

(4)

計算數據集純度的另一種方式，其中

2 決策樹和隨機森林算法基本思想

傳統的決策樹思想：一棵決策樹包含一個根結點、若干個內部結點和若干個葉結點，葉結點對應于決策結果，其他每個結點都對應一個屬性測試每個結點包含的樣本集合,根據屬性測試結果被劃分到子結點中，根結點包含樣本全集從根結點到每個葉節點的路徑對應一個判定測試序列,決策樹學習的目的是產生一棵泛化能力強的決策樹。

而隨機森林是多個決策樹的一種有機結合，改變了之前生成決策樹時固定的選擇樣本方式，通過隨機采樣方法從原始數據樣本集中選擇多個特征樣本，即有放回地抽取樣本構建一個樣本子集，再使用多個由樣本子集構建的決策樹分別進行分類，最終將分類結果進行融合。

傳統的隨機森林算法訓練過程如下:

輸入：數據集D={(X1,Y1),(X2,Y2),…,(Xm,Ym)}，屬性集A={a1,a2,…,ad}。

輸出：多個以node為節點的決策樹組成的森林。

1)如果D中樣本全屬于同一類別C，將node標記為C類葉節點；

2)如果A不為空或者D中樣本在A上取值相同，將node節點標記為葉節點；

3)從A中選擇最優的劃分屬性a*；

4)遍歷a*的每一個值，將分支節點標記為葉節點，其類別標記為D中樣本最多的類；

5)得到一個以node為根節點的一顆決策樹；

6)重復上面步驟，生成t個決策樹，對于每個新的測試樣例，綜合多個決策樹的分類結果作為隨機森林的分類結果。

3 基于改進隨機森林算法的預測

傳統的Random Forest算法僅僅是多個決策樹的集成。通過分析發現，其容易發生過擬合，以及不容易感知到特征之間的相互關聯，樣本代表性不平衡的數據也會嚴重影響其分類效果，且判定特征的準則會對結果產生很大影響。

文中提出的算法首先將數據通過適度的矩陣計算進行預擬合，同時也將特征之間的相互關聯融入特征，得到一個提煉過的高級特征，然后再通過隨機森林進一步地泛化擬合，并在生成之后進行剪枝，最終得到一個較高魯棒性的分類結果。

這樣處理方式的優勢在于一方面彌補了隨機森林在小樣本時易過擬合的缺陷，使模型對于特征間關系可以有所考量;另一方面對數據進行一個預擬合能夠降低算法的迭代次數，最重要的是可以在處理小樣本數據時,對噪聲數據有更好的抗性，且對不平衡的樣本取得較好的分類效果。

PF-RF算法描述如下:

輸入：數據集D={X1,X2,…,Xn,…,Xm},每個對象有特征集合x={a1,a2,…,ad}。

輸出：訓練集中每個對象對應的類別

C={y1,y2,…,ym}。

1)從數據集

D={X1,X2,…,Xn,…,Xm}

中取出每一個對象，從數據集中逐個取一個數據點，放入預擬合層進行處理。

2)進行逐層矩陣計算

φi=f(Wiφi-1+Bi)。

3)重復步驟2)，最后通過全連接層得到一個萃取后的特征

4)將處理后的數據集

再次放入集成擬合區。

5)集成區中每個基分類器中的每個節點通過其屬性

對D′進行劃分。

6)重復步驟5)，達到最后的結點時，通過投票算法得到最終結果。

4 實 驗

4.1 實驗描述

4.1.1 硬件

主頻為3.40 GHz的CPU，16 G內存和GTX970顯卡。

4.1.2 軟件

使用64位Windows操作系統，基于Tensorflow框架進行計算。

4.1.3 概述

為了測試算法的性能，文中選取UCI機器學習數據庫中的LETTER[15-16]數據集作為實驗數據進行測試。將提出的PF-RF算法與Random Forest算法進行以下性能的對比分析:

1)分類結果的準確率方面;

2)小數量樣本下的分類準確率;

3)算法的運行時間。

4.2 結果及分析

文中將兩種算法分別運行10次。LETTER數據集中有20 000條數據，每條數據包含16個屬性，數據集分為26類。將兩種算法在準確率方面進行對比，在LETTER數據集上的測試結果見表1。

從表1可以清楚地看到，Random Forest算法的準確率最高為95.07%，最低為91.45%，平均值為93.68%，準確率的范圍波動較大，這也是由于Random Forest算法在生成時選取樣本和節點屬性時采用隨機選取的方法，生成后也沒有進行有效的剪枝操作。當出現抽取樣本類別不平衡時，會出現準確性波動大的情況，且當同一類別樣本多次被選取時，容易導致分類結果的準確性較低。而文中提出的PF-RF算法準確率最高為96.63%，最低為95.26%，平均值為95.87%。PF-RF算法在準確率方面總體高于Random Forest算法，說明提出的PF-RF算法較為合理，得到的分類結果也更為準確。

表1 預測準確度 %

兩個算法在較低數量的LETTER數據集上運行時的表現如圖1所示。

圖1 算法準確度和數據量的關系

從圖1可以看出，在樣本較少時，傳統隨機森林的分類準確性波動較大，這是因為隨機抽樣時抽到少量噪聲樣本的時候，噪聲樣本占全部訓練樣本的比例會比較大。再加上最終類別較多，導致其更加不穩定，所以波動幅度很大。而改進后的PF-RF算法在樣本較少時，雖然準確度也受到很大影響，但是總體保持穩定,且提出的PF-RF算法在多分類時相比原始算法有一定的提升。這是因為改進后的算法有預擬合操作，同時也會進行剪枝，避免過度生長，最終表現出比傳統算法更好的魯棒性。

從LETTER的20 000條數據中隨機選取多個數量的數據對算法的運行時間進行比較。兩種算法的運行時間和數據量的關系如圖2所示。

圖2 算法運行時間和數據量的關系

在數據量較低時，PF-RF算法的運行時間略高于Random Forest算法。隨著數據量的增加，Random Forest算法運行時間的增長趨勢非常明顯，而PR-RF算法的運行時間增長相對平緩。導致這樣的原因是Random Forest算法沒有剪枝處理，數據規模地增長會導致它的執行時間也隨之大幅增長。相對而言，PF-RF算法的執行時間雖然也呈增長趨勢，但是相對Random Forest算法增長幅度緩慢許多。總體看來，PF-RF算法的運行時間優于原始算法。這是因為在生成森林之后會有剪枝操作，且處理的是已經預擬合之后的特征。

5 結 語

研究基于初始聚類中心的優化算法PF-RF，采用預擬合的隨機森林進行分類,有效地解決了原始算法在小樣本集時有時會過擬合的表現，并且算法中加入了剪枝步驟，有效解決了算法在多分類中容易過度增長的缺陷。文中所提到的泛化擬合層中的基學習器個數，它的取值是一個開放性問題，需要根據具體的基學習器種類和數據集的特點進行設定。對于使用決策樹作為基學習器時個數t的選定，以及其他基學習器的使用將是進一步的研究內容。