溫海標(biāo)

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

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

中圖分類號(hào)：TP311? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：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ù)樣本，對(duì)未知樣本類別的新樣本進(jìn)行樣本類別預(yù)測(cè)。在樣本收集過程中，常常由于某些類別的樣本數(shù)據(jù)難以收集，從而導(dǎo)致數(shù)據(jù)樣本集中一些類別樣本占少數(shù)，形成不平衡樣本集，例如醫(yī)學(xué)腫瘤特征數(shù)據(jù)集中，惡心腫瘤特征數(shù)據(jù)占少數(shù)。

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

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

1 LLRKNN算法

1.1 算法原理

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

1.2 算法步驟

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

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

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

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

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

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

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

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

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

具體算法如下：

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

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

輸出：待分類樣本類標(biāo)號(hà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個(gè)近鄰樣本

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

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

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

2? 實(shí)驗(yàn)設(shè)計(jì)

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

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

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

混淆矩陣如下表所示：

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

2.3 實(shí)驗(yàn)結(jié)果與分析

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

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

3 結(jié)束語

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