基于關(guān)聯(lián)規(guī)則和相似性在社交好友推薦算法的研究

丁瑞 謝志存 盧彪

【摘 要】隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，通信技術(shù)的發(fā)展以及社交平臺(tái)的多樣化，通過(guò)手機(jī)在社交平臺(tái)上進(jìn)行人機(jī)通信已經(jīng)成為人們交流的重要手段。在社交平臺(tái)上進(jìn)行交流預(yù)計(jì)會(huì)有更多的朋友，但是很難從如此眾多的用戶中找到志同道合的朋友。如何準(zhǔn)確地向用戶推薦具有相似興趣的朋友，是所有社交平臺(tái)都試圖解決的問(wèn)題，也是社交朋友推薦算法的研究熱點(diǎn)。因此，我們想開(kāi)發(fā)一種更準(zhǔn)確，更方便的社交好友推薦算法，并進(jìn)行創(chuàng)新性的改變。

【關(guān)鍵詞】關(guān)聯(lián)規(guī)則;相似性;社交推薦

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

一、相似性的測(cè)試研究

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

Pearson相關(guān)系數(shù)是在余弦相似性的基礎(chǔ)上加以改進(jìn)的，考慮到不同用戶的熱點(diǎn)關(guān)鍵字不同的問(wèn)題，即對(duì)用戶進(jìn)行去中心化，因此在實(shí)驗(yàn)研究算法改進(jìn)上運(yùn)用了Pearson相關(guān)系數(shù)算法來(lái)計(jì)算出用戶間發(fā)布的信息的相似特征值。

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

二、關(guān)聯(lián)規(guī)則算法優(yōu)化

（一）構(gòu)建改進(jìn)后的關(guān)聯(lián)規(guī)則Apriori算法

Apriori算法改進(jìn)核心思想是：改進(jìn)算法時(shí)，將準(zhǔn)備k階Tid表的生成是為了生成k + 1階候選項(xiàng)目集。生成k階Tid表的過(guò)程中，使用Apriori_gen生成k階候選項(xiàng)目集進(jìn)行排序。如果交易項(xiàng)目中包含的所有k個(gè)級(jí)別的候選項(xiàng)目的所有元素?cái)?shù)均小于或等于k，則此交易項(xiàng)目不會(huì)生成k + 1個(gè)級(jí)別的候選項(xiàng)目集，因此由此交易項(xiàng)目候選項(xiàng)集，不必編寫K級(jí)TID表，生成的k級(jí)TID表中的數(shù)據(jù)量小于上一個(gè)TID表中的數(shù)據(jù)量。通過(guò)對(duì)Apriori算法步驟流程和數(shù)學(xué)思想的理解，并實(shí)現(xiàn)算法運(yùn)行，最終得到推薦規(guī)則數(shù)據(jù)庫(kù)R。表1為交易數(shù)據(jù)庫(kù)（Transaction Database）D的所有大項(xiàng)集，取最小支持?jǐn)?shù)為3。

改進(jìn)后的AprioriTid算法具體分析如下：

1）生成 1 階候選項(xiàng)集 C[1]，生成 1 階大項(xiàng)集L[1]，同時(shí)生成 1 階 TID 表 TID[1]。如表2所示。

2）通過(guò)改進(jìn)的Apriori算法以次對(duì)各步大項(xiàng)集進(jìn)行運(yùn)算，直至最后的大項(xiàng)集為NULL為止。通過(guò)算法運(yùn)算得知，在生成5階大項(xiàng)集L[5]時(shí)為 null，算法結(jié)束。最后可得出大項(xiàng)集為：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}}。

（二）社交網(wǎng)絡(luò)好友推薦算法

關(guān)聯(lián)規(guī)則挖掘中Apriori算法在于挖掘隱含的、未知的、有價(jià)值的關(guān)聯(lián)模式，社交平臺(tái)中尋找志趣相投的好友，就是要在找出隱含的、未知的、有意義的好友關(guān)聯(lián)規(guī)則，在社交平臺(tái)中把Apriori算法用于好友推薦中會(huì)取得較好的效果。

本文算法具體步驟如下：

步驟1 通過(guò)句子詞性語(yǔ)言序列余弦相似度算法生成交易數(shù)據(jù)庫(kù) D。

步驟2 使用改進(jìn)后的AprioriTid算法計(jì)算出二階大項(xiàng)集。

步驟3 將二階大項(xiàng)集存入推薦規(guī)則數(shù)據(jù)庫(kù)R。

步驟4 根據(jù)輸入的用戶ID，在規(guī)則庫(kù)R中檢索出含有用戶ID 的二階大項(xiàng)集，選擇支持?jǐn)?shù)最高的前N個(gè)用戶放入推薦集合Ur，并將Ur推薦給用戶。

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

（一）數(shù)據(jù)集

為驗(yàn)證本文提出的推薦算法可行性與有效性，利用某網(wǎng)絡(luò)社交平臺(tái)中的實(shí)際生產(chǎn)數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，主要包含用戶發(fā)布的65042條動(dòng)態(tài)碎片信息，共有用戶1000人。為能準(zhǔn)確地反映實(shí)驗(yàn)結(jié)果，將用戶數(shù)據(jù)集的3/4作為訓(xùn)練集，1/4作為測(cè)試集。

（二）算法可行性檢測(cè)

覆蓋率（Coverage），評(píng)價(jià)一個(gè)社交平臺(tái)好友推薦算法往往從覆蓋率（Coverage）和準(zhǔn)確率（Precision）兩方面進(jìn)行考量，覆蓋率主要用于觀察推薦算法推薦的好友集合Ure與實(shí)際可推薦好友集合Ureal交集匯總好友數(shù)量占實(shí)際可推薦的好友比率。

準(zhǔn)確率（Precision），準(zhǔn)確率主要用來(lái)衡量算法的正確性、可行性，反映推薦出的準(zhǔn)確好友數(shù)所占好友數(shù)的百分比，越高越準(zhǔn)確性越好。

通過(guò)對(duì)本文算法和傳統(tǒng)的AprioriTid算法的比較，可以看出，本文算法在相同的數(shù)據(jù)記錄處理中，所需的時(shí)間更少（如圖1）。

四、結(jié)束語(yǔ)

如何在社交網(wǎng)絡(luò)過(guò)程中找到一個(gè)或多個(gè)志趣相投的朋友。在本文關(guān)于社交朋友推薦算法的研究中，我們不僅考慮社交角色的關(guān)系，而且考慮用戶發(fā)布的信息的相似性。因此，在推薦朋友時(shí)，我們主要從這兩個(gè)方面入手，并使用改進(jìn)的關(guān)聯(lián)規(guī)則推薦算法向用戶展示朋友列表。事實(shí)證明，類似于關(guān)聯(lián)規(guī)則的朋友推薦算法在用戶推薦中具有很大的研究?jī)r(jià)值，最終可以為用戶的社交互動(dòng)帶來(lái)更多的便利。