鄧振云，龔永紅，2，孫　可，張繼連

(1.廣西師范大學廣西多源信息挖掘與安全重點實驗室，廣西桂林541004；2.桂林航天工業(yè)學院，廣西桂林541004)

?

基于局部相關性的kNN分類算法

鄧振云1，龔永紅1，2，孫可1，張繼連1

(1.廣西師范大學廣西多源信息挖掘與安全重點實驗室，廣西桂林541004；2.桂林航天工業(yè)學院，廣西桂林541004)

摘要：kNN算法作為一種簡單、有效的分類算法，在文本分類中得到廣泛的應用。但是在k值(通常是固定的)的選取問題上通常是人為設定。為此，本文引入了重構和局部保持投影(locality preserving projections，LPP)技術用于最近鄰分類，使得k值的選取是由樣本間的相關性和拓撲結構決定。該算法利用l1-范數(shù)稀疏編碼方法使每個測試樣本都由它的k(不固定)個最近鄰樣本來重構，同時通過LPP保持重構前后樣本間的局部結構不變，不僅解決了k值的選取問題，并且避免了固定k值對分類的影響。實驗結果表明，該方法的分類性能優(yōu)于經(jīng)典kNN算法。

關鍵詞：kNN；保局投影；重構；稀疏編碼

0引言

在數(shù)據(jù)挖掘的研究與應用中，分類是用于預測分析的重要方式之一。它是一種有監(jiān)督的學習，通過對訓練樣本的分析，從中歸納出分類規(guī)則，以此來預測測試樣本的類別。目前常見的分類算法主要有：決策樹、關聯(lián)規(guī)則、貝葉斯、神經(jīng)網(wǎng)絡、遺傳算法、kNN算法等。本文集中在kNN分類算法的研究。

由于kNN算法在樣本較大以及特征屬性較多時，分類的效率就將大大降低，因此近年來學者們提出了許多針對kNN的改進算法。如文獻[1]提出將粗糙集理論應用到kNN算法中，實現(xiàn)屬性約簡，解決了kNN算法分類效率低的缺點；文獻[2]提出一種基于密度的樣本裁剪方法，降低kNN的計算量，提高分類的性能；文獻[3]提出一種基于類別的kNN改進模型，解決k近鄰選擇時大類別、高密度樣本占優(yōu)問題等；文獻[4]提出一種充分利用已知類別標簽數(shù)據(jù)進行自訓練的半監(jiān)督分類算法，顯著地提高了分類的準確率。這些算法主要通過一定的優(yōu)化策略或降維方法減少樣本之間相關性的計算，以提高分類的效率。而本文直接考慮樣本間的相關性、樣本的拓撲結構，對于kNN算法中k值的選取直接由數(shù)據(jù)本身驅動，避免了人為設定k值對分類的影響。

kNN算法是一種基于實例的學習方法[5]，最初用于解決文本分類的問題。其基本思想是：在訓練樣本中找到待測樣本的k(定值)[6-7]個最近鄰樣本，然后根據(jù)這k個最近鄰樣本的類別進行投票，以此來決定測試樣本的類別。但是在實際應用中，這種采取固定k值的方法經(jīng)常是不合理的，如圖1。

當k=5時，根據(jù)kNN分類算法將得到兩個樣本空間(圖1中兩個實線圓圈)。其中待測樣本1的k個最近鄰樣本選取合理，但對于待測樣本2而言，實際上令k=3更為合理(如虛線圓圈所示)，因為下方兩個訓練樣本距離待測樣本2較遠，如果把它們也作為最近鄰樣本，很可能會影響分類準確率。因此本文也認為：對于測試樣本取相同的k值是不合理的[8]；k值的選取應該由數(shù)據(jù)的分布或特點決定，即k值是從數(shù)據(jù)中學習的，對不同的測試樣本它的取值應該是不固定的。為了更加準確地根據(jù)數(shù)據(jù)分布或特點學習k值，應當充分考慮數(shù)據(jù)中的先驗知識，例如樣本間的相關性、樣本的拓撲結構等。

根據(jù)以上理論，本文用訓練樣本重構所有測試樣本生成相關性矩陣，并通過l1-范數(shù)稀疏編碼方法[9-11]對矩陣進行重構[12]，使得每個測試樣本都由它的k個相關的最近鄰樣本預測，同時通過LPP保持了樣本的局部結構而不受重構影響。這樣便使得每個測試樣本都由它的k(不固定)個相關的最近鄰樣本預測，分類的性能得到很大的提高。本文將提出的算法簡稱為LS-kNN(LPP-Sparse-kNN)算法。

1LS-kNN算法

1.1局部保持投影(LPP)

LPP是非線性方法拉普拉斯特征映射(Laplacian eigenmap)的線性近似，其特點是獲得原始數(shù)據(jù)在低維度上的投影，且保持數(shù)據(jù)的非線性流形特征不變。LPP算法的基礎是構造一個模擬局部結構的最近鄰圖，本算法應用此特性即構造一個模擬測試樣本的最近鄰的矩陣W。通常采用最小化目標函數(shù)式(1)來確定這個最近鄰矩陣W：

(1)

對公式(1)進行代數(shù)變化操作后發(fā)現(xiàn)，特征空間保持了原始的局部結構。操作如下：

tr(WTXDXTW)-tr(WTXSXTW)=tr(WTXLXTW)。

(2)

1.2重構

假設訓練集X∈Rn×d，測試集Y∈Rm×d，其中m、n、d分別是測試樣本的個數(shù)、訓練樣本個數(shù)和樣本的維數(shù)。本文算法的核心是通過訓練樣本去重構測試樣本，得到一個相關性矩陣W∈Rn×m，使得Y與WTX盡可能差距最少。這可以通過最小二乘損失函數(shù)[13]實現(xiàn)，即：

(3)

1.3LS-kNN算法的描述

由于公式(3)是凸函數(shù)，易知其解為W*=(XTX)-1XTY。但XTX在實際應用中不一定可逆，對此通常會考慮嶺回歸從而引入一個l2-范數(shù)使得函數(shù)可逆：

(4)

(5)

通過目標函數(shù)(5)進行重構將得到如下形式的投影矩陣W：

根據(jù)重構技術可知wij≠0即為相關的樣本，且第j列中wij≠0的個數(shù)即為第j個測試樣本最近鄰樣本的個數(shù)。因此從矩陣W的形式可判斷，第一個測試樣本(第一列)的最近鄰樣本數(shù)為2，即k=2，第二個測試樣本的最近鄰數(shù)為4。以此類推，可發(fā)現(xiàn)測試樣本沒有采用固定的最近鄰數(shù)即沒有用固定k值去尋找訓練樣本。

綜上可知，LS-kNN算法通過考慮樣本間的相關性，有效地解決了kNN分類存在的問題，并通過LPP保證了數(shù)據(jù)內部分布的完整性。注意，l2-范數(shù)就無法實現(xiàn)這個功能，因為它得到的矩陣不稀疏。

最后，給出LS-kNN分類算法的具體步驟。

算法1：LS-kNN分類算法。

輸入：樣本集，并作規(guī)范化處理。

輸出：測試集的類標簽。

1：由ADMM優(yōu)化算法(6)得到最優(yōu)解W；

2：根據(jù)W找到每個測試樣本對應的k個最近鄰訓練樣本；

3：對每個測試樣本，用與其對應的k個最近鄰樣本的類標簽進行分類投票；

4：輸出測試樣本的類標簽。

2LS-kNN算法的優(yōu)化

由于目標函數(shù)(5)是凸且非平滑的，因此本文采用ADMM(alternating direction method of multipliers)[15]算法來優(yōu)化此函數(shù)。目標函數(shù)(5)可等效于求解以下N個獨立的子問題：

(6)

其中wi向量是W的第i個列子向量且vec(W)=[w1，w2，…，wn]T。對目標函數(shù)(6)進行ADMM優(yōu)化，在目標函數(shù)(5)上增加一個虛擬變量(dummy variable)C使函數(shù)轉換為：

(7)

公式(7)較為復雜，因此可以使用擴展拉格朗日進行替代，使其變成如下形式：

(8)

ADMM算法采用迭代法思想，包括如下的迭代步驟：

(9)

通過以上分析，本文將目標函數(shù)(5)拆分為N個獨立的子問題，再使用ADMM算法求解最優(yōu)化的W。

算法2： ADMM算法，W的優(yōu)化。

Input： 數(shù)據(jù)集、懲罰函數(shù)ρ3。

Output：W、Λ。

1： InitializeW0，C0，Λ0；

2： repeat

3：Wk+1←Wk；

4：Ck+1←Ck；

5：Λk+1←Λk+ρ3(W+C)；

6：k=k+1；

7：UntilW最優(yōu)。

3實驗與結果分析

為了驗證算法的有效性，本文以分類準確率作為評價指標。用kNN分類算法、LMNN算法以及本文的LS-kNN改進算法，在LIBSVM數(shù)據(jù)集[16]上選取4個數(shù)據(jù)集ionosophere、seeds、heart、cheveland進行實驗(為了使數(shù)據(jù)特征之間具有可比性，已對數(shù)據(jù)集進行了標準化處理)。

為了保證3個算法比較的公平性，本實驗對樣本事先采取相同的預處理，并在每個數(shù)據(jù)集上用十折交叉驗證法做10次實驗來看算法效果。對于kNN和LMNN算法，我們令k=5；而LS-kNN算法的k值是由數(shù)據(jù)驅動產(chǎn)生，無需事先處理。最后對3種算法得到的實驗結果進行比較。

實驗結果的優(yōu)劣由分類準確率評定。多次實驗得到的分類準確率結果可以反映分類的可信度以及算法的穩(wěn)定性。分類準確率的均值越高，可信度也就越高，穩(wěn)定性越強。分類準確率的計算公式如下：

(11)

其中nmatch為測試樣本中正確分類的個數(shù)，n為測試樣本的總數(shù)。

圖2　LS-kNN算法在不同數(shù)據(jù)集不同參數(shù)取值下的分類準確率Fig.2　Classification accuracy of LS-kNN on the different datasets with different parameter setting

從圖2可以看出，當參數(shù)ρ1∈(10-5，10-4)，ρ2∈(10-5，10-4)范圍時，LS-kNN算法的分類準確率達到最優(yōu)，因此我們將在后面的對比實驗中，令ρ1、ρ2在(10-5，10-4)范圍內隨機取值。

通過對ρ1、ρ2進行調參使LS-kNN達到最優(yōu)，我們將其與kNN算法和LMNN算法進行對比，實驗過程中對每個數(shù)據(jù)集都重復10次，不但報告每次的實驗結果而且報告10次結果的均值和方差，如表1。

表1　kNN、LMNN與LS-kNN算法的分類準確率

為了更加直觀地比較kNN、LMNN和LS-kNN的分類性能，我們做了對比圖，如圖3所示。由圖3中4個數(shù)據(jù)集得出的實驗結果可知，LS-kNN算法的分類準確率明顯高于傳統(tǒng)kNN和LMNN算法。

圖3　kNN，LMNN與LS-kNN算法在4個數(shù)據(jù)集上的分類準確率Fig.3　Classification accuracy of kNN，LMNN and LS-kNN on four datasets

4結束語

本文提出了一種基于LPP和l1-范數(shù)的kNN改進算法LS-kNN，有效解決了傳統(tǒng)kNN分類算法中的兩個缺陷：k值需事先給定且固定；未考慮樣本之間的相關性。該算法思想是根據(jù)樣本的相關性和拓撲結構，用訓練樣本對所有測試樣本進行重構，以實現(xiàn)k值的選取由數(shù)據(jù)本身驅動，而無需人為設定。因此，本算法可用于無法通過經(jīng)驗或者需要長時間實驗選定k值的情況，大幅度減少選取k值的時間。最后通過與兩種算法以分類準確率為評價標準進行對比實驗，實驗結果表明，LS-kNN算法的分類準確率優(yōu)于kNN分類算法。

參考文獻：

[1]張著英，黃玉龍，王翰虎. 一個高效的KNN分類算法[J]. 計算機科學，2008，35(3)：170-172.

[2]李榮陸，胡運發(fā). 基于密度的kNN文本分類器訓練樣本裁剪方法[J]. 計算機研究與發(fā)展，2004，41(4)：539-545.

[3]張孝飛，黃河燕. 一種采用聚類技術改進的KNN文本分類方法[J]. 模式識別與人工智能，2009，22(6)：936-940.

[4]陸廣泉，謝揚才，劉星，等. 一種基于KNN的半監(jiān)督分類改進算法[J]. 廣西師范大學學報(自然科學版)，2012，30(1)：45-49. DOI: 10.16088/j.issn.1001-6600.2012.01.004.

[5]HAN Jiawei，KAMBER M. Data mining： concepts and techniques[M]. Waltham, MA: Morgan Kanfmann Publishers，2000.

[6]ZHANG Shichao.Cost-sensitive classification with respect to waiting cost[J]. Knowledge-Based Systems, 2010，23(5)： 369-378. DOI: 10.1016/j.knosys.2010.01.008.

[7]LALL U，SHARMA A.A nearest neighbor bootstrap for resampling hydrologic time series[J].Water Resouarces Research，1996，32(3)： 679-693. DOI: 10.1029/95WR02966.

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

[9]WU Xindong，ZHANG Chengqi，ZHANG Shichao.Database classification for multi-database mining[J]. Information Systems, 2005，30(1)： 71-88. DOI:10.1016/j.is.2003.10.001.

[10]JENATTON R，GRAMFORT A，MICHEL V，et al. Multi-scale mining of fMRI data with hierarchical structured sparsity[J]. Siam Journal on Imaging Sciences，2012，5(3)： 835-856. DOI:10.1137/110832380.

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

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

[13]KANG P，CHO S. Locally linear reconstruction for instance-based learning[J]. Pattern Recogntion，2008，41(11)： 3507-3518. DOI: 10.1016/j.patcog. 2008.04.009.

[14]LIANG Jinjin，WU De.Sparse least square support vector machine with L1 norm[J]. Computer Engineering and Design，2014，35(1)： 293-296，338.

[15]BOYD S. Alternating direction method of multipliers[EB/OL]. [2015-03-25]. http://stanford.edu/class/ee364b/lectures/admm_slides.pdf.

[16]CHANG C C，LIN C J.LIBSVM： A library for support vector machine[J]. ACM Transactions on Intelligent Systems and Technology，2011，2(3)：27.DOI： 10.1145/1961189.1961199.

(責任編輯黃勇)

A kNN Classification Algorithm Based on Local Correlation

DENG Zhenyun1，GONG Yonghong1，2，SUN Ke1，ZHANG Jilian1

(1. Guangxi Key Lab of Multi-source Information Mining & Security，Guangxi Normal University，Guilin Guangxi 541004，China； 2. Guilin University of Aerospace Technology，Guilin Guangxi 541004，China)

Abstract:As a simple and effective classification algorithm, kNN algorithm is widely used in text classification. However, the k value (usually fixed) is usually set by users. For this purpose, the reconstruction and locality preserving projections (LPP) technology is introduced into the nearest neighbor classification, which makes the selection of the k value to be determined by the correlation between the samples and the topology structure. The algorithm uses l1-norm sparse coding method to reconstruct the test sample by its k (not fixed) nearest neighbor samples and LPP keeps the local structure of the sample after the reconstruction, which not only solves the problem of choosing k value, but also avoids the influence of fixed k value on classification. Experimental results show that the classification performance of the proposed method is better than that of the classical kNN algorithm.

Keywords:k-nearest neighbor； locality preserving projections； reconstruction； sparse coding

中圖分類號：TP181

文獻標志碼：A

文章編號：1001-6600(2016)01-0052-07

基金項目：國家自然科學基金資助項目(61573270,61263035，61363009)；國家973計劃項目(2013CB329404)；廣西自然科學基金資助項目(2012GXNSFGA060004,2015GXNSFCB139011)；中國博士后科學基金資助項目(2015M570837)；廣西多源信息挖掘與安全重點實驗室開放基金資助項目(MIMS13-08)

收稿日期：2015-06-16

doi:10.16088/j.issn.1001-6600.2016.01.008

通信聯(lián)系人：張繼連(1977—)，男，廣西桂林人，廣西師范大學教授，博士。E-mail:jiliangzhang@sina.com；龔永紅(1970—)，女，廣西永福人，桂林航天工業(yè)學院副教授。E-mail: zysjd2015@163.com