基于LLRKNN算法的不平衡數據集分類應用

溫海標

摘要：不平衡數據集的特點是類樣本數量差異比較大，K近鄰（K-Nearest Neighbor，KNN）算法在對這種數據集分類時，容易出現多數類偏向，即容易將少數類識別為多數類。LLRKNN算法是為了降低多數類偏向的影響，對K近鄰樣本進行重構得出權值，算法分類決策由K近鄰樣本的權值決定。實驗結果表明，LLRKNN算法對不平衡數據集的性能優于KNN算法，具有更好的穩定性。

關鍵詞：不平衡數據;分類;K近鄰;重構

中圖分類號：TP311? ? ? ? 文獻標識碼：A? ? ? ? 文章編號：1009-3044（2018）36-0238-02

Abstract： Unbalanced data sets are characterized by large differences in the number of class samples. K-Nearest Neighbor （KNN） algorithm is prone to majority class bias when classifying such data sets， that is， it is easy to identify minority classes as majority classes. LLRKNN algorithm is designed to reduce the influence of most class bias. The weights of K-nearest neighbor samples are reconstructed. The classification decision of LLRKNN algorithm is determined by the weights of K-nearest neighbor samples. The experimental results show that the performance of LLRKNN algorithm for unbalanced data sets is better than that of KNN algorithm and has better stability.

Keywords： imbalanced data; classification; K nearest neighbour; reconstruction

數據樣本分類是利用已收集的數據樣本，對未知樣本類別的新樣本進行樣本類別預測。在樣本收集過程中，常常由于某些類別的樣本數據難以收集，從而導致數據樣本集中一些類別樣本占少數，形成不平衡樣本集，例如醫學腫瘤特征數據集中，惡心腫瘤特征數據占少數。

在機器學習的實際應用中，大多數分類訓練樣本集是非平衡的，有研究表示[1]，非平衡樣本集會影響機器從中學習的規則的準確性，而且失衡度越大，即各類訓練樣本數量差異越大，影響就越大。因此，如何優化傳統分類方法，以提升對不平衡數據分類性能是目前機器學習領域里研究熱點之一。

常見的傳統分類方法有：支持向量機、決策樹、隨機森林、神經網絡等。其中K最近鄰方法是選取K個待分類的近鄰樣本，以少數服從多數的規則，決定待分類樣本的類別，其原理簡單，易實現，得到廣泛研究。當采用K最近鄰方法對不平衡數據分類時，該方法的缺點時明顯的，如圖1，當K=4時，即待分類樣本選取4個近鄰點，根據KNN的“少數服從多數”規則，將待分類樣本的類別確定為三角形類。而待分類樣本的實際類別是圓形類，該方法在此錯分類的根本原因是“少數服從多數”的分類決策規則。因此使用K最近鄰方法對非平衡數據分類時，容易出現多數類偏向問題，分類準確率通常較低。本文采用局部線性重構方法，得出近鄰樣本的權值，根據各樣本類別的權值比重決定待分類樣本的類別，以優化K最近鄰方法分類決策規則，降低分類器對多數類的偏向。

1 LLRKNN算法

1.1 算法原理

LLRKNN算法的基本思想是對待分類樣本的K個近鄰點加權，減少多數類對分類決策的影響。其基本原理是待分類樣本可以被其局部領域內的近鄰樣本點采用重構方法[2]線性表示，重構的目的是得出各個近鄰樣本的權值，待分類樣本類標號由各類別的權值確定，而不是各類別樣本數量決定。LLRKNN算法分為預處理和類標號決定階段，預處理階段中把數據集中類標號未知的樣本作為待分類樣本，其他為訓練樣本，為了降低各個樣本的屬性值范圍不一致對選取近鄰點造成影響，將樣本的非類標號屬性值采用最小最大規范化法[3]轉換為[0，1]之間。類標號決定階段主要工作是采用歐式距離函數[4]計算出待分類樣本與訓練樣本的距離值，選擇的K個離待分類樣本最近的樣本作為局部領域內樣本，通過重構得出局部領域內每個近鄰樣本的權值，計算近鄰樣本各類別的權值，最后統計出最大權值的類，將其類標號賦予待分類樣本。

1.2 算法步驟

訓練樣本集記為[Xx1，x2，…，xn ，X∈Rd×n]，待分類樣本[y∈R1×d]，其中 n為樣本數，d為樣本屬性個數。

步驟1 把樣本的所有非類標號屬性值規范化為[0，1]區間，如下式：

式1中，A為樣本的非類標號屬性，max和min分別表示該屬性的最大和最小值。

步驟2 通過歐氏距離函數計算出待分類樣本與所有訓練樣本的距離：

根據式2計算的結果值，選取K個與待分類樣本距離值最小的樣本作為局部領域近鄰樣本。

步驟3 局部領域近鄰樣本線性重構待分類樣本，通過如下式得出每個近鄰樣本的權值：

式2中，[N∈Rk×d]是近鄰樣本矩陣，[W∈R1×k]為存儲了每個近鄰樣本的權值向量。

步驟4 通過計算式2得出每個近鄰樣本的權值，，根據下式計算待分類樣本與每類別近鄰樣本的線性組合的差值，差值最小的類作為待分類樣本類標號：

其中i表示近鄰樣本某一類的標號，[W*i]表示屬于i類的近鄰樣本權值向量，[N*]表示屬于i類的近鄰樣本矩陣，[y*]表示待分類樣本類標號。

具體算法如下：

[算法1? ? LLRKNN算法 輸入：訓練樣本集X，待分類樣本y

局部領域近鄰個數K

輸出：待分類樣本類標號

1：[Xy←normailze[0，1]Xy]

2： for i = 1 to n do

3：? ? [d←1×n] 零向量，元素為距離值

4：? ? [d←disty，xj]

5：? end for

6：? ? [N←]根據距離，選取K個近鄰樣本

7：? [W←argminWi=1mWN-y22]

8：[st.W·1T=1]

9： [y*←argminiy-W*iN*] ]

2? 實驗設計

2.1 數據集

實驗部分使用的4個數據集選自UCI數據庫[5]，基本信息如表1所示：

2.2 評價標準

測試分類方法的標準通常采用準確率，準確率高，說明分類效果好，但對不平衡數據分類，采用準確率是不合適的，因為錯分少數類的樣本對整體分類準確率影響不大。因此，本次實驗采用基于混淆矩陣（Confusion Matrix）的F-value，該值更能測驗分類方法的性能。

混淆矩陣如下表所示：

其中參數[β]用于調整查全和查準率的影響程度。實驗部分將[β]值設定為1，表示查全和查準率的影響程度相當。

2.3 實驗結果與分析

實驗采用五折交叉驗證法，將每個數據集等分五份進行五次實驗，每次實驗記錄查全率和查準率，并計算F-value數據，每個數據集進行五次實驗的F-value數據如圖2;其均值和標準差如表3所示，算法采用MATLAB編程實現。

由表3可知，用F-value值作分類器的評價標準時，LLRKNN算法比KNN算法提高8.7%～32%，說明LLRKNN算法對不平衡數據分類的性能要優于KNN。各個數據集的標準差值LLRKNN算法比KNN算法小，說明LLRKNN算法有更好的魯棒性。從圖2可以看出各數據集五次實驗的F-value值分布，也可看出LLRKNN算法更穩定。

3 結束語

LLRKNN算法是對待分類樣本的K近鄰進行線性重構得出相應的權值，在分類決策階段使用權值計算待分類樣本與近鄰樣本類別的重構誤差，誤差最小的類作為分類樣本類別，優化了KNN算法的分類決策方法，一定程度降低多數類偏向的影響。實驗中通過對比F-values值，結果表明LLRKNN算法對不平衡數據分類效果更好。

參考文獻：

[1] Wang B X， Japkowicz N. Boosting support vector machines for imbalanced data sets[J]. Knowledge & Information Systems， 2010， 25（1）：1-20.

[2] Zhang L， Chen C， Bu J， et al. Active Learning Based on Locally Linear Reconstruction[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2011， 33（10）：2026-2038.

[3] JiaweiHan， MichelineKamber， JianPei，等. 數據挖掘概念與技術[M]. 機械工業出版社， 2012.

[4] Pang-NingTan， MichaelSteinbach， VipinKumar. 數據挖掘導論：完整版[M].2版. 人民郵電出版社， 2011.

[5] UCI repository of machine learning datasets[DB/OL].http：//archive.ics.uci.edu

[通聯編輯：唐一東]