趙宇峰 李新衛(wèi)(西安工業(yè)大學計算機科學與工程學院 陜西 西安 710021)

0 引 言

隨著近幾年來移動互聯(lián)網(wǎng)的發(fā)展，智能手機變得越來越普及，智能手機這種隨時隨地上網(wǎng)的特性使得數(shù)據(jù)量爆炸式的增長，隨之而來的是數(shù)據(jù)怎樣才能供用戶消費，怎樣提供用戶感興趣的信息，成為了一個需要迫切解決的問題。搜索引擎作為一種用戶主動查詢信息的模式已經(jīng)變得越來越被動，它只能提供用戶主動需要的信息，而不能挖掘用戶潛在感興趣的信息并提供。而推薦系統(tǒng)恰好能夠做到根據(jù)用戶的行為挖掘用戶感興趣的內(nèi)容并推薦給用戶[1]。

1 傳統(tǒng)算法介紹

目前應(yīng)用比較廣泛的推薦算法包括基于內(nèi)容的推薦、協(xié)同過濾推薦和混合推薦三種，其中協(xié)同過濾推薦算法應(yīng)用最為成功，協(xié)同過濾推薦算法也是最早被提出的[2]?；趦?nèi)容的推薦算法源自于信息獲取領(lǐng)域，通過對推薦對象內(nèi)容中的特征提取并計算出推薦對象的內(nèi)容相似度進行推薦。這種推薦算法簡單直觀、容易理解、不需要領(lǐng)域知識，但它只能處理文本內(nèi)容，像視頻、歌曲這種信息就不能夠通過分析內(nèi)容進行推薦，即使可以分析視頻圖像和音頻信息也非常費時，可行性不強。協(xié)同過濾推薦算法又分為基于用戶的協(xié)同過濾(User-CF)和基于商品的協(xié)同過濾(Item-CF)[2]。

2 相關(guān)工作

2.1 傳統(tǒng)基于用戶的協(xié)同過濾推薦算法

傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法是通過與此用戶興趣最相似的幾個用戶，然后從這幾個相似興趣用戶中推薦用戶沒有聽過的歌曲。具體方法是通過用戶相似度算法找到每個用戶最相似的一些用戶，再匯總相似用戶聽歌記錄，從其中找出目標用戶沒有聽過的歌曲，再根據(jù)相似用戶的相似度來排序，求得每一首歌的偏好度，對這些歌曲進行排序，從而給目標用戶進行推薦[4]。具體的算法步驟如下：

(1) 構(gòu)造用戶- 歌曲數(shù)據(jù)表示矩陣。行向量表示用戶，列向量表示每一首歌曲，矩陣值表示用戶是否聽過此首歌曲，0代表沒有聽過，1代表聽過，它是一個0-1矩陣。

(2) 生成最近鄰居集。根據(jù)用戶- 歌曲矩陣使用用戶相似度算法進行用戶相似度計算，從而找到與目標用戶最近的用戶集。

(3) 產(chǎn)生推薦。找出離目標用戶最近的幾個用戶中目標用戶沒有聽過的歌曲，并統(tǒng)計這些歌曲的個數(shù)，然后通過這些歌曲中每個歌曲的個數(shù)與用戶相似度相乘，從而得出此歌曲的推薦值，最后將每個歌曲在每個用戶中推薦值統(tǒng)計求和，排序推薦值最高的幾首作為目標用戶的推薦結(jié)果。

2.2 傳統(tǒng)算法的不足

傳統(tǒng)的基于用戶協(xié)同過濾算法是對所有的用戶進行計算并求相似用戶，現(xiàn)在一個音樂系統(tǒng)的用戶高達幾億，計算起來效果很差，而且很多用戶都是相似度很低的，不需要進行計算。為了解決這個問題，可以先對用戶進行聚類，使相似的用戶歸為一類再進行協(xié)同過濾，使計算量大大降低。0-1矩陣只表示了用戶是否聽過這首歌，而不能表示用戶對這首歌的喜好程度，對用戶的分類效果較差。

2.3 引入k-means聚類優(yōu)化推薦算法

聚類是在沒有人工標注的基礎(chǔ)上，將具有相似屬性的數(shù)據(jù)聚集到一起的無監(jiān)督學習方法，它使具有相似性的數(shù)據(jù)集中到一起，處于同一組內(nèi)數(shù)據(jù)具有相似性，處于不同組內(nèi)的數(shù)據(jù)彼此不同。本文改進的協(xié)同過濾推薦算法就是在相似度高的用戶基礎(chǔ)之上進行推薦，使得算法具有更好的推薦效果。相似計算直接制約著聚類效果的好壞，從而影響到最終的推薦結(jié)果。算法原理如下：假定有一組用戶User，用戶總數(shù)是m，記作U(U1，U2，U3，…，Um)，每個用戶Ux都有n個屬性，記作Ux(Cx1，Cx2，Cx3，…，Cxn)，聚類的原理就是在集合User的基礎(chǔ)上對比每一個屬性，完成相似用戶的分組。k-means算法核心思想就是將給定的一組用戶User分為k組，每組都設(shè)定一個聚類中心，計算每個數(shù)據(jù)離此中心的距離，距離最小的歸為此組[6]。具體步驟如下：

(1) 用戶興趣標簽?zāi)Ｐ徒8]。模型從用戶聽歌日志出發(fā)，最終定位用戶的興趣標簽，步驟如圖1所示。

圖1 用戶興趣標簽建模步驟

用戶聽歌日志采集，在此測試算法中只取部分用戶作為數(shù)據(jù)集，大約有2 000用戶，聽歌記錄10萬條左右，格式如表1所示。

表1 用戶聽歌記錄

歌曲標簽表示了此歌曲的類型。本文使用的數(shù)據(jù)集中，歌曲標簽的初始標簽是歌曲上傳者添加的，聽歌用戶也可以自行添加描述標簽，數(shù)據(jù)格式如表2所示。

表2 歌曲標簽表

用戶興趣標簽，這一步就只將用戶聽過的歌曲的標簽映射到用戶興趣屬性列上，如表3所示。

表3 用戶標簽?zāi)Ｐ?/p>

標簽值表示此用戶聽歌記錄中此標簽的出現(xiàn)次數(shù)。考慮到用戶某一天內(nèi)對某一標簽的集中行為有可能會拉偏此用戶的興趣點，因此添加了tag數(shù)量的衰減因子[5]，衰減因子計算公式如下所示：

I(u,t)=log(1+c(u,t))

(1)

式中：c(u,t)表示用戶u中標簽t的數(shù)量，從而得到用戶標簽矩陣U-T，如表4所示。

表4 用戶標簽矩陣

(2) 生成聚類。對U-T矩陣進行k-means算法聚類，聚類中心隨機選取k個，距離函數(shù)使用歐式距離進行計算。計算每一個用戶向量到k個中心點的距離，然后將此用戶歸類到距離值最小的中心點，所有用戶計算完一次后再對每一類坐標求平均，得到新的k個中心點，再迭代計算直到中心點不變或變化小于設(shè)定的閾值，則聚類結(jié)束。

(3) 對得到的k個用戶類中每一類都使用基于用戶的協(xié)同過濾算法計算推薦結(jié)果。

2.4 k-means聚類算法改進[6]

(1) 游離點的去除。在所有數(shù)據(jù)點中，游離點是那些與其他所有點距離較遠的點，它們的存在會導(dǎo)致所屬類中中心點的偏離，從而影響到分類的效果。本文去除游離點的過程如下：

設(shè)用戶總數(shù)為m，所有用戶到其他用戶的總路徑條數(shù)為：

(2)

則所有用戶之間的距離和為：

(3)

gap(Ci,Cj)=

(4)

式中：Ci1,Cj1,…,Cin,Cjn是用戶Ci與Cj的n個屬性。根據(jù)L和D求距離平均值：

(5)

式(5)為所有用戶距離的平均值，對每一個用戶U計算出與其他所有用戶的距離LU=(Ui,Uj)，如果所有的LU≥EMV，則把此用戶歸為游離點，單獨一個分類，如果游離點的個數(shù)較少，則無法分為一類進行協(xié)同過濾，這樣可以將它分到距離某類中心點最近的類。

(2) 隨機點的選取對分類結(jié)果也會產(chǎn)生影響，會陷入局部最優(yōu)解。為了解決此問題，本文所采用的方法是采用聚類的改進算法：二分聚類。二分聚類的思想是：首先將所有點作為一個簇，然后將該簇一分為二(k=2的k-means聚類)，之后選擇能夠最大限度降低聚類代價函數(shù)的簇再次進行一分為二，直到聚類個數(shù)等于k結(jié)束。聚類代價函數(shù)定義為聚類的誤差平方和，如式(6)所示，某個類的誤差平方和最大，就說明此類中的點距離中心點的距離之和最大，就需要對此類進行再一次劃分。

(6)

3 實驗和評價

在數(shù)據(jù)集一樣的情況下，分別對傳統(tǒng)基于用戶的協(xié)同過濾算法、引入k-means聚類后的推薦算法和改進聚類后的推薦算法三種算法進行了多次重復(fù)試驗，并選取相對穩(wěn)定的結(jié)果數(shù)據(jù)進行對比分析。

3.1 數(shù)據(jù)集

本實驗采用的數(shù)據(jù)是從網(wǎng)絡(luò)上采集來的，包括用戶名、用戶聽歌記錄和歌曲標簽數(shù)據(jù)，取其中2 000名用戶，聽歌記錄近10萬條，標簽數(shù)據(jù)730條構(gòu)成數(shù)據(jù)集進行試驗。實驗環(huán)境：Intel i5-4590 處理器，主頻3.30 GHz，內(nèi)存8 GB，windows7 64位操作系統(tǒng)，PyCharm編程環(huán)境，python2.7。

3.2 評價指標

評價指標使用準確率(Precision)和召回率(Recall)，對每一個用戶的聽歌記錄時間進行降序排序，采用前80%作為訓(xùn)練集，后20%作為測試集進行實驗評價。

式(7)和式(8)分別為準確率(Precision)和召回率(Recall)的計算公式[2,7]。

(7)

(8)

3.3 三種算法的對比

對三種算法分別計算出不同分類個數(shù)k值時的準確率與召回率，變化關(guān)系如圖2、圖3所示的折線。

如圖2所示，引入k-means聚類算法后準確率要比傳統(tǒng)的基于用戶的協(xié)同過濾算法要好一些，當k值為4的時候，準確率提高0.65%左右，為最好分類。而對聚類算法進行優(yōu)化后，k值為5的時候，準確率比未優(yōu)化時提高近0.15%。

圖2 三種算法的準確率隨分類個數(shù)k的變化圖

圖3是三種算法的召回率變化圖，引入k-means聚類算法后準確率要比傳統(tǒng)的基于用戶的協(xié)同過濾算法要好，當k值為4的時候，召回率能夠提高0.65%左右。而對聚類算法進行優(yōu)化后，當k值為5的時候，召回率又增加近0.15%，但當k值增大時，優(yōu)化后的聚類又會比未優(yōu)化的聚類算法低，當用戶量一定時，去除游離點后，每個分類均受影響，有的分類個數(shù)非常少，推薦結(jié)果就不準確，從而影響整體推薦算法效果。

圖3 三種算法的召回率隨分類個數(shù)k的變化圖

4 結(jié) 語

為了提高推薦結(jié)果的準確率和召回率，本文先對用戶進行聚類，根據(jù)用戶聽歌曲的標簽進行分析，建立了用戶- 標簽?zāi)Ｐ?，進而使用k-means聚類對用戶進行聚類，從而興趣品味相近的用戶分到了一組，分組后再使用協(xié)同過濾算法進行推薦排名，使用戶的興趣分組更加準確，從而推薦效果更好，也使得系統(tǒng)過濾推薦的計算量降低，從而有更好的性能與結(jié)果。最后，算法使用從網(wǎng)絡(luò)上采集到的真實數(shù)據(jù)進行試驗，實驗結(jié)果表明，經(jīng)過改進優(yōu)化的推薦算法比傳統(tǒng)的基于用戶的協(xié)同過濾算法在準確率和召回率上都有明顯的提高。

[1] 劉旭東,陳德人,王惠敏.一種改進的協(xié)同過濾推薦算法[J].武漢理工大學學報(信息與管理工程版),2010,32(4):550- 553.

[2] 王國霞,劉賀平.個性化推薦系統(tǒng)綜述[J].計算機工程與應(yīng)用,2012,48(7):66- 76.

[3] 秦雨,余正濤,王炎冰,等.基于特征映射的微博用戶標簽興趣聚類方法[J].數(shù)據(jù)采集與處理,2015,30(6):1246- 1252.

[4] 榮輝桂,火生旭,胡春華,等.基于用戶相似度的協(xié)同過濾推薦算法[J].通信學報,2014,35(2):16- 24.

[5] 常曉雨,余正生.引入時間衰減項的興趣點推薦算法[J].杭州電子科技大學學報(自然科學版),2016,36(3):42- 46.

[6] 吳泓辰,王新軍,成勇,等.基于協(xié)同過濾與劃分聚類的改進推薦算法[J].計算機研究與發(fā)展,2011,48(S3):205- 212.

[7] 朱郁筱,呂琳媛.推薦系統(tǒng)評價指標綜述[J].電子科技大學學報,2012,41(2):163- 175.

[8] 陳潔敏,李建國,湯非易,等.融合“用戶- 項目- 用戶興趣標簽圖”的協(xié)同好友推薦算法[J].計算機科學與探索,2018(1):92- 100.