基于FP-Growth的社交好友推薦方法研究

熊才權，陳 曦

(湖北工業大學計算機學院，湖北 武漢 430068)

隨著Web2.0時代的發展，用戶成為網絡內容的主導者。人們通過網絡社交活動，例如評論關注轉發收藏等形式參與網絡社交獲取相應的信息。然而隨著網絡社區的發展，用戶數量規模的急劇擴增，人們對社交的需求更加豐富，人們不僅僅想要通過社交平臺跟線下的好友進行交互，還想通過網上社交活動拓展自己的朋友圈，以獲取一些自己需要的資源和時興的動態消息。在如今主流的社交網絡上的好友推薦大多采取FOF[1]理論拓展朋友圈，如果兩個用戶擁有很多共同好友，那么他們是朋友的概率將會很大。Armentano[2,3]等人將社交網絡結構和用戶特征結合，將鄰域內滿足條件的用戶推薦給目標用戶。Akbari[4]等人提出了一種基于圖拓撲和人工蜂群的新方法，改進了FOF為三度分離的好友推薦，有效的擴大了朋友推薦的范圍。基于已有的好友進行推薦，雖然具有較高的可信度，但是更多的是推薦線下可能認識的好友，無法推薦社交網絡上基于興趣相同的好友，同時也存在冷啟動問題。YANG[5]等人使用社會化標簽將社交網絡拓撲結構和用戶興趣網絡結合起來進行個性化推薦。Wu W[6]等人使用詞頻反文檔TF-IDF算法提取用戶文本關鍵詞，為每個用戶自動添加興趣和標簽，為目標用戶推薦興趣相似的用戶。肖曉麗[7]等人提出基于用戶興趣和社交信任的聚類推薦算法，對于用戶數據矩陣稀疏和擴展性差問題提出了解決方案，在一定程度上解決了冷啟動問題。基于興趣的好友推薦可以很好的解決社交網絡中朋友圈拓展問題，但是容易忽略潛在好友。王兵輝[8]提出社交網絡中潛在好友推薦算法。向程冠[9]等人改進AprioriTid算法應用于好友推薦。基于關聯規則算法的好友推薦可以解決復雜的好友關系網絡問題，同時也可以挖掘潛在好友。因此，本研究通過分析用戶相互關注關系挖掘用戶的好友關系，通過實驗比較分析關聯規則算法FP-Growth和Apriori算法計算好友關系數據，挖掘社交網絡中的好友頻繁模式，為好友推薦提供有效的建議。

1 好友關系復雜網絡問題

微博作為國內成熟的社交平臺，由于其主要的社交功能屬性，及其作為信息交流的集散地，大量的用戶活躍在其中，從而提供了可獲取的社交關系網絡，通過研究該平臺的社交網絡關系，不僅可以實現推薦系統的應用，同時通過對復雜的社會關系的解析可以提供高價值的數據分析。

圖1 單一/多好友關注關系網絡結構圖

用戶可以通過關注這種形式形成強關聯模式如圖1，一個用戶可以根據興趣關注某個好友，同時可以看到該好友還關注了哪些好友，而好友的好友還有其好友，如此，可以擴增好友圈，但尋找的過程中，通過瀏覽好友短文本信息，耗時久且效率低，并且一旦用戶根據興趣標簽關注多個好友，那么好友的好友的數量將激增，用戶將很難找到“志同道合”的好友，而數據挖掘知識能夠很好解決這類復雜問題，通過設定閾值，利用關聯規則算法挖掘出其中哪幾個好友常常是同時被關注的，也就是說某個好友被關注的同時還會連帶關注某些好友，以此強關聯模式幫助用戶找到相似興趣的好友具有較高的推薦可信度。

2 基于FP-Growth的好友推薦方法

1.1 FP-Growth算法

FP-growth算法是深度優先算法中最新最高效的本質上不同于Apriori算法的經典算法，將數據庫的信息壓縮成一個描述頻繁項相關信息的頻繁模式樹。Apriori算法有兩步驟：一是發現所有的頻繁項集；二是生成強關聯規則。發現頻繁項集是生成強關聯規則的前提也是算法中關鍵的步驟。在Apriori算法中利用“頻繁項集的子集是頻繁項集，非頻繁項集的超集是非頻繁項集”這一性質有效對頻繁項集進行修剪[10]。Apriori算法有兩個致命的性能瓶頸：1)產生的候選集過大(尤其是2-項集)，算法必須耗費大量的時間處理候選項集2)多次掃描數據庫，需要很大的I/O負載，在時間、空間上都需要付出很大的代價。FP-Growth[11]算法不同于Apriori算法,主要采取數據結構中樹存儲的概念對數據集進行挖掘，其中有兩個關鍵步驟：一是生成頻繁模式樹FP-tree；二是在頻繁模式樹FP-tree上挖掘頻繁項集，FPTree算法在不生成候選項的情況下完成Apriori算法的功能。

FP-Growth算法的效率優于一般的類Apriori算法，因為FP-Tree算法的整個過程只需要遍歷兩次事務數據庫，并且把大量的數據壓縮存儲在樹中，時間與空間的開銷都優于Apriori算法。

1.2 基于FP-Growth的好友頻繁模式挖掘

在復雜的社交網絡中，通過FP-Growth算法可以挖掘用戶-好友的關注關系。如表1好友關系數據集中，suid表示用戶編號，tuid表示用戶關注的好友。

好友頻繁模式挖掘步驟：

1)設定最小支持度為2。

2)tuid列中得到頻繁項的集合和每個頻繁項的支持度并降序排序{T2:7,T1:6,T3:6,T4:2,T5:2}記為L，依據L對tuid列重排序，如{T1,T2,T5}重排序后為{T2,T1,T5}，以此類推。

3)構建好友關系FP-Tree,以null為根節點，將tuid重排序后的項集依次插入樹中，如果項集中元素在FP-Tree中沒有節點，則重新建立節點。如果節點已經存在，則在原有節點上計數加1，直到項集中所有元素插入到樹中，則好友關系FP-tree樹構建完成圖2。

表1 好友關系數據集

圖2 構建好友關系FP-Tree

4)調用FP-growth(Tree，null)開始進行頻繁模式挖掘。偽代碼如下

輸入：好友關系Tree,模式后綴 a

過程：

if Tree含單個路徑R then

for 單路徑R每個節點(b) do

頻繁模式b U a組合，

該組合支持度support=b支持度(舍去小于設定支持度為2的組合)；

end for

else

for 多路徑項頭表D

b=DiU a組合為模式后綴，生成其條件模式基c

產生一個頻繁模式c U b組合，其支持度support =c支持度>2;

end for

end if

if Treeb≠? then

調用 FP_growth (Treeb,b)；

end if

輸出：滿足支持度的好友頻繁模式

由以上好友關系FP-Tree樹,可以根據模式后綴挖掘頻繁模式。如果條件FP-Tree是單路徑的，則可以通過簡單排列組合得到該后綴樹的頻繁模式。以模式后綴為T5的條件模式樹為例：它的條件模式基為(T2T1:1)，(T2T1T3:1)，通過組合變成{T2:2，T1:2，T3:1}，由于{T3:1}支持度小于1舍去，則通過排列組合后可以得到模式后綴為T5并且支持度大于2的頻繁模式：{ T2T5:2,T1T5:2,T2T1T5:2}。

圖3 模式后綴為T5的條件模式樹

單路徑條件模式樹可以直接采用排列組合挖掘頻繁模式，但是對于多路徑情況的條件，模式樹需要另外的考慮。以模式后綴為T3的條件模式樹為例，它的條件模式基為(T2T1:2),(T2:2),(T1:2)，這是一個多路徑樹，

首先通過模式后綴T3和項頭表中的每一項做組合得到一組頻繁模式{T2T3:4,T1T3:4}，然后遞歸調用FP-Growth，模式后綴為{T1,T3},它的條件模式基為{T2：2}，它是單路徑條件模式樹，通過組合可得{T1T2T3:2}。最后還需要挖掘模式后綴為{T2，T3}的頻繁模式，由于該模式后綴為空，則遞歸調用結束。最終得出模式后綴為T3的頻繁模式為{ T2T3:4,T1T3:4,T1T2T3:2}。

圖4 模式后綴為T3的條件模式樹

基于FP-growth好友推薦算法，最終得到支持度不小于2的好友頻繁模式見表2。

表2 好友頻繁模式生成表

從好友模式生成表中，挖掘出好友關系數據集中所有的頻繁模式，其中{T2T5:2}表示T2,T5用戶同時被關注，可以看作是一類組合，它的支持度為2。{T2T1T3:2}表示T2,T1,T3用戶同時被關注，該組合的支持度也為2。{T2T1:4}表示T2,T1用戶同時被關注，它的支持度為4。對于滿足最小支持度的組合也就是頻繁模式都可以挖掘出來，如果在社交平臺上需要某一類組合的最小支持度為20,那么通過FP-Growth遞歸挖掘，再通過降序排序就可以推薦Top-N好友組合，這就使得社交網絡復雜關注關系的好友推薦具有推薦意義。

3 實驗評估

3.1 實驗數據集

為了驗證算法的有效性，將新浪微博平臺作為實驗的對象，實驗數據集從新浪微博平臺抓取，通過清理、集成、變換3個步驟對數據集進行處理，將處理后的63641條新浪微博信息，1391718條用戶好友關系存儲數據庫。實驗中算法實現采用JAVA語言編寫,推薦規則的存儲采用Mysql5.5數據庫，實驗運行時的硬件配置為Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz (4 CPUs)，8G內存，256G 固態硬盤，操作系統為Win10。

3.2 評價指標

評價好友社交平臺采用召回率(Recall) 、準確率(Precision)和F1度量(F1-measure)三個指標進行評估，召回率主要用于觀察推薦算法推薦的好友集合Urc與實際可推薦好友集合Ureal交集中好友數量占實際可推薦的好友比率

(1)

準確率主要用來衡量算法的正確性、可行性，反應推薦出的準確好友數所占推薦好友數的百分比，越高準確性越好，計算如下：

(2)

F1度量(F1-measure)將準確率和召回率的調和平均數作為一個評價標準。F1度量綜合考慮了推薦系統的性能，其表達公式如下：

(3)

3.3 實驗結果與分析

在本次實驗中，將FP-Growth算法和Apriori算法在好友推薦的實例中進行對比實驗，主要通過以下三個方面：

1)設定支持度為20，從微博用戶關注數據集中生成1 k、2 k、3 k、4 k、5 k、6 k、7 k 、8 k數據集，比較算法運行效率如圖5所示。

圖5 FP-Growth算法和Apriori算法數據增大時執行時間比較

從圖1 FP-Growth算法和Apriori算法數據增大時執行時間比較所示，在相同支持度的情況下，隨著數據量的增大，FP-Growth算法在執行時間上總是優于Apriori算法，由于FP-Growth利用FP-Tree樹的數據結構進行存儲和計算數據，不需要頻繁掃描數據庫，利用計算機內存計算，大大減少了計算數據時間。

2)設定恒定的用戶關注數據集，通過調整最小支持度為10、20、30、40、50、60、70、80比較算法運行效率如圖6所示。

圖6 FP-Growth算法和Apriori算法支持數數增大時執行時間比較

本次實驗從數據集中篩選2k數據量，通過調整不同的支持度比較FP-Growth算法和Apriori算法執行時間，從圖表中可以看出FP-Growth算法執行效率較高。隨著最小支持度增大，候選項集將會相應減少，兩種算法運行效率都會相應提高。

3)為了驗證本文FP-Growth好友推薦模型的有效性，本實驗將其與現有的社交網絡好友推薦模型：基于關系的兩階段好友推薦模型[12](簡寫為M1模型)、以及基于協同過濾的好友推薦模型[13](簡寫為M2模型)進行對比實驗，推薦目標用戶Top10，Top20，Top30，Top40好友，并且比較、觀察三個模型在不同推薦好友數量下的F1度量值隨推薦好友數量變化的結果見圖7。

圖7 對比實驗結果圖

從實驗結果看出FP-Growth好友推薦算法在推薦好友數量為30時，F1值達到最高，在準確率和召回率上都相對優于其他兩種模型。

4 結論

FP-Growth算法利用內存運算比較Apriori算法在執行時間上有明顯的優勢，在準確率和召回率上這兩個算法結果相同。本實驗通過FP-Growth好友推薦模型與基于關系的兩階段好友推薦模型、基于內容的好友推薦模型作比較，其FP-Growth好友推薦算法相較于其他兩種算法具有較高的F1度量，同時由于FP-Growth關聯規則算法，是根據用戶間的關注關系進行數據挖掘，在實際應用場景推薦中，更具有可信度，在社交網絡中可以很好為用戶提供好友推薦序列，提高用戶交友體驗，但是基于FP-Growth算法本身是基于內存的計算，對于大數據運行還是需要采取并行化計算，同時由于本文只是對所有的用戶關注關系進行數據挖掘，并沒有涉及用戶文本，推薦結果比較多樣，所以在今后的研究工作中還需要抽取用戶文本主題，通過對主題聚類更加精確地給目標用戶推薦好友。