【競賽】一種提升多分類準確性的Trick
- 2020 年 3 月 13 日
- 筆記
本文是我之前做多分類比賽常用的一種trick, 如果碰到多分類問題時，不妨自己試試看，該方案在之前的螞蟻定位等多分類競賽中都帶來了不錯的提升。我在很多開源的數據集上也做了實驗，基本90%的數據集都可以在原始單個模型的基礎上帶來或多或少的提升。
1 用於多分類問題的KNN修正的隨機森林
1.1 摘要
隨機森林是一種高效並且可擴展性較好的演算法, K最近鄰演算法則是一種簡單並且可解釋較強的非參數化演算法。在本篇文章中,我們針對多分類問題提出了一種將隨機森林和KNN演算法相結合框架,我們先用訓練數據對隨機森林模型進行訓練然後用訓練好的隨機森林模型對我們的訓練集和測試集進行預測分別得到訓練集和測試集的概率矩陣,然後將測試集中的可疑樣本取出並在概率空間中進行KNN訓練測試,我們的框架很大地提升了測試集中可疑樣本的預測準確率;此外我們從預測的概率空間對訓練數據進行噪音的過濾與刪除,從而進一步提升了我們模型的預測準確率。在大量實驗數據的測試中,我們的方法都取得了非常顯著的效果。
1.2 簡介
隨著機器學習和數據挖掘技術的發展,機器學習和大數據處理在許多領域已經變得愈加重要,垃圾郵件的監測能夠幫助用戶過濾掉垃圾郵件,方便用戶瀏覽郵件,提升用戶體驗;信用卡欺詐的預測,貸款用戶是否逾期還款的預測能幫助銀行和貸款機構識別高信用度的用戶,大大降低銀行和貸款方的風險;用戶購物興趣愛好的預測能幫助賣方更好的為用戶推薦喜愛的產品,提高交易成功率同時方便用戶購物等等。這些產品的成功主要來源於兩大核心因素,一個是能夠挖掘數據之間的非線性關係的模型設計,另一個則是高速的可擴展的高性能演算法的設計。
在所有的機器學習演算法中,隨機森林在大量的數據集上都展現了較好的性能,隨機森林(Random Forest)模型是由Breiman和Cutler在2001年提出的一種基於分類回歸樹的演算法[1]。它由bagging技術和決策樹組成,通過對生成的多棵決策樹做bagging操作,在不改變模型偏差的情況下降低了模型的方差,從而大大提高了模型的準確率。隨機森林中,每棵決策樹的生成相互獨立,因此可以通過並行操作來完成多棵樹的同時建立，所以決策樹在處理大規模數據時也擁有著較好的可擴展性,在速度上相比於其他的方法例如Boosting等都有著較明顯的優勢。在分類效果上,隨機森林在大量數據集上的表現也戰勝了SVM,LR等機器學習模型，被認為是所有分類器中效果最好的分類器之一[2]。因為隨機森林的這些優點,它也被廣泛的應用在文本分類,垃圾郵件監測等各個領域。
K近鄰演算法是一種非參數化的演算法[3], 在KNN用於分類問題時，我們通常通過計算測試點與訓練集中所有點的距離並找出最近的K個點(鄰居),以最近K個點的投票結果作為我們模型最終的分類結果。KNN演算法不存在明顯的訓練過程,所以KNN演算法也常被稱作是懶惰學習(Lazy Learning)。在數據的特徵維度不是很高同時樣本個數中等的時候,KNN的設計簡單高效同時具有較好的可解釋性,所以KNN演算法被廣泛使用於機器學習的諸多任務當中,常常作為很多演算法的Baseline。當特徵的維度較高同時訓練樣本較大的時候,我們為了提高K近鄰搜索的效率,時常我們會採用一些特殊的演算法例如KD-Tree等[4,5,6]。
本篇文章我們將隨機森林模型和KNN模型相結合,先使用訓練數據訓練得到隨機森林模型,然後用訓練好的隨機森林模型分別對訓練數據和測試數據進行預測得到概率矩陣$N_1 * K$,$N_2 * K$, 其中$N_1$為訓練樣本的個數,$N_2$為測試樣本的個數,$K$為類的個數,然後我們從測試數據中尋找到測試數據中的**可疑樣本**(具體的定義參考後文),然後採用KNN模型對測試結果中的可疑樣本進行糾正,從而提高模型在可疑樣本中的預測性能.此外我們將訓練數據中的**可疑樣本**當做噪音進行刪除, 發現在多個數據集中我們的模型性能都得到了進一步的提升。本文的主要貢獻如下:
- 我們提出了一種將KNN和隨機森林相結合的模型預測框架；
- 通過對訓練集中的噪音樣本或難以學習的樣本進行刪除,在非噪音部分進行KNN訓練進一步提高了模型的性能；
- 我們的演算法相比於單獨採用隨機森林或者KNN演算法進行訓練預測的方法取得了更好的結果.
本文我們會按照下面的順序討論我們的演算法,在第二部分我們會介紹隨機森林和KNN的背景知識；在第三部分我們會介紹我們的演算法以及它的改進版本；在第四部分我們會觀察我們的實驗結果並進行實驗的討論;第五部分我們給出本文的結論以及未來工作。
1.3 背景
1.3.1 隨機森林
隨機森林(Random Forest)是由 Leo Breiman和Adele Cutler在2001年共同提出的一種集成演算法[1],它通過對訓練數據進行Boostrap取樣[9]同時對特徵進行列取樣從而構建大量的去相關性的樹,然後對這些樹的預測結果求均值作為最終的結果。隨機森林演算法不僅設計簡單,而且有著很多非常好的性質,我們可以利用隨機森林中的OOB誤差近似N折交叉驗證的結果從而可以節省N折交叉驗證的時間,隨機森林關於特徵重要性的構建可以很好地幫助我們進行數據特徵選擇與降維，隨機森林中每棵樹的構建相互獨立,可以並行完成,因而大大降低模型構建的速度,增加模型的可擴展性。不僅如此,在大量的實驗中,我們發現隨機森林模型在很少會出現嚴重的擬合現象。在Manuel Fern{'{a}}ndez Delgado進行的大量對比實驗中[3],我們發現在大量的數據集上相較於SVM,LR,ANN等模型隨機森林都取得了更好的結果,被認為是性能最好的模型之一。
1.3.2 KNN
K近鄰演算法是一種非參數化的演算法,因為它的簡單高效以及較好的可解釋性,所以KNN演算法被廣泛應用於機器學習的諸多任務當中,同時也被認為是數據挖掘領域的10大機器學習演算法之一[7]。KNN演算法常常被用來處理分類和回歸問題，當KNN演算法用於分類問題時，我們經常通過計算測試點與訓練集中所有點的距離，然後找出最近的K個點(鄰居),並以最近K個點的投票結果作為我們模型最終的分類結果,但這樣往往會忽略距離的影響,所以一些演算法會選擇對最近的K個點的距離進行加權並以加權後的結果作為模型的預測結果[8]。雖然KNN演算法有著諸多的優點,但是KNN演算法也存在較大的問題,當數據維度較高樣本較多時,KNN常常會受到存儲空間和計算複雜度的困擾,同時KNN將所有的訓練樣本當做是相關實例,所以KNN演算法在存在噪音的數據集上往往受到較大的影響。
1.3.3 可疑樣本定義
此處我們給出可疑樣本的定義。
假設我們存在$N$個樣本$(x_1,y_1),(x_2,y_2),…,(x_N,y_N)$,$x_i$為第$i$個樣本的特徵,$y_i$為第$i$個樣本對應的標籤,$y_i in {1,2,3…,K}$,$K ge 3$為類的個數,我們採用已經訓練好的模型$Model$對$N$個樣本進行預測,得到一個$N*K$的概率矩陣,我們用$p_{ij}$表示為$Model$把第$i$個樣本預測為第$j$類的概率,並且將每一個樣本中概率最大的值對應的類作為我們最終的預測結果.即$argmax_j ~ p_{ij}, j in K$為第$i$個樣本的預測結果.
可疑樣本定義: 對於每一個樣本$x_i $, 令$ q_i = max ~ p_{ij},~ j in {1,2,…,K}, i in {1,2,…,N}$,我們將所有 $q_i le threshold,i in {1,2,…,N} $的樣本定義為可疑樣本,表示模型對該類樣本的預測沒有較強把握.
而實踐中我們也發現模型對於可疑樣本的預測準確率往往遠小於對於其他樣本的預測準確率. 詳細的比較可以我們放在後續的實驗中。
1.4 演算法設計
這一模組我們給出我們的演算法的動機以及新的演算法的偽程式碼。
1.4.1 演算法動機
演算法動機: 很多數據分析問題直接採用一些傳統的模型例如感知機模型,線性支援向量機,邏輯回歸,KNN等模型時所取得的效果較差,而採用基於樹的模型,例如隨機森林等往往可以取得較好的結果. 大多時候我們會選擇直接將預測的結果作為最終的結果或者通過集成的方法來對模型進行進一步的提高,但是這樣的計算代價往往較大,因為我們需要訓練大量的模型來增加模型之間的差異性。本文從另外一個角度出發,通過修正不確定樣本來提高模型的分類準確率。
我們在實踐中發現, 在樹模型的預測結果中存在較多的可疑樣本,這些樣本的預測準確率往往較低, 但是我們認為在同一個模型的預測概率空間中,測試集中不確定樣本的預測概率分布與訓練集中的不確定樣本概率分布會擁有較為相似的分布, 所以我們考慮在預測概率空間中對不確定樣本進行KNN操作來提高對不確定樣本的分類準確率,實驗中我們發現通過該方法確實可以較大提升我們對於不確定樣本的預測準確率。
1.4.2 演算法1
1.4.2.1 演算法步驟
1.輸入: 訓練數據$Train$,${(x_1,y_1),(x_2,y_2),…,(x_{N_1},y_{N_1}) }, x_i in R^d, y_i in {1,2,…, M}$, 測試集$Test$,${(x_1,y_1),(x_2,y_2),…,(x_{N_2},y_{N_2}) }$.可疑樣本的$Threshold$. $KNN$的$K$以及採用的距離函數。
2.模型訓練: 對數據集Train進行訓練獲得模型$Model$。
3.模型預測:使用模型$Model$分別對訓練集和測試集進行預測得到訓練集的預測概率矩陣$Matrix_Tr in R^{N_1 * M}$以及測試集的概率矩陣$Matrix_Te in R^{N_2 * M}$。
4.KNN糾正: 將測試集中預測結果概率低於$Threshold$的樣本的預測數據提取出來形成新的測試集$Test'$,將訓練集的預測矩陣作為新的訓練集的特徵並使用$KNN$進行訓練獲得KNN模型,使用$KNN$對$Test'$進行預測,並將新的預測結果替代原先的預測結果。
5.輸出:將糾正後的預測結果作為最終結果進行輸出。
1.4.2.2 演算法示意圖
1.4.3 演算法2
1.4.3.1 演算法步驟
1.輸入: 訓練數據$Train$,${(x_1,y_1),(x_2,y_2),…,(x_{N_1},y_{N_1}) }, x_i in R^d, y_i in {1,2,…, K}$, 測試集$Test$,${(x_1,y_1),(x_2,y_2),…,(x_{N_2},y_{N_2}) }$.訓練集可疑樣本的$Threshold_Tr$.測試集可疑樣本的$Threshold_Te$.$KNN$的$K$以及採用的距離函數。 2.模型訓練: 對數據集$Train$進行訓練獲得模型$Model$。 3.模型預測:**使用模型$Model$分別對訓練集和測試集進行預測得到訓練集的預測概率矩陣$Matrix_Tr in R^{N_1 * K}$以及測試集的概率矩陣$Matrix_Te in R^{N_2 * K}$。 4.KNN糾正: 將測試集中預測結果概率低於$Threshold_Te$的樣本的預測數據提取出來形成新的測試集$Test'$,將訓練集的預測矩陣高於$Threshold_Tr$作為過濾之後的訓練集的特徵並使用$KNN$進行訓練獲得$KNN$模型,使用$KNN$對$Test'$進行預測,並將新的預測結果替代原先的預測結果。 5.輸出:將糾正後的預測結果作為最終結果進行輸出。
1.4.3.2 演算法示意圖
1.5 實驗
1.5.1 數據集
- Abalone Data Set
- Poker Hand Data Set
- CAR
- HAR
- Letter Recognition
- Nursery
- JsBach Chorals Harmony
- Page Block
- Magic
1.5.2 實驗設計
1.5.2.1 訓練集測試集劃分
我們的實驗數據全部來自UCI,如果數據集存在已經劃分好的訓練集和測試集,我們在訓練集上進行3折交叉驗證選取最優的參數,然後在訓練數據上重新訓練得到我們的最終模型,再在測試集上進行測試。
如果數據集上不存在已經劃分好的訓練集和測試集,則我們將數據按照7:3的比例劃分為訓練集和測試集,同樣的,在訓練數據上我們採用3折交叉驗證獲取最佳參數,然後使用最優參數在訓練數據上重新進行模型訓練,然後再在測試集上進行測試。
此外關於Poker Hand Data Set,我們隨機取樣200000個樣本作為我們的訓練測試數據。
1.5.2.2 參數設置
下面是我們實驗中關於隨機森林做交叉驗證時的參數,訓練集和測試集置信區間的參數設置以及在第二層KNN參數設置.
隨機森林的參數:樹的個數(n_estimators)為[100,200,500,1000],樹的深度(max_depth)為[3,5,8,10,20],樹最小分割樣本(min_smaples_split)為[2,5,8],樹葉子(min_smaples_leaf)的最小樣本數為[2,5,8]；
訓練樣本的置信閾值$Threshold_{Tr}為[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65]；
測試樣本的置信閾值$Threshold_{Te}為[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65]；
KNN的參數,K為[1,3,5,7,9],距離函數為[Cityblock,Euclidean,Chebyshev]。
1.5.3 實驗結果
實驗部分我們主要希望驗證如下幾個結論：
- 隨機森林相比於KNN能更好的挖掘數據之間的非線性關係,從而獲得更高的準確率
- 隨機森林在預測的高概率空間中能獲得更高的準確率,在低概率空間則往往只能得到較低的準確率
- 通過KNN對隨機森林預測中的可疑樣本進行糾正可以很好地提高預測的準確率
- 對訓練集中的數據進行噪音刪除可以進一步提高模型的準確率
1.5.3.1 隨機森林相較於KNN能更好的挖掘數據之間的非線性關係
為了驗證隨機森林相比於KNN演算法能更好地發掘數據之間的非線性關係,這邊我們對8個數據集分別進行KNN和隨機森林的訓練以及測試,隨機森林的訓練測試步驟按照參數設置部分中的隨機森林進行處理;KNN的訓練測試,我們將KK設置為[1,3,5,7,9],距離函數設置為[Cityblock,Euclidean,Chebyshev]分別進行訓練測試並將所有結果中最好的結果作為KNN的最終結果。
從上面的結果中我們發現隨機森林演算法在所有的8個數據集上相較於KNN都取得了更好的效果,這也驗證了我們的猜想,隨機森林相較於KNN能更好的挖掘數據之間的非線性關係同時取得更好的實驗效果。
1.5.3.2 隨機森林模型中高概率和低概率測試集的分布
為了方便,我們默認將0.5作為測試集的置信閾值,最終的結果參見下表:
從上表中我們發現模型中預測概率較高的往往也具有較高的準確率,而模型中預測分類概率較低的往往也具有較低的準確率。符合我們的認知。
1.5.3.3 驗證KNN糾正可以提升隨機森林預測結果的準確率（演算法1）
我們此處仍然以0.5作為測試集的置信閾值,我們對測試集預測結果低於0.5的結果進行KNN處理,最終的結果參見下表:
通過觀察上表我們發現,採用KNN對隨機森林模型預測結果中不確定的部分進行KNN糾正可以很好的提升模型的準確率.
1.5.3.4 驗證對訓練數據進行噪音過濾可以進一步的提升模型的準確率（演算法2）
同樣的,我們將0.5作為測試集的置信閾值,與上面實驗的不同之處在於我們對訓練集的預測結果設置閾值[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65],將隨機森林對於訓練集預測結果小於某一閾值的結果作為噪音刪去. 然後在剩餘的訓練集中進行KNN糾正.最終的結果如下:
通過觀察上表我們發現,除了數據集JsBach Chorals Harmony,模型的效果下降了一點,其他數據集都表現出了較好的性能,這也從側面說明訓練數據中的這些預測結果較低的數據往往就是噪音,刪除這些噪音能對KNN的預測帶來較好的幫助。
1.5.3.5 演算法探索
上述的實驗我們將0.5作為測試集的置信閾值,這邊我們在[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65]間調整測試集的置信閾值,並比較當前結果與之前默認閾值的結果. 實驗的結果可以參考下表.
通過觀察上表我們發現,通過調整置測試集信閾值的大小,我們的模型的性能還可以得到進一步的提升。
1.6 結論
本文我們提出了一種將隨機森林和KNN演算法相結合的框架,我們的框架在多分類問題中進一步提升了測試集中可疑樣本的預測準確率,之後我們又在此框架的基礎上對訓練樣本進行噪音數據的處理,從而進一步提升了我們模型的性能,在大量實驗數據的測試中,我們的方法都取得了非常顯著的效果。目前該框架仍然還存在諸多可以改進和研究的地方,在未來的工作中,我們一方面會考慮將此框架擴展到其他模型中,例如神經網路模型等;另一方面,我們會進一步研究可疑樣本的預測分布規律並考慮對預測較差的樣本進行再學習等。
1.7 參考文獻
- L. Breiman. Random forests. Machine Learning, 45(1):5–32, 2001
- Manuel Fern{'{a}}ndez Delgado, Eva Cernadas,Sen{'{e}}n Barro, Dinani Gomes Amorim. Do we need hundreds of classifiers to solve real world classification problems? JMLR,2014.
- Altman, N. S.. "An introduction to kernel and nearest-neighbor nonparametric regression". The American Statistician. 46 (3): 175–185. 1992
- Andrew Glassner. An Introduction to Ray Tracing. Morgan Kaufmann,1989. ISBN 0-12286-160-4.
- Vlastimil Havran. Heuristic Ray Shooting Algorithms. PhD thesis,Czech Technical University in Prague, 2001.
- Wald I, Havran V. "On building fast kd-trees for ray tracing, and on doing that in O(N log N)". In: Proceedings of the 2006 IEEE
- Wu X, Kumar V, Ross Quinlan J, Ghosh J, Yang Q, Motoda H,McLachlan GJ, Ng A, Liu B, Yu PS, Zhou ZH, Steinbach M,Hand DJ, Steinberg D (2007) Top 10 algorithms in data mining.Knowl Inf Syst 14(1):1–37. 2007
- Samworth R. J. "Optimal weighted nearest neighbour classifiers". Annals of Statistics. 40 (5): 2733–2763. 2012
- Ann. Statist. Bootstrap Methods: Another Look at the Jackknife. Volume 7, Number 1 (1979), 1-26.
The End
