基于自然近鄰圖的標簽傳遞算法

韓靈珊

摘要：提出一種基于自然近鄰搜索的構圖方法，通過自然近鄰圖得到圖中節(jié)點邊的權值及鄰接矩陣，并應用于標簽傳播算法中。構圖過程中對最近鄰居的搜索過程是一種自適應的無參數(shù)過程，從而減少了標簽傳播算法的參數(shù)個數(shù)。UCI數(shù)據(jù)集的實驗結果表明，基于自然近鄰圖的標簽傳播算法能夠提高分類準確率，是一種較好的分類方法。

關鍵字：半監(jiān)督學習；標簽傳播算法；自然近鄰；

近年來，半監(jiān)督學習[1]在機器學習理論廣泛應用的背景下得到了長足的發(fā)展[2-3]，它集合了監(jiān)督學習和無監(jiān)督學習，利用有標簽樣本和大量含有有效信息的未標簽樣本進行訓練和分類。基于圖的半監(jiān)督學習[4-7]依靠強大的數(shù)學理論支撐，依據(jù)圖方法很好的刻畫了數(shù)據(jù)自身的結構特征，以方法的直觀性和良好的分類性能得到了研究學者們的高度關注。標簽傳播算法[8]是基于圖的半監(jiān)督學習算法中最具代表性的算法之一。它將標簽數(shù)據(jù)和未標簽數(shù)據(jù)表示成圖模型中的節(jié)點，根據(jù)數(shù)據(jù)間的距離關系構建連接節(jié)點之間的邊的權重，進而從圖譜的角度出發(fā)設計算法對節(jié)點進行分類。可以說，對于基于圖的半監(jiān)督學習而言，圖的構造對于算法性能有著較大的影響。常用的圖包括全連接圖和k近鄰圖[9]及基于稀疏分解[10]的構圖方法。

本文提出一種無參數(shù)、自適應的被動尋找近鄰的構圖方法來嘗試應用到標簽傳播算法中，對算法進行重新構圖，再通過計算圖中節(jié)點間的權值得到其鄰接矩陣，從而使標簽平滑的在整個圖上傳播，直到達到一個穩(wěn)定狀態(tài)。通過實驗結果證明本文提出的構圖方法是一種有效的構圖方法，算法不僅收斂速度加快并且減少了事先需要確定的參數(shù)的個數(shù)，使用簡單。

1.自然最近鄰

1.1自然最近鄰居

最近鄰居概念在早先就被提出，并廣泛用于機器學習和模式識別等領域。其中最著名的兩個概念是K-最近鄰和-最近鄰。K-最近鄰的思想是對于給定的數(shù)據(jù)集中的每一個數(shù)據(jù)對象找出K個與其相似度最大或者說距離最小的數(shù)據(jù)對象，其中K是事先人為給出的參數(shù)。而-最近鄰的思想是對于給定的一個數(shù)據(jù)集，找出每個數(shù)據(jù)對象在其掃面半徑內的近鄰個數(shù)，其中同樣為人為給定的掃面半徑參數(shù)，使用這種方法得到的數(shù)據(jù)對象在掃面半徑內的最近鄰的個數(shù)有可能不同。從一方面而言，由于K和都是人為給定的參數(shù)而不是結合數(shù)據(jù)對象自身的特點進行搜索最近鄰居，導致后續(xù)算法有可能因為參數(shù)設置不同而出現(xiàn)分類效果偏差較大；從另外一方面而言，K-最近鄰和-最近鄰對于數(shù)據(jù)密度非常敏感，當數(shù)據(jù)分布差異較大，在數(shù)據(jù)分布稀疏區(qū)域可能出現(xiàn)由于參數(shù)設置不當而造成搜索最近鄰居有大的偏差。自然最近鄰[5]的概念不同于傳統(tǒng)的最近鄰居概念，它是一種新的鄰居概念。尋找自然最近鄰的過程不需要設置參數(shù)，是一種無尺度，被動尋找近鄰的過程。這也是與尋找K-最近鄰和-最近鄰過程方法最大的不同點。

自然最近鄰[11]的主要思想是對于數(shù)據(jù)集中稠密區(qū)域的數(shù)據(jù)對象有較多的最近鄰居或者說在稠密區(qū)域的數(shù)據(jù)對象有較高的能量，而在稀疏區(qū)域中的數(shù)據(jù)對象則擁有較少的最近鄰居，即有較低的能量，對于數(shù)據(jù)對象中最離群的數(shù)據(jù)而言，只有一個最近鄰居也就是說這個最離群點具有最低能量。自然最近鄰的搜索過程實際上也可以看作是一種特殊的K-最近鄰搜索過程，它為每個點賦予了不同的K值并且保證每個數(shù)據(jù)對象至少有一個最近鄰，不同點在于自然最近鄰的搜索過程是一種自適應的、被動搜索最近鄰居的過程。

定義1.1 自然最近鄰居（3N鄰居） 在給定的數(shù)據(jù)集中，對于數(shù)據(jù)對象X，若有數(shù)據(jù)對象Y認為X是其最近鄰居，并且對于數(shù)據(jù)集中最離群的數(shù)據(jù)對象Z而言，有一個數(shù)據(jù)對象認為Z是其最近鄰居，那么我們稱數(shù)據(jù)對象Y為數(shù)據(jù)對象X的自然最近鄰居。

定義1.2 自然特征域（supk） 由公式1.1 自適應得到的supk的值稱為數(shù)據(jù)集的自然特征域。

supk= （1.1）

其中表示點y的第r最近鄰域。

由公式1.1可以得到一個簡單的計算方法來搜索數(shù)據(jù)集的自然最近鄰居，算法描述如下：

輸入數(shù)據(jù)集X

1、r=1，flag=0，before=size of X， after=0

2、

3、while flag=0

4、If before-after==0 then flag=1 else

5、For

5.1 計算i的第r個最近鄰居

5.2

5.3

Endfor

If

before=after

Endif

6、r=r+1，after=the number of X that

7、Endif

8、Endwhile

9、

算法1 確定supk的值，并且計算出每個數(shù)據(jù)點的3N鄰域最近鄰域。

1.2自然最近鄰域圖

根據(jù)算法1可知，自然近鄰的選擇過程是自動的一個過程，可以搜索到數(shù)據(jù)集中每個數(shù)據(jù)對象的自然最近鄰，并產(chǎn)生出每個數(shù)據(jù)點對應的最近鄰居數(shù)據(jù)集，因而可以根據(jù)數(shù)據(jù)點的連接來構造自然最近鄰域圖。

自然最近鄰域圖就是連接數(shù)據(jù)集中每個自然最近鄰居所形成的自適應鄰域圖，并且圖中任意節(jié)點i和節(jié)點j之間存在一條邊，當且僅當i是j的自然鄰居或j是i的自然鄰居。

2.基于自然最近鄰的標簽傳播算法

2.1概念定義

標簽傳播算法的主要思想是使每個樣本的標簽信息迭代傳遞給它的近鄰樣本，直到達到全局穩(wěn)定的狀態(tài)。我們假設樣本數(shù)據(jù)集為，其中：n表示樣本的總數(shù)；表示所有樣本的類別標簽集合。表示某一樣本的類別，c表示樣本的總的類別個數(shù)。已標記樣本為，其類標為，；未標記樣本集合為，即X中剩下n-l個樣本為未標簽樣本，且。期望學得函數(shù)f： X→Y可以準確地對示例x預測其標記y。

將基于自然最近鄰的構圖方法用于標簽傳播算法中，實際上是使用自然最近鄰的搜索方法找到數(shù)據(jù)集中每個樣本點的自然最近鄰，并通過構造自然最近鄰域圖，將樣本點作為圖當中的節(jié)點，圖中節(jié)點之間的邊的權值表示樣本與其自然最近鄰之間的相似度。

與經(jīng)典的標簽傳播算法一樣，定義一個的非負矩陣F表示每個樣本的標簽概率矩陣，用來表示樣本數(shù)據(jù)點屬于某一標簽類別的概率；例如，對于任意樣本數(shù)據(jù)其對應的表示數(shù)據(jù)樣本屬于第類標簽的概率，最終樣本數(shù)據(jù)的預測標簽信息選擇使得樣本數(shù)據(jù)屬于第類的概率最大的標簽類別；即。

初始狀態(tài)階段，若為已標記樣本，即，則F的第j列元素的值定義為：

并將其記為；若為未標記樣本，即，初始設定時將其每一列元素的值設置為-1，記為。

2.2算法描述

基于自然最近鄰的標簽傳播算法的步驟描述如下：

1、根據(jù)算法1計算每個數(shù)據(jù)樣本的最近鄰居數(shù)據(jù)集，并構造自然最近鄰域圖。

2、計算鄰接矩陣W，即

3、計算圖的正則化拉普拉斯矩陣，其中D為對角矩陣，其對角線元素。

4、根據(jù)更新樣本點的標簽概率：

4.1

4.2 t=t+1，

4.3 令

5、重復步驟4.2和4.3，直到F收斂到確定的值，循環(huán)終止。

6、為未標簽樣本進行標簽標記

2.3收斂性證明

為了證明算法最終能夠收斂到一個確定的值，將圖的拉普拉斯矩陣S分解為四個子矩陣，即

則有

根據(jù)可知，

當時，可以表示為

由于S的特征值區(qū)間為，所以當時有

因此可得出

由上式可以證明算法能夠收斂到一個唯一的確定的值，同時也可以看出，在執(zhí)行算法時，可不通過循環(huán)直接計算得出標簽概率矩陣，并且其結果不依賴于的取值。

3、實驗及其分析

為了測試算法的分類準確率，選擇表1所示的5個UCI數(shù)據(jù)集作為實驗對象。實驗采用的計算機的硬件配置如下：i3 CPU主頻3.5GHz，內存8GB，采用Python2.7.4編程軟件。

分別采用監(jiān)督學習K近鄰（KNN）、基于K近鄰圖的標簽傳播算法和基于自然近鄰圖的標簽傳播算法解決這5個數(shù)據(jù)集的分類問題；監(jiān)督學習K近鄰的參數(shù)設為1；同時，各算法的共有參數(shù)均設為一致。具體對于每一個數(shù)據(jù)集中參數(shù)取值情況見表2。

對于每個實驗數(shù)據(jù)集，采用隨機抽取L個數(shù)據(jù)組成已標記樣本數(shù)據(jù)集，并且規(guī)定已標簽樣本數(shù)據(jù)集中每一類標簽已標簽樣本的個數(shù)相同。剩余的N-L個樣本數(shù)據(jù)組成未標記樣本數(shù)據(jù)集。以Iris數(shù)據(jù)集為例，由于該數(shù)據(jù)集中樣本被分為三個類別，所以在選擇已標簽樣本時，已標簽樣本的個數(shù)分別取3，6，9，12，15……。獨立重復上述樣本選取過程20次作為隨機實驗的輸入樣本數(shù)據(jù)集，并將這20次獨立重復試驗結果的平均值作為評價算法效果的最終依據(jù)。并以未標記樣本最終分類的準確率作為算法有效性的衡量標準。各數(shù)據(jù)集的實驗結果如圖1所示。

從圖中可以看出，當已標記數(shù)據(jù)較少時，標簽傳播算法的性能均優(yōu)于K近鄰算法，當已標記數(shù)據(jù)的數(shù)量增大時，標簽傳播算法和K近鄰算法的準確性之間的差異逐漸減小；而基于自然近鄰圖的標簽傳播算法的分類準確率略優(yōu)于基于K近鄰圖的標簽傳播算法。因此可以得到的結論是：當已標記數(shù)據(jù)的數(shù)量較少時，標簽傳播算法是一種有效的分類方法，并且基于自然近鄰圖的標簽傳播算法的算法性能略高于基于K近鄰圖的標簽傳播算法效率。

4、結論

標簽傳播算法是一種典型的半監(jiān)督學習算法，將自然近鄰選擇的方法運用到標簽傳播算法的過程中，可以減少參數(shù)對算法分類準確率的影響，提高算法的收斂速度，是一種較有效的半監(jiān)督學習算法。

參考文獻

[1] Chapelle O， Scholkopf B. Semi-supervised learning[M].Cambridge： MIT Press， 2006： 193-196

[2] Nigam K，Mccallum A，Thrun S，et al.Text classification from labeled and unlabeled documents using EM[J].Machine Learning，2000，39（2/3）：103-134

[3] Mailard O A，Vayatis N.Complexity versus agreement for many views：Co-regularization for multi-view semi-supervised learning[J].Lecture Notes in Computer Science，2009，5809：232-246

[4] Blum A，Chawla S.Learning from labeled and unlabeled data using graph mincuts.Proceedings of the 18th International Conference on Machine Learning.Williamstorn，USA；Morgan Kaufmann Publisher，2001，19-26

[5] Zhu X J，Ghahramani Z，Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[C]，Proc of the 20th Int Conf on Machine Learning.Washington：AAAI Press，2003：912-919

[6] Fanhua Shang，L.C. Jiao，Yuanyuan Liu，Hanghang Tong. Semi-supervised learning with nuclear norm regularization[J]. Pattern Recognition . 2013 （8）

[7] Zhu X J，Ghahramani Z，Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[C]，Proc of the 20th Int Conf on Machine Learning.Washington：AAAI Press，2003：912-919

[8] Zhou D Y，Bousquet O，Lal T N，et al. Learning with local and global consistency[C].Proc of Advances in Neural Information Processing System.Massachusetts：MIT press，2003：321-328.

[9] 王雪松，張曉麗等，一種簡潔局部全局一致性學習，控制與決策[J]，2011：26（11）1726-1734

[10] Cheng H， Liu Z C， Yang L. Sparsity induced similarity measure for label propagation. In： Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto，Japan： IEEE， 2009. 317？324

[11] 鄒咸林；自然最近鄰居在高維數(shù)據(jù)結構學習中的應用[D]；重慶大學；2011年