基于稀疏學(xué)習(xí)的kNN分類

宗 鳴，龔永紅，文國秋，程德波，朱永華

(1.廣西師范大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院，廣西桂林541004；2.廣西區(qū)域多源信息集成與智能處理協(xié)同創(chuàng)新中心，廣西貴港537000；3.桂林航天工業(yè)學(xué)院信息工程系，廣西桂林541004；4.廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西南寧530004)

?

基于稀疏學(xué)習(xí)的kNN分類

宗 鳴1，2，龔永紅3，文國秋1，程德波1，2，朱永華4

(1.廣西師范大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院，廣西桂林541004；2.廣西區(qū)域多源信息集成與智能處理協(xié)同創(chuàng)新中心，廣西貴港537000；3.桂林航天工業(yè)學(xué)院信息工程系，廣西桂林541004；4.廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西南寧530004)

在kNN算法分類問題中，k的取值一般是固定的，另外，訓(xùn)練樣本中可能存在的噪聲能影響分類結(jié)果。針對以上存在的兩個問題，本文提出一種新的基于稀疏學(xué)習(xí)的kNN分類方法。本文用訓(xùn)練樣本重構(gòu)測試樣本，其中，l1-范數(shù)導(dǎo)致的稀疏性用來對每個測試樣本用不同數(shù)目的訓(xùn)練樣本進(jìn)行分類，這解決了kNN算法固定k值問題；l21-范數(shù)產(chǎn)生的整行稀疏用來去除噪聲樣本。在UCI數(shù)據(jù)集上進(jìn)行實驗，本文使用的新算法比原來的kNN分類算法能取得更好的分類效果。

稀疏學(xué)習(xí)；重構(gòu)；l1-范數(shù)；l21-范數(shù)；噪聲樣本

0 引言

模式分類是人工智能和模式識別中的一個基本問題。其主要考慮的問題：給定N個已知類別的C類樣本，對于任意給定的測試樣本，如何確定其類別，從而完成模式分類。迄今為止，已有很多分類器被提出，其中最具代表性的是最近鄰(NN)分類器，其將測試樣本歸為與其距離最近的樣本所在的類[1]。kNN (k-Nearest Neighbor)算法是一種應(yīng)用廣泛的分類方法，它是最近鄰算法的推廣形式。kNN算法的核心思想：如果一個樣本在特征空間中的k個最相似的樣本中的大多數(shù)屬于同一個類別，則該樣本也屬于這個類別。

圖1 二類分類問題，k=5時情形Fig.1 Binary classification with a fixedk value, i.e. k=5

本文發(fā)現(xiàn)傳統(tǒng)的kNN算法每次都用同樣k個數(shù)目的訓(xùn)練樣本對測試樣本進(jìn)行分類，這在應(yīng)用中通常不合實際。圖1以二類問題為例，在kNN算法中，k固定取5，對于左邊的測試樣本分類，顯然被分為第一類；對于右邊的測試樣本分類，其也被分為第一類；然而與其最鄰近的兩個訓(xùn)練樣本都是屬于第二類，此時由于k固定取5，將其分為第一類可能不合理，應(yīng)將其分為第二類更準(zhǔn)確，即此時k取2比較合理。因此，本文認(rèn)為固定k對每一個測試樣本不合理，k的取值應(yīng)該由數(shù)據(jù)的分布決定，而且決定的方法不是人為設(shè)定，應(yīng)是學(xué)習(xí)數(shù)據(jù)而得到的。此外，認(rèn)為樣本之間是存在相關(guān)性的，考慮樣本間的相關(guān)性更能揭示數(shù)據(jù)特點，對于每個測試樣本，應(yīng)該用與之相關(guān)的訓(xùn)練樣本對其進(jìn)行分類。為此，本文用訓(xùn)練樣本重構(gòu)測試樣本得到訓(xùn)練樣本與測試樣本之間的相關(guān)性關(guān)系，并用lasso(the least absolute shrinkage and selection operator)正則化因子產(chǎn)生稀疏性[2-4]，實現(xiàn)對每個測試樣本用經(jīng)過稀疏選擇的訓(xùn)練樣本來對其進(jìn)行分類，從而解決經(jīng)典kNN算法中k值固定問題。另外，基于數(shù)據(jù)集中存在噪聲數(shù)據(jù)[5]的可能性，本文通過l21-范數(shù)產(chǎn)生整行稀疏性，實現(xiàn)用經(jīng)去除噪聲的訓(xùn)練數(shù)據(jù)集對測試樣本進(jìn)行分類。因此，本文提出基于稀疏學(xué)習(xí)的kNN分類算法——kNN classification based on sparse learning ，簡記為SL-kNN。該算法不僅考慮了樣本之間的相關(guān)性，并利用稀疏學(xué)習(xí)實現(xiàn)訓(xùn)練樣本子集選擇，從而可以較好地解決kNN算法中k值固定問題和樣本中含噪聲問題。

1 基于稀疏學(xué)習(xí)的kNN分類

1.1 重構(gòu)

本文假設(shè)有訓(xùn)練樣本空間X∈Rn×d，n為訓(xùn)練樣本數(shù)目，d為特征數(shù)目；測試樣本空間Y∈Rm×d，m為測試樣本數(shù)目，d為特征數(shù)目；投影矩陣W∈Rn×m。一般我們用線性模型擬合訓(xùn)練數(shù)據(jù)集，常用最小二乘法，即：

(1)

這里‖·‖F(xiàn)是Frobenius矩陣范數(shù)，yi∈Rd×1，wi是W的第i列向量。

所謂重構(gòu)指的是用一組線性無關(guān)的向量的線性組合來近似地表達(dá)一個給定的向量[6-7]，這里就是用訓(xùn)練樣本重構(gòu)測試樣本，分類問題中yi一般為類標(biāo)簽，W表示類標(biāo)簽Y與訓(xùn)練特征X之間的函數(shù)關(guān)系。而在本文中yi表示第i個測試樣本，經(jīng)過重構(gòu)過程得到的矩陣W表示訓(xùn)練樣本X和測試樣本Y之間的相關(guān)性，即相關(guān)系數(shù)。W中元素值wij表示第i個訓(xùn)練樣本與第j個測試樣本之間的相關(guān)性大小，wij>0時代表正相關(guān)，wij<0時代表負(fù)相關(guān)，wij=0時代表不相關(guān)；如果W中某列向量有r個元素值不為0，則分類時k應(yīng)取r，并用對應(yīng)的這r個訓(xùn)練樣本來對相應(yīng)的測試樣本進(jìn)行分類，對于其他測試樣本，同理可得到各自的k值，這就解決了kNN算法中k值固定問題，但目標(biāo)函數(shù)(1)得出的W不是稀疏的。

1.2 稀疏學(xué)習(xí)

我們通常用最小二乘損失函數(shù)來確定線性模型中的向量參數(shù)W，即：

(2)

該損失函數(shù)是凸的，其解為W*=(XXT)-1XYT，但是其中的XXT不一定可逆，需要加上一正則化因子對其正則化以使XXT可逆。本文添加lasso解決此問題，同時lasso被證明能使結(jié)果W產(chǎn)生稀疏性，這稱為元組稀疏(elementsparsity)[2，8-9]，對每個測試樣本稀疏選擇相應(yīng)的訓(xùn)練樣本來進(jìn)行分類，從而解決了上面提到的k值固定問題。另外，添加l21-范數(shù)用來使W產(chǎn)生整行的稀疏，即行稀疏(rowsparsity)[10]，用來去除噪聲樣本。因此可以得到以下經(jīng)過正則化的目標(biāo)函數(shù)：

(3)

目標(biāo)函數(shù)(3)可以求解，求出的W一般具有如下形式，簡單舉例：

W表示訓(xùn)練樣本與測試樣本之間的相關(guān)性，行代表訓(xùn)練樣本，列代表測試樣本。W第一列有3個值不為零，說明第一個測試樣本和第一、三、五個訓(xùn)練樣本相關(guān)，應(yīng)該用這3個訓(xùn)練樣本對第一個測試樣本進(jìn)行分類，即此時k=3。同理分別對第二、三個測試樣本進(jìn)行分類，得到相應(yīng)的k=2、k=1，這里k的取值是通過lasso對訓(xùn)練樣本稀疏選擇得到的。另外W中第四行全為0，即出現(xiàn)整行稀疏性，這是l21-范數(shù)導(dǎo)致的結(jié)果，這意味著第四個訓(xùn)練樣本與所有的測試樣本都不相關(guān)，顯然為噪聲樣本，在分類時予以去除。

目標(biāo)函數(shù)(3)在重構(gòu)過程中利用lasso稀疏學(xué)習(xí)出與每個測試樣本相關(guān)的訓(xùn)練樣本，即對每個測試樣本用不同數(shù)目的訓(xùn)練樣本進(jìn)行分類，并且用l21-范數(shù)導(dǎo)致的整行稀疏性去除數(shù)據(jù)集中存在的噪聲，有效解決了kNN算法中存在的k值固定問題和數(shù)據(jù)集中的噪聲問題。

1.3SL-kNN算法

重構(gòu)、lasso和l21-范數(shù)這三者被整合到一個函數(shù)里，成為了一個優(yōu)化問題，即目標(biāo)函數(shù)(3)。求解目標(biāo)函數(shù)(3)可以從整體上得出一個最優(yōu)解W，學(xué)習(xí)W的過程是由數(shù)據(jù)驅(qū)動的，因此能確保得到的關(guān)系最優(yōu)，并且通過lasso使W具有稀疏性，從而使得每個測試樣本需要的k值不同。l21-范數(shù)使W具有整行稀疏性，用來去除噪聲樣本，然后根據(jù)W的每一列取出與該測試樣本相關(guān)的訓(xùn)練樣本構(gòu)造出分類器，最后對每個測試樣本進(jìn)行分類。上面的過程我們稱為SL-kNN算法，下面我們給出具體的算法步驟，見算法1。

算法1SL-kNN算法。

輸入：訓(xùn)練樣本和測試樣本；

輸出：進(jìn)行分類后的測試樣本的類別；

1.將輸入樣本數(shù)據(jù)進(jìn)行正規(guī)化；

2.根據(jù)算法2(下文給出)求解目標(biāo)函數(shù)(3)，得到最優(yōu)解W；

3.根據(jù)W每列非零元素的個數(shù)得到每個測試樣本的k值；

4.根據(jù)上面得到的k值，選出相應(yīng)的這k個訓(xùn)練樣本，并用這k個訓(xùn)練樣本來對該測試樣本進(jìn)行分類；

5.根據(jù)這k個訓(xùn)練樣本中的大多數(shù)屬于同一個類別，則判定該測試樣本也屬于這個類別；

6.對所有的測試樣本執(zhí)行步驟4～5進(jìn)行分類；

7.算法結(jié)束。

1.4 算法優(yōu)化分析

目標(biāo)函數(shù)(3)是凸的但非光滑的，本文通過設(shè)計一個新的加速近似梯度法來求解該函數(shù)，首先在目標(biāo)函數(shù)(3)上進(jìn)行近似梯度法，通過如下設(shè)置[12]：

(4)

L(W)=f(W)+λ1‖W‖1+λ2‖W‖2，1，

(5)

注意到f(W)是凸且可微的，λ1‖W‖1和λ2‖W‖2，1是凸但非平滑的。使用近似梯度法優(yōu)化W，通過下面的優(yōu)化規(guī)則迭代地更新W：

(6)

其中Gη(t)(W，W(t))=f(W(t))+〈‖‖W‖1+λ2‖W‖2，1，f(W(t))=XXTW(t)-XYT，η(t)和W(t)分別是調(diào)優(yōu)參數(shù)和在第t次迭代獲得的W值。

通過忽略公式(6)中獨立的W，我們可以將其改寫為：

(7)

(8)

同時，為了加速公式(6)中的近似梯度法，本文進(jìn)一步引進(jìn)輔助變量V(t+1)，即：

(9)

算法2中列出了優(yōu)化算法的偽代碼，并在定理1中說明了其收斂性。

算法2 解決公式(3)的偽代碼。

輸入：η(0)，α(1)=1，γ；

輸出：W

1 初始化t=1；

2 初始化W(1)為一個隨機(jī)的對角矩陣；

3repeat

4whileL(W(t))>Gη(t-1)(πη(t-1)(W(t))，W(t))do

5Setη(t-1)=γη(t-1);

6end

7Setη(t)=η(t-1)；

10 計算公式(9)；

11until公式(3)收斂。

定理1 設(shè){W(t)}是由算法2產(chǎn)生的序列，那么對于?t≥1，式(10)成立：

(10)

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

本文實驗數(shù)據(jù)來自UCI機(jī)器學(xué)習(xí)庫(http：//archive.ics.uci.edu/～ml/)，其中Fertility數(shù)據(jù)集、Blood Transfusion Service Center(簡記BloodTrans)數(shù)據(jù)集、German Credit(簡記German)數(shù)據(jù)集、Climate Model Simulation Crashes(簡記Climate)數(shù)據(jù)集、Australian數(shù)據(jù)集和SPECTF Heart(簡記SPECTF)數(shù)據(jù)集都是二類數(shù)據(jù)集，Seeds和Balance Scale(簡記Balance)數(shù)據(jù)集為三類數(shù)據(jù)集，具體情況見表1。實驗環(huán)境為Windows XP系統(tǒng)環(huán)境，實現(xiàn)算法的軟件為Matlab7.11.0。

表1 UCI數(shù)據(jù)集基本情況

表2 兩種算法在UCI數(shù)據(jù)集上的分類準(zhǔn)確性(均值±方差)

在每個數(shù)據(jù)集上用十折交叉驗證法[14]做10次實驗看算法效果，主要的對比算法是kNN算法和L-kNN算法，其中kNN算法是一種經(jīng)典的數(shù)據(jù)挖掘分類算法，而L-kNN算法是只考慮稀疏性(即只使用l1-范數(shù))而沒有考慮去除噪聲樣本的算法，即相比目標(biāo)函數(shù)(3)沒有考慮l21-范數(shù)正則化項。為了保證公平性，kNN算法、L-kNN算法和SL-kNN算法在每一次實驗中選用相同的訓(xùn)練集和測試集，記錄這兩種算法10次實驗取得的分類準(zhǔn)確率。一般準(zhǔn)確率越高，分類的準(zhǔn)確性越好，否則，分類的準(zhǔn)確性越低。kNN算法、L-kNN算法和SL-kNN算法在8個數(shù)據(jù)集上進(jìn)行實驗的分類準(zhǔn)確性(Accuracy)結(jié)果的均值和方差如表2所示。

兩種算法在數(shù)據(jù)集上10次實驗的分類準(zhǔn)確率結(jié)果如圖2～9所示。

圖2 FertilityFig.2 Fertility

圖3 BloodTransFig.3 BloodTrans

圖4 SeedsFig.4 Seeds

分析表2可知，通過和kNN方法、L-kNN方法比較，本文提出的改進(jìn)方法SL-kNN獲得了最好的分類準(zhǔn)確率。例如，SL-kNN算法的分類準(zhǔn)確率在8個數(shù)據(jù)集上平均比kNN算法和L-kNN算法分別提高了4.69%和1.13%。另外，根據(jù)圖2～9，我們也發(fā)現(xiàn)SL-kNN算法幾乎在每一次實驗中都有較高的分類準(zhǔn)確率。

SL-kNN算法比L-kNN算法準(zhǔn)確率高是因為使用了l21-范數(shù)消除噪聲樣本，例如，在Australian和Climate數(shù)據(jù)集上，該算法的分類準(zhǔn)確率比L-kNN方法分別提高了2.9%和1.29%。這意味著Australian和Climate數(shù)據(jù)集可能含有噪聲樣本，進(jìn)一步來說，Australian數(shù)據(jù)集可能有更多的噪聲樣本。綜合來看，相比于kNN算法和L-kNN算法，SL-kNN算法具有更好的分類效果，對噪聲的魯棒性也更強(qiáng)。

圖5 GermanFig.5 German

圖6 AustralianFig.6 Australian

圖7 ClimateFig.7 Climate

圖8 SPECTFFig.8 SPECTF

圖9 BalanceFig.9 Balance

3 結(jié)束語

本文針對kNN算法在分類問題中遇到的兩個問題，即k值固定不變問題和如何去除噪聲樣本問題，提出了一種新的基于稀疏學(xué)習(xí)的kNN分類算法(SL-kNN)，用重構(gòu)獲得測試樣本與訓(xùn)練樣本之間的相關(guān)性，用lasso產(chǎn)生樣本間相關(guān)系數(shù)的稀疏性，用l21-范數(shù)去除訓(xùn)練數(shù)據(jù)集中的噪聲。在UCI數(shù)據(jù)集上進(jìn)行的實驗結(jié)果表明，SL-kNN算法比kNN算法取得更高的分類準(zhǔn)確率，對噪聲的魯棒性更優(yōu)。

[1] QIN Yongsong， ZHANG Shichao， ZHU Xiaofeng， et al. Semi-parametric optimization for missing data imputation[J]. Applied Intelligence, 2007，27(1)：79-88. DOI: 10.1007/s10489-006-0032-0.

[2] ZHU Xiaofeng，HUANG Zi，CHENG Hong，et al.Sparse hashing for fast multimedia search[J].ACM Transactions on Information Systems，2013，31(2)：9. DOI: 10.1145/2457465.2457469.

[3] ZHU Xiaofeng， LI Xuelong， ZHANG Shichao. Block-row sparse multiview multilabel learning for image classification [J].IEEE Transactions on Cybernetics， 2016， 46(2)：450-461. DOI:10.1109/TCYB.2015.2403356.

[4] ZHU Xiaofeng， ZHANG Lei， HUANG Zi. A sparse embedding and least variance encoding approach to hashing [J].IEEE Transactions on Image Processing， 2014， 23(9)：3737-3750. DOI:10.1109/TIP.2014.2332764.

[5] LIU Huawen，ZHANG Shichao.Noisy data elimination using mutual k-nearest neighbor for classification mining[J].Journal of Systems and Software，2012，85(5)：1067-1074. DOI:10.1016/j.jss.2011.12.019.

[6] ZHU Xiaofeng，HUANG Zi，SHEN Hengtao，et al.Linear cross-modal hashing for efficient multimedia search[C]//Proceedings of the 21st ACM International Conference on Multimedia. New York: ACM Press, 2013: 143-152. DOI:10.1145/2502081.2502107.

[7] ZHU Xiaofeng，HUANG Zi，SHEN Hengtao，et al.Dimensionality reduction by mixed kernel canonical correlation analysis [J]. Pattern Recognition，2012， 45(8)：3003-3016. DOI:10.1016/j.patcog.2012.02.007.

[8] HASTIE T，TIBSHIRANI R，F(xiàn)RIEDMAN J.統(tǒng)計學(xué)習(xí)基礎(chǔ)：數(shù)據(jù)挖掘、推理與預(yù)測[M].范明，柴玉梅，咎紅英，譯.北京：電子工業(yè)出版社，2003：7-8.

[9] ZHU Xiaofeng，SUK H，SHEN D G.Matrix-similarity based loss function and feature selection for Alzheimer’s disease diagnosis[C]//Proceeding of IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos, CA:IEEE Computer Society，2014:3089-3096. DOI:10.1109/CVPR.2014.395.

[10] ZHU Xiaofeng，HUANG Zi，YANG Yang，et al.Self-taught dimensionality reduction on the high-dimensional small-sized data[J]. Pattern Recognition，2013，46(1)：215-229. DOI:10.1016/j.patcog.2012.07.018.

[11] ZHU Xiaofeng， ZHANG Shichao， JIN Zhi，et al. Missing value estimation for mixed-attribute data sets[J]. IEEE Transactions on Knowledge and Data Engineering，2011， 23(1)：110-121. DOI:10.1109/TKDE.2010.99.

[12] ZHU Xiaofeng，HUANG Zi，CUI Jiangtao，et al. Video-to-shot tag propagation by graph sparse group lasso[J]. IEEE Transactions on Multimedia，2013，15(3)：633-646. DOI:10.1109/TMM.2012.2233723.

[13] NESTEROV Y.Introductory lectures on convex optimization： A basic course[M]. Berlin: Springer， 2004.

[14] ZHU Xiaofeng， LI Xuelong， ZHANG Shichao，et al.Robust joint graph sparse coding for unsupervised spectral feature selection [J].IEEE Transactions on neural networks and learning systems， 2016, PP(99)：1-13. DOI:10.1109/TNNLS. 2016.2521602.

(責(zé)任編輯 黃 勇)

kNN Classification Based on Sparse Learning

ZONG Ming1，2，GONG Yonghong3，WEN Guoqiu1，CHENG Debo1，2，ZHU Yonghua4

(1.College of Computer Science and Information Technology，Guangxi Normal University，Guilin Guangxi 541004，China; 2.Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing， Guigang Guangxi 537000，China；3.Department of Information Engineering，Guilin University of Aerospace Technology， Guilin Guangxi 541004，China; 4.School of Computer，Electronics and Information， Guangxi University， Nanning Guangxi 530004，China)

The value ofkis usually fixed in the issue ofkNearest Neighbors (kNN) classification. In addition， there may be noise in train samples which affect the results of classification. To solve these two problems， a sparse-basedkNearest Neighbors (kNN) classification method is proposed in this paper. Specifically， the proposed method reconstructs each test sample by the training data. During the reconstruction process，l1-norm is used to generate the sparsity and differentkvalues are used for different test samples， which solves the issue of fixed value ofk. Andl21-norm is used to generate row sparsity which can remove noisy training samples. The experimental results on UCI datasets show that the proposed method outperforms the existing kNN classification method in terms of classification performance.

sparse learning；reconstruction；l1-norm；l21-norm；noise sample

10.16088/j.issn.1001-6600.2016.03.006

2015-09-09

國家自然科學(xué)基金資助項目(61450001，61263035，61573270)；國家973計劃項目(2013CB329404)；中國博士后科學(xué)基金資助項目(2015M570837)；廣西自然科學(xué)基金資助項目(2012GXNSFGA060004，2015GXNSFCB139011，2015GXNSFAA139306)

文國秋(1987—),女,廣西桂林人,廣西師范大學(xué)講師。E-mail:wenguoqiu2008@163.com；龔永紅(1970—)，女，廣西永福人，桂林航天工業(yè)學(xué)院副教授。E-mail:zysjd2015@163.com

TP181

A

1001-6600(2016)03-0039-07