韓靈珊

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

關(guān)鍵字：半監(jiān)督學(xué)習(xí)；標(biāo)簽傳播算法；自然近鄰；

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

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

1.自然最近鄰

1.1自然最近鄰居

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

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

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

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

supk= （1.1）

其中表示點(diǎn)y的第r最近鄰域。

由公式1.1可以得到一個(gè)簡(jiǎn)單的計(jì)算方法來搜索數(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 計(jì)算i的第r個(gè)最近鄰居

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的值，并且計(jì)算出每個(gè)數(shù)據(jù)點(diǎn)的3N鄰域最近鄰域。

1.2自然最近鄰域圖

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

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

2.基于自然最近鄰的標(biāo)簽傳播算法

2.1概念定義

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

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

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

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

并將其記為；若為未標(biāo)記樣本，即，初始設(shè)定時(shí)將其每一列元素的值設(shè)置為-1，記為。

2.2算法描述

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

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

2、計(jì)算鄰接矩陣W，即

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

4、根據(jù)更新樣本點(diǎn)的標(biāo)簽概率：

4.1

4.2 t=t+1，

4.3 令

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

6、為未標(biāo)簽樣本進(jìn)行標(biāo)簽標(biāo)記

2.3收斂性證明

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

則有

根據(jù)可知，

當(dāng)時(shí)，可以表示為

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

因此可得出

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

3、實(shí)驗(yàn)及其分析

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

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

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

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

4、結(jié)論

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

參考文獻(xià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] 王雪松，張曉麗等，一種簡(jiǎn)潔局部全局一致性學(xué)習(xí)，控制與決策[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ù)結(jié)構(gòu)學(xué)習(xí)中的應(yīng)用[D]；重慶大學(xué)；2011年