基于數(shù)據(jù)挖掘和聚類分析的協(xié)同過濾推薦算法

何岫鈺

（北京語言大學商學院，北京 100083）

為避免信息堆積混亂、分析用戶偏好以及提高運營效率[1]，研究推薦算法具有重要意義。海量的資源和用戶導致協(xié)同過濾算法的空間和時間復雜度爆發(fā)式增長，這給推薦算法帶來非常大的挑戰(zhàn)[2]。許多學者對此進行了深入研究，司品印等結合用戶畫像和資源評分構建推薦模型，基于用戶的協(xié)同過濾算法完成推薦[3]，但數(shù)據(jù)具有一定稀疏性，推薦結果的準確性低。郭曉宇等人提取用戶興趣，采用K 均值算法將具有相似興趣類型的用戶聚為一類；采用基于模糊聚類的協(xié)同過濾和基于用戶興趣的聚類方法，最終完成推薦[4]。但是該方法的計算量較大。

文中提出基于數(shù)據(jù)挖掘和聚類分析的協(xié)同過濾推薦算法，在提高推薦精度的同時減少數(shù)據(jù)的稀疏性對推薦結果的影響。

1 數(shù)據(jù)挖掘和聚類分析的協(xié)同過濾推薦

1.1 雙向關聯(lián)規(guī)則的標簽相似度聚類

設擁有資源個數(shù)為m資源集為R={R1,R2,…,Rn}，用標簽將資源分為n類，標簽集為T={T1,T2,…,Tn}。為挖掘標簽與資源兩者之間的關聯(lián)關系，根據(jù)雙向關聯(lián)規(guī)則原理構建標簽資源矩陣[5]，表達式如下：

式中，trij表示標簽Tj標注資源Ri的頻次。

當出現(xiàn)兩個及兩個以上的標簽（稱為標簽對）共同標注同一資源時，稱為標簽共現(xiàn)，通過共現(xiàn)頻次，挖掘標簽與資源之間的關聯(lián)[6]。設標注同一資源的次數(shù)為tfi,j，標簽之間的緊密程度表示為：

式中，F(xiàn)in(ti)表示標簽總數(shù)；tdij表示標簽tj與ti一起標記過的資源數(shù)量。當tfi,j值越大，F(xiàn)in(ti)越小時，則tdij越大，標簽ti和tj之間關系越密切。同理，用戶對資源的評分可以看作是資源上所有標簽之間關系的綜合體現(xiàn)，評分越高，表明緊密程度越大。

任一標簽的關聯(lián)向量V1可以用來表示該標簽與其他所有標簽之間的聯(lián)系。關聯(lián)向量集為Vi=(tdi1,tdi2,…,tdin)，分別表示標簽ti與標簽1、標簽2 以及標簽n之間的緊密程度。文中采用余弦相似度來評判向量與向量之間的相似程度，表達式如下：

K-means 聚類算法是通過分析數(shù)據(jù)間的模式和關系來識別出有用的結構和模式的機器學習算法，指定數(shù)據(jù)簇的類別數(shù)為C，通過簇頭對數(shù)據(jù)進行表達[7]。設需要聚類的標簽集T的聚類中心為z1,z2,…,zc。K-means 聚類算法的標簽聚類流程如下：

步驟一：任意選取C個標簽聚類的樣本點z1(1),z2(1),…,zc(1)作為初始聚類中心。

步驟二：以距離最近為準則，對標簽樣本集進行聚類，確定每個標簽樣本所屬類別。

步驟三：通過k次迭代，獲得新的聚類中心，z1(k),z2(k),…,zc(k)。

步驟四：重復步驟二、步驟三、步驟四的過程，直到確定聚類中心的穩(wěn)定位置。

利用K-means 的思想，將標簽與聚類中心的歐氏距離dij替換式（3）中的相似度sim(ti,tj)，根據(jù)標簽之間的相似度完成標簽的聚類[8]。如果兩個標簽的相似性超過一定閾值，則將它們聚類為同一原始類別。如果某一類別中含有極少數(shù)的標簽，則將此類別剔除。

為得到更好的聚類效果，對上述原始類別再次進行細分聚類[9]。其步驟如下：

步驟一：將標簽對(ti,tj) 和標簽之間的相似度sim(ti,tj)匯聚到標簽集T里。

步驟二：通過不斷地合并標簽集T里最相似的標簽，直到全部標簽之間的相似度小于設定閾值，完成循環(huán)。

步驟三：不斷更新聚類中心并重新計算標簽與聚類中心的相似度，并不斷優(yōu)化聚類結果，直到得到一個相對穩(wěn)定的聚類結果[10]。

1.2 基于標簽聚類的協(xié)同過濾推薦算法

推薦分兩個過程：初始推薦和個性化推薦。初始推薦：采用基于標簽的協(xié)同過濾算法為用戶推薦資源。個性化推薦：基于標簽聚類后對資源的排名完成個性化推薦。推薦步驟如下：

步驟一 聚類后，聚類數(shù)量遠小于標簽數(shù)量。通過用戶的瀏覽歷史等日常行為進行統(tǒng)計分析，了解用戶的偏好標簽；計算標簽與資源之間的緊密程度，如式（4）和式（5）所示；相似度越高，則資源排名越靠前，完成基本推薦[11]。

式中，tnr(t,r) 表示標簽t標注資源r的頻次；cos(t,r)表示該標簽與資源的緊密程度。進而獲得資源列表排序R′，完成基本推薦[12]。

步驟二 將標簽作為聯(lián)系資源與用戶之間的紐帶計算資源與用戶之間的緊密程度[13]。以標注度id(u,ci)和關聯(lián)度wd(r,ci)為指標，設定聚類后的標簽子集為ci，用戶為u，標注頻次為ci，則二者的集合為ad(u,r)。為提高資源推薦的多樣化，防止熱門標簽的過多權重，對熱門標簽增加懲罰，其公式如下：

步驟三 將步驟一、二進行線性組合，獲得用戶對資源的興趣值，并根據(jù)興趣值大小對資源進行重新排序，輸出最終的推薦結果[14-16]。對于完成推薦的資源r，用下列公式表示：

式中，α表示權重參數(shù)。

最終為用戶推薦的資源列表R″為：

其中，ε為最小閾值，為用戶u標注過興趣、喜好或評分計算出整體偏好值的加權幾何平均值。

2 仿真實驗

2.1 實驗準備

選取六個不同的數(shù)據(jù)集進行實驗，分別采用文中標簽聚類方法、模糊聚類方法、K-means 聚類方法以及基于密度的聚類方法對上述六種數(shù)據(jù)集進行聚類。并以標準互信息（NMI）和標準熵（NE）評估聚類結果的平衡狀態(tài)。

2.2 結果與分析

四種不同聚類方法的聚類評估結果如表1 所示。由表1 可知，文中標簽聚類算法的NE 值達到100%，計算可得平均NMI 值為94.9%，表明聚類后數(shù)據(jù)集的平衡狀態(tài)和準確性較好，均高于其他方法，可有效地對數(shù)據(jù)進行分類，聚類效果良好。

表1 不同聚類方法的聚類結果評估情況

使用IMP 方法可以度量用戶對推薦電影的接受程度。計算每個用戶的IMP 分數(shù)平均值，獲得整體推薦效果。實驗結果如圖1 所示。由圖1 可知，標簽聚類推薦算法的權重參數(shù)為0.6、協(xié)同過濾推薦算法的權重參數(shù)為0.3 時，各自達到最佳的推薦IMP 值。這說明標簽聚類推薦算法的IMP 值在整體上也高于協(xié)同過濾推薦算法，表明文中算法具備較好的推薦性能。

圖1 兩種推薦算法IMP評估結果

驗證命中率和歸一化折損累計增益（Normalized Discounted Cumulative Gain,NDCG），結果如圖2所示。由圖2 可知，與傳統(tǒng)協(xié)同過濾推薦算法相比，使用標簽聚類后的推薦命中率和NDCG 均有顯著的提升，標簽聚類能夠捕捉到更復雜、更細致的用戶興趣模式，從而為用戶提供更準確、更個性化的推薦結果。

圖2 兩種推薦算法下的指標評估

3 結論

為了提高推薦系統(tǒng)的可擴展性和用戶滿意度，提出了基于數(shù)據(jù)挖掘和聚類分析的協(xié)同過濾推薦算法。實驗結果表明，標簽聚類能夠有效地對數(shù)據(jù)進行分類，并具有良好的聚類效果。當應用標簽聚類推薦算法的閾值為0.6 時，算法的推薦性能最佳。此外，經(jīng)過標簽聚類后的推薦算法相比傳統(tǒng)的協(xié)同過濾推薦算法在命中率和歸一化折損累計增益方面都有顯著的提升。