麻 天 ，余本國(guó) ，張 靜 ，宋文愛(ài) ，景 昱

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

0 引言

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

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

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

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

1.1 Canopy 算法

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

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

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

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

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

1.2 bi-Kmeans 算法

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

(1)從原始樣本集合中隨機(jī)取k 個(gè)初始中心點(diǎn)。

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

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

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

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

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

表1 不同聚類算法對(duì)比

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

1.3 Canopy+bi-Kmeans 算法

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

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

2 計(jì)算用戶偏好相似性

2.1 計(jì)算用戶偏好

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

TF-IDF 用計(jì)量統(tǒng)計(jì)的方式來(lái)評(píng)估某個(gè)關(guān)鍵詞在其所在的語(yǔ)料庫(kù)中的重要性[13]，公式如下：

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

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

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

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

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

2.3 計(jì)算用戶偏好相似性

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

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

2.4 融合用戶屬性相似度

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

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

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

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

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

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

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

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

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

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

然后對(duì)項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)，最后進(jìn)行推薦，公式如下：

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用開(kāi)源的數(shù)據(jù)集MovieLens-1M。實(shí)驗(yàn)中使用交叉驗(yàn)證方式對(duì)用戶評(píng)分進(jìn)行預(yù)測(cè)。

4.2 評(píng)估指標(biāo)

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

其中，rui為用戶u 對(duì)項(xiàng)目i 的真實(shí)評(píng)分，Pui為用戶u 對(duì)于項(xiàng)目i 的預(yù)測(cè)評(píng)分。分母為測(cè)試集，分子為用戶u 對(duì)項(xiàng)目i 真實(shí)評(píng)分和預(yù)測(cè)分?jǐn)?shù)的差值。通過(guò)計(jì)算Test 中Pui與rui的平均絕對(duì)誤差，評(píng)估模型的性能。

4.3 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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