基于自然近鄰圖的標(biāo)簽傳遞算法

韓靈珊

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

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

近年來，半監(jiān)督學(xué)習(xí)[1]在機(jī)器學(xué)習(xí)理論廣泛應(yīng)用的背景下得到了長足的發(fā)展[2-3]，它集合了監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)，利用有標(biāo)簽樣本和大量含有有效信息的未標(biāo)簽樣本進(jìn)行訓(xùn)練和分類。基于圖的半監(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é)點，根據(jù)數(shù)據(jù)間的距離關(guān)系構(gòu)建連接節(jié)點之間的邊的權(quán)重，進(jìn)而從圖譜的角度出發(fā)設(shè)計算法對節(jié)點進(jìn)行分類?？梢哉f，對于基于圖的半監(jiān)督學(xué)習(xí)而言，圖的構(gòu)造對于算法性能有著較大的影響。常用的圖包括全連接圖和k近鄰圖[9]及基于稀疏分解[10]的構(gòu)圖方法。

本文提出一種無參數(shù)、自適應(yīng)的被動尋找近鄰的構(gòu)圖方法來嘗試應(yīng)用到標(biāo)簽傳播算法中，對算法進(jìn)行重新構(gòu)圖，再通過計算圖中節(jié)點間的權(quán)值得到其鄰接矩陣，從而使標(biāo)簽平滑的在整個圖上傳播，直到達(dá)到一個穩(wěn)定狀態(tài)?！?br>