基于混合聚類與融合用戶興趣的協(xié)同過濾推薦算法*

麻 天 ，余本國 ，張 靜 ，宋文愛 ，景 昱

(1.中北大學(xué) 軟件學(xué)院，山西 太原 030051；2.山西省軍民融合軟件工程技術(shù)研究中心，山西 太原 030051；3.海南醫(yī)學(xué)院 生物醫(yī)學(xué)信息與工程學(xué)院，海南 ?？?571199)

0 引言

在信息快速發(fā)展的現(xiàn)代社會中，推薦算法已經(jīng)普遍出現(xiàn)在人們的生活中，給人類生活無形中帶來巨大便利[1]，如短視頻推薦[2]、音樂歌曲推薦[3]、新聞信息推薦[4]。協(xié)同過濾推薦算法在工程上更容易實現(xiàn)。該算法分為兩類：基于用戶的協(xié)同過濾推薦算法(user-based collaborative filtering)和基于項目的協(xié)同過濾推薦算法(item-based collaborative filtering)[5]。簡言之：物以類聚，人以群分。雖然協(xié)同過濾推薦算法與其他推薦算法相比有很多優(yōu)點，但解決推薦效率低、推薦質(zhì)量低、冷啟動和稀疏矩陣等問題一直是研究者不斷努力改進的方向[6]。其中在計算不同用戶之間的相似性時也存在很多問題，相似度計算不精準(zhǔn)是影響推薦準(zhǔn)確性的一個關(guān)鍵因素[1]。

很多研究學(xué)者提出很多方法改進以上存在的問題。趙偉等在傳統(tǒng)K-means 聚類算法的基礎(chǔ)上做了改進，有效地解決了有關(guān)用戶聚類的一些問題[7]。王蓉等提出了一種混合聚類與融合屬性特征的協(xié)同過濾推薦算法，在一定程度上能提高推薦效率，解決冷啟動問題，為聚類算法在推薦系統(tǒng)中的研究開辟了新思路[6]。

本文依據(jù)上述學(xué)者的思路，改進了算法，通過建立Canopy+bi-Kmeans 混合聚類模型[8]和一種改進的相似度計算方法，提出一種基于混合聚類與融合用戶偏好的協(xié)同過濾推薦算法，從而可以達到提高推薦可靠性、提高推薦精度的效果。利用MovieLens 數(shù)據(jù)集進行試驗得出結(jié)果表明，該算法不僅能有效解決存在的冷啟動問題，而且可提高推薦算法效率。

1 Canopy+bi-Kmeans 混合聚類算法

1.1 Canopy 算法

首先利用Canopy 算法對數(shù)據(jù)集進行一次聚類，這種算法有利有弊，不需要指定k 值，可以快速得到聚類簇，但是精度較低[9]。算法過程如下：

(1)從原始數(shù)據(jù)中生成樣本列表X=[x1，x2，…，xm]，在設(shè)定初始距離閾值T1、T2時，通過兩種方式調(diào)整參數(shù)：先驗知識和交叉驗證，且T1＞T2。

(2)選取Canopy 質(zhì)心。從列表X 中任選一個樣本，令第一個樣本為P，并將P 從列表中刪除。

(3)從列表X 中隨機選取一個樣本R，計算R 到所有Canopy 質(zhì)心的距離，判斷其中最小的距離D：如果D≤T1，則令R 為一個弱標(biāo)記，表示R 屬于該質(zhì)心，并將R 加入其中；如果D≤T2，則將R 進行強標(biāo)記，表示R 屬于該質(zhì)心，更新強樣本標(biāo)記質(zhì)心，并將樣本R 從列表X 中移除[10]；如果D＞T1，則R 形成一個新的聚簇，并將R 從列表X 中刪除。

(4)若列表X 中元素個數(shù)不為零，則不斷重復(fù)上述步驟(3)。

1.2 bi-Kmeans 算法

bi-Kmeans(bisecting K-means)聚類算法受隨機選擇初始質(zhì)心的影響比較小，改進K-means算法隨機選擇初始質(zhì)心的隨機性造成聚類結(jié)果不確定性的問題。簡言之：“高內(nèi)聚，低耦合”。意思是讓每個類簇之間要有明顯的界限，類簇內(nèi)部的點要團結(jié)緊湊[11]。bi-Kmeans 算法步驟如下：

(1)從原始樣本集合中隨機取k 個初始中心點。

(2)以這k 個中心點為標(biāo)準(zhǔn)，計算所有樣本點到中心的距離，計算后將其加入到距離最近的類簇。這樣每個樣本都有自己的簇了。

(3)重新計算每個簇中的樣本中心點，如果中心點未發(fā)生變化轉(zhuǎn)到步驟(4)，發(fā)生變化回到步驟(2)。

(4)得出結(jié)果。

輸出：劃分出的聚類簇以及聚類中心。

在選擇聚類時，利用SSE(Sum of Squared Error)當(dāng)作度量聚類效果的指標(biāo)。不同聚類算法對比見表1。

表1 不同聚類算法對比

從表1 以直觀地發(fā)現(xiàn)，bi-Kmeans 計算出來的SSE值最小，并且趨于穩(wěn)定值，說明聚類的效果也最好。因此，本文選用bi-Kmeans 這個聚類方法。

1.3 Canopy+bi-Kmeans 算法

Canopy+bi-Kmeans 這個聚類組合有很多優(yōu)點，如增強了單獨聚類抗干擾的能力，加快了相似性計算的速率。Canopy+bi-Kmeans 算法流程圖如圖1 所示。

圖1 Canopy+bi-Kmeans 算法流程圖

2 計算用戶偏好相似性

2.1 計算用戶偏好

通常用戶會根據(jù)個人的興趣對項目打分。文獻[12]簡單地根據(jù)標(biāo)簽的數(shù)量來判斷用戶的偏好，從而使得當(dāng)前潮流標(biāo)簽權(quán)重過高使得某些用戶選擇冷門標(biāo)簽時無法得到更準(zhǔn)確的推薦，未能將用戶的興趣偏好充分展現(xiàn)出來。這對上述問題，本文利用TF-IDF 的方法對用戶偏好進行計算。

TF-IDF 用計量統(tǒng)計的方式來評估某個關(guān)鍵詞在其所在的語料庫中的重要性[13]，公式如下：

其中，Pua表示用戶u 對項目標(biāo)簽a 的偏好值，Pua值與偏好程度成正比；n 表示項目總數(shù)，s 表示項目標(biāo)簽總數(shù)；表示用戶u 標(biāo)注標(biāo)簽a 的次數(shù)，表示用戶u 標(biāo)注的總次數(shù)；numm表示用戶總數(shù)，numua表示標(biāo)注過標(biāo)簽a 的用戶數(shù)；表示標(biāo)簽總數(shù)，表示標(biāo)簽a 的總數(shù)。

由式(1)可以看出，用戶選擇的標(biāo)簽被用戶選得少并且此標(biāo)簽占整個標(biāo)簽集合的比重越小，這樣就能在一定程度上明確用戶偏好，從而提高推薦效率。

2.2 融合時間系數(shù)的衰減函數(shù)

傳統(tǒng)的推薦算法對用戶標(biāo)簽偏好常用靜態(tài)標(biāo)簽標(biāo)識，一般用0 和1 來表示。這樣可以明顯看出在任何時候這些標(biāo)簽所起到的推薦作用都是相同的，對于某些時效性較強的推薦并不能起到較好的推薦效果。例如：某用戶以前喜歡古典音樂，現(xiàn)在喜歡流行音樂，如果不考慮用戶興趣偏好隨時間變化就會導(dǎo)致推薦不貼合用戶偏好[14]。在實際中用戶的興趣往往是處于動態(tài)變化中的[15]。相對于早期的用戶行為，近期的用戶行為對于推薦更有意義，因此將用戶近期的標(biāo)簽給予較高的權(quán)重，從而使推薦更具有時效性，提高推薦效率。本文引入一種衰減函數(shù)并且融入時間系數(shù)來充分貼合用戶興趣偏好隨時間的變化，公式如下：

其中，Tui∈(0，1)，代表用戶u 對項目i 的時間權(quán)重；Ts表示時間窗口參數(shù)，其值表示用戶偏好興趣持續(xù)時間；tnow表示當(dāng)前做推薦的時間，tui表示用戶對項目作出評價的時間；Tatt是時間衰減參數(shù)，代表興趣偏好衰減速率；表示對計算結(jié)果進行上舍入處理，Ts×表示用戶評價項目時間所處的時間段。若用戶在一周的時間內(nèi)興趣偏好基本沒變，則認為該用戶興趣保持穩(wěn)定的周期為7 天，即Ts=7。若用戶評價完項目后在7 天內(nèi)進行推薦，即tnow-tui≤7，則用戶興趣在第8 天后才開始衰減，每7 天為一個衰減周期，衰減周期內(nèi)衰減系數(shù)相同。

2.3 計算用戶偏好相似性

根據(jù)前文分析，在利用TF-IDF 方法計算用戶興趣偏好時加入融入時間系數(shù)的衰減函數(shù)得出用戶興趣偏好，更新用戶標(biāo)簽矩陣中的值，公式如下：

最后歸一化歐式距離，公式如下：

2.4 融合用戶屬性相似度

在計算相似度時，采用常規(guī)的相似的算法不會將不同用戶的個人屬性進行相似性對比，如性別和年齡等屬性。因此，本文考慮了上述用戶屬性，并且將這些基本的用戶屬性融入到相似度計算中。

(1)年齡屬性相似度，公式如下：

其中，u 和v 分別代表兩個用戶，N(u，v)的取值范圍為[0，1]之間，值越小相似度越?。籲u和nv分別為用戶u 和v 的年齡。

(2)性別屬性相似度，公式如下：

其中，u 和v 代表不同的用戶，Xu和Xv分別是用戶u 和v 的性別。

(3)根據(jù)上述用戶性別和年齡屬性相似度，根據(jù)實際情況分別給予不同的權(quán)重得出用戶屬性相似度，公式如下：

其中，權(quán)重系數(shù)α∈[0，1]，在不同的推薦場景和領(lǐng)域中可以根據(jù)實際情況對α 值進行調(diào)整。

3 融合用戶興趣的協(xié)同過濾推薦算法

首先通過對sim1(u，v)和sim2(u，v)線性組合，將用戶興趣偏好和屬性融合得到綜合相似度，得到一種新的相似度計算模型，公式如下：

式中，λ∈[0，1]為權(quán)重系數(shù)，sim(u，v)值與兩個用戶的相似性成反比關(guān)系。

然后對項目進行評分預(yù)測，最后進行推薦，公式如下：

4 實驗與分析

4.1 實驗數(shù)據(jù)

實驗采用開源的數(shù)據(jù)集MovieLens-1M。實驗中使用交叉驗證方式對用戶評分進行預(yù)測。

4.2 評估指標(biāo)

經(jīng)過多輪訓(xùn)練減小評分誤差，獲得最優(yōu)參數(shù)推薦模型。常用評價指標(biāo)是平均絕對誤差(MAE)，這種誤差計算方式見式(10)：

其中，rui為用戶u 對項目i 的真實評分，Pui為用戶u 對于項目i 的預(yù)測評分。分母為測試集，分子為用戶u 對項目i 真實評分和預(yù)測分數(shù)的差值。通過計算Test 中Pui與rui的平均絕對誤差，評估模型的性能。

4.3 結(jié)果分析

首先確定本文涉及到的參數(shù)值，參數(shù)分別為：Ts、Tatt和λ。

實驗1：通過MAE 值來確定時間窗口參數(shù)Ts的值。如圖2 所示，在K=50 時，Tatt=20、Tatt=40、Tatt=60、Tatt=80、Tatt=100 的條件下，MAE 的值的變化趨勢都是先降后升。當(dāng)Tatt=40，Ts=4 時，MAE 值最?。划?dāng)Tatt=100，Ts=5 時，MAE值最??；當(dāng)Tatt分別為20、60 和80，Ts=6 時，MAE 值最小。令Ts=6 來進行后續(xù)的實驗，即用戶的興趣偏好的變化周期為6 天。

圖2 不同Ts 值對應(yīng)的MAE 值

實驗2：判定Tatt的值。如圖3 所示，在K=50，Ts=6時，Tatt=30、Tatt=40、Tatt=50、Tatt=60、Tatt=70、Tatt=80、Tatt=90時，MAE 的值先下降；到Tatt=60 時，MAE 值達到最低，然后上升。所以令Tatt=60，進行后續(xù)實驗。

圖3 不同Tatt 值對應(yīng)的MAE

實驗3：確定式(8)中參數(shù)λ 的值。當(dāng)λ=1 時，sim(u，v)=sim1(u，v)，表示只利用用戶的興趣偏好來計算用戶之間的相似性；當(dāng)λ=0 時，sim(u，v)=sim2(u，v)，表示僅利用用戶的屬性計算用戶之間的相似性。如圖4 所示，在K=20、K=40、K=60、K=80 時，MAE 值先下降后上升；當(dāng)λ=0.4 時，MAE 值最小，推薦效果最好。

圖4 不同λ 對應(yīng)的MAE 值

實驗4：在近鄰不同的情況下，比較了不同推薦算法的推薦性能，其中包括將基于用戶的協(xié)同過濾推薦算法(UBCF)[16]、基于K-means 聚類的協(xié)同過濾推薦算法(K-means UBCF)[17]、基于Canopy+K-means 混合聚類的協(xié)同過濾推薦算法(Canopy+K-means UBCF)與本文提出的算法進行了對比。得出的實驗結(jié)果如圖5 所示。

圖5 不同算法對應(yīng)的MAE 值

由圖5 可知，隨著目標(biāo)用戶最近鄰居個數(shù)的增加，實驗中所用的UBCF、K-means UBCF、Canopy+K-means UBCF 和本文所提出的算法的MAE 值都會逐漸降低并趨于一個穩(wěn)定值。由圖5 可以直觀地發(fā)現(xiàn)，本文所提出的算法相對于其他3 種算法推薦準(zhǔn)確度最高。例如，當(dāng)最近鄰居個數(shù)為35 時，Canopy+K-means UBCF 的MAE 值為0.758，同樣條件下本文所提出的算法的MAE 值為0.741，推薦效果提升了1.7%。

5 結(jié)論

本文提出一種基于混合聚類與融合用戶偏好的協(xié)同過濾推薦算法，通過建立Canopy+bi-Kmeans 混合聚類模型并且將傳統(tǒng)的相似性度量算法中加入用戶屬性和用戶興趣偏好。實驗結(jié)果表明，本文提出的基于混合聚類與融合用戶偏好的協(xié)同過濾推薦算法在一定程度上提高了推薦可靠性。由于本文的算法是在各方面條件較為理想的環(huán)境下實現(xiàn)的，其魯棒性和穩(wěn)定性有待提高，因此下一步的工作是將該算法運用到現(xiàn)實項目中，并且不斷追求更高的推薦效率。