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

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

關(guān)鍵詞：好友推薦；關(guān)聯(lián)規(guī)則；出相似度；入相似度；信任度

中圖分類號：TP181

文獻標(biāo)志碼：A

0引言

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

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

1相關(guān)工作

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

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

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

2關(guān)聯(lián)規(guī)則算法及改進

2.1關(guān)聯(lián)規(guī)則算法

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

定義1設(shè)I={i1，i2，…，in}為項目的集合；D為所有事務(wù)的集合；{Tid， T}代表一個事務(wù)， T={i1，i2，…，ik}為某事務(wù)包含的項目集，每個事務(wù)有對應(yīng)的標(biāo)識符Tid。其中：TI，DI。

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

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

傳統(tǒng)的Apriori算法存在如下不足：

1）在剪枝策略上，需要對數(shù)據(jù)集進行多次遍歷；2）挖掘頻繁項集的同時，會產(chǎn)生大量無關(guān)候選項占用系統(tǒng)資源等。

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

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

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

3BHA在微博好友推薦中的應(yīng)用

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

3.1相似度

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

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

3.2信任度

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

4實驗與分析

4.1實驗環(huán)境及準(zhǔn)備

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

4.2實驗結(jié)果分析

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

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

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

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

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

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

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

5結(jié)語

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

1）針對微博用戶數(shù)據(jù)的特點，多角度改進關(guān)聯(lián)規(guī)則挖掘算法；

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

3）對挖掘得到的推薦結(jié)果按強關(guān)系和弱關(guān)系用戶進行篩選，進一步提升推薦的準(zhǔn)確性。

1. 微博用戶社交關(guān)系網(wǎng)絡(luò)：G=（U，E，A，F(xiàn)），其中E為有向邊集合

2. 用戶-關(guān)注矩陣：UA 用戶-跟隨矩陣：UF

3. 用戶-關(guān)注矩陣的轉(zhuǎn)置：（UA）T用戶-跟隨矩陣的轉(zhuǎn)置：（UF）T

參考文獻：

[1]劉建國，周濤，汪秉宏.個性化推薦系統(tǒng)的研究進展[J].自然科學(xué)進展，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]李杰，徐勇，王云峰，等.面向個性化推薦的強關(guān)聯(lián)規(guī)則挖掘[J].系統(tǒng)工程理論與實踐，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]易芝，汪琳琳，王練.基于關(guān)聯(lián)規(guī)則相關(guān)性分析的Web個性化推薦研究[J].重慶郵電大學(xué)學(xué)報（自然科學(xué)版），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]唐燦，唐亮貴，劉波.一個面向新興趣點發(fā)現(xiàn)的模糊興趣挖掘算法[J].計算機科學(xué)，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]鮑玉斌，王大玲，于戈.關(guān)聯(lián)規(guī)則和聚類分析在個性化推薦中的應(yīng)用[J].東北大學(xué)學(xué)報（自然科學(xué)版），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]丁振國，陳靜.基于關(guān)聯(lián)規(guī)則的個性化推薦系統(tǒng)[J].計算機集成制造系統(tǒng)，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]陳克寒，韓盼盼，吳健.基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J].計算機學(xué)報，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]王玙，高琳.基于社交圈的在線社交網(wǎng)絡(luò)朋友推薦算法[J].計算機學(xué)報，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].計算機應(yīng)用，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]向程冠，熊世恒，王東.基于關(guān)聯(lián)規(guī)則的社交網(wǎng)絡(luò)好友推薦算法[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]張中峰，李秋丹.社交網(wǎng)站中潛在好友推薦模型研究[J].情報學(xué)報，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.