基于稀疏學習的自適應近鄰分類算法

程德波，蘇毅娟，宗 鳴，朱永華

（1.廣西師范大學 計算機科學與信息工程學院，廣西 桂林541004；2.廣西師范學院 計算機與信息工程學院，廣西 南寧530023；3.廣西大學 計算機與電子信息學院，廣西 南寧530004）

0 引 言

通過研究分析［1，2］發現k－NN （k－nearest neighbor）算法存在鄰域大小k難以取定的缺陷，文獻 ［3］提出k＝（數據集樣本數n超過100時效果較好），這種取法通常要經過大量的實驗和分析才能確定合適的k值，通常得到的結果并不理想，而且每一個待分類樣本都用固定領域大小k最近的已知樣本構造的分類器來進行分類，但在實際應用中每個樣本的鄰域是不同的，因此每個測試樣本應選取不同大小的鄰域來對其進行分類。結合下面的例子來討論k－NN 算法存在的缺陷。

例如，如圖1為一個二類數據集。當k＝1時，待分類樣本1將會被誤判為第二類，待分類樣本2分類正確；當k＝3時，待分類樣本2將會誤判為第一類；當k＝7時，同樣待分類樣本2將會誤判為第一類。根據分析可以發現待分類樣本1屬于第一類，適合它的k值應該可以取3、5、7等；待分類樣本2屬于第二類，適合它的k值應該可以取1、9、11等。

圖1 分類樣本數據集

上述存在的問題顯然是由用戶定義k值產生，即使是通過實驗確定k值，還是沒有考慮數據樣本之間的相關性，不是數據驅動的。本文方法是數據驅動的，由數據分布決定k－NN 中k （k是學習而來）。具體的說，本文借助稀疏學習［4，5］和重構［6］的相關知識用于k－NN 分類來改良算法，提出了一種k－NN 分類算法——基于稀疏學習的自適應近鄰分類算法SL－SAN （self－adaptive neighbor classification based on sparse learning）。

1 SL－SAN算法

1.1 重構技術與稀疏編碼

重構技術：重構是指用一組線性無關向量的線性組合來近似地表達一個給定的向量。待分類樣本通過重構技術可以在一定半徑的空間內找到與它近鄰的已知樣本。因此，對于已知樣本X＝｛xi｝ni＝1∈Rn×d，n為樣本數，d 為維數；待分類樣本Y ＝｛yi｝mi＝1∈Rm×d，m 為樣本數，d 為維數，用已知樣本xi重構每一待分類樣本yi獲取重構系數矩陣W ∈Rn×m的目標函數如下

式中：wi——重構系數矩陣W 的列向量子數，在文中解釋為xi與yi的相似性度量。wi值越大，說明已知樣本yi與待分類樣本xi越相似，但通過得到wi還不能很容易的找到待分類樣本大小為k個已知樣本的鄰域。以下介紹本文算法目標函數的導出。

最小二乘方模型可以用來處理回歸問題也可以用來處理分類問題［7］，本文采用最小二乘方來處理分類問題，其模型如下

川菜亦博采各大菜系之長，善于借鑒，善于創新，其早已馳名中外，在國際上享有“食在中國，味在四川”的美譽。

1.2 SL－SAN分類算法

SL－SAN 算法將所有已知樣本數據作為訓練樣本，所有待分類樣本作為測試樣本；用訓練樣本對測試樣本進行重構得到重構系數矩陣；借助稀疏學習，采用l1－范數正則化因子壓縮重構系數矩陣，使得重構系數矩陣成為稀疏矩陣。重構系數子數的稀疏位置不同確保了每個測試樣本用不同的訓練樣本進行重構，且稀疏約束下得到重構系數子數為0時，表示該訓練樣本不參與該測試樣本的重構，因此不僅保留了樣本之間的相關性，而且獲得了每個測試樣本對應鄰域不同個相似訓練樣本。算法主要思想描述如下：

假設測試樣本X ∈Rn×d，n為樣本數，d 為維數；訓練樣本Y ∈Rm×d，m 為樣本數，d為維數。根據重構和稀疏學習的知識采用式 （4）函數：用所有的訓練樣本X 重構每一測試樣本Y，得到重構系數矩陣并將其稀疏成為稀疏系數矩陣，以此求解全局最優解W。式 （4）即為Lasso（the least absolute shrinkage and select operator）［11］，Lasso是式 （2）加l1－范數而來，并用l1－范數懲罰目標函數使得絕對值較小的系數自動壓縮為0，從而產生稀疏模型。并且正則化因子參數λ越大得到的稀疏密度越大，即W 為0的元素越多。

經式 （4）最優化計算得到的W ∈Rn×m，在本文中m代表m 個測試樣本，n 代表n 個訓練樣本跟每個測試樣本之間的相似關系。且wij的值表示第i個測試樣本與第j 個訓練樣本的相似性。若wij＞0，說明第i個測試樣本與第j 個訓練樣本正相關，且數值越大，表明越相關；若wij＝0，表示它們不相關；若wij＜0，說明它們負相關。例如

得到的最優化W 是一個重構稀疏系數矩陣。W 第1列不為0的數表明第1個測試樣本跟第1個和第4個訓練樣本正相關，因此，第1個測試樣本進行分類時設置k＝2；同理，第2個和第3個測試樣本的k值依次應為1和3。

學習W 的過程是數據驅動（data－driven），因此能確保得到關系是最優，并且通過Lasso的l1－范數使得每個測試樣本需要的k值不同，然后只需根據W 取出與該測試樣本相關的訓練樣本構造分類器，進行分類。得到全局最優化結果W 后，可以對Y 測試樣本（y單個測試樣本）的每個測試樣本構造分類器，通過各分類器得到每個測試樣本的類標簽。

SL－SAN 算法偽代碼描述如下所述：

?

SL－SAN 算法創新的使用Lasso來研究k－NN 的k值固定問題，SL－SAN 算法雖然使用跟Lasso一樣的目標函數，但是與Lasso有兩個區別：①Lasso一般用于分類或者回歸等應用，本文創新的利用Lasso介紹k－NN 算法的k值固定值問題；②不同于常見使用LARS （least angle regression）方法求解Lasso的目標函數，本文采用算法2來優化目標函數。SL－SAN 跟常見的k－NN 算法比較：首先，k－NN 是懶惰學習方法，對每一個測試樣本單獨的求k－NN 中的k值，SL－SAN 一次重構所有測試樣本，即考慮了測試樣本的相關性也考慮了訓練樣本的相關性。其次，k－NN 算法采用用戶自定義或者十折交叉驗證方法獲取k值，且經常k值對所有測試例子一樣，而本文的SL－SAN 通過Lasso重構方法能得到測試樣本和訓練樣本之間的相關性矩陣W。經實驗驗證，SL－SAN 算法是優于經典k－NN 方法。

1.3 算法優化

等式 （4）是凸的，但后面正則化項是非光滑的。故本文提出一種有效的算法來光滑目標函數并求得最優解W。首先對wi（1≤i≤m）求導并命其為0，可得

注意到Di依賴于W，因此它們也是未知的。根據文獻［12］本文提出采用一種迭代算法來求解最優解W，即算法2如下：

?

證明：根據算法的第2步可得到

因此有

根據文獻［13］對于任意向量w 和w0，我們有。因此最后一步成立，即算法在每次迭代中減小目標值。

W（t）（1≤i≤m）在收斂處滿足等式 （5）。由于問題 （5）是一個凸問題，滿足等式 （7）意味著W 對于問題（5）來說是一個全局最優解。因為在每一次迭代時都有封閉形式解，因此，算法2可以將問題 （5）收斂到它的全局最優解，故我們的算法收斂非常快。

2 實驗結果與分析

實驗的評價指標采用分類準確率，分類準確率越大表明效果分類效果越好。計算公式如下

式中：n——元組數，ncorrect——正確分類的元組數。

實驗部分使用的數據集來源于UCI［13，14］，實驗數據集介紹見表1。

表1 用于實驗的數據集

本文算法用MATLAB 語言編程實現，并在win7系統下MATLAB 7.1軟件上進行實驗。實驗使用10折交叉驗證法，從所有樣本中取出一個作為測試樣本 （作為待分類樣本），余下的作為訓練樣本。通過用表1 數據集進行實驗，每個數據集重復實驗10次，并取10 次實驗準確率的均值加上方差可以得到表2實驗結果。

表2 SC－SAN、k－NN 準確率加上方差

通過表2可以發現：從準確率來看，4個數據集在使用算法SL－SAN 分類時所得準確率比經典k－NN 算法分類時要高，且分類準確率提高了3%～8%；從方差的角度來看，SL－SAN 算法比k－NN 算法具有很好的穩定性。通過圖2可以更直觀的看出SL－SAN 算法的優越性。經實驗證實SLSAN 算法比經典k－NN 算法分類效果要好。

3 結束語

SL－SAN 算法創新使用稀疏學習和重構技術來介紹k－NN 算法的k值固定值問題，并解決了k值難以取定的難題，完善了k－NN 算法沒有考慮待分類樣本與所有已知樣本之間相關性的缺陷。具體表現為，SL－SAN 算法學習得到W 的過程是數據驅動過程，通過W 獲得測試樣本的k鄰域自然也是自適應的，無需人為設定，并且重構后可以得知待分類樣本分布情況，得到的k （不固定）個已知樣本是充分考慮了待分類樣本與已知樣本之間的相關性。本文算法適用于k－NN 分類算法的適用范圍。

圖2 4個數據集用兩種算法分類10次實驗準確率的對比

［1］Zhang Shichao.Cost－sensitive classification with respect to waiting cost［J］.Knowledge－Based System，2010，23 （5）：369－378.

［2］Zhu Xiaofeng，Zhang Shichao，Jin Zhi，et al.Missing value estimation for mix ed－attribute data sets［J］.IEEE Transactions Knowledge Data Engineering，2011，23 （1）：110－121.

［3］Lall U，Sharma A.A nearest－neighbor bootstrap for resampling hydrologic time series ［J］.Water Resour Res，1996，32 （3）：679－693.

［4］Jenatton R，Gramfort A，Michel V，et al.Mutial scale mining of fMRI data with hierarchical structured sparsity ［J］.SIAM Journal on Imaging Sciences，2012，5 （3）：835－856.

［5］Zhu Xiaofeng，Huang Zi，Shen Hengtao，et al.Dimensionality reduction by mixed－kernel canonical correlation analysis［J］.Pattern Recognition，2012，45 （8）：3003－3016

［6］KANG P，CHO S.Locally linear reconstruction for instancebased learning ［J］.Pattern Recognition，2008，41 （11）：3507－3518.

［7］LIANG Jinjin，WU De.Sparse least square support vector machine with L1norm ［J］.Compute Engineering and Design，2014，35 （1）：293－296 （in Chinese）.［梁錦錦，吳德.稀疏L1范數最小二乘支持向量機 ［J］.計算機工程與設計，2014，35 （1）：293－296.］

［8］Zhu Xiaofeng，Huang Zi.Sparse hashing for fast multimedia search ［J］.ACM Transactions on Information System，2013，31 （2）：1－24.

［9］Zhu Xiaofeng，Zhang Lei，Huang Zi.A spars e embedding and least variance encoding app roach to hashing ［J］.IEEE Transactions on Image Processing，2014，23 （9）：3737－3750.

［10］Zhu Xiaofeng，Huang Zi，Cui Jiangtao.Hengtao Shen：Video－to－shot tag propagation by grapsparse group lasso［J］.IEEE Transactions on Multimedia，2013，15 （3）：633－646.

［11］Zhu Xiaofeng，Huang Zi.Self－taught dimensionality reduction on the high－dimensional small－sized data［J］.Pattern Recognition，2013，46 （1）：215－229.

［12］Zhu Xiaofeng，Huang Zi，Shen Hengtao，et al.Linear crossmodal hashing for efficient multimedia search ［C］／／ACM Multimedia，2013：143－152.

［13］UCI repository of machine learning datasets ［DB／OL］.［2014－05－06］.http：／／archive.ics.uci.edu／－ml／，2014.

［14］LE SONG.Codes and data［EB／OL］.［2014－05－06］.http：／／www.cc.gatech.edu／～lsong／code.htm，2014.