一種基于合作關(guān)系的陌生人推薦系統(tǒng)

李卓華，黃翔

（佛山科學(xué)技術(shù)學(xué)院電子信息工程學(xué)院，佛山 528225）

0 引言

科技的發(fā)展改變了人們的生活方式，一些具有代表性的社交網(wǎng)站已成為影響力巨大的信息平臺(tái)。社交網(wǎng)絡(luò)上的用戶和信息出現(xiàn)爆炸式增長(zhǎng),要找到感興趣的內(nèi)容變得越來(lái)越困難。為幫助人們快速準(zhǔn)確地找到自己想要的資源，推薦系統(tǒng)應(yīng)運(yùn)而生[1]。它對(duì)于緩解信息過(guò)載、重建用戶關(guān)系非常有效，因此在社交網(wǎng)絡(luò)中得到了廣泛應(yīng)用，并主要用于向目標(biāo)用戶推薦好友（相同興趣或愛(ài)好的其他用戶）。但目前用來(lái)解決陌生人推薦的系統(tǒng)，尤其是應(yīng)用在一些用戶與用戶之間有明顯的合作需求的社區(qū)平臺(tái)中（如職場(chǎng)社交、創(chuàng)業(yè)社交、購(gòu)物社區(qū)等），推薦系統(tǒng)得出的推薦結(jié)果不盡如人意。

1 基于合作關(guān)系的社交場(chǎng)景

在此類合作需求的社交場(chǎng)景中，用戶具有較為明確的社交目的，通常需要其他用戶來(lái)協(xié)助解決某一特定的需求。以創(chuàng)業(yè)社交中的組建團(tuán)隊(duì)為例，為了使團(tuán)隊(duì)的工作效率最大化，團(tuán)隊(duì)成員之間需要各司其職，各取所長(zhǎng)，從而通過(guò)這樣明確的供需互補(bǔ)促成團(tuán)隊(duì)誕生。很明顯，此時(shí)特別強(qiáng)調(diào)用戶的雙向匹配程度，既要推薦符合該需要的潛在用戶加入團(tuán)隊(duì)并合作，還要被推薦用戶能滿足相應(yīng)團(tuán)隊(duì)及成員的某一方面需求，雙方的供應(yīng)與需求能互相匹配。

同樣的，在其他的基于合作的社交場(chǎng)景中，需求都強(qiáng)調(diào)合作關(guān)系，如職場(chǎng)求職的職位匹配、創(chuàng)業(yè)事務(wù)的發(fā)布與完成，等等。

2 現(xiàn)有研究

傳統(tǒng)的推薦算法比較成熟，但多應(yīng)用于分析用戶興趣偏好或需求推薦的資源，如商品、電影、音樂(lè)等。如文獻(xiàn)[2]提出的協(xié)同過(guò)濾推薦算法通過(guò)計(jì)算目標(biāo)用戶的鄰近用戶集合來(lái)預(yù)測(cè)真實(shí)評(píng)分，達(dá)到推薦目的；文獻(xiàn)[3]提出基于內(nèi)容的推薦方法嘗試推薦與用戶評(píng)分高的項(xiàng)目相似的資源。傳統(tǒng)的推薦算法主要用于對(duì)物品的推薦。與傳統(tǒng)算法推薦目標(biāo)不同的是，社交場(chǎng)景下的推薦算法的目標(biāo)是用戶集合，傳統(tǒng)推薦技術(shù)不能在此類場(chǎng)景下直接應(yīng)用。

Lo等[4]提出根據(jù)互動(dòng)次數(shù)衡量用戶間的親密度，互動(dòng)次數(shù)越多說(shuō)明關(guān)系越好。Chin[5]則根據(jù)任意兩個(gè)用戶間手機(jī)交互的次數(shù)來(lái)進(jìn)行推薦。這也是Facebook好友推薦系統(tǒng)“People You May Know”的一種典型算法基礎(chǔ)。它強(qiáng)調(diào)，將有緊密社交關(guān)系的用戶同社交網(wǎng)絡(luò)中沒(méi)有聯(lián)系的用戶區(qū)分開來(lái)，但其實(shí)驗(yàn)結(jié)果表明，該類推薦算法的推薦結(jié)果中陌生人的比重較低。

另外，Shen等[6]根據(jù)用戶關(guān)注過(guò)的Blog分析出用戶的興趣模型，由模型計(jì)算興趣相似度進(jìn)而發(fā)現(xiàn)潛在好友。Zheng等[7]則是根據(jù)用戶去過(guò)的地方構(gòu)建興趣模型。實(shí)驗(yàn)結(jié)果表明，該推薦方法向用戶推薦的好友反映了用戶具有相同或相似的興趣，對(duì)于用戶通過(guò)社交網(wǎng)絡(luò)認(rèn)識(shí)新朋友有較好的效果，常適用于基于興趣社交的社交場(chǎng)景。

通過(guò)分析發(fā)現(xiàn)，現(xiàn)有的應(yīng)用于社交場(chǎng)景的推薦策略以用戶的社交行為為依據(jù)，提出了多種推薦方法，歸納為：

（1）基于社交關(guān)系的推薦

挖掘與被推薦用戶社交行為密切的用戶，核心思想是如果好友推薦結(jié)果中有與被推薦用戶有一定聯(lián)系的用戶，則推薦的結(jié)果更有可能被接受。

（2）基于興趣關(guān)系的推薦

致力于尋找社交平臺(tái)上興趣愛(ài)好相似的用戶。通過(guò)用戶的一系列關(guān)鍵詞，建立用戶的向量表示，計(jì)算每個(gè)用戶向量之間的相似度來(lái)衡量用戶的相似程度。

此兩類推薦方法在各自特定場(chǎng)景中能取得較好的推薦效果，但在處理基于合作關(guān)系的社交場(chǎng)景的推薦問(wèn)題時(shí)有以下的不足：

（1）推薦不準(zhǔn)確。現(xiàn)有的推薦方法依據(jù)的是相似性度量，然而在基于合作關(guān)系的社交場(chǎng)景中，用戶更加關(guān)心那些能滿足自己某一特定需求的用戶[8]，若只考慮用戶之間的相似性，顯然結(jié)果是不理想的。

（2）單向的推薦容易造成垃圾信息。現(xiàn)有的推薦方法只是把被推薦人單向性地推薦給目標(biāo)用戶，沒(méi)有考慮被推薦的用戶是否會(huì)對(duì)目標(biāo)用戶感興趣，而合作關(guān)系的確立是雙向的[9]，單向性的推薦容易造成推薦的不準(zhǔn)確。

針對(duì)傳統(tǒng)的從社交或興趣單一角度進(jìn)行好友推薦的方法存在的局限性，本文綜合考慮用戶供應(yīng)與需求的數(shù)據(jù)匹配，提出一種相互吸引度來(lái)改進(jìn)社交相似度的新算法。

3 推薦算法的實(shí)現(xiàn)

3.1 算法框架

系統(tǒng)實(shí)現(xiàn)的框架包括三部分：數(shù)據(jù)采集、數(shù)據(jù)分析、結(jié)果呈現(xiàn)。其中，數(shù)據(jù)采集，又分為目標(biāo)用戶的供應(yīng)數(shù)據(jù)和需求數(shù)據(jù)。供應(yīng)數(shù)據(jù)就是目標(biāo)用戶可以提供的資源，這里的資源可以是具體的物品，也可以是服務(wù)或是技能等，這些數(shù)據(jù)是目標(biāo)用戶根據(jù)自己的實(shí)際情況主動(dòng)去編輯輸入的，這部分功能稱之為供應(yīng)數(shù)據(jù)獲取模塊。而目標(biāo)用戶的需求數(shù)據(jù)，是指用戶希望在平臺(tái)內(nèi)獲得的資源，要通過(guò)用戶的使用來(lái)隱性獲取，例如用戶的搜索，瀏覽等記錄[10]，這部分功能為需求數(shù)據(jù)獲取模塊。

綜上所述，整個(gè)算法框架概括如圖1所示。

圖1 算法框架圖

3.2 具體實(shí)現(xiàn)

本算法采用基于雙向匹配的指數(shù)來(lái)計(jì)算推薦結(jié)果，即通過(guò)供應(yīng)數(shù)據(jù)和需求數(shù)據(jù)計(jì)算用戶與用戶之間的相互吸引程度。具體的技術(shù)方案如下：

（1）服務(wù)器通過(guò)用戶所能提供的資源以及其他用戶對(duì)其評(píng)價(jià)，獲得用戶的供應(yīng)數(shù)據(jù)；同時(shí)，服務(wù)器通過(guò)跟蹤分析用戶的搜索和瀏覽歷史記錄，獲得用戶的需求數(shù)據(jù)，并建立對(duì)應(yīng)的供應(yīng)矩陣和需求矩陣。獲得的用戶供應(yīng)數(shù)據(jù)和需求數(shù)據(jù)，通過(guò)數(shù)據(jù)庫(kù)等存儲(chǔ)引擎進(jìn)行存儲(chǔ)。

（2）已獲得的供應(yīng)數(shù)據(jù)與需求數(shù)據(jù)，采用了不同的數(shù)據(jù)獲取規(guī)則。如用戶的供應(yīng)數(shù)據(jù)中，如果用戶所能提供的資源是通過(guò)評(píng)分來(lái)衡量其權(quán)重，其評(píng)分是有數(shù)值上限的，而用戶的需求數(shù)據(jù)，如果是通過(guò)用戶瀏覽某資源的次數(shù)來(lái)衡量用戶對(duì)該資源的需求權(quán)重，其瀏覽次數(shù)是沒(méi)有數(shù)值上限的。所以需要在兩種數(shù)據(jù)構(gòu)成的矩陣中進(jìn)行數(shù)值標(biāo)準(zhǔn)化。參考文獻(xiàn)[11]給出數(shù)值標(biāo)準(zhǔn)化的公式：

（3）利用數(shù)值標(biāo)準(zhǔn)化后的供應(yīng)矩陣和需求矩陣，設(shè)X和Y分別表示用戶u的需求數(shù)據(jù)構(gòu)成的矩陣和其他用戶的供應(yīng)數(shù)據(jù)構(gòu)成的矩陣。當(dāng)其他用戶的供應(yīng)矩陣與用戶u的需求矩陣相似度高，說(shuō)明其滿足用戶u的需求的概率就大，對(duì)用戶u的吸引度高。計(jì)算用戶u的需求數(shù)據(jù)和其他每個(gè)用戶的供應(yīng)數(shù)據(jù)的Pearson相關(guān)系數(shù)，記為其他用戶v對(duì)u的吸引度Att（u,v）。其中v泛指其他的任一用戶，且v屬于除目標(biāo)用戶u的其余用戶集合R。

所述Pearson相關(guān)系數(shù)的計(jì)算公式如下[12]：

其中，Xi表示用戶對(duì)第i個(gè)資源的需求指數(shù)，Yi表示用戶對(duì)第i個(gè)資源的供應(yīng)指數(shù)，Xˉ表示需求指數(shù)的和的平均值，Yˉ表示供應(yīng)指數(shù)的平均值。

（4）上述v對(duì)u的吸引度Att（u,v）范圍為[-1,1]，在該范圍內(nèi)設(shè)定閾值k，對(duì)u的吸引度大于閾值k的用戶組成u的最近鄰集合設(shè)為D。

（5）利用上述供應(yīng)矩陣和需求矩陣，計(jì)算用戶u的供應(yīng)數(shù)據(jù)和u的最近鄰集合D中每個(gè)用戶的需求數(shù)據(jù)的Pearson相關(guān)系數(shù)，記為u對(duì)最近鄰中的用戶的吸引度Att（d,u），其中d屬于D且D包含于R。

（6）為了滿足雙向匹配的原則，用戶u與用戶d應(yīng)滿足供需互補(bǔ)的關(guān)系，這樣能在最大程度上促進(jìn)合作關(guān)系的確立。計(jì)算用戶u與用戶d的相互吸引度Mat（u,d），計(jì)算公式如下：

（7）選取相互吸引度最高的N個(gè)用戶進(jìn)行相互推薦。

4 實(shí)驗(yàn)分析

為評(píng)估本文提出的基于雙向匹配的推薦算法的性能，本節(jié)進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)使用的數(shù)據(jù)集來(lái)自2012年國(guó)際知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘競(jìng)賽（KDDCup）公開的騰訊微博數(shù)據(jù)[13]，其中包括：用戶關(guān)注關(guān)系、用戶社交行為、用戶關(guān)鍵詞。

實(shí)驗(yàn)中，為進(jìn)一步模擬社交環(huán)境，對(duì)原數(shù)據(jù)集進(jìn)行了信息過(guò)濾,將用戶社交網(wǎng)絡(luò)數(shù)據(jù)中沒(méi)有用戶關(guān)鍵詞數(shù)據(jù)的用戶過(guò)濾掉，最終留下6095個(gè)用戶來(lái)模擬一個(gè)小型社交網(wǎng)絡(luò)，并作為實(shí)驗(yàn)數(shù)據(jù)集。本節(jié)評(píng)估推薦列表長(zhǎng)度N取值分別為{5,10,15,20}、本文算法的閾值k取值為0.4時(shí)不同算法的各指標(biāo)的平均值。閾值k在實(shí)際使用中隨數(shù)據(jù)集的不同而不同，可通過(guò)實(shí)驗(yàn)確定最佳值。從實(shí)驗(yàn)數(shù)據(jù)集中隨機(jī)抽取100名用戶作為待生成推薦列表的用戶。

在實(shí)驗(yàn)數(shù)據(jù)集中，記錄有每個(gè)用戶的關(guān)注關(guān)系、社交行為和關(guān)鍵詞。在item.txt中，以（用戶ID，用戶類別，用戶關(guān)鍵詞ID）三元組的形式記錄了從用戶個(gè)人資料提取的信息（如圖2），我們將用戶資料中提取的關(guān)鍵詞ID作為用戶的供應(yīng)數(shù)據(jù)，在供應(yīng)矩陣中將對(duì)應(yīng)元素置1。

圖2 用戶供應(yīng)數(shù)據(jù)

從圖2用戶提取的數(shù)據(jù)在供應(yīng)矩陣中，表示如圖3所示。

圖3用戶供應(yīng)矩陣

在user_key_word.txt中，以（用戶ID，用戶關(guān)鍵詞）二元組的形式記錄了從用戶所發(fā)微博提取的信息（如圖4），其中用戶關(guān)鍵詞的每一項(xiàng)都是“關(guān)鍵詞ID：權(quán)重”的形式，權(quán)重越大，用戶對(duì)該關(guān)鍵詞的興趣越強(qiáng)。我們將用戶所發(fā)微博中提取的關(guān)鍵詞作為用戶的需求數(shù)據(jù)，在需求矩陣中將對(duì)應(yīng)元素置為該關(guān)鍵詞的權(quán)重。

圖4用戶需求數(shù)據(jù)

從圖4用戶提取的數(shù)據(jù)在需求矩陣中，表示如下圖5所示：

圖5 用戶需求矩陣

同時(shí)，本文采用如下方法來(lái)計(jì)算用戶間相互吸引度：

（1）在用戶關(guān)鍵詞數(shù)據(jù)中，以用戶個(gè)人資料提取的關(guān)鍵詞作為用戶的供應(yīng)數(shù)據(jù)，在供應(yīng)矩陣中將對(duì)應(yīng)元素置1；

（2）在用戶關(guān)鍵詞數(shù)據(jù)中，以用戶所發(fā)微博提取的關(guān)鍵詞作為用戶的需求數(shù)據(jù)，在需求矩陣中將對(duì)應(yīng)元素置為該關(guān)鍵詞的權(quán)重；

（3）假設(shè)為用戶u生成推薦列表，則用戶u稱為目標(biāo)用戶，其他每個(gè)用戶稱為候選用戶。處理新的候選用戶時(shí)，利用供應(yīng)矩陣和需求矩陣計(jì)算候選用戶與目標(biāo)用戶的相互吸引度；

（4）將相互吸引度最高的N個(gè)用戶推薦給目標(biāo)用戶。

對(duì)于本文算法提供Top-N列表的推薦系統(tǒng)，我們通過(guò)實(shí)驗(yàn)，主要從查準(zhǔn)率、查全率、F指標(biāo)等三個(gè)常用算法指標(biāo)上進(jìn)行分析對(duì)比。其中：

查準(zhǔn)率（Precision）：為給某用戶u生成的推薦列表中，用戶u關(guān)注的人的數(shù)量與推薦中用戶總數(shù)的比值[14]，本實(shí)驗(yàn)中推薦用戶總數(shù)即為推薦列表的長(zhǎng)度。

查全率（Recall）：為給某用戶u生成的推薦列表中，用戶u關(guān)注的人的數(shù)量與用戶u實(shí)際關(guān)注的人的總數(shù)之比值[15]。

F指標(biāo)（Fmeasure）：為查準(zhǔn)率和查全率的調(diào)和平均數(shù)[14]。

實(shí)驗(yàn)中，對(duì)比基于Jaccard相似度的算法[16]和基于粉絲數(shù)的算法[17]這兩種推薦算法，對(duì)本文新提出的基于雙向匹配的推薦算法進(jìn)行綜合評(píng)估。圖6-8分別對(duì)比了三種推薦算法的各個(gè)指標(biāo)。

圖6 三種算法查準(zhǔn)率對(duì)比

從圖6可以看出：①隨著推薦列表長(zhǎng)度N的增長(zhǎng)，各算法推薦的準(zhǔn)確率在下降，查準(zhǔn)率曲線整體呈下降趨勢(shì)；②本文算法在查準(zhǔn)率比基于Jaccard相似度和基于粉絲數(shù)的算法要高；③在推薦列表長(zhǎng)度N=20時(shí)，基于粉絲數(shù)的推薦算法查準(zhǔn)率高于本文算法，這主要是由于用戶關(guān)注列表中熱門用戶的分布較均勻，導(dǎo)致不管推薦列表增長(zhǎng)多少，增長(zhǎng)的部分總會(huì)存在一部分熱門用戶，從而有利于基于粉絲數(shù)的推薦算法，這也解釋了為什么該算法的查準(zhǔn)率曲線下降較為平緩。

圖7 三種算法查全率對(duì)比

從圖7可以看出：①本文算法和基于Jaccard相似度的算法比基于粉絲數(shù)的算法查全率要高；②隨著推薦列表長(zhǎng)度N的增長(zhǎng)，查全率曲線總體呈上升趨勢(shì)。

圖8 三種算法F指標(biāo)對(duì)比

從圖8可以看出：①本文算法和基于Jaccard相似度的算法的綜合表現(xiàn)優(yōu)于基于粉絲數(shù)的算法；②在推薦列表長(zhǎng)度N=20時(shí)，基于粉絲數(shù)的算法的綜合表現(xiàn)優(yōu)于基于Jaccard相似度的算法，但仍劣于本文算法。

5 結(jié)語(yǔ)

通過(guò)上一節(jié)實(shí)驗(yàn)的綜合對(duì)比，可以看出：從查準(zhǔn)率、查全率、F指標(biāo)三方面分析，本文提出的新算法均優(yōu)于基于Jaccard相似度的算法和基于粉絲數(shù)的算法。其主要原因是由于本文算法綜合考慮了用戶間的供需關(guān)系和興趣參數(shù)。此新算法特別適用于用戶供需關(guān)系明確的平臺(tái)的推薦系統(tǒng)中，通過(guò)供需合作關(guān)系的參數(shù)重構(gòu)，解決了當(dāng)前社交網(wǎng)絡(luò)的用戶推薦技術(shù)主要依據(jù)的是用戶之間的相似性的推薦弊端，提高了用戶的社交價(jià)值，具有較高的實(shí)用性。