標(biāo)簽傳播算法理論及其應(yīng)用研究綜述

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

1、第30卷第1期2013年1月計(jì)算機(jī)應(yīng)用研究ApplicationResearchofComputersVol.30No.1Jan．2013標(biāo)簽傳播算法理論及其應(yīng)用研究綜述*張俊麗，常艷麗，師文(南京大學(xué)信息管理學(xué)院，南京210093)摘要:介紹了標(biāo)簽傳播算法理論，分析了標(biāo)簽傳播算法的特點(diǎn)，總結(jié)了其在多媒體信息檢索、分類(lèi)、標(biāo)注、處理和社區(qū)發(fā)現(xiàn)等方面的應(yīng)用研究，最后探討了標(biāo)簽傳播算法未來(lái)的研究方向。關(guān)鍵詞:標(biāo)簽傳播算法;半監(jiān)督學(xué)習(xí);多媒體;社區(qū)發(fā)現(xiàn)中圖分類(lèi)號(hào):TP301文獻(xiàn)標(biāo)志碼:A文章編號(hào):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機(jī)器學(xué)習(xí)算法可以分為有監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)算法兩變，使其像一個(gè)源頭把標(biāo)簽傳向未標(biāo)注數(shù)據(jù)。最終，當(dāng)?shù)^(guò)大類(lèi)。所謂有監(jiān)督學(xué)習(xí)，是指從已經(jīng)標(biāo)注好類(lèi)別的數(shù)據(jù)樣本中程結(jié)束時(shí)，相似節(jié)點(diǎn)的概率分布也趨于相似，可以劃分到同一學(xué)習(xí);而無(wú)監(jiān)督學(xué)習(xí)，是指根據(jù)數(shù)據(jù)本身的內(nèi)在特點(diǎn)進(jìn)行學(xué)習(xí)，個(gè)類(lèi)別中，從而完成標(biāo)簽傳播過(guò)程。樣本事先并沒(méi)有清晰的分類(lèi)。半監(jiān)督學(xué)習(xí)(SSL)是一種監(jiān)督具體算法，)是已標(biāo)注數(shù)據(jù)

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

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

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

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