特征聚類的混合協(xié)同過濾算法研究

杜民雙，何靈敏

(中國計量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

推薦算法是目前個性化推薦系統(tǒng)的研究熱點(diǎn)問題，在電子商務(wù)領(lǐng)域有著廣泛應(yīng)用，其核心思想就是利用數(shù)據(jù)挖掘技術(shù)與人工智能技術(shù)來改進(jìn)傳統(tǒng)的協(xié)同過濾算法在實(shí)際中的應(yīng)用[1-2].隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，人們逐漸從信息匱乏的時代進(jìn)入到了信息過載的時代.在這樣的情況下無論是信息消費(fèi)者還是信息生產(chǎn)者都遇到了極大的挑戰(zhàn)：作為消費(fèi)者如何從大量的信息中找到自己感興趣的部分；而作為信息生產(chǎn)者如何使自己的信息脫穎而出，讓消費(fèi)者對自己的信息感興趣，同樣是一件不容易的事情.推薦系統(tǒng)正是為了解決這種問題而產(chǎn)生的.

推薦系統(tǒng)作為一種高效的解決方法，為用戶推薦可能感興趣的項目.協(xié)同過濾作為一種應(yīng)用最廣泛的推薦算法之一，它的主要思想是：利用已有用戶群過去的行為或意見來預(yù)測當(dāng)前目標(biāo)用戶最可能喜歡哪些東西或?qū)δ男〇|西感興趣.Breese等人[2]將協(xié)同過濾推薦算法主要分為基于內(nèi)存和基于模型兩大類，這兩類協(xié)同過濾推薦技術(shù)各有特點(diǎn).基于內(nèi)存的協(xié)同過濾根據(jù)相似性對象不同又可以分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾.它是協(xié)同過濾技術(shù)中最成功的算法，它利用整個用戶評分?jǐn)?shù)據(jù)集來計算用戶之間的相似度，尋找與目標(biāo)用戶偏好最相近的N個鄰居即Top-N推薦.它的特點(diǎn)是思想簡單，有較高的精確度，但是為了得到目標(biāo)用戶的推薦結(jié)果，必須掃描整個數(shù)據(jù)集，這樣就會帶來數(shù)據(jù)的可擴(kuò)展性問題.隨著用戶和項目都在大量增加，基于內(nèi)存的協(xié)同過濾很不適合在線推薦系統(tǒng)[3-4].而與基于內(nèi)存的協(xié)同過濾不同的是基于模型的協(xié)同過濾是利用用戶的評分?jǐn)?shù)據(jù)集訓(xùn)練出一個模型，利用模型給目標(biāo)用戶進(jìn)行推薦.基于模型的協(xié)同過濾推薦主要有：樸素貝葉斯模型[5]、聚類分析模型[6-8]、圖模型[9]、以及基于矩陣分解模型的奇異值分解[10]等.模型推薦算法可以在很短的時間內(nèi)作出響應(yīng)，同時緩解了傳統(tǒng)的協(xié)同過濾數(shù)據(jù)稀疏性和可擴(kuò)展性等問題.但是它的缺點(diǎn)是：模型訓(xùn)練時間比較長，且對于數(shù)據(jù)變動過于敏感，推薦的結(jié)果準(zhǔn)確性也缺乏很好的解釋性等.

為了使推薦系統(tǒng)同時具有更好的擴(kuò)展性和更好的推薦準(zhǔn)確性，本論文提出對首先利用用戶的特征運(yùn)用K-Means算法給用戶聚類，然后在聚類的基礎(chǔ)上對每個聚類后的聚簇中利用混合協(xié)同過濾框架為每個聚簇訓(xùn)練一個模型.從而達(dá)到對推薦擴(kuò)展性和準(zhǔn)確性的提高.

1　改進(jìn)優(yōu)化

為了解決基于內(nèi)存的協(xié)同過濾面臨的可擴(kuò)展性問題，于是根據(jù)用戶的特征運(yùn)用K-Means算法給用戶聚類.為了減小用戶經(jīng)過聚類之后帶來的推薦精度下降的問題，本論文提出對混合協(xié)同過濾框架進(jìn)行改進(jìn).即在聚類之后在每個聚簇中利用基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾進(jìn)行混合模型的建立.從而提高算法的推薦準(zhǔn)確性.本文的算法流程圖如圖1.

圖1　算法流程示意圖Figure 1　Algorithm flow diagram

1.1　基于用戶特征的K-Means聚類

輸入：目標(biāo)用戶Ua，最終的聚類個數(shù)M

輸出：目標(biāo)用戶Ua所在的聚類.

1)從用戶的特征數(shù)據(jù)集中隨機(jī)地選擇M個用戶特征向量來作為聚類的質(zhì)心.

2)計算其余的用戶向量距離M個質(zhì)心的距離，然后把用戶加入到距離質(zhì)心最近的那個簇中.

3)每個用戶都已經(jīng)屬于其中的一個簇，根據(jù)每個質(zhì)心所包含的數(shù)據(jù)向量的集合，重新計算從而得到新的質(zhì)心.

4)如果新計算得到的質(zhì)心與原來的質(zhì)心之間的距離達(dá)到每個事先設(shè)置好的閾值，算法中止；否則需要迭代步驟2)～4).

1.2　混合協(xié)同過濾框架

由于基于模型的推薦算法在一定程度上解決了傳統(tǒng)的協(xié)同過濾算法面臨的可擴(kuò)展性問題，但隨之而來的是推薦精度的下降[5].為了使推薦算法具有兩者的優(yōu)點(diǎn)，于是提出了一種混合協(xié)同過濾框架，從而可以有效地提高用戶經(jīng)過K-Means算法聚類之后的推薦精度.這個框架包括兩步：第一步中論文的訓(xùn)練集采用5折交叉驗證的方式來產(chǎn)生，并分別在訓(xùn)練集上運(yùn)用基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾算法對訓(xùn)練集進(jìn)行預(yù)測，分別產(chǎn)生基于用戶的協(xié)同過濾的預(yù)測結(jié)果和基于項目的協(xié)同過濾的預(yù)測結(jié)果.第二步中訓(xùn)練集是第一步基于用戶的協(xié)同過濾產(chǎn)生的預(yù)測結(jié)果與基于項目的協(xié)同過濾產(chǎn)生的預(yù)測結(jié)果，并將分別產(chǎn)生的預(yù)測結(jié)果進(jìn)行建模使其與真實(shí)值之間的誤差越來越小.其中基于用戶的協(xié)同過濾相似度的計算采用的是改進(jìn)的Pearson相似度[11]，相似度計算公式如下：

(1)

基于項目的協(xié)同過濾相似度的計算采用的是修正的余弦相似性的計算公式如下：

sim(u,v)=

(2)

1.2.1第一步

第一步的作用是產(chǎn)生第二步的建模訓(xùn)練數(shù)據(jù).定義R表示用戶的原始評分矩陣，將整個原始的評分矩陣隨機(jī)的平均分成五等分，其中第j份用Rj表示，Rj表示除了Rj以外的其他數(shù)據(jù).如果Rj被用作訓(xùn)練數(shù)據(jù)那么相應(yīng)的Rj就被用作測試數(shù)據(jù).FU表示基于用戶的協(xié)同過濾，F(xiàn)I表示基于項目的協(xié)同過濾.用式(1)產(chǎn)生第二步的訓(xùn)練數(shù)據(jù).

(3)

1.2.2第二步

第二步的作用是將第一步產(chǎn)生的訓(xùn)練數(shù)據(jù)對基于項目的協(xié)同過濾和基于用戶的協(xié)同過濾進(jìn)行線性融合.融合后的建模模型如下：

F(rui)=θ(1)FU(rui)+θ(2)FI(rui).

(4)

其中F(rui)表示經(jīng)過線性融合后的預(yù)測函數(shù)，θ(1)和θ(2)表示基于項目的協(xié)同過濾和基于用戶的協(xié)同過濾所占的預(yù)測值的權(quán)重.

最終的目標(biāo)是要求預(yù)測值與真實(shí)值之間的誤差最小，即表示成如式(5)所示的最小值：

f=|F(rui)-rui|.

(5)

因為論文的問題是具有實(shí)際意義的，利用線性回歸模型融合后，將所有的權(quán)重參數(shù)約束為非負(fù)，所以最終表示成了帶有約束條件的二次規(guī)劃問題.通過拉格朗日乘子和KT條件解答.

2　實(shí)驗和分析

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

實(shí)驗數(shù)據(jù)采用的是MovieLens公開數(shù)據(jù)集，本文數(shù)據(jù)集采用MovieLens公開數(shù)據(jù)集，分別在100 K和1 M兩個數(shù)量級的數(shù)據(jù)集上進(jìn)行實(shí)驗.其中100 K數(shù)據(jù)集包含了943個用戶對1 682部電影的10萬條評分記錄.1M數(shù)據(jù)集包含了6 040個用戶對3 900部電影的100萬條評分記錄.本文用到了歷史評分信息和用戶特征信息兩個數(shù)據(jù)集.其中用戶的特征信息如表1.本論文選取了其中的三個屬性并根據(jù)專家意見給每個屬性表示成數(shù)值的形式：age(1～3)、gender(0～1)、occupation(1～8)，首先運(yùn)用基于用戶特征的K-Means算法進(jìn)行聚類，然后隨機(jī)的把在一個簇中的評分?jǐn)?shù)據(jù)分成兩份，一份占總評分?jǐn)?shù)據(jù)的80%用作訓(xùn)練集，另一份占總評分?jǐn)?shù)據(jù)的20%用作測試集.

表1　用戶特征信息表

2.2　評價指標(biāo)

推薦系統(tǒng)多采用準(zhǔn)確度來對算法的好壞進(jìn)行評價[3].準(zhǔn)確度是衡量推薦算法預(yù)測用戶對項目的評分與用戶實(shí)際對項目的評分的相似程度，通常采用平均絕對誤差(MAE)來衡量推薦算法的準(zhǔn)確度.MAE是一個簡單卻魯棒的用于評估的推薦精度技術(shù)，計算的是預(yù)測評分與實(shí)際評分差的絕對值.MAE越小，則推薦精度也會越高.用戶U的平均絕對誤差計算如下：

(6)

其中F(rui)代表用戶u對項目i的預(yù)測得分，rui表示用戶u對項目i的實(shí)際得分N表示測試集的大小.

2.3　結(jié)果仿真分析

為了驗證本文所提出算法的有效性，設(shè)計了三組對比實(shí)驗：第一組先用用戶特征聚類再用基于用戶的協(xié)同過濾，第二組先用用戶的特征進(jìn)行聚類再用基于項目的協(xié)同過濾，第三組也就是本文提出的先用基于用戶特征進(jìn)行聚類再用混合協(xié)同過濾框架的算法進(jìn)行推薦作對比.Cacheda等人[4]經(jīng)過實(shí)驗后得出在MovieLens數(shù)據(jù)集上聚成8個簇時算法在精確度和擴(kuò)展性上得到了很好的折中，本文的實(shí)驗聚簇也是設(shè)定為8個.

本文數(shù)據(jù)集采用MovieLens公開數(shù)據(jù)集，分別在100 K和1 M兩個數(shù)量級的數(shù)據(jù)集上進(jìn)行實(shí)驗.仿真結(jié)果如圖2和圖3.

圖2　MovieLens 100 K數(shù)據(jù)集實(shí)驗圖Figure 2　Experiment diagram ofMovieLens 100K data set

圖3　MovieLens 1M數(shù)據(jù)集實(shí)驗圖Figure 3　Experiment diagram ofMovieLens 1M data set

由圖可以看出本論文提出的算法能夠提高推薦系統(tǒng)的準(zhǔn)確度.同時也驗證了在聚類之后基于項目的協(xié)同過濾要優(yōu)于基于用戶的協(xié)同過濾.

3　結(jié)　語

本文所提出的基于用戶特征聚類的混合協(xié)同過濾推薦算法在一定程度上解決了傳統(tǒng)算法面臨的可擴(kuò)展性問題和準(zhǔn)確性問題.然而在進(jìn)行K-Means算法進(jìn)行聚類時，初始點(diǎn)的選擇和聚簇個數(shù)的選擇對推薦系統(tǒng)效果的好壞也有很大的影響.另一方面，是否對其他更多的數(shù)據(jù)集具有普適性等問題，將會作為后期工作中繼續(xù)研究的內(nèi)容.

【參考文獻(xiàn)】

[1]UNGAR L H, FOSTER D P. Clustering methods for colla-borative filtering[C]//ProcofWorkshoponRecommendationSystemsatthe15thNationalConference.onArtificialIntelligence. Menlo Park:AAA I Press, 1998:11-15.

[2]BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]//Procofthe14thConferenceonUncertaintyinArt-ificialIntelligence. Madison:Morgan-Kaufmann, 1998:43-52.

[3]CACHEDA F, CARNEIRO V, FERNANDEZ D, et al. Comparison of collaborative filtering algorithms:limitations of current techniques and proposals for scalable, high-per-formance recommender systems[J].ACMTransactionsontheWeb, 2011, 5(1) :161-171.

[4]SEHGAL M S B, GONDAL I, DOOLEY L. Stacked regression ensemble for cancer class prediction[C]//Procof

IEEEInternationalConferenceonIndustrialInformatics. Perth, WA, Australia:IEEE, 2005:831-835.

[5]LIU H. A new user similarity modelto improve the accuracy of collaborative filtering[J].Knowledge-basedSystem, 2014, 15(2):156-166.

[6]KANIMOZHI M, LOGESHWARI K, SARANYA K, et al. Clustering for collaborative filtering application in Web recommenda-tions[J].InternationalJournalofComputerScience&MobileComputing, 2013,2(4):217-222.

[7]HUANG G Y, LI Y C, GAO J P, et al. Collaborative filtering recommendation algorithm based on user clustering of item attributes[J].ComputerEngineering&Design, 2010,31(5):1038-1041.

[8]XUE G R, LIN C X, YANG Q, et al. Scalable collaborative filtering using cluster-based smoothing[C]//Procofthe28thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval. New York:ACM Press, 2005:114-121.

[9]GAO H J, TANG J L, HU X, et al. Exploring temporal effects for location recommendation on location-based social networks[C]//Procofthe7thACMConferenceonRecommenderSystems. New York:ACM Press, 2013:93-100.

[10]GE S, GE X Y. An SVD-based collaborative filtering approach to alleviate cold-start problems[C]//Procofthe9thInternationalConferenceonFuzzySystemsandKnowledgeDiscovery. Sichuan,China:IEEE, 2012:1474-1477.

[11]衛(wèi)澤, 周登文. 基于用戶的優(yōu)化協(xié)同過濾推薦算法[J]. 計算機(jī)與數(shù)學(xué)工程, 2017,45(4):613-615.

WEI Z, ZHOU D W. Colaborative filtering recommend-ation optimization based on user[J].Computer&DigitalEngineering, 2017,45(4):613-615.