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

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

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

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

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

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

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

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

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

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

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

圖1　用戶評分矩陣

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

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

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

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

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

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

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

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

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

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

圖3　讀者特征矩陣

圖2　改進后算法流程

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

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

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

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

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

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

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

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

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

3　改進后算法分析與實驗

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

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

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

圖4　改進前后算法平均絕對誤差比較

s

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

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

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

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

表　改進前后算法對新讀者預(yù)測結(jié)果比較

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

4　結(jié)論

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

［參考文獻］

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

［16］古麗拜天·卡米爾.基于Web數(shù)據(jù)挖掘的智能推薦研究［D］.長沙：中南大學，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 ［責任編輯］邵晉蓉

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

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

［文章編號］1005－8214（2015）05－0076－04

［文獻標志碼］A

［中圖分類號］G252.1