基于關聯規則和相似性在社交好友推薦算法的研究

丁瑞 謝志存 盧彪

【摘 要】隨著移動互聯網技術的飛速發展，通信技術的發展以及社交平臺的多樣化，通過手機在社交平臺上進行人機通信已經成為人們交流的重要手段。在社交平臺上進行交流預計會有更多的朋友，但是很難從如此眾多的用戶中找到志同道合的朋友。如何準確地向用戶推薦具有相似興趣的朋友，是所有社交平臺都試圖解決的問題，也是社交朋友推薦算法的研究熱點。因此，我們想開發一種更準確，更方便的社交好友推薦算法，并進行創新性的改變。

【關鍵詞】關聯規則;相似性;社交推薦

以往的推薦算法都沒有很好的考慮各方面的問題，而我們想要真正的找到一個志趣相投的好友，我們既要考慮人物關系，也要考慮到用戶發布的信息相似性。所以我們在進行好友推薦的時候主要從這來兩個方面入手，可以達到更好的推薦效果。因此，我們提出來一種基于關聯規則和相似性的好友推薦算法，我們用Pesrson相關系數算法處理用戶間發布的信息的相似特征值，相似度到達給定閾值的信息可視為一條交易記錄，生成交易數據庫D，用關聯規則改進算法來處理特征值數據，計算出二階候選項集，并存入推薦規則數據庫R，最后選取支持數最高的前N個用戶加入到推薦列表中，將得到推薦列表展現給用戶。

一、相似性的測試研究

研究Pearson相關系數算法的原理，并使用Pearson算法計算交易數據集D。需要確定用戶發布的信息是否是相同類型的信息，并且沒有可供參考的上下文、句子或關鍵字。相似度用于衡量它們是否相同，同類信息是直接有效的方式。因此，當推薦朋友時，在計算相同的“事物”分段信息的相似度時，計算用戶發布的信息的相似度時，采用句子詞性語言序列余弦相似度算法。

Pearson相關系數是在余弦相似性的基礎上加以改進的，考慮到不同用戶的熱點關鍵字不同的問題，即對用戶進行去中心化，因此在實驗研究算法改進上運用了Pearson相關系數算法來計算出用戶間發布的信息的相似特征值。

對Pearson相關系數算法研究可知，句子之間最終可能產生多種相似關系，有線性相關關系、非線性相關關系、周期相關關系和不相關關系。通過Pearson相關系數，除了得到相關函數圖像，還有二者之間的相關系數，最后由眾多相關系數生成交易數據庫D。

二、關聯規則算法優化

（一）構建改進后的關聯規則Apriori算法

Apriori算法改進核心思想是：改進算法時，將準備k階Tid表的生成是為了生成k + 1階候選項目集。生成k階Tid表的過程中，使用Apriori_gen生成k階候選項目集進行排序。如果交易項目中包含的所有k個級別的候選項目的所有元素數均小于或等于k，則此交易項目不會生成k + 1個級別的候選項目集，因此由此交易項目候選項集，不必編寫K級TID表，生成的k級TID表中的數據量小于上一個TID表中的數據量。通過對Apriori算法步驟流程和數學思想的理解，并實現算法運行，最終得到推薦規則數據庫R。表1為交易數據庫（Transaction Database）D的所有大項集，取最小支持數為3。

改進后的AprioriTid算法具體分析如下：

1）生成 1 階候選項集 C[1]，生成 1 階大項集L[1]，同時生成 1 階 TID 表 TID[1]。如表2所示。

2）通過改進的Apriori算法以次對各步大項集進行運算，直至最后的大項集為NULL為止。通過算法運算得知，在生成5階大項集L[5]時為 null，算法結束。最后可得出大項集為：L={{A}，{B}，{C}，{E}，{A，B}，{B，C}，{B，E}，{C，E}，{A，B，E}，{B，C，E}，{A，C，E}，{A，B，C，E}}。

（二）社交網絡好友推薦算法

關聯規則挖掘中Apriori算法在于挖掘隱含的、未知的、有價值的關聯模式，社交平臺中尋找志趣相投的好友，就是要在找出隱含的、未知的、有意義的好友關聯規則，在社交平臺中把Apriori算法用于好友推薦中會取得較好的效果。

本文算法具體步驟如下：

步驟1 通過句子詞性語言序列余弦相似度算法生成交易數據庫 D。

步驟2 使用改進后的AprioriTid算法計算出二階大項集。

步驟3 將二階大項集存入推薦規則數據庫R。

步驟4 根據輸入的用戶ID，在規則庫R中檢索出含有用戶ID 的二階大項集，選擇支持數最高的前N個用戶放入推薦集合Ur，并將Ur推薦給用戶。

三、實驗結果與分析

（一）數據集

為驗證本文提出的推薦算法可行性與有效性，利用某網絡社交平臺中的實際生產數據作為實驗數據，主要包含用戶發布的65042條動態碎片信息，共有用戶1000人。為能準確地反映實驗結果，將用戶數據集的3/4作為訓練集，1/4作為測試集。

（二）算法可行性檢測

覆蓋率（Coverage），評價一個社交平臺好友推薦算法往往從覆蓋率（Coverage）和準確率（Precision）兩方面進行考量，覆蓋率主要用于觀察推薦算法推薦的好友集合Ure與實際可推薦好友集合Ureal交集匯總好友數量占實際可推薦的好友比率。

準確率（Precision），準確率主要用來衡量算法的正確性、可行性，反映推薦出的準確好友數所占好友數的百分比，越高越準確性越好。

通過對本文算法和傳統的AprioriTid算法的比較，可以看出，本文算法在相同的數據記錄處理中，所需的時間更少（如圖1）。

四、結束語

如何在社交網絡過程中找到一個或多個志趣相投的朋友。在本文關于社交朋友推薦算法的研究中，我們不僅考慮社交角色的關系，而且考慮用戶發布的信息的相似性。因此，在推薦朋友時，我們主要從這兩個方面入手，并使用改進的關聯規則推薦算法向用戶展示朋友列表。事實證明，類似于關聯規則的朋友推薦算法在用戶推薦中具有很大的研究價值，最終可以為用戶的社交互動帶來更多的便利。