基于聚類分析算法的圖書推薦系統(tǒng)的研究

●孫彥超（北京信息科技大學(xué)教務(wù)處，北京　100192）

基于聚類分析算法的圖書推薦系統(tǒng)的研究

●孫彥超（北京信息科技大學(xué)教務(wù)處，北京100192）

［關(guān)鍵詞］協(xié)同過濾；聚類；最近鄰居；推薦系統(tǒng)；評(píng)價(jià)矩陣

［摘要］針對(duì)協(xié)同過濾算法通過用戶評(píng)分矩陣生成推薦時(shí)會(huì)遇到“冷啟動(dòng)”、“數(shù)據(jù)稀疏性”問題，以及忽略用戶興趣實(shí)時(shí)變化及多樣性的特點(diǎn)，筆者在傳統(tǒng)協(xié)同過濾算法的基礎(chǔ)上引入聚類算法，對(duì)協(xié)同過濾算法進(jìn)行改進(jìn)，解決了傳統(tǒng)算法的“冷啟動(dòng)”及“數(shù)據(jù)稀疏性”問題。改進(jìn)后的算法利用北京信息科技大學(xué)圖書管理系統(tǒng)中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，結(jié)果證明新的算法比傳統(tǒng)協(xié)同過濾算法平均絕對(duì)誤差小，從而證明改進(jìn)后的算法具有較高的推薦質(zhì)量。

隨著高校圖書館信息化建設(shè)的不斷推進(jìn)，圖書管理系統(tǒng)建設(shè)的重點(diǎn)已經(jīng)由讀者“查找”圖書轉(zhuǎn)變?yōu)橄蜃x者“推薦”圖書，如何更好地為讀者推薦圖書，如何采集讀者對(duì)圖書的評(píng)價(jià)信息，如何有效實(shí)現(xiàn)每本圖書的最大價(jià)值，已成為圖書管理系統(tǒng)建設(shè)的一個(gè)重要環(huán)節(jié)。協(xié)同過濾算法憑借算法簡單容易實(shí)現(xiàn)、對(duì)數(shù)據(jù)對(duì)象依賴性低及推薦準(zhǔn)確率高等特性，被圖書推薦系統(tǒng)廣泛采用。協(xié)同過濾算法的基本原理是：根據(jù)用戶對(duì)項(xiàng)目的評(píng)價(jià)信息構(gòu)建用戶評(píng)價(jià)矩陣，［1］分析用戶評(píng)價(jià)矩陣生成目標(biāo)用戶的最近鄰居集合，然后根據(jù)最近鄰居集對(duì)物品評(píng)分形成對(duì)推薦。但是，該算法忽略了讀者的特征信息，比如，讀者的愛好跟其年齡、性別、專業(yè)、教育背景等特征信息有著緊密聯(lián)系。通常說，有著相似特征的讀者也具有相似的興趣。協(xié)同過濾算法把目標(biāo)讀者跟全體讀者作對(duì)比，分析其最相似用戶集，這種比較方式對(duì)推薦結(jié)果的準(zhǔn)確性和推薦效率都會(huì)產(chǎn)生巨大影響。本文在協(xié)同過濾算法的基礎(chǔ)上進(jìn)行改進(jìn)，在產(chǎn)生相似讀者集之前，根據(jù)讀者的特征信息對(duì)讀者進(jìn)行聚類，然后對(duì)每一類讀者生成評(píng)價(jià)矩陣，對(duì)目標(biāo)讀者根據(jù)該類評(píng)價(jià)矩陣計(jì)算相似度，從而生成最近鄰居集，依據(jù)最近鄰居集為目標(biāo)讀者預(yù)測(cè)對(duì)待評(píng)價(jià)圖書的評(píng)分，從而產(chǎn)生推薦。因?yàn)榻?jīng)過聚類后的讀者集合具有類內(nèi)較高相似度，不同類之間的讀者具有較低相似度，所以經(jīng)過改進(jìn)后的推薦算法從理論上能夠?yàn)樽x者提供較高質(zhì)量的推薦服務(wù)。

1　傳統(tǒng)協(xié)同過濾算法

推薦算法是推薦系統(tǒng)的核心，其算法的好壞直接決定系統(tǒng)推薦的質(zhì)量。協(xié)同過濾算法可以對(duì)視頻、音頻等結(jié)構(gòu)復(fù)雜的目標(biāo)產(chǎn)生推薦，［2］也可以利用評(píng)分?jǐn)?shù)據(jù)挖掘其隱含的愛好，并且可以產(chǎn)生高質(zhì)量的推薦，因而被業(yè)界廣泛采用。協(xié)同過濾算法主要思想為：收集用戶評(píng)價(jià)信息，將其整理并轉(zhuǎn)化為評(píng)分矩陣，利用評(píng)分矩陣計(jì)算目標(biāo)用戶相似度最高的鄰居集，依據(jù)最近鄰居生成推薦。［3］主要步驟可以分為四步：①建立用戶評(píng)價(jià)矩陣；②計(jì)算用戶間相似度，查找最近鄰居；③根據(jù)最近鄰居為目標(biāo)用戶預(yù)測(cè)評(píng)分；④產(chǎn)生推薦。算法具體過程如下。

（1）建立用戶評(píng)分矩陣。首先，采集用戶信息，對(duì)評(píng)價(jià)信息整理形成m行n列的評(píng)分矩陣。如圖1所示，其中，m表示用戶數(shù)，n表示項(xiàng)目數(shù)，rij表示用戶i對(duì)項(xiàng)目j的評(píng)分。

（2）計(jì)算用戶間相似度，查找最近鄰居。利用用

戶評(píng)價(jià)數(shù)據(jù)，構(gòu)建評(píng)分矩陣，進(jìn)而計(jì)算用戶對(duì)物品評(píng)價(jià)的相似性，根據(jù)評(píng)價(jià)相似性找到相似度最高的鄰居。通常計(jì)算利用評(píng)分矩陣計(jì)算相似度的方法有：使用余弦公式計(jì)算法、相關(guān)系數(shù)計(jì)算法及修正后的余弦公式計(jì)算法。［4］

圖1　用戶評(píng)分矩陣

①余弦公式法，用戶u的所有評(píng)分為向量，用戶u和v的相似度通過計(jì)算和余弦夾角值得到，余弦值越大表示相似度越高。該算法忽略了不同用戶評(píng)分尺度不同對(duì)相似度造成的影響。

②相關(guān)系數(shù)法，通過計(jì)算用戶評(píng)分相關(guān)性，公式如（2），通過對(duì)評(píng)分尺度歸一化處理，避免了余弦公式法的問題，提高了計(jì)算結(jié)果的準(zhǔn)確性；為用戶u和v評(píng)分的平均分，Ru,j為u對(duì)項(xiàng)目I的評(píng)分。

③修正余弦公式法。通過對(duì)用戶對(duì)項(xiàng)目評(píng)價(jià)的評(píng)分進(jìn)行歸一化處理，對(duì)經(jīng)過處理后的評(píng)價(jià)矩陣分析計(jì)算，提高算法得出相似度的準(zhǔn)確性。

（3）預(yù)測(cè)目標(biāo)用戶的評(píng)分。依據(jù)最相似鄰居對(duì)待評(píng)價(jià)對(duì)象的評(píng)分，計(jì)算目標(biāo)用戶對(duì)其的評(píng)分，如計(jì)算公式（4）,其中，N為用戶i的最近鄰居集，Rj,d表示i的最近鄰居j對(duì)項(xiàng)目d的評(píng)分，表示鄰居j的所有評(píng)分的平均值。

（4）產(chǎn)生推薦。為目標(biāo)用戶對(duì)待評(píng)價(jià)項(xiàng)目預(yù)測(cè)評(píng)分，根據(jù)預(yù)測(cè)值進(jìn)行降序排列，取相似度最大的若干個(gè)進(jìn)行推薦。在協(xié)同過濾算法產(chǎn)生推薦結(jié)果過程中，計(jì)算用戶相似度和生成最近鄰居集合是算法中最關(guān)鍵的兩步，同時(shí)也是最耗時(shí)的步驟。隨著用戶和對(duì)象規(guī)模的增長，評(píng)價(jià)數(shù)據(jù)占整個(gè)矩陣的比例迅速下降，從而使得用戶評(píng)分?jǐn)?shù)據(jù)在整個(gè)矩陣中極為稀疏，造成依據(jù)該評(píng)分矩陣產(chǎn)生推薦質(zhì)量下降。另外，對(duì)于新用戶和新項(xiàng)目，沒有任何評(píng)分信息，算法就無法依據(jù)歷史評(píng)分為新用戶產(chǎn)生推薦，也無法把新項(xiàng)目推薦給用戶。這就是協(xié)同過濾算法通常會(huì)遇到的“數(shù)據(jù)稀疏性”和“冷啟動(dòng)”問題。

2　改進(jìn)后協(xié)同過濾算法

由于傳統(tǒng)協(xié)同過濾算法利用用戶的評(píng)分矩陣產(chǎn)生計(jì)算相似度，產(chǎn)生推薦時(shí)會(huì)遇到“冷啟動(dòng)”和“數(shù)據(jù)稀疏性”問題。［5］本文提出了在協(xié)同過濾算法基礎(chǔ)上引入聚類算法對(duì)其進(jìn)行改進(jìn)，進(jìn)而應(yīng)用到個(gè)性化圖書管理系統(tǒng)中。改進(jìn)后的算法工作原理為：首先采集并整理讀者信息，根據(jù)讀者自身特征對(duì)其聚類并生成聚類后讀者對(duì)圖書評(píng)分矩陣，該矩陣更加精準(zhǔn)地反映每類讀者的評(píng)分相似程度，依據(jù)每類讀者特征可以分析其特征相似程度，根據(jù)同類讀者評(píng)分矩陣計(jì)算讀者興趣相似度。同時(shí)，考慮讀者特征相似度和興趣相似度所占權(quán)重，根據(jù)權(quán)重大小計(jì)算讀者整體相似度，以及整體相似度尋找目標(biāo)讀者的鄰居集，從而生成推薦。

（1）采集并整理讀者信息。為了給讀者產(chǎn)生最佳推薦服務(wù)，需要采集讀者的特征及評(píng)分?jǐn)?shù)據(jù)，如特征數(shù)據(jù)包括讀者的年齡、性別、所學(xué)專業(yè)、教育背景等，［6］這些特征信息主要為了對(duì)讀者進(jìn)行聚類，同時(shí)為計(jì)算聚類用戶的特征相似度服務(wù)。另外，需要收集讀者的借閱圖書信息和對(duì)圖書的評(píng)分信息，這部分信息主要是為了形成讀者對(duì)圖書的評(píng)分矩陣，利用評(píng)分矩陣可以計(jì)算出讀者的偏好相似度。［7］

（2）讀者聚類和生成聚類讀者評(píng)分矩陣。根據(jù)讀者的特征信息，本文采用K-Means算法對(duì)讀者聚類，可以極大地減少數(shù)據(jù)的維度，生成最近鄰居時(shí)，只用在目標(biāo)讀者的同一聚類的用戶中計(jì)算，計(jì)算的數(shù)據(jù)量明顯減小，同時(shí)，提高了推薦的準(zhǔn)確性和實(shí)時(shí)性；［8］在改進(jìn)的算法中，為了對(duì)讀者產(chǎn)生高相似度的聚類，主要選取讀者的性別、年齡、專業(yè)、教育背景作為特

征屬性，［9］生成讀者特征矩陣如圖3。

圖3　讀者特征矩陣

圖2　改進(jìn)后算法流程

其中，m為讀者數(shù)量，n為讀者特征數(shù)量，umn為用戶m對(duì)應(yīng)的特征n的值。通過對(duì)讀者特征信息整理，生成讀者特征矩陣后，利用K-Means聚類算法對(duì)其聚類，算法步驟如下：①任意選擇k個(gè)讀者作為聚類對(duì)象中心點(diǎn)；②利用歐式距離公式（5）計(jì)算其他讀者與中心點(diǎn)讀者的特征相似度，根據(jù)相似度對(duì)讀者聚類。［10］

③利用公式（6）更新讀者聚類中心，采用每類讀者相似度的平均值作為新的中心。利用新的中心點(diǎn)，跳轉(zhuǎn)到第2步，重新聚類。［11］

（3）計(jì)算讀者特征相似度及興趣相似度。

①計(jì)算讀者特征相似度。在圖書管理系統(tǒng)中，所有讀者均有個(gè)人特征，通過對(duì)讀者分析，按照性別、年齡、專業(yè)及教育背景進(jìn)行分類，讀者之間的相似度可以用特征相似函數(shù)表示，［12］如公式（7）：

其中，Sim（i,j）讀者i和j的特征相似度，Age（i,j）、Sex（i,j）、Major（i,j）及Hobby（i,j）分別表示讀者間年齡、性別、專業(yè)及愛好相似度。

②計(jì)算讀者興趣相似度。根據(jù)聚類后的讀者評(píng)分矩陣，利用修正余弦公式（3）計(jì)算讀者興趣相似度。

（4）計(jì)算讀者綜合相似度，生成讀者最近鄰居集。讀者綜合相似度的計(jì)算方式是將讀者的特征相似度和興趣相似度結(jié)合起來，如算法公式（8）。該計(jì)算方式既考慮了讀者的客觀特征相似度，同時(shí)兼顧了讀者的主觀興趣相似度。比傳統(tǒng)協(xié)同過濾算法更能全面地考慮讀者的相似度。［13］利用公式（8）計(jì)算讀者綜合相似度后，可以利用閾值法生成目標(biāo)讀者的最近鄰居集。

（5）預(yù)測(cè)目標(biāo)讀者評(píng)分，生成推薦結(jié)果。根據(jù)目標(biāo)讀者的最近鄰居，利用公式（4）預(yù)測(cè)其對(duì)待評(píng)價(jià)圖書的評(píng)分，得到對(duì)圖書的預(yù)測(cè)評(píng)分后，對(duì)圖書評(píng)分值進(jìn)行降序排序，取評(píng)分最大的若干圖書作為

推薦結(jié)果。［14］

3　改進(jìn)后算法分析與實(shí)驗(yàn)

為了測(cè)試改進(jìn)后算法推薦結(jié)果的效果，采用北京信息科技大學(xué)圖書館系統(tǒng)中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，其中，選取1000名讀者基本信息以及對(duì)1500個(gè)圖書的評(píng)價(jià)數(shù)據(jù)，分別從推薦算法的準(zhǔn)確性（MAE）、“冷啟動(dòng)”問題的解決及“數(shù)據(jù)稀疏性”問題的解決三方面比較改進(jìn)前后算法。

（1）推薦算法的準(zhǔn)確性。實(shí)驗(yàn)選用平均絕對(duì)誤差比較改進(jìn)前后算法，［15］如公式（8），其中，n表示圖書的個(gè)數(shù)，P表示讀者對(duì)圖書的預(yù)測(cè)評(píng)分，ri表示讀者對(duì)圖書的實(shí)際評(píng)分。計(jì)算出來的平均絕對(duì)誤差（MAE）越小，表示推薦質(zhì)量越高。［16］

使用公式（8）計(jì)算出來的結(jié)果如圖4所示。

圖4　改進(jìn)前后算法平均絕對(duì)誤差比較

s

由分析結(jié)果可見，改進(jìn)后算法的推薦結(jié)果整體上平均絕對(duì)誤差均比改進(jìn)前低，反映了改進(jìn)后的算法能夠提供較好的推薦質(zhì)量。［17］

（2）“冷啟動(dòng)”及“數(shù)據(jù)稀疏性”問題。“冷啟動(dòng)”問題最典型的是系統(tǒng)新加入新的讀者用戶，重點(diǎn)分析改進(jìn)前后算法對(duì)新的讀者推薦預(yù)測(cè)效果。［18］隨機(jī)從系統(tǒng)中選取10名新讀者，通過對(duì)其推薦預(yù)測(cè)結(jié)果見表。

從表中可見，改進(jìn)前算法對(duì)新讀者不能產(chǎn)生推薦，改進(jìn)后的算法可以向新讀者提供推薦服務(wù)，而且準(zhǔn)確

率較高。因而，新的算法能夠解決推薦算法常見的“冷啟動(dòng)”問題。［19］

表　改進(jìn)前后算法對(duì)新讀者預(yù)測(cè)結(jié)果比較

改進(jìn)后的算法，利用聚類算法將相似特征的讀者進(jìn)行聚類，根據(jù)每類讀者生成評(píng)分矩陣，從而降低了數(shù)據(jù)的緯度，減少了系統(tǒng)的計(jì)算量，進(jìn)而提高了算法推薦的準(zhǔn)確性和實(shí)時(shí)性，間接地解決了改進(jìn)前算法遇到的“數(shù)據(jù)稀疏性”問題。

4　結(jié)論

協(xié)同過濾算法憑借算法簡單容易實(shí)現(xiàn)、對(duì)數(shù)據(jù)對(duì)象依賴性低及推薦準(zhǔn)確率高等特性，被圖書推薦系統(tǒng)廣泛采用。針對(duì)傳統(tǒng)協(xié)同過濾算法會(huì)遇到“冷啟動(dòng)”及“數(shù)據(jù)稀疏性”問題，同時(shí)忽略了用戶興趣實(shí)時(shí)變化及多樣性的特點(diǎn)。本文在傳統(tǒng)協(xié)同過濾算法的基礎(chǔ)上引入聚類算法，利用讀者的特征信息對(duì)其進(jìn)行聚類,并將聚類后的讀者對(duì)圖書的評(píng)價(jià)轉(zhuǎn)化為評(píng)分矩陣，分別計(jì)算每類讀者的特征相似度和興趣相似度，通過分析讀者整體相似性，在同類讀者評(píng)分矩陣中找出相似度高的鄰居，依據(jù)鄰居推測(cè)其對(duì)待評(píng)價(jià)圖書的評(píng)分，根據(jù)評(píng)分結(jié)果生成推薦結(jié)果，改進(jìn)后算法縮小了查找最近鄰居的范圍，提高了算法的運(yùn)算效率。同時(shí)兼顧了讀者主觀興趣和讀者自身的客觀特征屬性，一定程度上提高了算法的準(zhǔn)確率，也解決了傳統(tǒng)算法的“冷啟動(dòng)”及“數(shù)據(jù)稀疏性”問題。進(jìn)而利用北京信息科技大學(xué)圖書管理系統(tǒng)中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，結(jié)果證明新的算法比傳統(tǒng)算法誤差小，說明改進(jìn)后的算法能夠產(chǎn)生較高的推薦質(zhì)量。

［參考文獻(xiàn)］

［1］蔣鵬.上下文感知推薦系統(tǒng)的研究與應(yīng)用［D］.廣州：華南理工大學(xué)，2013：1－3.

［2］靳立忠.基于用戶興趣聚類的協(xié)同過濾推薦技術(shù)的研究［D］.沈陽：東北大學(xué)，2007：7－8.

［3］紀(jì)良浩.協(xié)作過濾信息推薦技術(shù)研究［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2012（1）：78－82.

［4］程飛.基于用戶相似性的協(xié)同過濾推薦算法研究［D］.北京：北京交通大學(xué)，2012：5－6.

［5］任磊.推薦系統(tǒng)關(guān)鍵技術(shù)研究［D］.上海：華東師范大學(xué)，2012：10－17.

［6］李軍平.基于社會(huì)網(wǎng)絡(luò)分析的協(xié)同過濾推薦方法研究［D］.沈陽：遼寧大學(xué)，2013：1－6.

［7］孫歆.基于協(xié)同過濾技術(shù)的SCORM數(shù)字化教學(xué)資源庫研究［D］.杭州：浙江工業(yè)大學(xué)，2013：2－3.

［8］程淑玉.基于協(xié)同過濾算法的個(gè)性化推薦系統(tǒng)的研究［D］.合肥：合肥工業(yè)大學(xué), 2010：8－13.

［9］馮鑫.基于內(nèi)容的自適應(yīng)博客推薦方法的研究［D］.包頭：內(nèi)蒙古科技大學(xué)，2012：7－9.

［10］王均波.協(xié)同過濾推薦算法及其改進(jìn)研究［D］.重慶：重慶大學(xué)，2010：4－6.

［11］王棟針.對(duì)網(wǎng)絡(luò)熱點(diǎn)事件觀點(diǎn)漂移檢測(cè)技術(shù)的研究與實(shí)現(xiàn)［D］.沈陽：東北大學(xué), 2012：6－10.

［12］呂振山.基于RBF神經(jīng)網(wǎng)絡(luò)的文本過濾技術(shù)研究［D］.廣州：暨南大學(xué), 2008：23－30.

［13］楊春喜.Web文本內(nèi)容過濾關(guān)鍵技術(shù)的分析與研究［D］.廣州：暨南大學(xué)，2007：15－24.

［14］袁新成.基于向量空間模型的自適應(yīng)文本過濾研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2006：6－9.

［15］杜娟.基于內(nèi)容的網(wǎng)絡(luò)信息過濾模型的應(yīng)用研究［D］.大慶：大慶石油學(xué)院，2009：8－11.

［16］古麗拜天·卡米爾.基于Web數(shù)據(jù)挖掘的智能推薦研究［D］.長沙：中南大學(xué)，2010：16－20.

［17］Fu He-gang.Improvement of Item-Based CF Algorithm［J］.Journal of Chongqing University of Techonology，2011（9）：69－74.

［18］Shi Hua.Item-Basedand User-Baseddoubleclustering Collaborative Filtering Recommendation Algorithm ［D］.Changchun：Dongbei Normal Univesity，2009：20.

［19］Wu Yue-ping，Zheng Jian-guo.Improvedcollaborative filtering recommendation algorithm［J］.Computer EngineeringandDesign，2011（9）：3019－3021.

［收稿日期］2014－09－12 ［責(zé)任編輯］邵晉蓉

［作者簡介］孫彥超（1978－），男，河南南陽人，信息系統(tǒng)項(xiàng)目管理師，研究生學(xué)歷，主要研究數(shù)據(jù)庫與信息系統(tǒng)、數(shù)據(jù)挖掘等。

［基金項(xiàng)目］本文系北京信息科技大學(xué)2015年度教學(xué)改革立項(xiàng)“基于大數(shù)據(jù)的學(xué)籍狀態(tài)檢測(cè)與預(yù)警方法研究”（項(xiàng)目編號(hào)：2015JGZD06）資助成果之一。

［文章編號(hào)］1005－8214（2015）05－0076－04

［文獻(xiàn)標(biāo)志碼］A

［中圖分類號(hào)］G252.1