基于超網絡的社會化標簽相似性研究

潘旭偉, 曾雪梅, 李 濤

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

0 引言

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

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

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

1 相關工作

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

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

表1 基于標簽共現網絡局部信息的標簽相似性度量指標

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

2 基于超網絡的標簽相似性指標構建

2.1 社會化標簽超網絡的構建

在社會化標簽系統中,用戶U通過標簽T標注資源I,這種聯系可抽象表示為三部圖模型F(U,I,T,Y),其中U、I、T分別表示用戶、資源和標簽的有限集,Y為三者之間標注關系的集合[7]。對于任意的(u,i,t) 三元組,如果三者之間滿足標注關系則Y(u,i,t)=1,否則Y(u,i,t)=0。基于上述概念構建社會化標簽超網絡模型。

設對于一個以標簽為節點的超網絡H=(E,V),其中V表示標簽節點集合,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},則超網絡H=(E,V)定義為社會化標簽超網絡。由上述定義可知,該超網絡的節點為用戶標注的標簽,超邊為用戶的每次標注活動,其中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 社會化標簽相似性指標構建

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

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

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

3 實驗研究與結果分析

3.1 數據集與實驗設計

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

表3 原始數據集數據樣例

表4 實驗研究的數據集基本信息

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

3.2 結果分析

基于標簽超網絡和基于標簽共現網絡的標簽相似性指標在Delicious和Last.fm兩個數據集上鏈路預測實驗得到的AUC和Precision結果如圖1-圖4所示。

圖1 Delicious數據集超網絡與共現復雜網絡各指標的AUC結果

圖2 Delicious數據集超網絡與共現復雜網絡各指標的Precision結果

圖3 Last.fm數據集超網絡與共現復雜網絡各指標的AUC結果

圖4 Last.fm數據集超網絡與共現復雜網絡各指標的Precision結果

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

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

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

4 結語

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

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