用戶興趣相似性度量的關(guān)系預(yù)測算法*

黃宏程，陸衛(wèi)金，胡 敏，魏 青

1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065

2.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

用戶興趣相似性度量的關(guān)系預(yù)測算法*

黃宏程1,2+，陸衛(wèi)金1，胡 敏1，魏 青1

1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065

2.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

+Corresponding autho author:r:E-mail:huanghc@cqupt.edu.cn

HUANG Hongcheng,LUWeijin,HUM in,et al.User relationships prediction algorithm w ith interest sim ilarity measurement.Journalof Frontiersof Com puter Science and Technology,2017,11(7)：1068-1079.

用戶興趣；相似性；多階量化；關(guān)系預(yù)測

1 引言

近年來，微博以發(fā)布內(nèi)容簡短，關(guān)注機(jī)制靈活，推送消息及時的特點(diǎn)贏得用戶的青睞，取得了快速發(fā)展。以新浪微博為例，系統(tǒng)按照用戶標(biāo)簽、微博文本、關(guān)注用戶列表等信息推送消息。充分利用這些基本信息，挖掘用戶的興趣偏好，建立用戶興趣模型，用于準(zhǔn)確預(yù)測用戶間關(guān)系，對于改善用戶體驗(yàn)，增加網(wǎng)絡(luò)粘性和精準(zhǔn)廣告營銷大有裨益。因此，基于微博用戶興趣預(yù)測用戶關(guān)系已成為當(dāng)前互聯(lián)網(wǎng)數(shù)據(jù)挖掘的研究熱點(diǎn)。

目前對微博用戶興趣的研究大部分是基于用戶的注冊信息、標(biāo)簽[1]、微博內(nèi)容、地理位置[2]和社交圈[3]等進(jìn)行個性化的推薦[4]，使用戶有選擇地添加自己“感興趣”的好友。張珊靚等人[5]認(rèn)為用戶的好友推薦和時間相關(guān)，因此將時間作為一個重要參數(shù)引入到隨機(jī)游走算法中，按照Top N準(zhǔn)則將用戶作為好友關(guān)系推薦給其他用戶。吳成超等人[6]利用高斯概率隱語意模型挖掘長期興趣，通過評分時間窗獲取短期興趣，結(jié)合長短期興趣建立用戶興趣模型。孫靜宇等人[7]在基于用戶評分的協(xié)同過濾算法中，結(jié)合用戶的長短期興趣的時間加權(quán)方法，重點(diǎn)分析了用戶長短期興趣的識別問題，能夠更好地描述用戶興趣的變化。孫威[8]認(rèn)為在線社交網(wǎng)絡(luò)的用戶關(guān)系是穩(wěn)定的，將微博名人的興趣作為長期興趣，將普通用戶轉(zhuǎn)發(fā)和評論的內(nèi)容作為短期興趣，并用遺忘曲線衡量短期興趣。郭進(jìn)利[9]通過研究人類的行為動力學(xué)，認(rèn)為用戶的興趣隨時間增加而逐步衰減，由此構(gòu)建了相應(yīng)的衰減函數(shù)。

上述這些研究充分考慮了用戶“興趣漂移”的規(guī)律，但是忽略了部分興趣用戶會長期保持的問題，使得建立的興趣模型難以客觀地描述用戶興趣的變化過程，導(dǎo)致推送的消息有效性不高。本文針對該問題提出了基于用戶興趣相似性的關(guān)系預(yù)測算法。將用戶的標(biāo)簽信息表征長期興趣，微博文本信息表征短期興趣[10]，用戶的長期興趣可以通過關(guān)注列表推薦（即被關(guān)注用戶擁有的標(biāo)簽）和短期興趣反饋（即用戶自己的微博文本信息）來修正；通過用戶興趣狀態(tài)的轉(zhuǎn)換，更新用戶興趣；按照長短期興趣的分類，采用頻率統(tǒng)計(jì)和多階量化的方法度量用戶興趣度。根據(jù)社會學(xué)理論[11]：用戶間越相似，越可能成為好友的原則，本文通過余弦相似性度量用戶間的興趣相似度，相似度越高，則用戶成為朋友的可能性越高。

本文組織結(jié)構(gòu)如下：第2章提出用戶興趣模型，詳細(xì)闡述用戶興趣的修正、更新以及興趣度的度量，根據(jù)興趣度計(jì)算用戶相似性；第3章以新浪微博真實(shí)數(shù)據(jù)作為數(shù)據(jù)集，通過實(shí)驗(yàn)分析了本文提出的基于長短期興趣進(jìn)行用戶關(guān)系預(yù)測的算法的有效性；第4章總結(jié)本文工作。

2 用戶興趣建模

為了提高用戶關(guān)系預(yù)測的精度，同時兼顧到用戶“興趣漂移”和部分興趣持久保持的客觀規(guī)律，將用戶興趣分為長、短期興趣[6,12]。其中長期興趣通過關(guān)注列表獲得，短期興趣根據(jù)用戶自身的微博文本信息提取。用戶興趣模型如圖1所示。

本文分析微博的用戶原始數(shù)據(jù)，提取用戶興趣所需的標(biāo)簽信息、關(guān)注列表和微博文本信息。對文本分詞后，提取關(guān)鍵詞，參照騰訊、網(wǎng)易、搜狐和新浪微博等，將用戶興趣分為（美食，教育，娛樂，體育，時尚，財(cái)經(jīng)，科技、文化，軍事，讀書，汽車，音樂，游戲，星座，影視，購物，攝影，寵物，新聞，搞笑，生活）等21類；根據(jù)這21個興趣類提取每個興趣類所對應(yīng)的關(guān)鍵詞，每個興趣類會對應(yīng)多個關(guān)鍵詞（特征項(xiàng)）。

Fig.1 User interestmodel圖1 用戶興趣模型

經(jīng)數(shù)據(jù)處理后形成的用戶興趣向量為（美食，教育，娛樂，…，搞笑，生活），每個興趣類對應(yīng)的特征項(xiàng)代表用戶的標(biāo)簽和微博文本信息。對于用戶i來說，其興趣可用圖2所示。

Fig.2 Structureof interest-characteristics圖2 興趣類-特征項(xiàng)結(jié)構(gòu)圖

用戶i的興趣向量可以描述為：

式中，ILi是用戶i的長期興趣向量；ISi是用戶i的短期興趣向量。由于用戶i的微博文本信息中包含多個特征項(xiàng)，則ILi和ISi用如下向量表示：

其中，wLi是用戶i的長期興趣度向量；wSi是用戶i的短期興趣度向量。

此時用戶興趣向量和興趣度向量分別為：

由上文分析可知，用戶的短期興趣由微博文本信息中的興趣類對應(yīng)的特征項(xiàng)表征，長期興趣通過用戶標(biāo)簽信息來表征。本文將依次介紹用戶長期興趣的修正、更新過程，用戶興趣的度量方法和用戶間的相似性計(jì)算。

2.1 用戶長期興趣的修正

微博數(shù)據(jù)包含每個用戶的關(guān)注列表和標(biāo)簽信息，用戶在注冊時所填寫的用戶標(biāo)簽可以是平臺推薦的標(biāo)準(zhǔn)標(biāo)簽，如星座、運(yùn)動等，也可以個性化的填寫，比如宅男、愛睡覺等。通過分詞、提取、歸類后，用戶標(biāo)簽中同興趣類的多個特征項(xiàng)相互合并，只保留一個特征項(xiàng)代表其對應(yīng)的興趣類，則用戶的長期興趣就由這些不同的特征項(xiàng)構(gòu)成。

通常微博用戶都會對他人進(jìn)行關(guān)注，一旦用戶關(guān)注了其他用戶，就可以獲取到關(guān)注用戶的微博消息，這相當(dāng)于用戶訂閱其關(guān)注用戶的微博內(nèi)容，并對這些微博內(nèi)容感興趣，因此被關(guān)注的用戶博文會反映用戶的興趣。

假設(shè)任意一個用戶i的長期興趣向量為ILi=(ILi1,ILi2,…,ILim)，共有m個興趣類，即m個興趣特征項(xiàng)。用戶i的關(guān)注列表是X={x1,x2,…,xv}，共有v個用戶，將這v個用戶的標(biāo)簽內(nèi)容求并集，該并集即是用戶i的關(guān)注列表標(biāo)簽集，標(biāo)簽集內(nèi)元素的個數(shù)是：

本文的長期興趣是通過關(guān)注列表的推薦和短期興趣的反饋得到的。首先對分類完成以后的所有用戶標(biāo)簽進(jìn)行統(tǒng)計(jì)，原始數(shù)據(jù)經(jīng)過處理和分類以后，共有48 475個微博用戶，184 201個標(biāo)簽，平均每個用戶擁有4個標(biāo)簽，因此本文取推薦標(biāo)簽數(shù)為4。統(tǒng)計(jì)關(guān)注列表X中標(biāo)簽集的興趣類，將出現(xiàn)頻率最高的4個興趣類作為關(guān)注列表推薦，即推薦興趣向量為INi=(INi1,INi2,INi3,INi4)，其中INi1在X內(nèi)出現(xiàn)的頻率最高?，F(xiàn)有用戶i的長期興趣向量ILi及其內(nèi)的隨機(jī)興趣類j，

用ILij表示；短期興趣向量ISi；關(guān)注列表推薦向量INi及其內(nèi)的隨機(jī)興趣類k，用INik表示。

算法1用戶長期興趣修正算法

輸入：用戶長期興趣向量ILi及隨機(jī)興趣類ILij

用戶短期興趣向量ISi及隨機(jī)興趣類ISik

關(guān)注列表推薦興趣類INi

輸出：修正后的長期興趣向量ILi′

1.初始化 ILi′，令 ILi′=ILi

如果ILi為空，用INi初始化ILi′

2.如果ILi′元素?cái)?shù)量小于4

若 ILij∈ ISi，則將 ILij保留到 ILi′

若 ILij∈ INi，則將 ILij保留到 ILi′

若以上兩者情況都不滿足，將INi中出現(xiàn)頻率最高的興趣類添加到ILi′，直到ILi′元素?cái)?shù)量等于4

3.如果ILi元素?cái)?shù)量等于4，不做修正

4.如果ILi元素?cái)?shù)量大于4

若 INik∈ ILi，則將 INik保留到 ILi′

若 ILij∈ INi，則將 ILij保留到 ILi′

若 ILij∈ ISi，則將 ILij保留到 ILi′

若以上條件均不滿足，則將INik保留到ILi′，將ILij刪除

5.返回 ILi′

通過上述用戶的長期興趣修正算法可知，修正后用戶的長期興趣向量為 ILi′=(ILi1′,ILi2′,…,ILim′)。此時用戶長期興趣的興趣類數(shù)量為mi′。

2.2 用戶興趣的更新

用戶的長短期興趣都是動態(tài)變化的，在微博數(shù)據(jù)持續(xù)的時間段內(nèi)，如果短期興趣的某些興趣類持續(xù)活躍，能更充分地反映用戶在這段時間內(nèi)的興趣，則動態(tài)調(diào)整短期興趣為長期興趣；如果長期興趣的某些興趣類在微博文本數(shù)據(jù)和關(guān)注列表中長時間沒有體現(xiàn)，表明用戶可能對此不再感興趣，則在用戶興趣修正中將之除去。本節(jié)將詳細(xì)介紹用戶興趣的更新過程。

假設(shè)用戶i的微博文本中的短期興趣向量為ISi=(ISi1,ISi2,…,ISin)，對于任一興趣類j的權(quán)重為：

式中，N′是用戶i的微博文本中所有興趣類出現(xiàn)的頻率和；nj′表示興趣類j在用戶i的微博文本中出現(xiàn)的頻率。

從式（7）可以得到每個短期興趣類的權(quán)重，對短期興趣向量按權(quán)重從大到小進(jìn)行排序形成新的短期興趣向量 ISi′=(ISi1′,ISi2′,…,ISin′)，其對應(yīng)的權(quán)值向量為wSi′=(wSi1′,wSi2′,…,wSin′)，其中 wSi1′＞ wSi2′＞ … ＞ wSin′，此時用戶的長期興趣向量為修正過后的興趣向量集ILi′。

算法2用戶興趣更新算法

輸入：ILi′=(ILi1′,ILi2′,…,ILim′)及其權(quán)重 wLi′ISi′=(ISi1′,ISi2′,…,ISin′)及其權(quán)重 wSi′

輸出：ILi″，ISi″

1.for j=1 to n

若 ISij′∈ ILi′，則 ISi′刪除 ISij′

end for

2.for x=1 to m

若 ILix′? ISi′且 wSij′＞ wLix′

則 ISi′刪除 ISij′，ILi′添加 ISij′

3.若 ILix′=ISiq′(1 ≤ q≤n,j≠ q)

且 wSij′＞ wLix′+wSiq′

則 ISi′刪除 ISij′，ILi′添加 ISij′

end for

4.更新長、短期興趣向量

輸出 ILi″，ISi″

上述算法對用戶長期興趣和短期興趣進(jìn)行更新，最后形成新的長期興趣向量ILi″和短期興趣向量 ISi″。

2.3 用戶長短期興趣的度量

根據(jù)用戶微博文本的歷史信息來構(gòu)建用戶的興趣度計(jì)算模型，對于長期興趣本文認(rèn)為用戶i對其mi′個興趣類的偏好程度，可以通過標(biāo)簽集X內(nèi)標(biāo)簽出現(xiàn)的頻率來表征。以興趣類在關(guān)注列表中出現(xiàn)的頻率為基礎(chǔ)度量用戶i對其標(biāo)簽中的興趣類j的興趣度為：

對于用戶的短期興趣，歷史信息越接近當(dāng)前時刻越能表示用戶的當(dāng)前興趣，反之越不能體現(xiàn)用戶興趣，這種現(xiàn)象類似于人類行為動力學(xué)中的興趣衰減函數(shù)。因此，本文通過興趣衰減函數(shù)來刻畫用戶的短期興趣。另外用戶對某個興趣類關(guān)注越多表明用戶對該類別的興趣越明顯，本文視這一情況為重復(fù)記憶，記憶的次數(shù)越多，記憶總量越多，單次記憶的增量越少，直至穩(wěn)定狀態(tài)。衰減函數(shù)表達(dá)式為：

式中，k是衰減速率。假設(shè)用戶在t0時刻的興趣度為P(t0)，根據(jù)興趣衰減函數(shù)從t0到t時刻用戶的興趣度降低到：

其中，kt是在時間段t0到t內(nèi)的興趣衰減速率，衰減函數(shù)體現(xiàn)了在時間段[t0,t]內(nèi)記憶量隨時間的變化范圍。用戶在一段時間內(nèi)可能會多次發(fā)表或者轉(zhuǎn)發(fā)某一興趣類，多次重復(fù)記憶該興趣類，因此本文提出多階量化短期興趣的方法。對于某興趣類的一個特征項(xiàng)來說，微博在不同時刻多次發(fā)布了該特征項(xiàng)，發(fā)布時刻即為重復(fù)記憶的時刻。

從圖3中可以看出，用戶在每個時間段內(nèi)的興趣都會衰減，在不同的時段內(nèi)用戶具有不同的衰減曲率。如果相鄰時間段的興趣度初始值和衰減速率之間具有聯(lián)系，就可以度量當(dāng)前的用戶興趣。下面將介紹初始值Pn和衰減速率kn計(jì)算方法。在任意時刻，用戶的興趣度為：

Fig.3 Multi-orderquantization forshort-term interest圖3 多階量化短期興趣度

從圖3中可以看出，第n階段的初始時刻，興趣度Pn為：

式中，Hn是第n次記憶增加的記憶量；Mn是前n次剩余記憶量總和。Mn可以由上一階段的興趣度量化公式得出：

用戶在重復(fù)記憶某一興趣類的時候，單次的記憶量會不斷減少，記憶總量會不斷增大，但是增長趨勢漸近平緩最終收斂。本文定義Hn為：

此時興趣度Pn可以表示為：

由上述公式可知Pn和Pn-1之間的關(guān)系，為了得出任意時刻用戶的興趣度還需要得出kn和kn-1之間的關(guān)系。本文將相鄰的興趣衰減速率線沿著橫軸和豎軸進(jìn)行平移，使得兩段曲線具有相同的初始值，該過程如圖4所示。

Fig.4 Adjustmentof interest-forgetting rate圖4 興趣遺忘速率的調(diào)整

圖4中y是tn-1到tn的時間段內(nèi)相鄰兩條興趣度曲線間的衰減差值，可表示為：

由此可推出kn和kn-1之間的關(guān)系：

y值的上限是：

由圖4可知，y的取值與時間間隔成正相關(guān)，因此設(shè)置一個惰性因子α，表示二者的關(guān)系，時間間隔越大，α的取值越大。將ymax劃分為α段，α反映了在不同時刻的重復(fù)記憶對遺忘速率調(diào)整的程度。

對于αn-1的取值定義為：

式中，α0是惰性因子的初始值。計(jì)量時間以天為單位，若未滿一天按一天計(jì)算。

基于衰減函數(shù)的多階量化短期興趣度方法，通過初始值可以得到任意時刻的P、k和α，進(jìn)而可以計(jì)算用戶的短期興趣度，得到用戶的短期興趣度向量。

2.4 用戶相似性計(jì)算

通過上文對用戶興趣的修正和更新以后，分別得到新的興趣向量ILi″和ISi″，興趣度向量wLi″和wSi″。則用戶i的興趣向量和興趣度向量是：

得到Ii″和wi″后，再根據(jù)（美食，教育，娛樂，…，搞笑，生活）來調(diào)整并統(tǒng)一表征用戶興趣，同樣與用戶興趣度向量一一對應(yīng)，若用戶不包含某項(xiàng)興趣類，則在興趣度向量中對應(yīng)的興趣度值為0。綜上所述，可以得到具有相同的興趣度向量和不同的興趣度向量的各個用戶。

進(jìn)一步，通過計(jì)算用戶間的興趣相似性來度量用戶關(guān)系，若相似性值較大，則預(yù)測用戶之間產(chǎn)生關(guān)系的可能性較大；反之，則可能性較小。用戶間的興趣相似性是以用戶興趣度向量為基礎(chǔ)，使用余弦相似性指標(biāo)來計(jì)算任意兩個用戶的興趣相似性，公式為：

3 實(shí)驗(yàn)結(jié)果和驗(yàn)證

3.1 微博數(shù)據(jù)處理

本文使用北京理工大學(xué)的網(wǎng)絡(luò)搜索挖掘與安全實(shí)驗(yàn)室公布的新浪微博用戶數(shù)據(jù)[13]，來驗(yàn)證本文算法的性能。數(shù)據(jù)集包括72 910條用戶的個人信息和285MB的微博數(shù)據(jù)。微博用戶個人信息的原始數(shù)據(jù)包括用戶ID、地區(qū)、用戶名、關(guān)注（關(guān)注用戶數(shù)）、標(biāo)簽、關(guān)注列表等字段；用戶微博文本信息是指用戶發(fā)表和轉(zhuǎn)發(fā)的微博，包括用戶ID、回復(fù)數(shù)、評論數(shù)和微博產(chǎn)生的時間。原始數(shù)據(jù)如表1所示。

在處理數(shù)據(jù)之前需要對數(shù)據(jù)進(jìn)行預(yù)處理，根據(jù)本文算法的實(shí)際需求，去掉數(shù)據(jù)集內(nèi)關(guān)注列表數(shù)小于10個或者發(fā)表的微博數(shù)小于10條的不活躍用戶，因?yàn)樵擃愑脩舻年P(guān)注用戶和微博內(nèi)容較少，很難獲取到準(zhǔn)確的興趣數(shù)據(jù)，研究意義不大。經(jīng)預(yù)處理后得到48 475個用戶和1 127 164個用戶關(guān)系。由表2可知，用戶的微博數(shù)據(jù)雜亂，語義模糊，為了準(zhǔn)確提取用戶興趣，首先需要對微博數(shù)據(jù)進(jìn)行提取和分詞。本文采用基于漢語詞法分析系統(tǒng)最新版本的“NLPIR漢語分詞系統(tǒng)”，用Java重寫并將完全開源的漢語分詞系統(tǒng)Ansj作為數(shù)據(jù)的分詞工具。Ansj是Java編程，應(yīng)用于自然語言處理的準(zhǔn)確、高效、自由的中文分詞工具，可用于人名、地名、組織機(jī)構(gòu)名的識別和關(guān)鍵詞提取等領(lǐng)域。在Eclipse中導(dǎo)入ansj-seg.jar和ansj-tree-split.jar這兩個Java架包，其中ansj-seg是引用中文語料庫，ansj-tree是分詞模型。得到的分詞效果如表2所示。

Table1 M icroblog dataofusers表1用戶的微博數(shù)據(jù)

Table2 Resultsof participles表2 分詞結(jié)果

對微博數(shù)據(jù)分詞之后，去掉數(shù)據(jù)中的一些連詞或者無意義詞，如“的”，提取關(guān)鍵詞，如“睡覺”、“跑步”、“投資”等。根據(jù)用戶興趣向量（美食，教育，娛樂，…，搞笑，生活）對用戶分類以后，將每個用戶標(biāo)簽內(nèi)的特征項(xiàng)進(jìn)行同興趣類合并，得到不同的興趣類。通過分類和數(shù)據(jù)提取得到用戶的標(biāo)簽、關(guān)注列表信息和微博文本信息，如表3所示。

表3中，字段uid是用戶ID號；suid表示源用戶的ID號；tuid表示目的用戶的ID號，并且suid關(guān)注tuid；label是用戶標(biāo)簽；time是用戶發(fā)表或轉(zhuǎn)發(fā)微博的時間；topic是提取一個微博的主題。微博用戶既可以雙向關(guān)注也可以單向關(guān)注，因?yàn)楸疚乃惴ǚ治龅闹攸c(diǎn)是用戶的關(guān)注列表，所以在分析微博網(wǎng)絡(luò)時，考慮的用戶關(guān)系都是單向的。得到該網(wǎng)絡(luò)的一些關(guān)鍵數(shù)據(jù)如表4所示。

Table3 Processedm icroblog data表3 處理后的微博

Table 4 Data of localnetwork structure in Sinam icroblog表4 新浪微博局部網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)

從表4可知，微博網(wǎng)絡(luò)的用戶量較大，對應(yīng)的用戶關(guān)系數(shù)量相對較少，表明網(wǎng)絡(luò)結(jié)構(gòu)較為稀疏，聚類系數(shù)指標(biāo)也可以反映該結(jié)論；該網(wǎng)絡(luò)的平均度和平均路徑長度這兩項(xiàng)指標(biāo)反映出用戶之間的交流和互動比較方便；網(wǎng)絡(luò)節(jié)點(diǎn)的度分布較為均勻。圖5所示為新浪微博用戶的度分布。

Fig.5 Degree distribution of Sinam icroblog users圖5 新浪微博用戶的度分布

由圖5的總體趨勢可看出，當(dāng)關(guān)注數(shù)小于200時，微博用戶較為集中；當(dāng)用戶的關(guān)注數(shù)大于200時，用戶數(shù)量較少，但是用戶度分布范圍較大，體現(xiàn)了社交網(wǎng)絡(luò)的長尾效應(yīng)。

3.2 實(shí)驗(yàn)結(jié)果分析

本文提出的基于用戶興趣相似性的關(guān)系預(yù)測算法使用AUC和Precision評價指標(biāo)驗(yàn)證預(yù)測效果。將網(wǎng)絡(luò)中實(shí)際存在的用戶關(guān)系集E隨機(jī)分為95%的訓(xùn)練集ET和5%的測試集EP。用戶興趣是根據(jù)用戶的標(biāo)簽、微博文本內(nèi)容和關(guān)注列表獲取的，用戶的興趣被分為長期興趣和短期興趣。

圖6表示用戶標(biāo)簽數(shù)的分布情況，其中微博用戶添加標(biāo)簽的上限是10個。從圖6中可以得出，不存在標(biāo)簽的用戶在數(shù)據(jù)集內(nèi)所占比例高達(dá)45.73%，低于存在標(biāo)簽的用戶數(shù)量，因此可以用標(biāo)簽和關(guān)注列表來表征長期興趣。對于存在標(biāo)簽的用戶來說，標(biāo)簽數(shù)量分布較為不均勻，其中標(biāo)簽數(shù)小于4的用戶較多，大于4的用戶較少。這表明有一些用戶可能不知道添加標(biāo)簽或者不愿意去嘗試添加標(biāo)簽，導(dǎo)致無法準(zhǔn)確地描述用戶興趣；另一些用戶可能嘗試性地體驗(yàn)添加幾個標(biāo)簽，或者特意盡可能多地添加標(biāo)簽直到上限，從而充分地展示自己，但存在虛假或者不活躍興趣類的問題。因此，通過關(guān)注列表修正用戶興趣對于準(zhǔn)確描述用戶興趣，進(jìn)而提高用戶關(guān)系預(yù)測的準(zhǔn)確性具有重要的作用。

Fig.6 Distribution of thenumberofusersw ith thetag圖6 用戶數(shù)量隨標(biāo)簽的分布

用戶的短期興趣是由微博文本內(nèi)容表征的，短期興趣度需要經(jīng)過多階量化的方法獲取。在求短期興趣度時，有3個參數(shù)需要確定，即興趣度的初始值P0、衰減曲率的初始值k0和惰性因子α0。本文使用衰減函數(shù)進(jìn)行多階量化短期興趣的興趣度，為了便于計(jì)算和分析，設(shè)置初始興趣度P0=1.0，初始衰減速率k0=1.0。惰性因子α反映用戶重復(fù)記憶的頻率，影響著用戶的短期興趣度，但是因?yàn)椴煌脩魧ν慌d趣類具有不同的記憶頻率，為了降低計(jì)算的復(fù)雜性，設(shè)置一個初始定值α0。為了獲取α0，本節(jié)設(shè)置不同取值，通過多階量化的方式度量用戶的微博文本內(nèi)容，使用余弦函數(shù)計(jì)算用戶間的短期興趣相似性，最后通過AUC和Precision指標(biāo)進(jìn)行評價，經(jīng)過多次計(jì)算取得的平均值如圖7所示。

Fig.7 Impactof inertia facton forecasting resultsof short-term interestsim ilarity圖7 惰性因子對短期興趣相似性預(yù)測結(jié)果的影響

從圖7中可以看出，隨著初始惰性因子α0取值的增加，算法的AUC和Precision值逐漸變大，這是因?yàn)樵诙栊砸蜃虞^小時，重復(fù)記憶增加的記憶量變化較大，調(diào)整效果較明顯；在取值為6時，模型的AUC和Precision值最大，預(yù)測效果最好；當(dāng)取值大于6時，AUC和Precision值略有下降直至穩(wěn)定。這是由基于短期興趣相似性的預(yù)測算法中用戶對各個興趣類的記憶量具有衰減和趨于收斂的特性決定的。

為了驗(yàn)證通過多階量化的方式度量短期興趣的效果，本文基于微博文本內(nèi)容分別利用多階量化、TF-IDF和遺忘曲線方法度量用戶的興趣度，并通過余弦指標(biāo)計(jì)算用戶間的相似性。這3種預(yù)測算法的AUC和Precision值對比結(jié)果如圖8。

Fig.8 Comparison of differentprediction algorithms based onm icroblog contents圖8 基于微博文本內(nèi)容的預(yù)測算法的效果對比

從圖8中可以看出，基于多階量化短期興趣的預(yù)測算法的AUC和Precision值都要優(yōu)于基于遺忘曲線的預(yù)測算法[14]和基于IF-TDF的預(yù)測算法[15]，表明考慮用戶興趣變化并進(jìn)行多階量化，能夠較為有效地提高用戶關(guān)系預(yù)測的準(zhǔn)確性。

本文認(rèn)為用戶的短期興趣能夠轉(zhuǎn)化成長期興趣，長期興趣需要短期興趣的反饋來修正。用戶興趣的更新和修正，表明用戶的長短期興趣之間不但具有一定的差異性，也具有緊密的關(guān)聯(lián)性。為了驗(yàn)證用戶的長期興趣和短期興趣的關(guān)聯(lián)性，本文繼續(xù)對所有用戶標(biāo)簽、微博數(shù)和關(guān)注用戶數(shù)進(jìn)行統(tǒng)計(jì)，得到圖9。

從圖9中可以看出，用戶的標(biāo)簽數(shù)量在某種程度上能夠反映出用戶微博的活躍程度。標(biāo)簽越多的用戶，其發(fā)布的微博平均數(shù)量也越多，關(guān)注列表的用戶越多；微博和關(guān)注用戶的數(shù)量走勢雖然有一些波動，但整體上也呈現(xiàn)上升趨勢，這個現(xiàn)象表明用戶添加標(biāo)簽的數(shù)量與其微博活躍程度呈現(xiàn)正相關(guān)關(guān)系。因此本文認(rèn)為采用標(biāo)簽表征的長期興趣和微博文本內(nèi)容表征的用戶短期興趣具有相同的變化趨勢，體現(xiàn)了二者之間的關(guān)聯(lián)性。

Fig.9 Correlation between numberof tag and interestofusers圖9 標(biāo)簽數(shù)與用戶興趣關(guān)聯(lián)性

Fig.10 Contrastof interestdegreebetween long-term interestand short-term interest圖10 長短期興趣的興趣度對比

從圖10中可以看出，用戶長短期興趣度具有較大的差異性。用戶對每個興趣類的興趣度都較低，雖然長短期興趣對各興趣類具有不同的偏好程度，但長期興趣度在整體上低于短期興趣度。從用戶興趣的持久性來看，教育、音樂、新聞、星座等長期興趣類的興趣度高于短期興趣。在數(shù)據(jù)持續(xù)的這段較短的時間內(nèi)，用戶對科技、娛樂和購物等興趣類更感興趣。通過上述對用戶長短期興趣的關(guān)聯(lián)性和差異性的分析可知，本文將用戶興趣分為長短期興趣，對興趣的度量和整體更新具有合理性。

為了驗(yàn)證本文用戶興趣更新的效果，對比分析本文的預(yù)測算法和在本文算法的基礎(chǔ)上忽略用戶興趣更新的預(yù)測算法，得到的AUC和Precision值是通過100次實(shí)驗(yàn)得到的平均值。

從圖11中可以看出，本文的預(yù)測算法相比較于忽略用戶興趣更新預(yù)測算法的AUC值高1.647%，Precision值高0.932%。由實(shí)驗(yàn)結(jié)果可知，雖然用戶的微博文本內(nèi)容中包含的信息量較大，但是微博內(nèi)容特別雜亂，或者由于一些不可預(yù)知的原因，導(dǎo)致興趣類容易發(fā)生改變。因此考慮用戶的短期興趣類向長期興趣的轉(zhuǎn)換和長期興趣類的消失或沉默，準(zhǔn)確地細(xì)化用戶興趣的狀態(tài)并及時更新用戶興趣，能夠降低未知因素的干擾，得到較為穩(wěn)定的用戶興趣，提高用戶關(guān)系預(yù)測的準(zhǔn)確性。

Fig.11 Impactof interestupdating ofuserson forecasting results圖11用戶興趣更新對預(yù)測結(jié)果的影響

為了驗(yàn)證本文算法的預(yù)測效果，選取4種構(gòu)建用戶興趣的算法與本文的興趣相似性算法進(jìn)行對比分析。這4種算法分別是經(jīng)典算法TF-IDF和LDA[16]，基于隱含語義動態(tài)分析用戶興趣的DPLSA算法[17]，融合網(wǎng)絡(luò)結(jié)構(gòu)和微博內(nèi)容的TFP算法[18]。通過這4種算法計(jì)算用戶間的相似性，并通過AUC和Precison評價指標(biāo)對這些算法進(jìn)行評價，得到的預(yù)測效果如圖12所示。

從這5類算法的預(yù)測效果上來看，本文算法的預(yù)測效果最好，TFP算法次之，TF-IDF算法的效果最差。本文算法動態(tài)考慮了用戶興趣變化，并通過關(guān)注列表推薦興趣偏好，也在一定程度上融合了社交網(wǎng)絡(luò)的局部結(jié)構(gòu)特征，因此預(yù)測效果較為明顯。TFP算法融合了網(wǎng)絡(luò)結(jié)構(gòu)和微博內(nèi)容信息，從整體網(wǎng)絡(luò)結(jié)構(gòu)和用戶興趣兩方面考慮用戶的相似性，但是因?yàn)樾吕宋⒉γ總€用戶信息有嚴(yán)格的限制，難以獲取全部的結(jié)構(gòu)信息。另外該算法并未考慮用戶興趣的變化，影響了預(yù)測精度。DPLSA算法采用固定的時間窗口跟蹤用戶興趣的變化，表征用戶興趣不太準(zhǔn)確。TF-IDF和LDA算法都是通過語料庫來提取關(guān)鍵字，導(dǎo)致很多與興趣無關(guān)的關(guān)鍵字融入在興趣集內(nèi)，從而使得算法的預(yù)測精度較低。

綜上所述，本文對比并分析了用戶長期興趣和短期興趣之間的差異性和關(guān)聯(lián)性，并采用不同的方式度量、修正和更新用戶興趣。實(shí)驗(yàn)仿真結(jié)果表明，本文基于用戶興趣相似性的用戶關(guān)系預(yù)測算法設(shè)計(jì)合理有效，能夠準(zhǔn)確地描述用戶興趣，并提高用戶間關(guān)系預(yù)測的準(zhǔn)確性。

4 結(jié)束語

本文分析了目前基于用戶興趣的關(guān)系預(yù)測算法忽略用戶興趣具有持久性和易變性的特征，導(dǎo)致無法準(zhǔn)確描述用戶興趣，以及用戶關(guān)系預(yù)測準(zhǔn)確性低的問題。針對該問題，本文構(gòu)建了基于微博用戶興趣相似性的預(yù)測模型，根據(jù)關(guān)注列表推薦和短期興趣反饋來修正用戶的長期興趣，通過興趣類的長短期興趣轉(zhuǎn)換實(shí)現(xiàn)用戶興趣的更新；采用基于興趣衰減函數(shù)的多階量化方法計(jì)算短期興趣度，基于興趣類的頻率統(tǒng)計(jì)計(jì)算長期興趣度；最后通過余弦相似性計(jì)算用戶的興趣相似度來預(yù)測用戶關(guān)系。通過實(shí)驗(yàn)證明，本文針對用戶長短期興趣采用不同方式進(jìn)行度量，并對用戶興趣進(jìn)行修正、更新，能夠準(zhǔn)確地描述用戶興趣，對用戶關(guān)系預(yù)測具有較好的預(yù)測效果。

[1]Liu Zhiyuan,Shi Chuan,Sun Maosong.FolkDiffusion:a graph-based tag suggestionmethod for folksonom ies[C]//LNCS 6458:Proceedings of the 6th Asia Information Retrieval Societies Conference,Taipei,China,Dec 1-3,2010.Berlin,Heidelberg:Springer,2010:231-240.

[2]Backstrom L,Sun E,Marlow C.Findme if you can:improving geographicalpredictionw ith socialand spatialproximity[C]//Proceedings of the 19th International Conference on World WideWeb,Raleigh,USA,Apr 26-30,2010.New York:ACM,2010:61-70.

[3]Yang Changchun,Yang Jing,Ding Hong.A new friends recommendation algorithm for Sina m icroblogging[J].Computer Application and Software,2014,31(7):255-258.

[4]Wang Guoxia,Liu Heping.Survey of personalized recommendation system[J].Computer Engineering and Applications,2012,48(7):66-76.

[5]Zhang Shanliang,Zhou Yan.Timeweighted social networks link prediction algorithm based on random walk[J].Computer Applicationsand Software,2014,31(7):28-30.

[6]Wu Chengchao,WangWeiping.PLSA collaborative filtering algorithm incorporated w ith user interest change[J].Computer SystemsApplications,2014,23(5):162-166.

[7]Sun Jingyu,Li Xianhua,Yu Xueli.An improved item-based collaborative filtering algorithm w ith distinction between user's long and short interests[J].Journalof Zhengzhou University:Natural Science Edition,2010,42(2):35-38.

[8]Sun Wei.Interestmining and modeling form icro-bloggers ofmicro-blog[D].Dalian:Dalian University of Technology,2012.

[9]Guo Jinli.Complex networks and dynam ic evolutionmodel ofhuman behavior[M].Beijing:Science Press,2013:204-206.

[10]Qiu Jun.Research on user interestmodeling based onmicroblog social network[D].Shanghai:Shanghai Jiao Tong University,2013.

[11]Qiao Xiuquan,Yang Chun,LiXiaofeng,etal.A trust calculating algorithm based on social networking service users'context[J].Chinese Journal of Computers,2011,34(12):2403-2413.

[12]Li Feng,Pei Jun,You Zhiyang.Adaptive user interestmodel based on the implicit feedback[J].Computer Engineering and Applications,2008,44(9):76-79.

[13]Zhang Huaping.Sinam icroblog users'data[EB/OL].(2014-07-08)[2016-04-06].http://www.datatang.com/org/6880.

[14]Li Kechao,Liang Zhengyou.Exponential forgetting collaborative filtering recommendation algorithm incorporated w ith user interest change[J].Computer Engineering and Applications,2011,47(13):154-156.

[15]Pramono L H,Rohman A S,Hindersah D H.Modified weighting method in TF-IDF algorithm for extracting user topic based on email and socialmedia in integrated digital assistant[C]//Proceedings of the 2013 Joint International Conference on Rural Information&Communication Technology and Electric-Vehicle Technology,Bandung,Indonesia,Nov 26-28,2013.Piscataway,USA:IEEE,2013:1-6.

[16]Bian Jinqiang,Jiang Zengru,Chen Qian.Research onmultidocument summarization based on LDA topic model[C]//Proceedings of the 6th International Conference on Intelligent Human-Machine Systems and Cybernetics,Hangzhou,China,Aug 26-27,2014.Piscataway,USA:IEEE,2014:113-116.

[17]Yan Meng,Zhang Xiaohong,Yang Dan,etal.A component recommender for bug reports using discrim inative probabilitylatent semantic analysis[J].Information and Software Technology,2016,73:37-51.

[18]Shang Yanm in,Zhang Peng,Cao Yanan.A new interestsensitive and network-sensitivemethod for user recommendation[J].Journalon Communication,2015,36(2):121-129.

附中文參考文獻(xiàn):

[3]楊長春,楊晶,丁虹.一種新的新浪微博好友推薦算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(7):255-258.

[4]王國霞,劉賀平.個性化推薦系統(tǒng)綜述[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(7):66-76.

[5]張珊靚,周晏.基于隨機(jī)游走的時間加權(quán)社會網(wǎng)絡(luò)鏈接預(yù)測算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(7):28-30.

[6]吳成超,王衛(wèi)平.考慮用戶興趣變化的概率隱語意協(xié)同推薦算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(5):162-166.

[7]孫靜宇,李鮮花,余雪麗.區(qū)分用戶長短期興趣的IBCF改進(jìn)算法[J].鄭州大學(xué)學(xué)報:理學(xué)版,2010,42(2):35-38.

[8]孫威.微博用戶興趣挖掘與建模研究[D].大連:大連理工大學(xué),2012.

[9]郭進(jìn)利.復(fù)雜網(wǎng)絡(luò)和人類行為動力學(xué)演化模型[M].北京:科學(xué)出版社,2013:204-206.

[10]仇鈞.基于微博社會網(wǎng)絡(luò)的用戶興趣模型研究[D].上海:上海交通大學(xué),2013.

[11]喬秀全,楊春,李曉峰,等.社交網(wǎng)絡(luò)服務(wù)中一種基于用戶上下文的信任度計(jì)算方法[J].計(jì)算機(jī)學(xué)報,2011,34(12):2403-2413.

[12]李峰,裴軍,游之洋.基于隱式反饋的自適應(yīng)用戶興趣模型[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(9):76-79.

[14]李克潮,梁正友.適應(yīng)用戶興趣變化的指數(shù)遺忘協(xié)同過濾算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(13):154-156.

[18]尚燕敏,張鵬,曹亞男.融合鏈接拓?fù)浣Y(jié)構(gòu)和用戶興趣的朋友推薦方法[J].通信學(xué)報,2015,36(2):121-129.

黃宏程（1979—），男，河南南陽人，2006年于重慶郵電大學(xué)獲得碩士學(xué)位，現(xiàn)為博士研究生，重慶郵電大學(xué)通信與信息工程學(xué)院副教授，CCF會員，主要研究領(lǐng)域?yàn)閺?fù)雜網(wǎng)絡(luò)，信息處理，大數(shù)據(jù)技術(shù)與應(yīng)用等。

LUWeijin was born in 1989.He is an M.S.candidate at School of Communication and Information Engineering,Chongqing University of Postsand Telecommunications.His research interest ispersonalized recommendation.

陸衛(wèi)金（1989—），男，江蘇南通人，重慶郵電大學(xué)通信與信息工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閭€性化推薦。

HU M inwasborn in 1971.She received theM.S.degree from Chongqing University of Postsand Telecommunications in 2002.Now she isan associate professor and M.S.supervisor at Schoolof Communication and Information Engineering,Chongqing University of Postsand Telecommunications.Her research interests includew ireless communication,communication network system and protocol,etc.

胡敏（1971—），女，重慶人，2002年于重慶郵電大學(xué)獲得碩士學(xué)位，現(xiàn)為重慶郵電大學(xué)通信與信息工程學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)闊o線通信，通信網(wǎng)體系與協(xié)議等。

WEIQing was born in 1990.He is an M.S.candidate at School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications.His research interests include communication network system and big dataanalysis,etc.

魏青（1990—），男，河南信陽人，重慶郵電大學(xué)通信與信息工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)橥ㄐ啪W(wǎng)體系，大數(shù)據(jù)分析等。

User Relationships Prediction Algorithm w ith Interest Sim ilarity M easurement*

HUANG Hongcheng1,2+,LUWeijin1,HUM in1,WEIQing1
1.School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,China
2.Collegeof Computer Science,Chongqing University,Chongqing 400044,China

For the problem that current researchers only pay their attention to the changeability and ignore the durability when they study user interest inm icroblog,this paper proposes a user relationship prediction algorithm based on interest sim ilarity.In this algorithm,interests are divided into two types:long-term interest characterized by labels and short-term interestcharacterized by texts,and a frequency statisticsandmulti-orderquantizationmethod isused to measure and update the degree of user interestaccording to the features of the interest.The sim ilarity between user interests is computed by themethod of cosine sim ilarity which is used to predictuser relationship.Results show that the proposed algorithm can accurately describe user's interest,and improve the precision of user relationship prediction.

user interest;sim ilarity;multistagequantization;relationship prediction

gcheng was born in 1979.He

the M.S.degree in communication and information engineering from Chongqing University of Posts and Telecommunications in 2006.Now he is an associate professor at School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,and the member of CCF.His research interests include complex network,information processing,big data technology and application,etc.

A

：TP391

*The National Natural Science Foundation of China under Grant No.61401051(國家自然科學(xué)基金);the Foundation and Frontier Research Projectof Chongqing Science and Technology Comm ission under GrantNo.cstc2014jcyjA 40039(重慶市科委基礎(chǔ)和前沿研究項(xiàng)目);the Science and Technology Research Projectof Chongqing Municipal Education Comm ittee under Grant No.KJ1400402(重慶市教委科學(xué)技術(shù)研究項(xiàng)目).

Received 2016-06,Accepted 2016-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1045.012.htm l

摘 要：針對目前研究微博用戶興趣變化時，只考慮用戶興趣的易變性而忽略了用戶興趣持久性的問題，提出了基于用戶興趣相似性的用戶關(guān)系預(yù)測算法。將用戶興趣分為短期興趣和長期興趣，用戶的文本信息表征為短期興趣，用戶的標(biāo)簽表征為長期興趣。根據(jù)長短期興趣的特征，采用頻率統(tǒng)計(jì)和多階量化的方法度量用戶興趣度并更新用戶興趣狀態(tài)。最后通過余弦相似性指標(biāo)計(jì)算用戶間的興趣相似度來預(yù)測用戶關(guān)系。實(shí)驗(yàn)結(jié)果表明，該算法能夠準(zhǔn)確描述用戶興趣，提高用戶關(guān)系預(yù)測的準(zhǔn)確性。