算法簡介
標籤傳播算法(LPA)是由Zhu等人於2002年提出,它是一種基於圖的半監督學習方法,其基本思路是用已標記節點的標籤信息去預測未標記節點的標籤信息。利用樣本間的關係建立關係完全圖模型,在完全圖中,節點包括已標註和未標註數據,其邊表示兩個節點的相似度,節點的標籤按相似度傳遞給其他節點。標籤數據就像是一個源頭,可以對無標籤數據進行標註,節點的相似度越大,標籤越容易傳播。由於該算法簡單易實現,算法執行時間短,複雜度低且分類效果好,引起了國內外學者的關注,並將其廣泛地套用到多媒體信息分類、虛擬社區挖掘等領域中。本文利用關鍵字labelpropagation、標籤傳播、標籤傳遞、標記傳播、標記傳遞等詞作為關鍵字,對國內外資料庫及網路資源進行了檢索,結果發現,目前國內外相關文獻期刊論文約有90篇,其中國外82篇,國內8篇,國內外碩博論文3篇。
算法基本理論
根據LPA算法基本理論,每個節點的標籤按相似度傳播給相鄰節點,在節點傳播的每一步,每個節點根據相鄰節點的標籤來更新自己的標籤,與該節點相似度越大,其相鄰節點對其標註的影響權值越大,相似節點的標籤越趨於一致,其標籤就越容易傳播。在標籤傳播過程中,保持已標註數據的標籤不變,使其像一個源頭把標籤傳向未標註數據。最終,當疊代過程結束時,相似節點的機率分布也趨於相似,可以劃分到同一個類別中,從而完成標籤傳播過程。