唐昌宏， 劉 月

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州　350116；2. 福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室， 福建 福州　350116)

?

張量分解在用戶影響力度量中的應(yīng)用

唐昌宏1, 2， 劉 月1

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州350116；2. 福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室， 福建 福州350116)

摘要：提出一種基于張量分解的有影響力用戶識別算法. 該算法首先構(gòu)建基于查詢主題的用戶交互關(guān)系張量， 接著利用張量分解算法對用戶行為進(jìn)行預(yù)測， 最后融合各種交互關(guān)系和用戶的主題信息給出用戶影響力的綜合評判. 實(shí)驗(yàn)結(jié)果表明， 與非負(fù)矩陣分解相比， 張量分解的挖掘精度提升了約10%， 而與PageRank相比， 張量分解的挖掘精度提升了約20%.

關(guān)鍵詞：用戶影響力； 主題相關(guān)度； 互關(guān)系； 張量； 社交媒介

0引言

社會影響力已成為制約社交網(wǎng)絡(luò)的動(dòng)態(tài)演化過程、 社交網(wǎng)絡(luò)結(jié)構(gòu)以及用戶行為的至關(guān)重要的因素[1]. 研究網(wǎng)絡(luò)中用戶的社會影響力有著十分廣闊的應(yīng)用前景， 如： 用戶分類[2]、 個(gè)性化推薦[1, 3]等. 當(dāng)前的研究工作主要有兩大類： 基于PageRank的方法[2, 4-5]、 基于矩陣[1, 3, 6]或張量的方法[7-9]. 基于PageRank的方法假設(shè)用戶的影響力由好友的影響力所決定， 認(rèn)為好友的影響力大， 則該用戶也可能有較大影響力. 基于矩陣或張量的方法則把用戶的交互行為用潛在的公共行為來描述， 通過解析潛在行為來推測用戶的交互關(guān)系強(qiáng)度. 然而， 社交網(wǎng)絡(luò)上， 用戶與用戶之間往往具有多種交互關(guān)系， 并且不同用戶關(guān)注的領(lǐng)域是不同的， 當(dāng)前的方法沒有充分利用社交媒介上用戶的各種交互關(guān)系信息以及用戶的主題信息. 針對當(dāng)前方法的不足， 我們將考慮用戶的交互信息以及用戶與查詢主題之間的相關(guān)度， 以期望提高用戶挖掘的精度. 本研究提出一種基于張量分解的用戶影響力度量方法. 該方法將用戶的多種交互關(guān)系行為表示成幾個(gè)公共的潛在行為， 提取用戶潛在行為結(jié)構(gòu)， 而且具有直觀的行為解釋.

1相關(guān)工作

社交媒介上用戶影響力分析是通過利用社交媒介上的用戶信息來推斷用戶在網(wǎng)絡(luò)上的影響力. 當(dāng)前的研究工作主要有兩大類：

1) 基于PageRank的方法. N Agarwal等[10]關(guān)注有影響力博主的識別， 通過考慮用戶內(nèi)容的評論數(shù)量、 內(nèi)容發(fā)起的討論規(guī)模、 出鏈數(shù)、 入鏈數(shù)以及內(nèi)容的長度等因素， 以PageRank算法為基礎(chǔ)， 建立一個(gè)有影響力博主的識別模型. K K Cai等[2]利用用戶回復(fù)信息中的觀點(diǎn)傾向性， 將用戶的影響力分為積極、 消極和中性， 通過用戶間的回復(fù)關(guān)系建立圖模型， 并用迭代方式確定出用戶的影響力大小. 張碉等[4]以主題為單位， 提取用戶間的回復(fù)關(guān)系， 構(gòu)建用戶對話關(guān)聯(lián)圖， 在PageRank算法基礎(chǔ)上， 提出基于多屬性的用戶影響力排序算法， 并進(jìn)一步分析了用戶影響力的演化趨勢.

2) 基于矩陣或張量的方法. P Cui等[3]則利用用戶的點(diǎn)擊以及用戶間的好友關(guān)系與內(nèi)容分享關(guān)系構(gòu)造用戶-帖子關(guān)系矩陣， 并利用概率混合因素矩陣分解(PHFMF)的方法， 實(shí)現(xiàn)對用戶影響力的挖掘. S Moghaddam等[7]利用產(chǎn)品的評論評級信息挖掘產(chǎn)品評論的質(zhì)量， 作者通過“評級—評論者—產(chǎn)品”交互信息構(gòu)建三階張量， 并利用張量分解技術(shù)實(shí)現(xiàn)對產(chǎn)品評論質(zhì)量的估計(jì). M Nickel等[8]主要介紹融合多種交互關(guān)系的張量模型， 并通過矩陣分解技術(shù)對原始張量進(jìn)行降維處理， 減小了計(jì)算時(shí)的數(shù)據(jù)規(guī)模.

針對融合多種交互關(guān)系信息度量用戶影響力的問題， 本研究提出一種基于張量分解的影響力用戶識別方法. 首先， 將社交媒介上用戶的多種交互關(guān)系表示成張量. 其次， 用融合多種用戶交互關(guān)系的RESCAL張量分解算法[8]給出用戶交互行為強(qiáng)度的預(yù)測. 最后， 融合用戶主題與交互關(guān)系信息， 對用戶影響力進(jìn)行綜合評價(jià)， 并實(shí)現(xiàn)對用戶的排名.

2基于張量分解的用戶影響力度量模型

2.1問題描述

2.2基于多種交互關(guān)系的三階張量模型

社交媒介中， 用戶的影響力可以由一些潛在的行為來刻畫， 本研究將介紹一種基于RESCAL張量分解的方法來預(yù)測用戶之間的交互關(guān)系強(qiáng)度.

首先， 使用RESCAL張量分解必須滿足以下兩個(gè)條件：

條件1： RESCAL張量分解方法要求被分解的三階張量的前兩維的維數(shù)必須相同. 張量所描述的必須是同一個(gè)實(shí)體集合中兩兩實(shí)體間的若干種關(guān)系. 而本研究要描述的恰恰是同一批用戶集合中兩兩用戶之間的多種交互關(guān)系.

條件2： 張量中每一個(gè)元素的取值是非負(fù)的. 本研究處理的是用戶之間的交互關(guān)系， 即： 粉絲數(shù)、 評論數(shù)、 主題相關(guān)度等， 這些取值均滿足非負(fù)條件.

其次， 社交網(wǎng)絡(luò)上用戶的信息除了自身的微博內(nèi)容信息外， 還有很多交互信息， 如： 用戶之間的粉絲關(guān)系、 關(guān)注關(guān)系、 用戶對用戶微博的轉(zhuǎn)發(fā)、 評論關(guān)系等. 這些用戶之間的交互信息一定程度上隱含了用戶影響力的信息. 為充分利用這些用戶之間的交互信息， 并對這些信息進(jìn)行量化表示， 引入三階張量. 三階張量在形式上類似于三維數(shù)組， 可以形式化地寫為Z=(zijk)N×N×M， 其中：N為用戶數(shù)量，M為用戶之間的交互關(guān)系數(shù)量. 張量中的每一個(gè)元素zijk可以解釋為： 第i個(gè)用戶和第j個(gè)用戶在第k種交互關(guān)系上的取值. 因此， 三階張量對用戶之間的各種社交關(guān)系有較強(qiáng)的解釋性.

將社交媒介上多種用戶交互關(guān)系構(gòu)建成基于查詢主題的用戶交互關(guān)系張量； 接著利用融合多種交互關(guān)系的RESCAL張量分解算法[7]對用戶的社交行為強(qiáng)度進(jìn)行預(yù)測； 然后， 融合用戶的各種交互關(guān)系強(qiáng)度和用戶的主題信息給出用戶影響力的綜合評判， 并利用影響力評判值給出用戶的排序列表.

2.2.1RESCAL張量分解原理

根據(jù)上述的說明， 張量的第k層矩陣可近似表示為： Zk≈ARkAT. 因此， 整個(gè)張量的估計(jì)問題可以轉(zhuǎn)化為如下的優(yōu)化問題：

(1)

進(jìn)一步地， 為了避免優(yōu)化過程中出現(xiàn)的過擬合問題， 可以將上述優(yōu)化問題修正為如下形式：

(2)

2.2.2融合多種交互關(guān)系的用戶張量

設(shè)Z∈RN×N×M表示用戶交互關(guān)系張量，N為用戶數(shù)，M為交互關(guān)系數(shù)， 張量元素zijk表示用戶ui與uj在第k種關(guān)系上的強(qiáng)度. 為構(gòu)建融合多種社交關(guān)系的用戶張量， 首先給出用戶交互關(guān)系的度量：

1) 粉絲、 評論關(guān)系. 如果網(wǎng)絡(luò)中的用戶數(shù)量為N， 則令： IA=(Iij)N×N為用戶粉絲關(guān)系指示矩陣， 即：

(3)

2) 用戶關(guān)注關(guān)系. 假定用戶U(i)的粉絲數(shù)用F(i)來表示， 則U(i)在粉絲關(guān)系上對U(j)的影響可用如下公式來衡量：

(4)

如果U(i)是U(j)的粉絲， 且U(i)的粉絲數(shù)很大， 那么U(j)也很有可能有較大的粉絲數(shù).

3) 用戶微博的評論關(guān)系. 如果用戶U(i)的微博收到的評論數(shù)為review(i)， 則U(i)在評論關(guān)系上對U(j)的影響可用如下公式來衡量：

(5)

4) 用戶間的主題關(guān)系. 以“籃球”這一主題為例， 提取用戶常用的144個(gè)籃球詞匯， 如表1所示.

表1　籃球相關(guān)的部分關(guān)鍵詞

利用BM25模型[11]確定用戶和主題間的相關(guān)度. 計(jì)算方法如下：

設(shè)Q={q1, q2, …, qm}為查詢主題， D={d1, d2, …, dN}為文檔集合，BM25算法就是計(jì)算中每個(gè)文檔dj與查 詢主題之間的相關(guān)性.BM25算法公式如下：

(6)

假定用戶U (i)的主題相關(guān)度記為topic(i)， 則U (i)在主題關(guān)系上對U (j)的影響可用如下公式來衡量：

(7)

5) 基于多種交互關(guān)系用戶張量. 用戶張量由三個(gè)關(guān)系矩陣組成， 分別用Y1， Y2， Y3表示， 含義如下：

粉絲層:

(8)

評論層:

(9)

主題層:

(10)

為了統(tǒng)一張量的量綱， 可以對張量進(jìn)行歸一化處理， 處理方法如下：

(11)

2.2.3融合多種交互關(guān)系的RESCAL張量分解

根據(jù)RESCAL張量分解算法原理， 用戶張量就可以近似地表示為： Z≈ARAT.

上述分解式中， A與R的估計(jì)等價(jià)于如下優(yōu)化問題：

(12)

張量分解算法如圖1所示.

圖1張量分解算法

Fig.1Tensorfactorizationalgorithm

2.2.4基于張量分解的用戶綜合影響力度量

根據(jù)上述定義， 張量Z=(zijk)N×N×3每層的含義不同， 要針對每一層張量的含義逐層定義用戶的影響力.

令ufjk表示U(i)在第k種關(guān)系下的影響力. 根據(jù)J S Weng等[5]的觀點(diǎn)， 用戶影響力取決于好友的總影響力. 因此， 用戶影響力可按如下方式定義：

好友的粉絲數(shù)總和(ufi1) :

(13)

好友的評論數(shù)總和(ufi2):

(14)

好友的主題相關(guān)度總和(ufi3):

(15)

可以定義用戶在查詢主題下的綜合影響力得分如下：

(16)

由公式可知， 只有用戶的主題相關(guān)度和交互關(guān)系強(qiáng)度均比較大時(shí)， 用戶的綜合影響力得分才會比較大.

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

3.1實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)數(shù)據(jù)來自新浪微博， 共采集了624個(gè)用戶， 50 219條評論， 包含523對評論關(guān)系和777對粉絲關(guān)系.

首先， 先對基準(zhǔn)方法的選擇給出說明：

1)PageRank算法.PageRank用于衡量特定網(wǎng)頁相對于搜索引擎索引中的其他網(wǎng)頁而言的重要程度， 實(shí)現(xiàn)了將鏈接價(jià)值概念作為排名因素.PageRank是目前度量影響力比較熱門的方法， 如：KKCai[2]、 張碉[4]、NAgarwal等[10]都以PageRank算法為基礎(chǔ)度量網(wǎng)絡(luò)用戶影響力.

2) 非負(fù)矩陣分解算法(NMF). 目前矩陣分解方法已在用戶或產(chǎn)品推薦領(lǐng)域得到了廣泛的應(yīng)用. 主要是利用用戶—產(chǎn)品、 用戶—用戶或者產(chǎn)品—產(chǎn)品之間的交互信息來確定推薦項(xiàng)目.PCui[3]、SMoghaddam[7]、MNickel等[8]已經(jīng)在這方面做了很多有價(jià)值的工作.

然后， 人工篩選了與籃球有關(guān)的前15名有影響力的用戶. 并以PageRank、 非負(fù)矩陣分解為基準(zhǔn)方法， 分別計(jì)算出PageRank、 非負(fù)矩陣分解和張量分解方法給出的有影響力用戶的列表； 將PageRank、 非負(fù)矩陣分解和張量分解方法得到的用戶列表分別與人工排序的結(jié)果進(jìn)行比較.

3.2評價(jià)指標(biāo)

1) 張量分解精度指標(biāo)RMSE.

(17)

該指標(biāo)反映了原始數(shù)據(jù)與張量分解后的預(yù)測數(shù)據(jù)之間的平均偏差.

2) 用戶排序精度指標(biāo).

(18)

其中： Ak為人工排序中的前名用戶集； Bk為實(shí)驗(yàn)排序中的前名用戶集. 該指標(biāo)反映了前名實(shí)驗(yàn)排序與人工排序的吻合程度.

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

1) 在探索不同用戶主題信息間的差異時(shí)， 我們畫出了用戶主題相關(guān)度的分布圖， 如圖2所示. 其中： 橫坐標(biāo)表示主題相關(guān)度， 縱坐標(biāo)表示用戶數(shù).

從圖2可以看出, 社交網(wǎng)絡(luò)中真正與查詢主題相關(guān)的用戶僅占全部用戶的極少部分. 因此， 通過考慮查詢主題來挖掘用戶影響力是有意義的.

2) 在圖1所述的張量分解算法中， 最優(yōu)潛在特征數(shù)需要根據(jù)實(shí)際情況來確定. 現(xiàn)有文獻(xiàn)中對于這個(gè)參數(shù)的一般確定方法如下：

Step1： 取K=1, 2, 3, …， 利用分解算法， 分別計(jì)算出不同潛在特征數(shù)對應(yīng)的用戶潛在特征矩陣A(1), A(2), A(3), …, 以及中心張量R(1), R(2), R(3), …；

Step2： 分別計(jì)算不同潛在特征數(shù)下的張量預(yù)測值Xpredict(K)=A(K)TR(K)A(K)；

由上述步驟， 可得到K值(橫坐標(biāo))與RMSE(縱坐標(biāo))之間的關(guān)系, 如圖3所示. 可見， 隨著K的增大， 誤差RMSE不斷減小， 當(dāng)K=4時(shí)模型誤差達(dá)到最小值. 因此， 對于這批數(shù)據(jù)而言， 應(yīng)該取4個(gè)潛在特征最為合適.

3) 利用人工篩選的列表， 將張量分解方法得到的用戶列表與PageRank以及NMF方法得到的用戶列表進(jìn)行比較， 結(jié)果如圖4所示. 由結(jié)果可知： 用張量分解方法做影響力用戶的挖掘任務(wù)時(shí)， 結(jié)果優(yōu)于NMF方法及PageRank方法.

4結(jié)語

針對融合多種交互關(guān)系度量用戶影響力的問題， 提出一種基于張量分解的影響力用戶識別方法. 首先， 利用張量來描述用戶間的各種交互關(guān)系. 其次， 利用RESCAL分解算法對用戶交互行為進(jìn)行解構(gòu). 最后， 給出融合多種交互關(guān)系和主題信息的影響力公式， 并給出用戶排序列表. 實(shí)驗(yàn)表明， 與PageRank和非負(fù)矩陣分解相比， 融入主題的張量分解方法在影響力用戶挖掘問題上更加有效.

參考文獻(xiàn)：

[1]CUIP,WANGF.Item-levelsocialinfluencepredictionwithprobabilistichybridfactormatrixfactorization[C]//Twenty-FifthAAAIConferenceonArtificialIntelligence.NewYork:ACM, 2011: 331-336.

[2]CAIKK,BAOSH,YANGZ, et al.Anopinionorientedlinkanalysismodelforinfluencepersonadiscovery[C]//ProceedingsoftheFourthACMInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2011: 645-654.

[3]CuiP,WANGF,LIUSW, et al.Whoshouldsharewhat,Item-levelsocialinfluencepredictionforusersandpostsranking[C]//Proceedingsofthe34thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2011: 185-194.

[4] 張碉, 張宏莉, 張偉哲, 等. 識別網(wǎng)絡(luò)論壇中有影響力用戶[J]. 計(jì)算機(jī)研究與發(fā)展, 2013(10): 2 195-2 205.

[5]WENGJS,LIMEP,JIANGJ, et al.TwitterRank:findingtopic-sensitiveinfluentialtwitterers[C]//ProcofWSDM.NewYork:ACM, 2010: 261-270.

[6]JAMALIM,ESTERM.Amatrixfactorizationtechniquewithtrustpropagationforrecommendationinsocialnetworks[C]//ProceedingsoftheFourthACMConferenceonRecommenderSystems.NewYork:ACM, 2010: 135-142.

[7]MOGHADDAMS,JAMALIM,ESTERM.Extendedtensorfactorizationmodelforpersonalizingpredictionofreviewhelpfulness[C]//ProceedingsoftheFifthACMInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2012: 163-172.

[8]NICKELM,TRESPV,KRIEGELHP.FactorizingYAGOscalablemachinelearningforlinkeddata[C]//Proceedingsofthe21stInternationalConferenceonWorldWideWeb.NewYork:ACM, 2012: 271-280.

[9]WEIJJ,TANGCH,LIAOXW, et al.Miningsocialinfluenceinmicrobloggingviatensorfactorizationapproach[C]//ProceedingsoftheInternationalConferenceonCloudComputingandBigData.Fuzhou: [s.n.], 2013: 583-591.

[10]AGARWALN,LIUH，TANGL， et al.Identifyingtheinfluentialbloggersinacommunity[C]//ProceedingsoftheInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2008: 207-218.

[11]ROBERTSONS,ZARAGOZAH,TAYLORM.SimpleBM25extensiontomultipleweightedfields[C]//ProceedingsofthethirteenthACMInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2004: 42-49.

(責(zé)任編輯： 沈蕓)

The application of tensor factorization on user influence measure

TANG Changhong1, 2, LIU Yue1

(1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China；2. Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou, Fujian 350116, China)

Abstract:This paper proposes a method for identifying influential users based on tensor factorization (TF). This method fitst constructs interaction tensor based on the topic. Then, we extract the user behavior by factorizing the tensor. Finally, the users’ influences are evaluated by comprehensively considering the topic and interaction information between users. The experiments shows that, compared with NMF and PageRank method, the accuracy of TF method can increase by 10% and 20%, respectively.

Keywords:user influence; topic relevance; interactive relationship; tensor; social media

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61300105)； 教育部博士點(diǎn)基金資助項(xiàng)目(2012351410010)； 福建省科技重大專項(xiàng)基金資助項(xiàng)目(2013H6012)； 福州市科技計(jì)劃資助項(xiàng)目(2012-G-113, 2013-PT-45)

通訊作者:劉月(1984-)， 副教授， 主要從事矩陣論研究， liuyue@fzu.edu.cn

收稿日期:2014-05-14

文章編號：1000-2243(2016)02-0176-06

DOI:10.7631/issn.1000-2243.2016.02.0176