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

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

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

?

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

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

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

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

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

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

1研究背景

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

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

2相關(guān)工作

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

協(xié)同過濾技術(shù)的關(guān)鍵就是通過計(jì)算用戶之間的相似性為當(dāng)前用戶找到一個(gè)最近鄰居集(Neighbor)，并按照相似性的大小進(jìn)行排序，根據(jù)鄰居用戶提供的信息篩選出當(dāng)前用戶最可能感興趣的項(xiàng)目并進(jìn)行推薦。例如：對一個(gè)當(dāng)前用戶u，使用Person相關(guān)度或者目前常用的向量空間相似度計(jì)算其與用戶集中的任一用戶ua的相似性sim(u,ua)，按大小進(jìn)行排序形成用戶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)度計(jì)算用戶之間的相似性，計(jì)算公式如下：

(1)

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

(2)

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

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

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

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

基于項(xiàng)目屬性計(jì)算項(xiàng)目相似性計(jì)算公式如下：

(3)

(4)

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

(5)

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

(6)

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

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

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

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

(7)

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

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

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

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

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

第六步，輸出k個(gè)聚類。

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

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

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

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

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

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

4實(shí)驗(yàn)及結(jié)果分析

4.1實(shí)驗(yàn)數(shù)據(jù)集及評價(jià)標(biāo)準(zhǔn)

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

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

(8)

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

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

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

表1　圖書屬性表

表2　用戶-評價(jià)表

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

4.2實(shí)驗(yàn)數(shù)據(jù)集及評價(jià)標(biāo)準(zhǔn)

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

表3　MAE值分析表

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

圖1　MAE值分析表

圖2　收斂時(shí)間分析表

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

5結(jié)語

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

[參考文獻(xiàn)]

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

[2]張騰季.個(gè)性化混合推薦算法的研究[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áng)勇,施伯樂.基于項(xiàng)目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào),2003,14(9):1621-1628.

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

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

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

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

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

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

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

[12]皮佳明.基于用戶興趣變化的協(xié)同過濾推薦算法研究[D].昆明:云南財(cái)經(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- )，男，講師，博士研究生，從事智能計(jì)算與數(shù)據(jù)挖掘研究。

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

[收稿日期]2015-12-12

[中圖分類號]TP319.3

[文獻(xiàn)標(biāo)識碼]A

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