標簽傳播算法理論及其應用研究綜述

《標簽傳播算法理論及其應用研究綜述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第30卷第1期2013年1月計算機應用研究ApplicationResearchofComputersVol.30No.1Jan．2013標簽傳播算法理論及其應用研究綜述*張俊麗，常艷麗，師文(南京大學信息管理學院，南京210093)摘要:介紹了標簽傳播算法理論，分析了標簽傳播算法的特點，總結(jié)了其在多媒體信息檢索、分類、標注、處理和社區(qū)發(fā)現(xiàn)等方面的應用研究，最后探討了標簽傳播算法未來的研究方向。關(guān)鍵詞:標簽傳播算法;半監(jiān)督學習;多媒體;社區(qū)發(fā)現(xiàn)中圖分類號:TP301文獻標志碼:A文章編號:1001-3695(2013)01-0

2、021-05doi:10．3969/j．issn．1001-3695．2013．01．004OverviewonlabelpropagationalgorithmandapplicationsZHANGJun-li，CHANGYan-li，SHIWen(SchoolofInformationManagement，NanjingUniversity，Nanjing210093，China)Abstract:Thisarticleintroducedthetheoreticalstudyoflabelpropagationalgo

3、rithm， rizeditsapplicationsinmultimediainformationprocessing，retrieval，annotation，classificationandcommunitydiscovery， Finally，analyseditscharacteristicsandsumma-etc．thispaperproposedthefutureprospectsandthetrendsofdevelopmentsoftheLPAalgorithm．Keywords:labelpropaga

4、tionalgorithm(LPA);semi-supervisedlearning(SSL);multimedia;communitydiscovery機器學習算法可以分為有監(jiān)督學習和無監(jiān)督學習算法兩變，使其像一個源頭把標簽傳向未標注數(shù)據(jù)。最終，當?shù)^大類。所謂有監(jiān)督學習，是指從已經(jīng)標注好類別的數(shù)據(jù)樣本中程結(jié)束時，相似節(jié)點的概率分布也趨于相似，可以劃分到同一學習;而無監(jiān)督學習，是指根據(jù)數(shù)據(jù)本身的內(nèi)在特點進行學習，個類別中，從而完成標簽傳播過程。樣本事先并沒有清晰的分類。半監(jiān)督學習(SSL)是一種監(jiān)督具體算法，)是已標注數(shù)據(jù)

5、，［3］如下:令(，)…(xyxyY11llL=學習和無監(jiān)督學習相結(jié)合的方法，其主要思想是:基于數(shù)據(jù)分{}∈{1…C}是類別標簽，類別數(shù)y…y1lC已知，且均存在于標布上的模型假設，利用少量的已標注數(shù)據(jù)進行指導并預測未標簽數(shù)據(jù)中。令(，)…(，)為未標注數(shù)據(jù)，xyxyYl+1l+1l+ul+uU=記數(shù)據(jù)的標記，然后合并到標記的數(shù)據(jù)集中［1，2］。{}不可觀測，l＜＜u，令數(shù)據(jù)集y…yl+1l+uX={}x…x∈R。D1l+u標簽傳播算法LPA)是由［3］(［3］(Zhu等人于2002年提出，它問題轉(zhuǎn)換為:從數(shù)據(jù)集X中，利用YL

6、的學習，為未標注數(shù)據(jù)集是一種基于圖的半監(jiān)督學習方法，其基本思路是用已標記節(jié)點的每個數(shù)據(jù)找到對應的標簽Y。U的標簽信息去預測未標記節(jié)點的標簽信息。利用樣本間的關(guān)將所有數(shù)據(jù)作為節(jié)點(包括已標注和未標注數(shù)據(jù))，創(chuàng)建系建立關(guān)系完全圖模型，在完全圖中，節(jié)點包括已標注和未標一個完全連接圖，其邊的權(quán)重計算式如下:注數(shù)據(jù)，其邊表示兩個節(jié)點的相似度，節(jié)點的標簽按相似度傳遞給其他節(jié)點。標簽數(shù)據(jù)就像是一個源頭，可以對無標簽數(shù)據(jù)wij=exp(－2dij2σ)=exp(－(xDd∑d=1i2)d2－x)(1)jσ進行標注，節(jié)點的相似度越大，標簽越容易

7、傳播。由于該算法其中:表示任意兩個節(jié)點的歐氏距離，權(quán)重dij受控于參數(shù)wijσ。為衡量一個節(jié)點的標注通過邊傳播到其他節(jié)點的概率，在 簡單易實現(xiàn)，算法執(zhí)行時間短，復雜度低且分類效果好，引起了此定義一個(l+u)×(l+u)概率傳遞矩陣T如下所示:國內(nèi)外學者的關(guān)注，并將其廣泛地應用到多媒體信息分類、虛擬社區(qū)挖掘等領(lǐng)域中。本文利用關(guān)鍵字labelpropagation、標簽傳播、標簽傳遞、標記傳播、標記傳遞等詞作為關(guān)鍵詞，對國內(nèi)外數(shù)據(jù)庫及網(wǎng)絡資源進行了檢索，結(jié)果發(fā)現(xiàn)，目前國內(nèi)外相關(guān)其中:是節(jié)點Tijj到wijT=Pji()→=ijl

8、+u∑wk=1kji的傳播概率。(2)文獻期刊論文約有博論文3篇。90篇，其中國外82篇，國內(nèi)8篇，國內(nèi)外碩同時定義一個()l+u的標注矩陣，令×CY=δ(，c)，yYici它的第i行代表著節(jié)點的標注概率，第c列代表類別，若yY=iic1則表示節(jié)點是屬于c類別，否則為0。通過