數(shù)據(jù)挖掘系列篇(20):社交網(wǎng)絡SNS的好友推薦算法

時間：2023-03-15 00:38:01 | 來源：電子商務

時間：2023-03-15 00:38:01 來源：電子商務

—————————————禁止轉(zhuǎn)載—————————————————————

花了幾天看了些做社交的好友推薦，現(xiàn)在很多App都有社交場景，本身就是做用戶的場景，所以以后肯定要在這塊有一些應用。像早期的論壇類的更偏重資訊類的信息，后來像優(yōu)酷土豆這又是做視頻類，網(wǎng)易云音樂做音樂類。豆瓣相對來說還比較全一些，有包含資訊、音樂電臺等這些。也用了一些其他做社交場景的App，包括像脈脈、釘釘這些。感覺不是太好，具體原因就是都不是什么認識的人，活躍度也不高。很多App基本上就是屬于少數(shù)意見領袖，這些人有大量的粉絲。而還有一幫大量用戶，他們粉絲不多活躍也不高。本質(zhì)上來說，還是沒有找到他們感興趣的內(nèi)容。就跟昨天一樣，突然騰訊視頻給我推了下2007出的《遠古入侵》，這推的太給力了！一部科幻、時空穿越、冒險題材的英劇就應該推給我這樣tag的用戶。

我們平時光計算用戶的關系親密度，比如兩者的SNS互動次數(shù)、媒介場景關系度、地理位置相關度，這些缺陷都很依賴用戶之間的活躍程度。后來又有人提出了好友的好友、圈子、共同興趣、共同話題等方面角度進行研究。實際場景中我們也是會結合 “社交”+“興趣”兩點平衡，找到一個比較融合的權衡，推薦用戶感興趣的content。

計算共同好友比例

一般最簡單推薦好友就是計算兩者有哪些共同好友，如果共同好友很多自然就認識的概率很大。比如我和Jackie是同學，但是我們可能都因為用Facebook時間不長，可能都沒相互添加，那就可以計算我和Jackie之間發(fā)現(xiàn)同學的占比是多少。包括像同事、家人、朋友等等都差不多。在社交網(wǎng)絡中, 可以根據(jù)現(xiàn)有的社交網(wǎng)絡圖給用戶推薦新的好友, 比如給用戶推薦好友的好友?；诤糜训暮糜淹扑]算法可以用來為用戶推薦在現(xiàn)實社會中相互熟悉而在當前社交網(wǎng)絡中沒有聯(lián)系的其他用戶。例如使用人人網(wǎng)時, 經(jīng)?？吹揭恍┚梦绰?lián)系的老同學出現(xiàn)在推薦好友列表中。

優(yōu)點是簡潔、易實現(xiàn), 效果明顯。但是其缺點也是顯而易見的, 如果用戶好友人數(shù)不夠多, 那么無論是為其推薦其他好友或者將其推薦給其他人都會變得很難。其次是該算法只是關注“ 人” 的因素而忽略了其他因素, 可能影響所推薦好友的準確性。

最簡單的好友推薦算法是為用戶推薦共同好友數(shù)最多的用戶。其基本思想是, 用戶之間的共同好友越多, 則他們越可能是好友。由于這種方法受用戶好友總數(shù)影響較大, 因此通常根據(jù)共同好友比例計算相似度來推薦好友。

在Twitter和新浪微博等有向社交網(wǎng)絡中, 用戶u關注的人out(u)和關注用戶u的人in(u)是兩個不同的集合, 因此使用共同好友比例計算相似度有三種不同形式, 本文采用出度的方法, 用戶u和用戶v的共同好友比例fuv表示為:

其中, out(u)表示用戶u關注的用戶集合, out(v)表示用戶v關注的用戶集合。out(u)∩ out(v)表示兩個集合的交集。|out(u)|和|out(v)|分別表示集合out(u)和out(v)的元素個數(shù)。

互動次數(shù)

不管人們有多少共同好友, 都無法確定是否會一直與其保持聯(lián)系。社交網(wǎng)站傾向于促使用戶盡可能多地與別人產(chǎn)生互動, 這樣他們就能看到并從中提取信息。如果兩個人之間沒有互動, 很難稱得上朋友。

社交網(wǎng)絡中用戶之間的互動包括消息、評論、轉(zhuǎn)發(fā)和收藏等形式, 轉(zhuǎn)發(fā)和評論等行為在一定程度上代表著信息對于用戶的吸引力, 評論與轉(zhuǎn)發(fā)等通常有不同的權重, 為了簡化計算, 這里對消息、評論和轉(zhuǎn)發(fā)取相同權重。

用戶u與用戶v之間的互動情況iuv可以用兩者之間互動次數(shù)占用戶u和用戶v全部互動行為的比例來表示, 本文提出的互動比例計算方法如下:

其中, interact(u, v)表示用戶u對用戶v的互動次數(shù), interact(u)表示用戶u對所有用戶的總互動次數(shù)。兩用戶之間互動次數(shù)用單向互動次數(shù)的平均值表示。

社交興趣度


本文對根據(jù)社交圖譜計算用戶相似度的傳統(tǒng)方法進行改進, 從共同好友和互動情況兩方面來表現(xiàn)用戶之間的關系親密程度, 從而計算出目標用戶對待推薦用戶的社交興趣度, 以此描述目標用戶和待推薦用戶成為好友的可能性。

建立n個用戶之間的關系矩陣A, A是一個n× n矩陣, 其中, 如果用戶u和v是好友關系(或用戶u關注了用戶v), 則auv=1, 否則auv=0。矩陣A中第u行ua= (au1, au2, , aun)反映了用戶u的好友關系。

。其中, fuv表示用戶之間的共同好友比例, iuv表示用戶之間的互動情況比例。α 是綜合共同好友比例和互動比例的參數(shù), 其取值范圍為[0, 1], 不同數(shù)據(jù)集中α 可能有不同的最佳值, 可根據(jù)經(jīng)驗取值或者在特定數(shù)據(jù)集上逐步調(diào)整和比較以獲得最佳值。本文中取α =0.5。矩陣C中元素cuv反映了用戶u與用戶v關系的親密程度。

最近鄰協(xié)同過濾技術中, 由于最近鄰居與目標用戶對項目的評分非常相似, 因此目標用戶對未評分項目的評分可以通過最近鄰居對該項目評分的加權平均值近似表示。類似地, 在好友推薦中, 可以把待推薦用戶看作待評分項目, 把好友作為鄰居, 把用戶u與用戶v的關系親密程度看作用戶u對用戶v的評分或者鄰居用戶v的權重。

興趣相似度

社交網(wǎng)絡中用戶留下的文字和行為可以反映用戶興趣和需求。通常用戶可使用自然語言或者標簽主動展示其喜好。這種方法可以獲得一些關于用戶興趣愛好的信息, 但是其缺點也比較明顯, 自然語言理解技術不能很好地理解用戶的描述, 而且用戶興趣是動態(tài)變化的, 興趣描述很容易過時, 況且很多時候用戶并不知道或者很難用語言描述喜歡什么。因此, 需要通過算法自動發(fā)掘用戶歷史行為數(shù)據(jù), 以推測用戶興趣, 從而推薦滿足興趣的項目。

計算用戶之間的興趣相似度, 主要思想是: 如果用戶喜歡相同物品, 則說明具有相似的興趣。微博內(nèi)容可以看作物品, 如果兩個用戶曾經(jīng)評論、轉(zhuǎn)發(fā)或者收藏過同樣的微博, 則說明他們具有相似的興趣。此外, 也可以根據(jù)用戶在社交網(wǎng)絡中的發(fā)言提取用戶的興趣標簽(關鍵詞), 計算用戶的興趣相似度?；跇撕灥耐扑]中, 很多時候用戶主動標記使用的標簽很少, 這可能是由于用戶沒有使用標簽的習慣或者用戶新近加入或者用戶活躍度較低。因此, 通常從用戶的內(nèi)容數(shù)據(jù)中抽取關鍵詞作為標簽或者是根據(jù)標簽之間的相似度做一些關鍵詞擴展。

本文運用現(xiàn)有知識計算興趣相似度。用關鍵詞向量描述興趣, 用TF-IDF公式計算關鍵詞權重, 用關鍵詞向量之間的余弦相似度表示興趣相似度。

一般來說, 用戶興趣可以通過向量空間模型表示為一個關鍵詞向量。從微博內(nèi)容中提取關鍵詞的過程需要引入一些自然語言處理技術。關鍵詞向量生成過程包括中文文本分詞、命名實體(如人名、地名、組織名等)檢測、關鍵詞排名和關鍵詞權重計算等。用戶u興趣特征向量可以表示為

,N為用戶總數(shù), ni為包含ei的用戶數(shù)目。

向量空間模型的優(yōu)點是簡單, 缺點是丟失了一些信息, 比如關鍵詞之間的關系信息。但是, 在絕大多數(shù)應用中, 向量空間模型對于文本的分類、聚類、相似度計算已經(jīng)可以給出令人滿意的結果。

用戶之間的興趣相似度可以通過興趣特征向量之間的余弦相似度計算如下:

余弦值與相似度成正比, 余弦值越小表示相似度越低, 余弦值越大表示相似度越高, 其取值范圍為[0, 1], 0表示完全不同, 1表示完全相同。

綜合社交和興趣的好友推薦

不同的社交網(wǎng)絡中人們的目的和側重點往往是存在差異的, 因此, 人們通常在不同的社交網(wǎng)站建立不同的關系網(wǎng)絡。例如人人網(wǎng)中的好友通常以同學校友或者熟人為主, 而豆瓣網(wǎng)中的好友卻大多因相似興趣而聚集。因此本文先計算交際興趣度和興趣相似度, 然后將二者綜合評分, 最終推薦得分最高的Top-k位用戶。由于只需要計算存在好友關系的用戶之間的共同好友比例和互動比例, 因此可以有效提高效率。

社交圖譜是靜態(tài)的, 沒有時間變化概念, 認識10年的朋友和昨天才發(fā)生交集的朋友在社交關系圖上沒有明顯差別; 而興趣圖譜是動態(tài)的, 其變化通常會反映在歷史行為中。社交圖譜反映了用戶的交友傾向, 而興趣圖譜反映了用戶的興趣偏好, 將兩者綜合考慮很可能獲得比單純考慮社交關系或者興趣愛好更好的推薦結果。為了便于控制以上兩個因素對最終結果的影響, 可將社交興趣度和興趣相似度分別按最大值歸一化。綜合社交關系和興趣偏好的最終評分可表示如下:

其中, β 是改進的好友推薦算法的可調(diào)參數(shù), 表示最終評分中社交因素的權重, β 取值范圍為[0, 1], 本文實驗中β 取0.5。s(u, v)為社交興趣度。w(u, v)為興趣相似度。

本文好友推薦算法執(zhí)行過程如圖1所示:

圖1 基于社交和興趣的好友推薦方法實驗與分析

從 2012 KDD 競賽所提供的騰訊微博數(shù)據(jù)中提取部分作為實驗數(shù)據(jù), 對本文提出的算法進行實驗分析。所采集數(shù)據(jù)包括用戶社交網(wǎng)絡(關注關系)、用戶社交行為(通知、轉(zhuǎn)發(fā)和評論行為)以及用戶關鍵詞(關鍵詞及其權重)。

從用戶社交網(wǎng)絡中隨機選取5個較活躍用戶作為種子, 采用寬度優(yōu)先策略收集用戶好友關系, 過濾掉好友數(shù)目少于5個和大于150的用戶, 最終得到3 237個用戶, 以此模擬一個小型的社交網(wǎng)絡。隨后的實驗中只考慮這些用戶之間的好友關系。平均每個用戶關注13.4個人, 為非常稀疏的好友網(wǎng)絡, 網(wǎng)絡稀疏度99.6%, 表現(xiàn)出明顯的數(shù)據(jù)長尾性。根據(jù)以上獲得用戶列表, 分別從用戶社交行為和用戶關鍵詞中提取出相關用戶的社交行為和關鍵詞。實驗數(shù)據(jù)處理步驟如圖1所示。根據(jù)關系網(wǎng)絡計算共同好友比例, 根據(jù)行為信息計算交互比例, 綜合共同好友比例和交互比例獲得社交興趣度。然后根據(jù)用戶關鍵詞建立興趣向量, 從而計算興趣相似度。最后綜合社交和興趣兩方面因素獲得最終評分, 將評分最高的k位用戶推薦給目標用戶。

Top-k推薦中常用的評價指標有準確率(Precision)、召回率(Recall)以及綜合準確率和召回率的F1-measure。其定義如下:

實驗比較了基于共同好友比例、基于興趣相似度、基于共同好友比例和興趣相似度以及基于社交和興趣相似度4種好友推薦算法的性能。

微信公眾號：datafa（數(shù)據(jù)分析聯(lián)盟）

微信群：加V 784414374

QQ群：252805327

新書鏈接：

【數(shù)據(jù)分析俠 《人人都會數(shù)據(jù)分析》20萬字書籍】http://m.tb.cn/h.AJEkoq 點擊鏈接，再選擇瀏覽器打開；或復制這條信息￥fSnh09F0Vpy￥后打開 手淘

————未完待續(xù)

2016.05.21