溫海標(biāo)

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

關(guān)鍵詞：不平衡數(shù)據(jù);分類;K近鄰;重構(gòu)

中圖分類號：TP311? ? ? ? 文獻(xiàn)標(biāo)識碼：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

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

在機(jī)器學(xué)習(xí)的實際應(yīng)用中，大多數(shù)分類訓(xùn)練樣本集是非平衡的，有研究表示[1]，非平衡樣本集會影響機(jī)器從中學(xué)習(xí)的規(guī)則的準(zhǔn)確性，而且失衡度越大，即各類訓(xùn)練樣本數(shù)量差異越大，影響就越大。因此，如何優(yōu)化傳統(tǒng)分類方法，以提升對不平衡數(shù)據(jù)分類性能是目前機(jī)器學(xué)習(xí)領(lǐng)域里研究熱點之一。

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

1 LLRKNN算法

1.1 算法原理

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

1.2 算法步驟

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

步驟1 把樣本的所有非類標(biāo)號屬性值規(guī)范化為[0，1]區(qū)間，如下式：

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

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

根據(jù)式2計算的結(jié)果值，選取K個與待分類樣本距離值最小的樣本作為局部領(lǐng)域近鄰樣本。

步驟3 局部領(lǐng)域近鄰樣本線性重構(gòu)待分類樣本，通過如下式得出每個近鄰樣本的權(quán)值：

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

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

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

具體算法如下：

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

局部領(lǐng)域近鄰個數(shù)K

輸出：待分類樣本類標(biāo)號

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←]根據(jù)距離，選取K個近鄰樣本

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

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

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

2? 實驗設(shè)計

2.1 數(shù)據(jù)集

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

2.2 評價標(biāo)準(zhǔn)

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

混淆矩陣如下表所示：

其中參數(shù)[β]用于調(diào)整查全和查準(zhǔn)率的影響程度。實驗部分將[β]值設(shè)定為1，表示查全和查準(zhǔn)率的影響程度相當(dāng)。

2.3 實驗結(jié)果與分析

實驗采用五折交叉驗證法，將每個數(shù)據(jù)集等分五份進(jìn)行五次實驗，每次實驗記錄查全率和查準(zhǔn)率，并計算F-value數(shù)據(jù)，每個數(shù)據(jù)集進(jìn)行五次實驗的F-value數(shù)據(jù)如圖2;其均值和標(biāo)準(zhǔn)差如表3所示，算法采用MATLAB編程實現(xiàn)。

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

3 結(jié)束語

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

參考文獻(xiàn)：

[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，等. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 機(jī)械工業(yè)出版社， 2012.

[4] Pang-NingTan， MichaelSteinbach， VipinKumar. 數(shù)據(jù)挖掘?qū)д摚和暾鎇M].2版. 人民郵電出版社， 2011.

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

[通聯(lián)編輯：唐一東]