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

熊才權(quán)，陳 曦

(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430068)

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

1 好友關(guān)系復(fù)雜網(wǎng)絡(luò)問題

微博作為國內(nèi)成熟的社交平臺，由于其主要的社交功能屬性，及其作為信息交流的集散地，大量的用戶活躍在其中，從而提供了可獲取的社交關(guān)系網(wǎng)絡(luò)，通過研究該平臺的社交網(wǎng)絡(luò)關(guān)系，不僅可以實(shí)現(xiàn)推薦系統(tǒng)的應(yīng)用，同時(shí)通過對復(fù)雜的社會關(guān)系的解析可以提供高價(jià)值的數(shù)據(jù)分析。

圖1 單一/多好友關(guān)注關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)圖

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

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

1.1 FP-Growth算法

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

FP-Growth算法的效率優(yōu)于一般的類Apriori算法，因?yàn)镕P-Tree算法的整個(gè)過程只需要遍歷兩次事務(wù)數(shù)據(jù)庫，并且把大量的數(shù)據(jù)壓縮存儲在樹中，時(shí)間與空間的開銷都優(yōu)于Apriori算法。

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

在復(fù)雜的社交網(wǎng)絡(luò)中，通過FP-Growth算法可以挖掘用戶-好友的關(guān)注關(guān)系。如表1好友關(guān)系數(shù)據(jù)集中，suid表示用戶編號，tuid表示用戶關(guān)注的好友。

好友頻繁模式挖掘步驟：

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

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

3)構(gòu)建好友關(guān)系FP-Tree,以null為根節(jié)點(diǎn)，將tuid重排序后的項(xiàng)集依次插入樹中，如果項(xiàng)集中元素在FP-Tree中沒有節(jié)點(diǎn)，則重新建立節(jié)點(diǎn)。如果節(jié)點(diǎn)已經(jīng)存在，則在原有節(jié)點(diǎn)上計(jì)數(shù)加1，直到項(xiàng)集中所有元素插入到樹中，則好友關(guān)系FP-tree樹構(gòu)建完成圖2。

表1 好友關(guān)系數(shù)據(jù)集

圖2 構(gòu)建好友關(guān)系FP-Tree

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

輸入：好友關(guān)系Tree,模式后綴 a

過程：

if Tree含單個(gè)路徑R then

for 單路徑R每個(gè)節(jié)點(diǎn)(b) do

頻繁模式b U a組合，

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

end for

else

for 多路徑項(xiàng)頭表D

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

產(chǎn)生一個(gè)頻繁模式c U b組合，其支持度support =c支持度>2;

end for

end if

if Treeb≠? then

調(diào)用 FP_growth (Treeb,b)；

end if

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

由以上好友關(guān)系FP-Tree樹,可以根據(jù)模式后綴挖掘頻繁模式。如果條件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)，這是一個(gè)多路徑樹，

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

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

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

表2 好友頻繁模式生成表

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

3 實(shí)驗(yàn)評估

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 評價(jià)指標(biāo)

評價(jià)好友社交平臺采用召回率(Recall) 、準(zhǔn)確率(Precision)和F1度量(F1-measure)三個(gè)指標(biāo)進(jìn)行評估，召回率主要用于觀察推薦算法推薦的好友集合Urc與實(shí)際可推薦好友集合Ureal交集中好友數(shù)量占實(shí)際可推薦的好友比率

(1)

準(zhǔn)確率主要用來衡量算法的正確性、可行性，反應(yīng)推薦出的準(zhǔn)確好友數(shù)所占推薦好友數(shù)的百分比，越高準(zhǔn)確性越好，計(jì)算如下：

(2)

F1度量(F1-measure)將準(zhǔn)確率和召回率的調(diào)和平均數(shù)作為一個(gè)評價(jià)標(biāo)準(zhǔn)。F1度量綜合考慮了推薦系統(tǒng)的性能，其表達(dá)公式如下：

(3)

3.3 實(shí)驗(yàn)結(jié)果與分析

在本次實(shí)驗(yàn)中，將FP-Growth算法和Apriori算法在好友推薦的實(shí)例中進(jìn)行對比實(shí)驗(yàn)，主要通過以下三個(gè)方面：

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

圖5 FP-Growth算法和Apriori算法數(shù)據(jù)增大時(shí)執(zhí)行時(shí)間比較

從圖1 FP-Growth算法和Apriori算法數(shù)據(jù)增大時(shí)執(zhí)行時(shí)間比較所示，在相同支持度的情況下，隨著數(shù)據(jù)量的增大，F(xiàn)P-Growth算法在執(zhí)行時(shí)間上總是優(yōu)于Apriori算法，由于FP-Growth利用FP-Tree樹的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲和計(jì)算數(shù)據(jù)，不需要頻繁掃描數(shù)據(jù)庫，利用計(jì)算機(jī)內(nèi)存計(jì)算，大大減少了計(jì)算數(shù)據(jù)時(shí)間。

2)設(shè)定恒定的用戶關(guān)注數(shù)據(jù)集，通過調(diào)整最小支持度為10、20、30、40、50、60、70、80比較算法運(yùn)行效率如圖6所示。

圖6 FP-Growth算法和Apriori算法支持?jǐn)?shù)數(shù)增大時(shí)執(zhí)行時(shí)間比較

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

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

圖7 對比實(shí)驗(yàn)結(jié)果圖

從實(shí)驗(yàn)結(jié)果看出FP-Growth好友推薦算法在推薦好友數(shù)量為30時(shí)，F(xiàn)1值達(dá)到最高，在準(zhǔn)確率和召回率上都相對優(yōu)于其他兩種模型。

4 結(jié)論

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