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

何岫鈺

（北京語言大學(xué)商學(xué)院，北京 100083）

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

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

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

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

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

式中，trij表示標(biāo)簽Tj標(biāo)注資源Ri的頻次。

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

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

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

K-means 聚類算法是通過分析數(shù)據(jù)間的模式和關(guān)系來識(shí)別出有用的結(jié)構(gòu)和模式的機(jī)器學(xué)習(xí)算法，指定數(shù)據(jù)簇的類別數(shù)為C，通過簇頭對(duì)數(shù)據(jù)進(jìn)行表達(dá)[7]。設(shè)需要聚類的標(biāo)簽集T的聚類中心為z1,z2,…,zc。K-means 聚類算法的標(biāo)簽聚類流程如下：

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

步驟二：以距離最近為準(zhǔn)則，對(duì)標(biāo)簽樣本集進(jìn)行聚類，確定每個(gè)標(biāo)簽樣本所屬類別。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，ε為最小閾值，為用戶u標(biāo)注過興趣、喜好或評(píng)分計(jì)算出整體偏好值的加權(quán)幾何平均值。

2 仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)準(zhǔn)備

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

2.2 結(jié)果與分析

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

表1 不同聚類方法的聚類結(jié)果評(píng)估情況

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

圖1 兩種推薦算法IMP評(píng)估結(jié)果

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

圖2 兩種推薦算法下的指標(biāo)評(píng)估

3 結(jié)論

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