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

(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]。其中在計算不同用戶之間的相似性時也存在很多問題，相似度計算不精準是影響推薦準確性的一個關(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 為一個弱標記，表示R 屬于該質(zhì)心，并將R 加入其中；如果D≤T2，則將R 進行強標記，表示R 屬于該質(zhì)心，更新強樣本標記質(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 個中心點為標準，計算所有樣本點到中心的距離，計算后將其加入到距離最近的類簇。這樣每個樣本都有自己的簇了。

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

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

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

在選擇聚類時，利用SSE(Sum of Squared Error)當(dāng)作度量聚類效果的指標。不同聚類算法對比見表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ù)標簽的數(shù)量來判斷用戶的偏好，從而使得當(dāng)前潮流標簽權(quán)重過高使得某些用戶選擇冷門標簽時無法得到更準確的推薦，未能將用戶的興趣偏好充分展現(xiàn)出來。這對上述問題，本文利用TF-IDF 的方法對用戶偏好進行計算。

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

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

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

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

傳統(tǒng)的推薦算法對用戶標簽偏好常用靜態(tài)標簽標識，一般用0 和1 來表示。這樣可以明顯看出在任何時候這些標簽所起到的推薦作用都是相同的，對于某些時效性較強的推薦并不能起到較好的推薦效果。例如：某用戶以前喜歡古典音樂，現(xiàn)在喜歡流行音樂，如果不考慮用戶興趣偏好隨時間變化就會導(dǎo)致推薦不貼合用戶偏好[14]。在實際中用戶的興趣往往是處于動態(tài)變化中的[15]。相對于早期的用戶行為，近期的用戶行為對于推薦更有意義，因此將用戶近期的標簽給予較高的權(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ù)得出用戶興趣偏好，更新用戶標簽矩陣中的值，公式如下：

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

2.4 融合用戶屬性相似度

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

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

其中，u 和v 分別代表兩個用戶，N(u，v)的取值范圍為[0，1]之間，值越小相似度越??；nu和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 評估指標

經(jīng)過多輪訓(xùn)練減小評分誤差，獲得最優(yōu)參數(shù)推薦模型。常用評價指標是平均絕對誤差(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 可知，隨著目標用戶最近鄰居個數(shù)的增加，實驗中所用的UBCF、K-means UBCF、Canopy+K-means UBCF 和本文所提出的算法的MAE 值都會逐漸降低并趨于一個穩(wěn)定值。由圖5 可以直觀地發(fā)現(xiàn)，本文所提出的算法相對于其他3 種算法推薦準確度最高。例如，當(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)實項目中，并且不斷追求更高的推薦效率。