基于相似度和信任度的關聯規則微博好友推薦

王濤　覃錫忠　賈振紅　牛紅梅　曹傳玲

摘要：針對關聯規則個性化好友推薦中規則挖掘效率及推薦有效性不高的問題，首先提出基于散列及位圖的改進關聯規則算法BHA。該算法通過引入散列技術，減少了頻繁2項集挖掘所需的時間；利用位圖及相關性質，壓縮無關候選項，減少了數據集所需的遍歷次數。另外，在BHA的基礎上，提出基于相似度及信任度的推薦算法STA，利用出、入相似度定義信任度，有效解決了新浪微博未提供顯示信任關系的問題，同時彌補了相似度推薦未考慮用戶間遠近層次關系的缺陷。采集新浪微博用戶數據進行實驗，在關聯規則挖掘效率的對比上，BHA挖掘所需的平均時間僅為改進AprioiriTid算法的47%；在好友推薦的有效性上，推薦算法STA較SNFRBOAR算法在準確率及召回率上分別提升了15.2%和9.8%。實驗結果表明，STA能夠有效降低規則挖掘所需的平均時間，并使實際好友推薦的有效性得到提升。

關鍵詞：好友推薦；關聯規則；出相似度；入相似度；信任度

中圖分類號：TP181

文獻標志碼：A

0引言

隨著Web 2.0技術的發展，微博已經成為了繼博客之后，一種新的交流共享平臺。由此，基于微博的線上交友逐漸成為了一種流行的交友方式，用戶可以利用它將現實生活中的人際關系搬至網絡，也能建立單純的線上好友關系。然而，隨著社交網站用戶呈現爆炸式的增長，如何為用戶尋找合適的好友成為了基于社交網絡的好友推薦需解決的重要問題。

目前，個性化推薦系統中常用的推薦技術主要有基于內容的推薦，協同過濾推薦，及關聯規則推薦等[1]。其中基于關聯規則的個性化推薦技術[2]具有能夠發現用戶的新興趣點、無需領域知識和可實現“跨類型”的推薦等優點，在電子商務等領域得到了廣泛應用。本文基于現有推薦技術，對目前關聯規則好友推薦算法存在的規則挖掘效率較低及推薦有效性不高的問題展開進一步研究。

1相關工作

針對關聯規則個性化推薦的研究主要圍繞三個方面進行：1）個性化推薦關聯規則算法的研究；2）推薦模型及策略等方面的研究；3）減少挖掘產生的冗余規則研究。其中對于關聯規則算法的研究成為了當前研究的重點[3]。如文獻[4]通過考慮各項目的重要程度，對關聯規則算法進行改進。文獻[5]提出了針對新興趣點發現的協作算法。文獻[6]首先利用模糊聚類進行數據預處理，在此基礎上再進行頻繁項集的挖掘。

根據不同的應用場景，基于關聯規則的個性化推薦策略研究同樣也是一個重要的研究領域。如文獻[7]對面向大規模定制的個性化推薦的相關特性進行分析，提出了面向不同客戶群體的關聯規則個性化模型。文獻[8]以電子商務為應用背景，提出了一套個性化的電子商務推薦系統。

針對基于社交網絡的好友推薦，其推薦策略主要圍繞兩個方面展開：一方面是以用戶間的關系作為推薦依據進行好友推薦[9-11]；另一方面則是根據用戶的社交資料或發布的相關消息，從中提取用戶的興趣傾向，推薦興趣相似的好友[12-14]。本文以新浪微博好友推薦作為應用背景，首先針對規則挖掘效率較低的不足，通過基于位圖的數據格式，引入散列優化技術，并利用相關性質刪除無關候選項，對其進行了改進。其次，為提升關聯規則好友推薦的準確性，圍繞以用戶間關系為主的推薦策略進行研究，通過計算用戶的出相似度和入相似度，推薦與用戶具有共同興趣且微博社交關系較為相似的好友。在此基礎上，結合信任度計算，使好友推薦在推薦結果的有效性方面有更進一步的提升。

2關聯規則算法及改進

2.1關聯規則算法

Apriori算法是一種逐層搜索的算法，該算法的基本思想是：首先通過預先設定的最小支持度和相關性質找出所有的頻繁項集，由得到的頻繁項集產生強關聯規則。最后由設定的最小置信度，從結果中篩選出可信度較高的，形如：x→y的強關聯規則，相關定義如下：

定義1設I={i1，i2，…，in}為項目的集合；D為所有事務的集合；{Tid， T}代表一個事務， T={i1，i2，…，ik}為某事務包含的項目集，每個事務有對應的標識符Tid。其中：TI，DI。

定義2包含k個項目的集合稱為k項集，其中支持度計數為包含某k項集Ik的事務數，記為：Sup（Ik）。

定義3給定D和最小支持度min_sup，對IkI，若Sup（Ik） ≥min_sup，則稱Ik為頻繁k項集。

傳統的Apriori算法存在如下不足：

1）在剪枝策略上，需要對數據集進行多次遍歷；2）挖掘頻繁項集的同時，會產生大量無關候選項占用系統資源等。

針對這些問題，本文提出了基于散列及位圖的改進關聯規則算法BHA（Bitmap and Hashing Algorithm），主要從降低數據集的遍歷次數、壓縮無關候選項占用的系統資源兩方面進行改進。

4）利用性質2，由L3={ABC，ABE}，k=3可得：L3中包含的項集個數小于3+1，所以L4不存在。

本文提出的BHA利用位圖數據間的“與”運算有效減少了對原事務數據庫的遍歷，提升了算法的計算效率，降低了算法的時間復雜度。對于傳統Apriori算法，當事務數據庫包含的事務及相應的項目較多時，算法的絕大部分時間消耗在了頻繁2項集L2的生成上。通過利用計算散列函數的方法，將每個桶地址計數低于最小支持度的候選項集刪除，有效地對候選2項集進行了壓縮。在此基礎上，由L2生成C3的過程中，利用性質1，刪除了候選3項集C3中的無關項{ABD，ACD，ADE，BCD，BDE，CDE}，當事務庫較大時，可有效減少生成Lk（k>2）時所需的系統資源，降低算法的空間復雜度。

3BHA在微博好友推薦中的應用

基于關聯規則的好友推薦，如文獻[16]，只考慮了用戶的關注關系，并未結合微博用戶的社交關系進行深入分析。因此，本文以進一步提高好友推薦的有效性為主要目的，基于微博用戶的社交關系網絡及用戶間的連接關系，針對推薦策略展開進一步研究。

3.1相似度

首先由需要進行好友推薦的目標用戶U1，U2，U3，U4，建立微博用戶社交關系網絡G=（U，E，A，F），如圖1所示，其中，U為所有目標用戶；E為有向邊的集合；A為所有目標用戶的關注用戶集合；F為所有目標用戶的跟隨用戶集合，集合U與集合A、F的關系是：UA，UF。每條邊的箭頭指向表示用戶間的關系是關注還是跟隨。

由社交網絡的同質性理論[17]，即用戶雙方互相關注是因為他們擁有共同的興趣愛好。在此基礎上考慮用戶微博社交關系的相似程度，分別引入出相似度和入相似度概念，相關定義如下：

3.2信任度

由于目前基于信任的推薦方法大都只關注了用戶間的顯式信任關系，即由用戶事先給定的值度量信任關系，忽略了有價值的隱式信任關系[18]。針對新浪微博等社交平臺并未提供用戶間的顯式信任關系，且相似度推薦并未考慮目標用戶間遠近層次關系對推薦結果的影響，使信任度的引入變得很有必要。本文基于六度分割理論[19]，結合信任網絡的層次性，在已有出、入相似度定義的背景下，提出了基于相似度的信任度概念，改進了文獻[20]中僅考慮用戶間的關注相似，但未考慮用戶間的跟隨相似情況，使得信任度的計算在原有基礎上更加精確。

4實驗與分析

4.1實驗環境及準備

本文實驗的硬件環境為：core i5、主頻2.6GHz、內存4GB、硬盤500GB，操作系統為Windows 7，實驗工具為MySQL、Excel、Eclipse和JDK1.7。為驗證算法的有效性，本文基于新浪微博，首先選取同一朋友圈的2位微博用戶，將其作為初始目標用戶，基于廣度優先原則，遍歷所有初始目標用戶的關注及跟隨情況。由于遍歷后的數據中會有較多明星、企業等用戶出現，為保證實驗數據的典型性及實用性，僅考慮數據中跟隨情況較為平均的用戶，并將這些用戶作為目標用戶，繼續進行遍歷，以此類推，重復6次。得到的數據集中共包含6702位目標用戶，其中有570351條關注數據和391401條跟隨數據，最后將實驗采集的數據集進行預處理后分為70%的測試集和30%的訓練集。

4.2實驗結果分析

由于數據集經過預處理后，關注數據和跟隨數據的排列結構相似，因此，在關聯規則挖掘效率的對比上，實驗設定最小支持度為20，在關注及跟隨數據中，分別選取500條數據，共1000條進行第一組實驗。數據篩選的原則建立在數據稀疏程度的基礎上，并保證每條事務中包含的項目個數大于30。接著，各取1000條數據，共2000條進行第二組實驗，以此類推，直至10000條數據。將本文的BHA與文獻[16]中的改進AprioriTid算法進行對比，實驗結果如圖3所示。另外給定7000條數據，在最小支持度min_sup=10，20，30，40，50的條件下進行實驗，結果如圖4所示。

由圖3可知，在給定最小支持度的條件下，BHA算法挖掘所需的平均時間僅為前者的47%，主要原因是改進AprioriTid算法對事務集的重復遍歷極大地增加了關聯規則算法的時間復雜度，并且沒有對產生的無關候選項集進行有效的壓縮，使得算法在數據較多的情況下，挖掘所需的時間明顯上升。

由圖4可知，隨著最小支持度的增加，規則挖掘所需的運行時間都在不斷減小，當最小支持度大于60時，沒有挖掘出符合條件的強關聯規則，兩種算法的運行時間相似。

在推薦的有效性方面，首先對推薦算法STA的相似度及信任度進行驗證，設定最小支持度為10，分別利用STA及SNFBOAR算法[16]進行好友推薦，最后取其TOP-5的推薦結果，具體如表6所示。

由表中數據可以看出，STA推薦結果中排名靠前的用戶都距離目標用戶較近，主要是從高信任度用戶中選出相似度較高的好友。SNFBOAR算法排名前2的用戶主要為相似度較高、但距離目標用戶的層次較遠的用戶，由于SNFBOAR算法僅考慮了基于關注相似的相似度，使得推薦出的實際排名較為靠前的用戶會在綜合推薦度上低于STA所推薦的用戶。

其中：n表示微博推薦用戶集合（已成為好友的用戶集合）， r表示算法推薦用戶集合。

選取推薦好友個數分別為10、20、30、40、50，對兩種算法進行實驗，最后得出實驗結果如圖5和6所示。根據圖5、6可以看出，由于本文在相似度基礎上考慮了信任度對推薦結果的影響，使得推薦算法能夠在好友推薦個數發生變化時穩定保持較高的推薦準確率和召回率，相比SNFRBOAR算法，二者分別平均提升了15.2%和9.8%。

5結語

作為實際生活中朋友關系的補充，在線社交網絡消除了現實中存在的距離等阻礙因素，為用戶提供了更加方便和新穎的交友方式。本文將關聯規則個性化推薦方法運用于微博的好友推薦中，通過對算法效率和推薦策略兩方面的改進，使得規則挖掘所需的時間以及推薦的準確率、召回率都有所改善。下一步的工作主要有三點：

1）針對微博用戶數據的特點，多角度改進關聯規則挖掘算法；

2）基于本文的相關定義，對用戶信任度展開深入研究；

3）對挖掘得到的推薦結果按強關系和弱關系用戶進行篩選，進一步提升推薦的準確性。

1. 微博用戶社交關系網絡：G=（U，E，A，F），其中E為有向邊集合

2. 用戶-關注矩陣：UA 用戶-跟隨矩陣：UF

3. 用戶-關注矩陣的轉置：（UA）T用戶-跟隨矩陣的轉置：（UF）T

參考文獻：

[1]劉建國，周濤，汪秉宏.個性化推薦系統的研究進展[J].自然科學進展，2009，19（1）：1-15. （LIU J G， ZHOU T， WANG B H. Personalized recommender systems： a survey of the state-of-the-art [J]. Progress in Natural Science， 2009， 19（1）： 1-15.）

[2]LIN W， ALVAREZ S A， RUIZ C. Efficient adaptive-support association rule mining for recommendation systems [J]. Data Mining and Knowledge Discovery 2002， 6（1）： 83-105.

[3]李杰，徐勇，王云峰，等.面向個性化推薦的強關聯規則挖掘[J].系統工程理論與實踐，2009，29（8）：144-152. （LI J， XU Y，WANG Y F， et al. Strongest association rules mining for personalized recommendation [J]. System Engineering — Theory & Practice， 2009， 29（8）： 144-152.）

[4]易芝，汪琳琳，王練.基于關聯規則相關性分析的Web個性化推薦研究[J].重慶郵電大學學報（自然科學版），2007，19（2）：234-237. （YI Z， WANG L L， WANG L. Research on Web personalized recommendation based on correlation analysis of association rule [J]. Journal of Chongqing University of Posts and Communications （Natural Science），2007， 19（2）： 234-237.）

[5]唐燦，唐亮貴，劉波.一個面向新興趣點發現的模糊興趣挖掘算法[J].計算機科學，2007，34（6）：204-206. （TANG C， TANG L G， LIU B. A fuzzy interest data mining algorithm for new interest oriented [J]. Computer Science， 2007， 34（6）： 204-206.）

[6]鮑玉斌，王大玲，于戈.關聯規則和聚類分析在個性化推薦中的應用[J].東北大學學報（自然科學版），2003，24（12）：1149-1152. （BAO Y B， WANG D L， YU G. Application of association rules and clustering analysis to personalized recommendation [J]. Journal of Northeastern University （Natural Science）， 2003， 24（12）： 1149-1188.）

[7]LI J， XU Y， WANG Y， et al. Strongest association rules mining for efficient applications [C]// Proceeding of the 2007 Fourth IEEE Conference on Service Systems and Service Management. Piscataway， NJ： 2007： 502-507.

[8]丁振國，陳靜.基于關聯規則的個性化推薦系統[J].計算機集成制造系統，2003，9（10）：891-893. （DING Z G， CHEN J. Individuation recommendation system based on association rule [J]. Computer Integrated Manufacturing Systems， 2003， 9（10）： 891-893.）

[9]陳克寒，韓盼盼，吳健.基于用戶聚類的異構社交網絡推薦算法[J].計算機學報，2013，36（2）：349-359. （CHEN K H， HAN P P， WU J. User clustering based social network recommendation [J]. Chinese Journal of Computers， 2013， 36（2）： 349-359.）

[10]王玙，高琳.基于社交圈的在線社交網絡朋友推薦算法[J].計算機學報，2014，37（4）：801-808. （WANG Y， GAO L. Social circle-based algorithm for friend recommendation in online social networks [J]. Chinese Journal of Computers， 2014， 37（4）： 801-808.）

[11]王名揚，賈沖沖，楊東輝.基于三度影響力的社交好友推薦機制[J].計算機應用，2015，35（7）：1984-1987. （WANG M Y， JIA C C， YANG D H. Social friend recommendation mechanism based on three-degree influence [J]. Journal of Computer Applications， 2015， 35（7）： 1984-1987.）

[12]JECKMANS A， TANG Q， HARTEL P. Poster： privacy-preserving profile similarity computation in online social networks [C]// CCS 11： Proceedings of the 18th ACM Conference on Computer and Communications Security. New York： ACM， 2011： 793-796.

[13]PIAO S， WHITTLE J. A feasibility study on extracting twitter users interests using NLP tools for serendipitous connections [C]// Proceedings of the 2011 IEEE Third International Conference on Privacy， Security， Risk and Trust （PASSAT） and 2011 IEEE Third International Conference on Social Computing （SocialCom）. Piscataway， NJ： IEEE， 2011： 910-915.

[14]唐曉波，祝黎，謝力.基于主題的微博二級好友推薦模型研究[J].圖書情報工作，2014，58（9）：105-113. （TANG X B， ZHU L， XIE L. Two-level microblog friend recommendation based on topic model [J]. Library and Information Service， 2014， 58（9）： 105-113.）

[15]PARK J S， CHEN M-S， YU P S. Using a hash-based method with transaction trimming for mining association rules [J]. IEEE Transactions on Knowledge and Data Engineering， 1997， 9（5）： 813-825.

[16]向程冠，熊世恒，王東.基于關聯規則的社交網絡好友推薦算法[J].中國科技論文，2014，9（1）：87-91.（XIANG C G， XIONG S H， WANG D. Social network friends recommendation algorithm based on association rules [J]. China Sciencepaper， 2014， 9（1）： 87-91.）

[17]張中峰，李秋丹.社交網站中潛在好友推薦模型研究[J].情報學報，2011，30（12）：1319-1325. （ZHANG Z F， LI Q D. Latent friend recommendation in social network services[J]. Journal of the China Society for Scientific and Technical Information， 2011， 30（12）： 1319-1325.）

[18]XING X， ZHANG W， JIA Z， et al. Trust-based top-k item recommendation in social networks [J]. Journal of Information and Computational Science， 2013， 10（12）： 3685-3696.

http：//www.joics.com/publishedpapers/2013_10_12_3685_3696.pdf

[19]KE X. A social networking services system based on the “six degrees of separation” theory and damping factors [C]// ICFN 2010： Proceedings of the 2010 2nd International Conference on Future Networks. Washington， DC： IEEE Computer Society， 2010： 438-441.

[20]XING X， ZHANG W， JIA Z， et al. Trust-based social item recommendation： a case study [C]// Proceedings of the 2012 2nd International Conference on Computer Science and Network Technology. Piscataway， NJ： IEEE， 2012： 1050-1053.