潘旭偉, 曾雪梅, 李 濤

(浙江理工大學 經(jīng)濟管理學院,浙江 杭州 310018)

0 引言

社會化標簽是用戶為自己感興趣的資源定義的一個或多個標簽,且在系統(tǒng)中其他用戶可見。社會化標簽發(fā)揮了用戶的集體智慧,改變了原有基于少數(shù)專家的分類體系,是一種開放、靈活、有趣的信息分類組織方式[1]。用戶自定義的社會化標簽刻畫了用戶的行為和偏好,作為一種有價值的資源已用于解決大數(shù)據(jù)時代信息過載的鏈路預測與個性推薦中[2]。在利用社會化標簽進行鏈路預測和個性化推薦過程中,首先要進行標簽的相似性評估,構(gòu)建能夠準確刻畫社會化標簽相似性的度量指標就顯得尤為重要。

到目前為止,對標簽相似性度量方法的研究主要是利用向量空間矩陣和基于圖或網(wǎng)絡的標簽共現(xiàn)關系來度量標簽之間的相似度。這些標簽相似性度量方法將用戶-資源-標簽三元標注關系轉(zhuǎn)化為向量空間或圖/網(wǎng)絡,在這個轉(zhuǎn)化過程中存在語義丟失、標簽內(nèi)含信息減弱等問題。如何準確刻畫社會化標注過程中形成的用戶-資源-標簽三元關系并保持它們內(nèi)在關聯(lián)信息而不割裂這種聯(lián)系,成為標簽相似性指標構(gòu)建過程中迫切需要解決的問題。

超圖和超網(wǎng)絡理論[3]的出現(xiàn),為更好地認識和理解大量現(xiàn)實復雜系統(tǒng)提供了新思路。在超圖和超網(wǎng)絡中,一條超邊可以連接若干相同或不同的節(jié)點。在社會化標注中,可以利用超邊聯(lián)系用戶一次標注活動中的用戶、資源和標簽,從而保持用戶-資源-標簽的三元結(jié)構(gòu)之間的內(nèi)在聯(lián)系信息。為此提出基于超網(wǎng)絡的標簽相似性度量方法,在構(gòu)建社會化標簽超網(wǎng)絡基礎上,建立刻畫標簽相似性的度量指標,并利用鏈路預測的AUC和Precision評價方法對構(gòu)建的相似性指標的有效性展開實驗驗證研究。

1 相關工作

自社會化標簽出現(xiàn)以來,因其為信息資源的組織、共享和推薦提供了新思路和新維度,基于標簽的鏈路預測和推薦的研究和應用也隨即展開,主要形成了基于向量或張量[4]、基于圖或網(wǎng)絡[5]和基于主題[6]等方法。標簽相似性度量是對標簽之間共同語義特征的量化表示,一種常見的方法是將用戶-資源-標簽的三元關系映射轉(zhuǎn)化為向量空間,通過采用如余弦相似度等指標計算標簽向量間的相似性[7]。結(jié)合頻率和用戶評分[8]、考慮標簽時序特征[2]等其他要素的方法也得到了探討?；谙蛄靠臻g模型的標簽相似性度量需要將用戶-資源-標簽三元關系映射轉(zhuǎn)化為向量空間,容易造成用戶-資源-標簽三元關系的語義丟失和向量空間高維、稀疏問題。為解決這些問題,可將張量應用于社會化標注中,利用基于多元關系的張量分解方法進行標簽相似性評估與預測[9]。

社會化標注形成的用戶-資源-標簽三元關系可抽象表示為二部圖或三部圖模型,所以基于二部圖/三部圖的物質(zhì)擴散模型成為了另一種標簽相似度度量及鏈路預測和推薦的重要方法,如ZHANG等[5]將物質(zhì)擴散原理分別運用于用戶-資源和資源-標簽兩個二部圖中獲得了比單一的二部圖更好的推薦效果。社會化標簽的三部圖模型中存在用戶、資源、標簽三種不同類節(jié)點,其邊僅存在于不同類節(jié)點之間,割裂了同類節(jié)點之間的共現(xiàn)關系。針對這一問題,張昌利等[10]、吳小蘭和章成志[11]在社會化標簽三部圖基礎上構(gòu)建了標簽共現(xiàn)網(wǎng)絡G(T,E),其中T為點集,代表了系統(tǒng)中所有的標簽,E∈T×T為邊集,連接了具有共現(xiàn)關系的標簽。該網(wǎng)絡是一種典型的復雜網(wǎng)絡,其拓撲結(jié)構(gòu)刻畫了標簽的語義關聯(lián)關系。研究表明,標簽共現(xiàn)網(wǎng)絡對標簽語義相似度的影響主要體現(xiàn)于局部拓撲結(jié)構(gòu)[10],因此根據(jù)網(wǎng)絡拓撲結(jié)構(gòu)和復雜網(wǎng)絡節(jié)點相似性理論[12],可定義如表1所示的基于標簽共現(xiàn)網(wǎng)絡局部信息的標簽相似性度量指標。

表1 基于標簽共現(xiàn)網(wǎng)絡局部信息的標簽相似性度量指標

表1中,Γ(x)為連接節(jié)點x所有邊集合,即節(jié)點x的鄰居節(jié)點集合,k(x)=|Γ(x)| 表示節(jié)點x連接邊的數(shù)量或鄰居節(jié)點數(shù)量,稱為節(jié)點x的度。其中CN指標為基礎指標,表示節(jié)點x和y之間共有邊(鄰居)的數(shù)量,表達了共同鄰居特征。依據(jù)社會網(wǎng)絡分析中的三元閉包原理,認為節(jié)點間共有鄰居越多則這兩個節(jié)點越相似。Sa,Ja,So,HPI和HDI這五個指標在CN基礎上,采用不同方式考慮了節(jié)點x或/和y節(jié)點度的反向作用,即節(jié)點x或/和y的鄰居數(shù)越多,那么在節(jié)點x和y之間共有鄰居數(shù)量相同的情況下,它們之間越不相似。RA和AA指標根據(jù)節(jié)點x和y共有鄰居節(jié)點的度構(gòu)建相似性指標,表示它們共有鄰居節(jié)點的度越大,那么節(jié)點x和y之間的相似性越低,RA直接采用x和y共有鄰居節(jié)點的度為分母,AA通過對數(shù)弱化直接取節(jié)點度的影響。表1中的指標分別從標簽共現(xiàn)網(wǎng)絡結(jié)構(gòu)的不同側(cè)面刻畫了標簽相似性指標,這些指標在不同的情景下有不同表現(xiàn),復雜網(wǎng)絡的實驗表明CN,AA,RA等指標通常具有更好的表現(xiàn)[12]。

2 基于超網(wǎng)絡的標簽相似性指標構(gòu)建

2.1 社會化標簽超網(wǎng)絡的構(gòu)建

在社會化標簽系統(tǒng)中,用戶U通過標簽T標注資源I,這種聯(lián)系可抽象表示為三部圖模型F(U,I,T,Y),其中U、I、T分別表示用戶、資源和標簽的有限集,Y為三者之間標注關系的集合[7]。對于任意的(u,i,t) 三元組,如果三者之間滿足標注關系則Y(u,i,t)=1,否則Y(u,i,t)=0?；谏鲜龈拍顦?gòu)建社會化標簽超網(wǎng)絡模型。

設對于一個以標簽為節(jié)點的超網(wǎng)絡H=(E,V),其中V表示標簽節(jié)點集合,E表示超邊,代表一次標注活動,若:(1)E={E(u,i)|(u,i)∈U×I∩au,i=1},(2)E(u,i)={vt|t∈T∩Y(u,i,t)=1},則超網(wǎng)絡H=(E,V)定義為社會化標簽超網(wǎng)絡。由上述定義可知,該超網(wǎng)絡的節(jié)點為用戶標注的標簽,超邊為用戶的每次標注活動,其中E={E(u,i)|(u,i)∈U×I∩au,i=1}代表了標注活動中由用戶-資源二元組(u,i)所組成的邊集,而在邊集E中的每一條超邊E(u,i)={vt|t∈T∩Y(u,i,t)=1}都連接了在一次標注活動中用戶標注資源所使用的標簽。

2.2 社會化標簽相似性指標構(gòu)建

在社會化標簽超網(wǎng)絡中,用戶和資源被組合起來形成了超邊,一條超邊對應于一個用戶對一個資源的標注,標簽是具體標注的結(jié)果。在標注過程中,對同一資源而言,其內(nèi)容范疇通常是一定的,代表對資源描述的不同標簽在語義和內(nèi)容上很可能具有一定的相似性;同樣,對同一用戶而言,在標注中使用詞匯的習慣以及對資源的理解也是相對穩(wěn)定的,那么被頻繁用于標注一個資源的標簽之間也很可能是相似的。在社會化標簽超網(wǎng)絡中就對應為:同一個超邊連接兩個標簽節(jié)點的次數(shù)越多,這兩個標簽就越可能相似。此外,在社會化標簽系統(tǒng)中用戶可以使用多個標簽對資源進行標注,如果資源難以描述或者資源涵蓋內(nèi)容范圍比較大,那么用戶為求更準確的描述就會傾向于使用多個標簽進行標注,此時標簽描述的跨度就會更大,標簽之間的聯(lián)系不那么緊密。社交網(wǎng)絡中存在類似現(xiàn)象,如果一個人交際十分廣泛,那么他可能與大多數(shù)朋友都只是泛泛之交。因此可認為,在每次標注過程中,用戶使用更多的標簽標注資源,那么這些標簽之間的相似性可能就會變?nèi)酢?/p>

基于上述對用戶標注過程中使用的標簽相似性的分析,結(jié)合基于對象關系刻畫對象聯(lián)系與相近程度的鄰近聯(lián)系法則與三元閉包原理,根據(jù)社會化標簽超網(wǎng)絡的拓撲結(jié)構(gòu),提出了基于超網(wǎng)絡的構(gòu)建社會化標簽相似性度量指標的兩個基本原則。(1)共超邊原則:兩個標簽節(jié)點存在的共有超邊數(shù)越多,那么這兩個標簽節(jié)點就越相似,即兩個標簽被用戶共同使用來標注資源的頻率越高,這兩個標簽越相似。(2)超邊包含節(jié)點數(shù)原則:一條超邊所連接(包含)的標簽節(jié)點數(shù)越少,那么這些標簽節(jié)點就越相似,即用戶在標注一個資源時,使用的標簽數(shù)量越少,這些標簽間的相似性就越高。借鑒復雜網(wǎng)絡中的節(jié)點間相似性指標構(gòu)建的基本邏輯,建立了基于超網(wǎng)絡的社會化標簽相似性度量指標,如表2所示。

表2中,B(x)表示給定社會化標簽超網(wǎng)絡中的標簽節(jié)點x的超邊集合,B(x)={E(u,i)|(u,i)∈U×I×Y(u,I,t)=1},|B(x)|為包括標簽節(jié)點x的超邊數(shù)量,稱為節(jié)點的超度;z∈B(x)∩B(y),表示同時連接兩個標簽節(jié)點x,y的一條超邊,k(z)=|z|表示被超邊z連接的標簽節(jié)點個數(shù)。

3 實驗研究與結(jié)果分析

3.1 數(shù)據(jù)集與實驗設計

為驗證構(gòu)建的基于超網(wǎng)絡的社會化標簽相似性度量指標的有效性,實驗選取來自Delicious和Last.fm這兩個具有代表性社會化標簽應用平臺的數(shù)據(jù)。數(shù)據(jù)集中每條記錄由用戶、資源、標簽和標注時間4個字段構(gòu)成,若多個標簽用于用戶的一次標注,則由多條記錄進行表示。表3和表4為數(shù)據(jù)示例和數(shù)據(jù)集統(tǒng)計信息。

表3 原始數(shù)據(jù)集數(shù)據(jù)樣例

表4 實驗研究的數(shù)據(jù)集基本信息

本文采用網(wǎng)絡的鏈路預測實驗方法開展實驗設計,通過客觀的鏈路預測指標AUC和Precision對實驗結(jié)果進行評估。AUC指標從整體上衡量相似性指標的準確性,表示測試集中的邊的分數(shù)值比隨機選擇的一個不存在的邊分數(shù)值高的概率,即每次隨機從測試集中選一條邊與隨機選取的不存在的邊進行比較,如果測試集中邊的分數(shù)值大,則加1分,如果兩分數(shù)值相等加0.5分,若實驗獨立比較n次,其中n′次得1分,n″次得0.5分,則AUC=(n′+0.5n″)/n。AUC的大小代表了整體預測結(jié)果的準確性,AUC越大表示相似度指標越準確。Precision則只考慮排在前L位的邊預測是否準確,如果排在前L位的邊中有m個在測試集中則Precision=m/L。Precision代表相似性較高的節(jié)點對的預測準確性,其值越大預測越準確(本實驗研究中L=100)。為更客觀地進行實驗評估,利用K折交叉驗證將基于超網(wǎng)絡構(gòu)建的社會化標簽相似性度量指標與基于標簽共現(xiàn)網(wǎng)絡構(gòu)建的指標進行對比評估。

3.2 結(jié)果分析

基于標簽超網(wǎng)絡和基于標簽共現(xiàn)網(wǎng)絡的標簽相似性指標在Delicious和Last.fm兩個數(shù)據(jù)集上鏈路預測實驗得到的AUC和Precision結(jié)果如圖1-圖4所示。

圖1 Delicious數(shù)據(jù)集超網(wǎng)絡與共現(xiàn)復雜網(wǎng)絡各指標的AUC結(jié)果

圖2 Delicious數(shù)據(jù)集超網(wǎng)絡與共現(xiàn)復雜網(wǎng)絡各指標的Precision結(jié)果

圖3 Last.fm數(shù)據(jù)集超網(wǎng)絡與共現(xiàn)復雜網(wǎng)絡各指標的AUC結(jié)果

圖4 Last.fm數(shù)據(jù)集超網(wǎng)絡與共現(xiàn)復雜網(wǎng)絡各指標的Precision結(jié)果

對于基于標簽超網(wǎng)絡的系列標簽相似性指標,直接計算共有超邊數(shù)量的c-CN指標在兩個數(shù)據(jù)集中的AUC和Precision評估均具有較好表現(xiàn),明顯優(yōu)于考慮其不同規(guī)范化的c-Sa,c-Ja,c-So,c-HPI和c-HDI等指標,特別是對于Precision的評估表現(xiàn)。同時在共有超邊基礎上加入對超邊中元素個數(shù)的考慮后得到的c-AA,c-RA,c-min和c-max指標表現(xiàn)與c-CN各有優(yōu)劣,預測準確度均較高。因此由實驗結(jié)果可表明:在基于超網(wǎng)絡模型構(gòu)建的標簽相似度指標,共有超邊越多的標簽越相似,同時連接標簽節(jié)點的超邊中所包含的節(jié)點數(shù)越多則標簽的相似度減弱。需要特別指出的是,在共有超邊的基礎上加入節(jié)點超度不同規(guī)范化形式所派生的指標表現(xiàn)較差,表明加入節(jié)點超度要素對標簽相似性評估帶來一定的負向影響。

通過圖1-圖4對比不難發(fā)現(xiàn),在基于標簽超網(wǎng)絡的系列相似性指標中表現(xiàn)較為一致且比較好的c-CN,c-AA,c-RA,c-min和c-max這五個度量指標相較于基于標簽共現(xiàn)網(wǎng)絡的度量指標在鏈路預測的準確性上總體都有提升,相對而言,AUC評價的提升幅度要小于Precision評價的提升幅度。從評價指標的內(nèi)在邏輯來看,AUC側(cè)重于相似性指標整體預測準確性的評價,而Precision則側(cè)重于對相似性較高的標簽對的預測準確性評價。標簽相似性的度量主要是為個性化推薦提供服務的,在基于標簽的個性化推薦過程中,其推薦列表的項數(shù)是有限的,主要考慮的就是Top-N項,因而以Precision評價的預測準確性就顯得更為重要。因此,從標簽相似性度量的實踐適用性角度看,這五個標簽相似性度量指標在鏈路預測Precision評價方面的明顯改進提升,對于個性化推薦的具體應用實踐更具積極價值。

同時從圖1-圖4可以發(fā)現(xiàn),基于標簽超網(wǎng)絡共超邊原則構(gòu)建的相似性指標中,加入節(jié)點超度要素進行規(guī)范化后的c-Sa,c-Ja,c-So,c-HPI和c-HDI這五個指標表現(xiàn)不佳,并且總體表現(xiàn)還不如與之相對應的基于標簽共現(xiàn)網(wǎng)絡的指標?？梢詮倪@些指標加入節(jié)點超度的負向影響和網(wǎng)絡結(jié)構(gòu)特征差異兩方面進行初步解析。一般認為標簽節(jié)點度或超度越大,表示其鄰居數(shù)越多或被用來標注次數(shù)越多,那么它對標簽之間的相似性帶來負向影響,會弱化直接鄰居或共超邊的作用。這從標簽共現(xiàn)網(wǎng)絡的AA和RA指標比較中可以進一步證實,AA指標對節(jié)點度取對數(shù)作為權重進行規(guī)范化,削弱了節(jié)點度對指標的影響,所以在同一網(wǎng)絡中比不取對數(shù)的RA指標獲得更佳的結(jié)果。對于標簽超網(wǎng)絡和標簽共現(xiàn)網(wǎng)絡,由于節(jié)點超度和節(jié)點度在物理含義上的差異,其作用機制也不一樣,造成了它們間的不同結(jié)果。此外,網(wǎng)絡結(jié)構(gòu)特征差異也是一個重要因素。在對Delicious和Last.fm的網(wǎng)絡結(jié)構(gòu)深入分析中發(fā)現(xiàn),Last.fm中資源主要是音樂,內(nèi)容相對比較集聚,因而標注的標簽覆蓋的范圍也較小,對應的標簽網(wǎng)絡的緊密度就較高;而Delicious中資源是各類網(wǎng)站鏈接,涉及范圍廣,對應的標簽網(wǎng)絡的緊密度就不高。相關研究表明基于共有關系構(gòu)建的節(jié)點相似性指標對稀疏網(wǎng)絡具有更好的效果[17]。相對于Delicious而言,Last.fm標簽網(wǎng)絡密度較大,這也可能是在Last.fm數(shù)據(jù)集中,不管是基于標簽超網(wǎng)絡還是標簽共現(xiàn)網(wǎng)絡的相似性指標,其Precision評價都有多個指標的評價結(jié)果為0的一個重要原因。

4 結(jié)語

社會化標簽作為Web 2.0的重要應用之一,構(gòu)建起了用戶與資源之間連接紐帶。針對現(xiàn)有基于向量空間矩陣、二部圖、三部圖和標簽共現(xiàn)網(wǎng)絡等方法在標簽相似性評估和標簽鏈路預測與推薦中將用戶-資源-標簽三元內(nèi)在關系進行轉(zhuǎn)化映射造成不同程度標簽語義聯(lián)系丟失的問題,本文創(chuàng)新性地引入超網(wǎng)絡模型以系統(tǒng)性地刻畫用戶-資源-標簽三元內(nèi)在關系,提出基于超網(wǎng)絡的社會化標簽相似性評估方法。該方法聚焦于用戶的標注行為,以標簽為節(jié)點,以用戶標注活動為超邊,通過超邊連接標注活動中的用戶、資源和標簽,構(gòu)建社會化標簽超網(wǎng)絡,從而準確真實地刻畫出用戶的標注行為,并保持了用戶-資源-標簽三元關系的內(nèi)在語義聯(lián)系信息。建立基于超網(wǎng)絡的社會化標簽相似性度量的兩個基本原則:共有超邊原則和超邊包含節(jié)點數(shù)原則,并據(jù)此構(gòu)建系列的基于超網(wǎng)絡的社會化標簽相似性度量指標。選取來自Delicious和Last.fm兩個代表性社會化標簽應用的數(shù)據(jù)集,利用鏈路預測的AUC和Precision評價準則開展實驗驗證,結(jié)果表明,基于單純共超邊原則以及綜合共超邊與超邊包含節(jié)點數(shù)原則構(gòu)建的基于超網(wǎng)絡的標簽相似性指標表現(xiàn)良好,與基于標簽共現(xiàn)網(wǎng)絡構(gòu)建的標簽相似性度量指標相比提升明顯,對于基于標簽的鏈路預測和個性化推薦具有較高的實踐應用價值。

從現(xiàn)有實驗結(jié)果來看,與標簽共現(xiàn)網(wǎng)絡相比,本文提出的基于標簽超網(wǎng)絡的標簽相似性度量方法,在反映Top N預測的Precision評價結(jié)果有較大改進,而反映整體預測效果的AUC評價結(jié)果改進相對不顯著。提出的基于超網(wǎng)絡的社會化標簽相似性度量指標,主要是基于標簽節(jié)點共有超邊和共有超邊包含的節(jié)點數(shù)這兩個基本的網(wǎng)絡結(jié)構(gòu)特征構(gòu)建的,但標簽語義相似度的影響情況是比較復雜的,比如在網(wǎng)絡中有“弱連接效應”[18]的現(xiàn)象,這可能會影響以共超邊這種反映強連接關系的預測效果,從而影響了反映整體預測效果的AUC評價結(jié)果,而目前在這方面還沒有成熟的研究結(jié)論可供借鑒[3],后期在這方面值得探究。此外社會化標簽超網(wǎng)絡的其他一些拓撲結(jié)構(gòu)特征,如節(jié)點間的路徑及其距離,下一步也可進一步挖掘這些拓撲結(jié)構(gòu)特征與標簽節(jié)點相似性之間的關系,進而優(yōu)化改進社會化標簽相似性度量指標。