基于改進協(xié)同過濾算法的圖書網(wǎng)站個性化推薦模型構(gòu)建研究

李敬明，程家興，張　偉，方　賢

(1.安徽新華學(xué)院信息工程學(xué)院，安徽合肥 230088；2.合肥工業(yè)大學(xué)管理學(xué)院，安徽合肥 230009；

3.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，安徽合肥 230031)

?

基于改進協(xié)同過濾算法的圖書網(wǎng)站個性化推薦模型構(gòu)建研究

李敬明1,2，程家興1,3，張偉1，方賢1

(1.安徽新華學(xué)院信息工程學(xué)院，安徽合肥 230088；2.合肥工業(yè)大學(xué)管理學(xué)院，安徽合肥 230009；

3.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，安徽合肥 230031)

[摘要]協(xié)同過濾是推薦系統(tǒng)應(yīng)用最廣泛的方法，其中項目之間的相關(guān)性是影響推薦算法質(zhì)量的關(guān)鍵因素之一，針對基本協(xié)同過濾算法中未充分利用項目之間的相關(guān)系數(shù)，且算法的計算量也會隨著用戶和項目的不斷增加呈現(xiàn)出爆炸性的增長，從而導(dǎo)致推薦質(zhì)量低下等問題，本文提出了一種基于聚類分析的改進協(xié)同過濾算法。該算法加入項目相關(guān)性計算，利用聚類分析算法提高推薦算法效率，并將其應(yīng)用于圖書網(wǎng)站個性化推薦模型的構(gòu)建。仿真實驗表明，這種改進后的算法在收斂速度與算法準確性方面取得了顯著的提高。

[關(guān)鍵詞]改進協(xié)同過濾；聚類分析；個性化推薦；圖書推薦

1研究背景

近年來，隨著網(wǎng)絡(luò)信息資源的不斷豐富和發(fā)展，如何精準地向每個用戶推薦他們最感興趣的項目是目前各大網(wǎng)站保持用戶粘性和競爭力的關(guān)鍵技術(shù)，推薦系統(tǒng)在許多領(lǐng)域都表現(xiàn)出它的巨大應(yīng)用潛力，尤其在電子商務(wù)領(lǐng)域應(yīng)用更為廣泛，如一些大型的在線閱讀網(wǎng)站與圖書網(wǎng)站都不同程度地使用了各種個性化推薦系統(tǒng)[1]。協(xié)同過濾技術(shù)[2]是個性化推薦系統(tǒng)中最成功的推薦技術(shù)，通過分析歷史數(shù)據(jù)，將興趣相近的用戶作為目標用戶的鄰居放入鄰居集中，找出鄰居集中用戶感興趣的項目并推薦給當前用戶。目前使用的協(xié)同過濾算法是基于用戶-項目評價矩陣的，沒有考慮項目與項目之間的關(guān)系對最終推薦結(jié)果的影響，并且當用戶-項目矩陣不斷增加時，算法的計算量也在不斷增加，最終導(dǎo)致結(jié)算法的計算量大、可擴展性差及推薦結(jié)果的可信度低等。為了解決當前協(xié)同過濾技術(shù)存在的一系列問題，研究者們基于已有的算法提出了多種改進的算法思想并加以應(yīng)用。根據(jù)項目之間的相似性計算提出了基于評分預(yù)測的協(xié)作過濾方法[3]、利用算法精簡評分矩陣維數(shù)而提出的維數(shù)簡化算法[4]等。

本文采用了一種基于聚類分析的改進協(xié)同過濾算法，使用k-means聚類算法將現(xiàn)有的用戶進行聚類，使同一個聚類中用戶的興趣度最為相似。在預(yù)測評分時加入項目之間的相似性，提高預(yù)測評分的精確度。并將其應(yīng)用于優(yōu)化圖書網(wǎng)站的個性化推薦質(zhì)量。

2相關(guān)工作

協(xié)同過濾技術(shù)通過分析用戶的歷史數(shù)據(jù)，生成與目標用戶興趣相似的用戶并組成鄰居集，并將鄰居用戶集中感興趣的項目推薦給當前用戶，即產(chǎn)生top-N推薦集。在傳統(tǒng)基于用戶的協(xié)同過濾算法中，輸入當前用戶的待處理數(shù)據(jù)通常是一個m*n的用戶-項目評價矩陣R=(ratingij)(i∈m，j∈n)；m是用戶的數(shù)目，n是項目的數(shù)目。ratingij表示第i個用戶對第j個項目的評分。在本文構(gòu)建的模型中，ratingij通常為-1～5中的一個整數(shù)，其中-1表示其沒有瀏覽過該書籍，0則表示用戶閱讀了該項目但卻沒有進行評價，1～5數(shù)值的大小表示用戶對該書籍的喜愛程度。在其它推薦系統(tǒng)中，比如電子商務(wù)的推薦系統(tǒng)中我們也可以使用0～1中的一個整數(shù)表述用戶是否購買了某件商品，進而進行數(shù)據(jù)表述的工作。圖書個性化推薦系統(tǒng)用戶-項評分矩陣如下：

協(xié)同過濾技術(shù)的關(guān)鍵就是通過計算用戶之間的相似性為當前用戶找到一個最近鄰居集(Neighbor)，并按照相似性的大小進行排序，根據(jù)鄰居用戶提供的信息篩選出當前用戶最可能感興趣的項目并進行推薦。例如：對一個當前用戶u，使用Person相關(guān)度或者目前常用的向量空間相似度計算其與用戶集中的任一用戶ua的相似性sim(u,ua)，按大小進行排序形成用戶u的最近鄰居集neighbor∈{sim(u,u1),sim(u,u2),…,sim(u,um-1)}，并且滿足sim(u,u1)>sim(u,u2)>…>sim(u,um-1)。這里，我們使用Person相關(guān)度計算用戶之間的相似性，計算公式如下：

(1)

當產(chǎn)生了當前用戶u的最近鄰居Neighbor之后，將包括用戶u在內(nèi)的所有用戶評分項目合集減去當前用戶的所有已評分項目，得到當前用戶u的待預(yù)測評分項目合集Iu。并且計算用戶u對每一個項目i∈Iu的預(yù)測評分，篩選出評分最高的前n項，即產(chǎn)生top-N推薦集推薦給當前用戶，用戶對待預(yù)測項目的預(yù)測評分計算公式如下：

(2)

3基于改進協(xié)同過濾算法的圖書網(wǎng)站個性化推薦模型的構(gòu)建

3.1基于項目相關(guān)性的改進協(xié)同過濾算法

目前，基于用戶的協(xié)同過濾技術(shù)發(fā)展已經(jīng)十分成熟，但其有明顯的缺點，即沒有考慮到項目之間的相關(guān)性。比如預(yù)測當前用戶對一本歷史類書籍的評分時，可能會將鄰居用戶閱讀的傳記類書籍和偵探類書籍一起考慮進去并進行評分，很明顯，傳記類書籍對最后預(yù)測評分的影響要比偵探類書籍的大，但基于用戶的協(xié)同過濾技術(shù)會將兩者同等地考慮進去，降低了最終的推薦質(zhì)量。

本文采用了一種基于項目屬性計算項目之間相關(guān)性rel(i，ip)的改進協(xié)同過濾算法，并由此計算受不同項目之間相關(guān)性所影響的最終預(yù)測評分。通常使用Person相關(guān)度來計算項目之間的相關(guān)性，但此方法不具有客觀性，容易受用戶的主觀影響。不能客觀反映項目之間的相關(guān)性，導(dǎo)致最終的推薦質(zhì)量不精準。因此，本文使用了基于項目屬性矩陣的項目相關(guān)性計算。存在一個項目屬性矩陣Attr={attrij}，其中attrij表示第i個項目是否具有第j個屬性，且其值為0或1中的任一整數(shù)，0表示該項目不具有該屬性，1表示具有。Attr項目屬性矩陣如下：

基于項目屬性計算項目相似性計算公式如下：

(3)

(4)

當引入項目相關(guān)性之后，用戶相似性計算就改進為以下公式：

(5)

其中，sim(ua,ub)iP表示的是用戶a和用戶b基于待預(yù)測項目iP的相似性。最后，將(5)式代入(2)式中得到以下新的預(yù)測評分公式，并選出最近鄰居集和產(chǎn)生top-N推薦。

(6)

3.2基于聚類分析的K-means算法優(yōu)化協(xié)同過濾技術(shù)

協(xié)同過濾算法擴展性較差，每次進行個性化推薦時都要計算當前用戶與數(shù)據(jù)庫中每一個用戶的相似性，之后才能得到最近鄰居集并產(chǎn)生top-N推薦。當用戶-項矩陣過大時，計算量就會變得十分巨大，也會造成最終的推薦質(zhì)量低下，不能達到預(yù)期額推薦期望。因此，可以使用聚類分析對協(xié)同過濾技術(shù)進行優(yōu)化，提高個性化推薦質(zhì)量。

聚類分析[5-6]是模式識別和數(shù)據(jù)壓縮領(lǐng)域的一個重要問題，是非監(jiān)督學(xué)習(xí)的重要方法，我們可以事先對數(shù)據(jù)庫提供的用戶信息使用聚類分析算法進行聚類，使得在同一聚類中的用戶行為興趣的相似性較大，處于不同聚類的任兩個用戶的相似性即興趣相似度較小。當有用戶需要進行個性化推薦時，直接計算出該用戶屬于哪一個聚類。并在該聚類中產(chǎn)生最近鄰居集Neighbor，進而產(chǎn)生top-N推薦。這樣便極大地簡化了推薦過程。當有過大的用戶-項矩陣時，不會有過多的計算量，并且優(yōu)化了推薦質(zhì)量。

K-means是基于劃分的聚類算法[7-8]，該算法簡單且易于使用，運行速度快，與其它聚類算法相比應(yīng)用更加廣泛。設(shè)k是算法在數(shù)據(jù)集上輸出的聚類數(shù)量，數(shù)據(jù)集是n個圖書網(wǎng)站用戶構(gòu)成集合{I1，I2，…，In}，并隨機在數(shù)據(jù)集中找出k個用戶作為初始聚類中心，分別計算剩下的每個用戶與每個初始聚類中心的距離，并將此用戶其分配給距其距離最近的聚類中心所在的聚類，然后更新每個聚類的聚類中心,直到準則函數(shù)收斂[9]。

(7)

其中，gj是聚類Cj的聚類中心，且l∈{1，2，…，n}，j∈{1，2，…，k}，下面對k-means算法的實現(xiàn)過程簡要概述：

第一步，輸入：包含n個對象的項目集以及所需的聚類個數(shù)k；

第二步，初始化k個聚類中心{g1，g2，…，gk}，其中g(shù)j∈In，j∈{1，2，…，k}，In是所有用戶的集合；

第三步，使每一個聚類Cj與聚類中心gj相對應(yīng),In=In-{g1，g2，…，gk}；

第四步，從In第一個元素I1開始計算與各個距誒中心的相似度，并將其放入最相似的聚類中心gj所屬聚類Cj中，并在In集合中除去該對象，直到集合In為空；

第六步，輸出k個聚類。

3.3基于改進協(xié)同過濾算法的圖書網(wǎng)站個性化推薦模型

對基本協(xié)同過濾算法中的項目相關(guān)性以及利用聚類算法降低計算復(fù)雜度等兩方面進行了上述改進，并將其應(yīng)用于圖書網(wǎng)站個性化推薦建模中。具體步驟如下：

第一步，導(dǎo)入網(wǎng)站數(shù)據(jù)中的圖書屬性表和用戶評價表。根據(jù)圖書屬性表中的數(shù)據(jù)使用式(3)和式(4)聯(lián)合計算圖書之間的相關(guān)性；

第二步，根據(jù)3.2給出的步驟對網(wǎng)站用戶進行聚類，使處于相同聚類的用戶最相似；

第三步，根據(jù)用戶評價表使用式(5)計算用戶之間的相似性，并將前一百的用戶作為目標用戶的最近鄰居集，并通過最近鄰居集找出目標用戶的待預(yù)測評分書籍集合；

第四步，使用式(6)計算預(yù)測評分，并將評分前十的書籍作為推薦項目(top-N)推薦給用戶。

4實驗及結(jié)果分析

4.1實驗數(shù)據(jù)集及評價標準

常用的評價推薦系統(tǒng)推薦質(zhì)量的度量主要包括統(tǒng)計精度度量方法和決策支持精度度量方法兩類[10-11]，根據(jù)本文的實驗情況，這里我們使用平均絕對方差MAE方法。該方法通過計算當前用戶待預(yù)測項目的預(yù)測評分和實際評分的偏差作為度量來檢查推薦系統(tǒng)推薦結(jié)果的精確性。MAE值越低，推薦系統(tǒng)的推薦質(zhì)量越低。

設(shè)當前用戶的預(yù)測評分集合為{iP1，iP2，…，iPn}，用戶實際的評分集合為{i1，i2，…，in}，則MAE值得計算如下：

(8)

以上基于聚類分析優(yōu)化的協(xié)同過濾技術(shù)有效地避免了傳統(tǒng)協(xié)同過濾技術(shù)中出現(xiàn)的各種問題，我們選擇某圖書閱讀網(wǎng)站提供的數(shù)據(jù)，根據(jù)數(shù)據(jù)集中提供的描述文件采用18277條評價數(shù)據(jù)。共有2622名用戶參與了評價6609本書籍的評價，實驗采用了Matlab軟件處理實驗數(shù)據(jù)。

我們將所有數(shù)據(jù)集中的圖書分為15個屬性分類：懸疑、名著、影視、經(jīng)管、社科、生活、武俠、歷史、傳記、人物、恐怖、推理、言情、幻想、學(xué)術(shù)，共有屬性極大個數(shù)設(shè)為5，如表1所示。

產(chǎn)生一個m*n輸入矩陣，該矩陣是用戶-圖書評價矩陣，矩陣中每個值都是-1～5中的一個整數(shù)，值的高低代表了用戶對該評價書籍的喜愛程度。0表示用戶閱讀了該書籍卻沒有進行有效的評價，-1表示用戶沒有閱讀該書籍，部分數(shù)據(jù)如表2 所示。

表1　圖書屬性表

表2　用戶-評價表

當目標用戶進入時，服務(wù)器提取其歷史瀏覽日志，計算它與各個聚類中心的相似度，并將其分入最相似的一個聚類中。之后用(5)式計算目標用戶與當前聚類中每一個對象基于未評分圖書項目的相似度，并按照大小順序進行排列，產(chǎn)生當前用戶的最近鄰居集。找出最近鄰居集中所有鄰居已評分圖書的合集，除去其中當前用戶已評分的圖書項目，得到待預(yù)測評分的圖書候選集。使用(6)式計算當前用戶對所有未評分圖書的預(yù)測評分并按大小進行排列，選出前6項評分最高的圖書推薦給當前用戶，即產(chǎn)生top-N推薦集。

4.2實驗數(shù)據(jù)集及評價標準

將實驗得到的MAE值結(jié)果繪制成表格數(shù)據(jù)如表3所示，并與使用其它沒有進行優(yōu)化的協(xié)同過濾算法得到的結(jié)果進行比較。

表3　MAE值分析表

使用Matlab繪圖結(jié)果如圖1和圖2所示。

圖1　MAE值分析表

圖2　收斂時間分析表

未采用聚類優(yōu)化的協(xié)同過濾算法效率不高，收斂速度較慢，且當數(shù)據(jù)量過大時，推薦結(jié)果質(zhì)量比較差，從MAE值分析表(圖1)中可以看出，采用聚類之后的算法得到的結(jié)果相比而言質(zhì)量較高，能準確地推薦給用戶所希望看到的書籍。從收斂時間分析表(圖2)中可以看出，采用了聚類的算法收斂速度較快，實際操作中更能滿足企業(yè)用戶和閱讀用戶的需求。因此，給予項目相關(guān)性改進后的協(xié)同過濾算法得到的結(jié)果更加良好，值得進一步進行推廣。

5結(jié)語

基本的協(xié)同過濾算法是從用戶相似鄰居的角度，分析用戶興趣并自動進行推薦。此算法在信息量適度的情況下具有良好的效率，在進行網(wǎng)站數(shù)據(jù)分析時數(shù)據(jù)量通常十分龐大，使用基本算法時每次推薦都必須要在計算用戶與其它所有用戶的相似性之后再進行推薦，效率較低。使用聚類算法使得每次推薦的搜索范圍和計算量都大大降低，并且由于加入了項目之間的相似性計算，其推薦質(zhì)量相對于基本的協(xié)同過濾算法得到了很大的提升。

[參考文獻]

[1]Sivapalan S,Sadeghian A,Rahnama H,et al.Recommender systems in e-commerce[C].World Automation Congress, IEEE,2014:179-184.

[2]張騰季.個性化混合推薦算法的研究[D].杭州:浙江大學(xué),2013.

[3]Sarwar B,Karypis G,Konstan J,et al.Item-based collab—orative filtering recommendation algorithms[C]. Proceeding of the 10th international World Wide Web Conference,New York,ACM Press,2010:285-295.

[4]鄧愛林,朱揚勇,施伯樂.基于項目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報,2003,14(9):1621-1628.

[5]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機械工業(yè)出版社,2005:185-218.

[6]于文倩.聚類相關(guān)知識簡介[J].電子世界,2014(11):190.

[7]崔丹丹.K-Means聚類算法的研究與改進[D].合肥:安徽大學(xué),2012.

[8]沈艷,余冬華,王昊雷.粒子群K-means聚類算法的改進[J].計算機工程與應(yīng)用,2014(21):125-128.

[9]張雪鳳,張桂珍,劉鵬.基于聚類準則函數(shù)的改進K-means算法[J].計算機工程與應(yīng)用,2011,47(11):123-127.

[10]吳發(fā)青,賀樑,夏薇薇,等.一種基于用戶興趣局部相似性的推薦算法[J].計算機應(yīng)用,2008,28(8):1981-1985.

[11]梁天一,梁永全,樊健聰,等.基于用戶興趣模型的協(xié)同過濾推薦算法[J].計算機應(yīng)用與軟件,2014(11):261-263.

[12]皮佳明.基于用戶興趣變化的協(xié)同過濾推薦算法研究[D].昆明:云南財經(jīng)大學(xué),2014.

The Research on Construction of Library Website Personalized Recommendation Model Based on Improved Collaborative Filtering Algorithm

LI Jing-ming1,2，CHENG Jia-xing1,3， ZHANG Wei1，F(xiàn)ANG Xian1

(1.School of Information Engineering, Anhui Xinhua University, Hefei Anhui 230088, China；2.School of Management, Hefei University of Technology, Hefei Anhui 230009, China；3.School of Business, Anhui Finance and Economics University, Hefei Anhui 230031, China)

Abstract:Recommend system based on collaborative filtering algorithm has been widely used at present. Correlation between the two projects has not been considered in the basic collaborative filtering algorithm. There is a explosive growth of the compute when the users’ and the projects’ volume has been huge, which it reduces the quality of recommendation. An improvement collaborative algorithm based on clustering analysis is proposed in this paper. The project correlation calculation is added to collaborative filtering algorithm, which it is applied to build personal book recommend model. The experiments show that the improved algorithm can achieve good recommending quality.

Key words:improved collaborative filtering; clustering analysis; personalized recommendation; book recommendation

[作者簡介]李敬明(1979- )，男，講師，博士研究生，從事智能計算與數(shù)據(jù)挖掘研究。

[基金項目]國家自然科學(xué)基金項目“面向交易和服務(wù)過程的民營中小型銀行經(jīng)營模式及相關(guān)政策研究”(71403001)；安徽省教育廳人文社會科學(xué)研究重點項目“體制外金融與安徽小微企業(yè)對接服務(wù)機制和風(fēng)險防范研究”(SK2013A011)。

[收稿日期]2015-12-12

[中圖分類號]TP319.3

[文獻標識碼]A

[文章編號]2095-7602(2016)02-0040-06