基于聚類分析算法的圖書推薦系統的研究

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

基于聚類分析算法的圖書推薦系統的研究

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

［關鍵詞］協同過濾；聚類；最近鄰居；推薦系統；評價矩陣

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

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

1　傳統協同過濾算法

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

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

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

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

圖1　用戶評分矩陣

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

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

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

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

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

2　改進后協同過濾算法

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

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

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

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

圖3　讀者特征矩陣

圖2　改進后算法流程

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

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

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

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

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

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

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

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

推薦結果。［14］

3　改進后算法分析與實驗

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

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

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

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

s

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

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

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

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

表　改進前后算法對新讀者預測結果比較

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

4　結論

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

［參考文獻］

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

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

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

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

［5］任磊.推薦系統關鍵技術研究［D］.上海：華東師范大學，2012：10－17.

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

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

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

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

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

［11］王棟針.對網絡熱點事件觀點漂移檢測技術的研究與實現［D］.沈陽：東北大學, 2012：6－10.

［12］呂振山.基于RBF神經網絡的文本過濾技術研究［D］.廣州：暨南大學, 2008：23－30.

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

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

［15］杜娟.基于內容的網絡信息過濾模型的應用研究［D］.大慶：大慶石油學院，2009：8－11.

［16］古麗拜天·卡米爾.基于Web數據挖掘的智能推薦研究［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－），男，河南南陽人，信息系統項目管理師，研究生學歷，主要研究數據庫與信息系統、數據挖掘等。

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

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

［文獻標志碼］A

［中圖分類號］G252.1