模糊聚類的混合推薦算法研究

1、分類號tp312密級udc 碩士學位論文模糊聚類的混合推薦算法研究張愷學科專業(yè)_計算機軟件與理論指導教師秦亮曦教授 一論文答辯日期2010年05月29日 學位授予日期 答辯委員會主席顧平教授-論文評閱人李肯立教授覃海且_教授廣西大學學位論文原創(chuàng)性聲明和學位論文使用授權說明學位論文原創(chuàng)性聲明本人聲明：所呈交的學位論文是在導師指導下完成的，研究工作所取得的成果和相 關知識產權屬廣西大學所有。除已注明部分外，論文中不包含其他人已經發(fā)表過的研究 成果，也不包含本人為獲得其它學位而使用過的內容。對本文的研究工作提供過重要幫 助的個人和集體，均已在論文中明確說明并致謝。論文作者簽名：敎彳妝嚴卜年/月&qu

2、ot;日學位論文使用授權說明本人完全了解廣西大學關于收集、保存.使用學位論文的規(guī)定，即：本人保證不以其它單位為第一署名單位發(fā)表或使用本論文的研究內容；按照學校要求提交學位論文的印刷本和電子版本；學校有權保存學位論文的印刷本和電子版，并提供目錄檢索與閱覽服務； 學校可以采用彩印、縮印、數字化或其它復制手段保存論文； 學?？梢怨颊撐牡牟糠只蛉績热?。請選擇發(fā)布時間：區(qū)卩時發(fā)布解密后發(fā)布（保密論文需注明，并在解密后遵守此規(guī)定）模糊聚類的混合推薦算法研究在20世紀90年代提出推薦系統的概念之后，經過十多年的發(fā)展，推 薦系統已經被應用到了許多大型電子商務系統中。在對推薦系統的研究中, 如何對現有系統中

3、的推薦算法進行改進，以及提出新的推薦算法是其中的 研究熱點，其中混合策略的推薦算法是研究的主要內容，而如何避免推薦 系統中過擬合問題帶來的興趣缺失和系統的冷啟動帶來的評價障礙更是算 法設計與研究的難點。本文完成的主要工作如下:(1) 在對現存的推薦算法進行分析的基礎上，指出了這些算法的優(yōu)點和局限性。認為釆用混合策略推薦策略是解決現存推薦系統中缺陷的較好途徑, 因此設計了一個基于協同過濾和項目聚類的混合策略推薦算法(hybrid recommendation algorithm based on collaborative filtering and item clustering, hrci)

4、o該算法經過項目聚類降低用戶向量的維度，簡化用戶相似度計算。在對項目進行評價估計時，結合了 user-based和itembased協同過濾算法結果作為推薦結果。實驗結果表明，該算法在推薦性能上有很好的改善, 但是在評分估計方面還存在進一步改進的空間。(2) 將隸屬度函數應用到數據聚類中，提出了一種用戶聚類效果的度量方 法。并且在迭代思想和fcm算法(fuzzy cmeans)基礎上，設計了基于層 次的隸屬度矩陣迭代的imc聚類算法(iteration membership degree matrix clustering) o實驗證明，該算法便于確定最佳的用戶簇的數目，并且對簇的 邊界的劃分

5、更為恰當。(3) 將imc聚類算法的思想融合到hrci推薦算法中，提出了一種新的模糊聚類的混合推薦算法(hybrid recommendation based on fuzzy cluster,hrfc)o并提出了一種初始隸屬度矩陣的構造方法，以及基于模糊聚類的項目評分估計方法。實驗結果表明，hrfc算法比原有算法提高了項目評分 估計的準確度，從而使得算法的推薦性能進一步提高，并且在不同稀疏程 度的情況下算法性能穩(wěn)定，具有較高的實際應用價值。關鍵詞：推薦系統相似度混合策略模糊聚類research of hybrid recommendationalgorithm based on fuzzy

6、clusteringabstractafter the concept of recommender system proposed in 1990s, with decade of development, recommender system has been applied to large electronic commerce system. among the research of recommender system, how to improve the existing recommendation algorithms and proposing new recommen

7、dation algorithms have been hotspots. however, the research of hybrid recommendation algorithms is an major part. what's more, to avoid lost interests resulting from users overspecialization of recommender system and difficulties arisen from cold-start are the most difficult task in the design a

8、nd research recommendation algorithmsthe main research work of this paper are listed as follows:(1) on the basis of analysis of existing recommendation algorithms, it indicated the advantages and defects, and suggested that it is the better way to adopt hybrid recommendation algorithms to overcome t

9、he problems existing in the recommender systems. therefore, a hybrid recommendation based on collaborative filtering and item clustering(hrci) has been designed accordingly. it reduced the dimensions of user vector and simplified the calculation of similarity between users by item clustering. in eva

10、luation estimate of items, it combined result of the user-based and item-based collaborative filtering as the recommending result. as is shown in the experimental result, this algorithm improved the performances of recommendations in a good way, but more work should be done on the evaluation estimat

11、e of items(2) it applies grade of membership function into clustering, introduces ainsuitable method on measuring the effect of the clustering based on the iteration idea and fcm algorithm, an imc clustering algorithm based on hierarchical cluster and grade of membership matrix iteration has been de

12、signed. proved by experiment, this algorithm is convenient on confirming the numbers of the best user cluster, besides, it is more appropriate on the partitioning of the boundary of the clusters (3) merging imc clustering algorithm with hrci recommendation algorithms, it introduces a new algorithm o

13、f hrfc(hybrid recommendation based on fuzzy cluster) a constructional method of initializing grade of membership matrix is also introduced, as well as the item evaluation method based on fuzzy cluster. as is shown in the experimental result, hrfc improved the precision of evaluation estimate of item

14、s, therefore, it makes the recommendation performances upgraded, and the algorithm is stable in situations of different sparse levels, and with higher values of practical use.key words: recommender system; similarity; hybrid strategy; fuzzy cluster摘要iabstractill第一章緒論11.1研究背景11.2研究現狀及存在的問題21.3研究內容 31

15、.4論文結構4第二章數據挖掘與個性化推薦算法62.1推薦問題的提出和基本概念62.2基于關聯規(guī)則的推薦算法82.3基于內容的推薦算法92.4協同過濾算法102.4.1基于用戶的協同過濾102.4.2基于項的協同過濾112.5常見推薦算法的比較112.5.1基于內容的推薦算法的優(yōu)劣112.5.2協同過濾算法的優(yōu)劣122.6推薦系統的工作流程132.7本章小結14第三章混合策略的推薦算法163.1概述163.2算法的設計思路173.2.1目前采用的方法173.2.2算法的提出173.3 hrci算法的具體實現183.3.1項目聚類183.3.2相似度計算213.3.3做出推薦223.3.4兩種推薦

16、的實驗比較253.4實驗比較263.5本章小結31第四章隸屬度矩陣迭代的模糊聚類算法324.1模糊聚類的基本思想324.2基礎知識32421關系32422模糊數學中的關系33423模糊關系33424模糊矩陣344.2.5模糊等價關系3443模糊聚類的一般過程344.3.1數據標準化344.3.2找出模糊關系344.3.3模糊聚類354.4模糊c均值(fcm)算法364.5迭代隸屬度矩陣的模糊聚類算法374.5.1判斷標準374.5.2算法流程384.6實驗與比較384.7本章小結40第五章模糊聚類的混合策略推薦算法415.1算法的改進415.1.1隸屬度矩陣的建立415.1.2基于項的模糊聚類

17、425.1.3基于隸屬度矩陣的評分估計435.2 一種新的模糊聚類混合策略推薦算法445.3對比實驗465.3.1實驗準備465.3.2實驗結果與分析475.4稀疏性處理實驗與結果分析485.4.1數據準備485.4.2實驗結果與分析485.5本章小結50第六章結束語516.1全文總結516.2工作展望51參考文獻 53致 謝57攻讀碩士學位期間發(fā)表的學術論文目錄58第一章緒論1.1研究背景推薦系統的概念產生于上世紀末，是隨著信息科技和互聯網的迅速發(fā)展帶來的信息 過載產生的。搜索引擎技術的出現在一定程度上緩解了信息過載帶來的問題，但是還有 許多不足之處。一方面用戶需要提出信息主題，限定了潛在興

18、趣的發(fā)掘；另一方面系統 缺乏個性化的主動推薦。推薦系統是在認知科學、近似理論、信息檢索和預測學的理論 基礎上產生的。它最初應用于電子商務領域，人們所認同的推薦系統是以電子商務網站 為依托，通過提供商品的屬性和評價，對用戶的購買行為起到積極的建議作用。推薦 系統的工作原理，是通過分析用戶的行為表現出來的個性化特征，結合特定的推薦算法, 分析系統本身采集到的數據庫信息，得岀推薦項返回給用戶。協同過濾算法是量早應用于實際的推薦算法，通過計算用戶之間興趣愛好的相似 度，估計出未知評分，從而做出推薦。tapestry系統是最早的協同過濾算法的實現。 b. sarwar等提出一種基于項的協同過濾算法【叫是

19、對傳統協同過濾算法的一種改進?；趦热莸耐扑]則是一種自動提取項目屬性并根據相似度進行推薦的算法，主要適用于文 本屬性的項目對象。此外，機器學習和數據挖掘技術的發(fā)展，推薦算法有了更多的選擇。通過分析行為項之間的關聯關系，可以為用戶提供更多有用的推薦。對用戶建模的研究, 可以收集到更多有用的用戶信息，建立更精確的用戶模型。合理的用戶模型還可以 發(fā)現更多潛在的用戶興趣【2習。目前數據存儲的最大載體是web,結合web數據挖掘, 獲取用戶的訪問記錄和關聯關系，是構造用戶模型的重要途徑均。圖論、貝葉斯網 絡、分類、聚類分析和人工神經網絡【9】，也從不同角度提高了推薦效率。文獻10提出了一種基于項目評分預

20、測的協同過濾算法，改進了傳統的協同過濾算 法，是對推薦系統中存在的稀疏矩陣問題的一種很好的解決方案，即通過釆用計算項目 之間的相似度，并引入修正余弦度量和稀疏等級的概念，從而用固定值或者平均值來填 充目標用戶的評分，在一定程度上彌補了評分矩陣的缺失。pazzani等人山則從另一個 角度來解決稀疏矩陣的問題，利用統計學領域知識，獲取了更多的用戶個人信息，作為 用戶相似度的計算標準。利用神經網絡的方法來計算缺失的稀疏矩陣，在填充效果上 要更加精確一些，有一定的噪聲處理能力，但同時，時間效率上比前兩種方法要差一些。目前，推薦系統主要應用于各個電子商務領域，為用戶提供個性化服務，有利于提 高用戶的滿意

21、度和防止客戶流失。在電子商務領域，amazon和ebay主要釆用了協同過 濾的推薦算法；網頁推薦領域，主要有斯坦福大學的fab和采用實體知識庫的foxtrot 論文主題推薦系統；在電影推薦領域，netfilx和明尼蘇達大學的movielens公開自己的 實驗數據集，已經成為推薦系統領域常用的實驗測試數據；在新聞過濾方面，有 grouplens, phoaks等。在學術研究領域，推薦系統作為一個交叉學科也受到各類相 關會議越來越多的重視，數學、統計學、計算機科學和管理學的國際會議上，相關論文 的發(fā)表也越來越多。acm于2007年開始舉辦第一屆推薦系統年會,另外在ieee和acm 在機器學習和人工

22、智能領域的會議，推薦系統的研究文章占據了一定的比重。mit、明 尼蘇達大學.卡內基梅隆大學都有專門的推薦系統研究小組。google等搜索引擎公 司已將個性化推薦作為研發(fā)下一代搜索引擎的主要工作。因此，個性化推薦技術具有很 廣闊的應用前景。1.2研究現狀及存在的問題推薦系統的問題研究，主要包括以下方面：用戶建模，推薦算法的選擇，信息的反 饋。早期的用戶建模只獲取用戶少量的固定信息。隨著數據挖掘技術的完善，這樣的用 戶建模已經不能滿足系統的需要，考慮到用戶的興趣廣泛和興趣轉移等問題，對于用戶 信息，一般采用交互式采集方式，采集的客戶信息如果過多，就推薦效果而言是最好的, 但是可能會降低客戶滿意度，

23、同時還存在推薦系統可信度的問題，用戶因為擔心系統的 安全性而不敢把真實的數據提供給系統；而釆集的信息過少，在建立用戶模型的時候會 出現信息缺乏，導致建模不準確?？傊?，用戶建模的優(yōu)劣，很大程度上決定了推薦系統 性能和準確率。對于推薦算法，常用的算法有協同過濾、基于內容和基于網格的推薦算法。也可分 為基于個人歷史、基于社會活動和基于產品的推薦。無論哪種推薦算法，均是由用戶的 興趣出發(fā)，經過不同的算法策略，最終對用戶未來的興趣做出預測。協同過濾算法是最早提出的推薦算法。主要分為基于用戶的協同過濾、基于項的 協同過濾和基于模型的協同過濾算法。它的思想就是收集相關項（用戶）信息，然后搜 索最近鄰居，根據

24、鄰居的相關性做出推薦?；谶^去具有相同偏好的用戶（項）會具有 相似關聯的假設，將已知用戶的興趣推薦給未知用戶?；趦热莸耐扑]算法，是傳統信息檢索技術的一種演化算法。通過尋找某一用戶 偏好的項，從而尋找跟這一項相關度最高的項作為推薦項。這一推薦算法主要應用于推 薦項包含很多文本信息的應用當中，由于可以從文本中提取特征，并且對用戶的描述過 程中也包含了對用戶興趣和偏好的描述，因此可以在用戶建模的過程中通過收集用戶信 息，用來詳細的估計出用戶的興趣?；趦热莸耐扑]算法經常用于新聞、網頁和文檔的 推薦。兩種常用的推薦算法都涉及到一個相似度度量的問題，無論是用戶之間的相似度， 還是項之間的相似度，對于推

25、薦系統都是至關重要的。對于用戶之間的相似度，可以通 過用戶個人信息或者用戶對項的評分來計算，主要計量方式都是釆用向量余弦距離及其 變式、pearson相關系數等。在基于用戶的協同過濾算法中，隨著系統用戶的增多，在海量用戶中搜索最近鄰居 項成為制約系統的瓶頸。在這方面，基于項的協同過濾則是利用項之間的相似關系，降 低了計算量，很好的提高了系統的可擴展性和穩(wěn)定性。協同過濾算法的系統冷啟動【卿， 即對新加入用戶和項很難做出推薦，特別是在新用戶加入，釆集信息過少時尤其如此。 而新的項加入數據庫之后，則需要更長的時間才能獲得用戶評分，這種情況則需要考慮 應用組合推薦策略。隨著系統數據庫規(guī)模的增長，效率會

26、急劇衰減。通過維度簡化和矩 陣分解技術，可提高協同過濾算法的精確度和推薦速度劉。稀疏矩陣問題，在推薦系統 數據庫當中不可避免存在大量未被用戶評分的項，這種情況應當超過整個評價矩陣一半 以上的空間，這是因為用戶之間興趣的差異性造成的，稀疏矩陣的解決也是推薦系統研 究中的熱點問題。此外，推薦的精確度和多樣性之間的平衡問題【，也是目前推薦系統的熱點問題。 在文獻20中，作者提岀使用一種對分網絡的數學模型對用戶興趣進行預測，該算法基 于協同過濾的原理，通過對復雜網絡的研究，利用網絡動力學原理對用戶的共同興趣進 行劃分【別，得到了比協同過濾算法更高的精確度。開源項目中也有許多關于推薦系統的資源：tast

27、e是一個基于java ee平臺的開源 的推薦引擎，定義了完整的推薦模型包和實現了常見的推薦算法，已經成為一個推薦器 的集合，并加入了 apache mahout開源項目。duine是一個推薦框架，改進了用戶模型, 反饋和解釋模塊利模塊間的交互。grouplens是明尼蘇達大學計算機科學工程學院的研 究小組，該小組采集了多種應用領域的不同規(guī)模的數據，是目前推薦實驗的常用數據集。13研究內容推薦系統是一門新型課題。經過十多年的研究，雖然取得了一些進展，但仍然存在 很多有待解決的問題。本文首先在總結傳統推薦算法和前人研究成果的基礎上，設計出 一種基于項目聚類的混合策略的推薦算法，提高了推薦精度，在一

28、定程度上解決了系數 矩陣問題。此外為了提高評價估計的精度和準確度，本文提出了一種聚類效果判別方式, 并采用模糊聚類和構造隸屬度矩陣方法對項目聚類，達到更好的聚類效果，提高評分估 計精度。通過對比實驗，本文提出的基于模糊聚類的混合推薦算法提高了推薦精度和評 價估計。通過對五組不同稀疏程度的數據集進行實驗表明，這種推薦效率和評價估計的 提髙是穩(wěn)定的。1.4論文結構本文的主要研究內容是希望提出一種混合策略的推薦算法，該算法能在整體上提高 推薦的準確度，同時很好的處理原始數據中的離群點?；谝陨夏康?，在以往研究的基 礎上，本文針對提高推薦系統的精度，以及推薦精確度和多樣性之間的平衡，提出了一 種基于模

29、糊聚類的混合推薦算法。本文各個章節(jié)的組織結構如下：第一章緒論，介紹了推薦系統的產生和及相關研究背景，簡要概述了推薦系統的不 同推薦方法、研究現狀和存在的問題第二章將介紹傳統的個性化推薦算法，以及加入數據挖掘領域知識的新的推薦算 法，通過對算法性能的分析，比較這些傳統算法的優(yōu)點和局限。第三章將介紹提出的一個混合策略的推薦算法hrci (hybrid recommendation algorithm based on collaborative filtering and item clustering)o 該算法結合了項目聚類和 協同過濾算法，即通過項目聚類降低用戶向量的維度，簡化用戶相似度計算

30、。并且利用 同類對象之間的相關度，對目標項的評分進行估計。最后從基于用戶和基于項兩種方式 的結合，得出推薦列表。第四章從fcm模糊聚類算法出發(fā)，將隸屬度函數應用到數據聚類中，提岀了一種 適用于用戶聚類的效果度量方法。介紹了基于迭代思想的fcm算法，基于fcm算法的 迭代思想，設計了基于層次的隸屬度矩陣迭代的imc聚類算法(iteration membership degree matrix clustering)o實驗證明，該算法便于發(fā)現用戶的簇的數目，并且對邊界數據 的處理方式恰當，適合項目聚類的要求，為改進hrci算法提供了條件。第五章將imc聚類算法思想融合到hrci推薦算法中，提出了一

31、種新的hrfc推 薦算法(hybrid recommendation based on fuzzy cluster, hrfc)。并提出 了初始化隸屬 度矩陣的構造方法，證明了模糊聚類算法在評分估計中的作用。經過驗證，新的推薦算 法提高了原算法的評分估計精確，算法性能穩(wěn)定，具有實際使用價值。最后總結了論文的工作，為進一步研究做岀展望。第二章 數據挖掘與個性化推薦算法2.1推薦問題的提出和基本概念推薦系統是融合多個學科知識相結合，用以解決信息過載問題的一種工具。在推薦 過程中，用戶不再需要向系統提交自己的索引關鍵字來查找內容，而是將整個過程轉變 為系統為主導的主動向用戶做出推薦，不需要用戶向系統

32、描述對象的詳細特征。目前推 薦系統已經在實際應用中發(fā)揮著作用，推薦問題的實質就是尋找用戶集中的元素與項集 中的元素興趣度關聯的關系問題。比如，對于一個銷售cd的商店來說，推薦系統就的 用途就是根據銷售的歷史記錄，幫助店主找出目標客戶可能喜歡聽的cd是哪些，以便 向客戶進行推薦。推薦系統按功能劃分可以分為三個模塊：用戶模塊.項目模塊和推薦模塊圖2-1推薦系統的組成模塊fig. 2-1 the construction of recommender system設矩陣u = (uy)m%n是用戶特征矩陣，切是用戶i的第/個特征分量；設矩陣 f 是推薦項目的特征矩陣，是項目的第丿個特征分量；矩陣恥館

33、扁是用 戶的評分矩陣，如圖，其中是第i個用戶對第丿項的打分，q的初始值都為0。利用收 集到的數據，構建評分矩陣r和用戶特征矩陣u,繼而建立用戶模型，并選用適當的推 薦算法，提取用戶模型中隱含的用戶興趣，對目標用戶可能會感興趣的項做出預測。user idlsb»rating1000200501881074322678x5<08052000)11552041t7825c002006107603150700020743226t8x700300009308910761823r =j0000800306718885879440061076031400080020400609140688r

34、00aao5074322678x8d00008丿503807158992600610760317606718885878圖2-2構造用戶評價距陣fig. 2*2 building the evaluation matrix of users推薦算法是推薦系統的核心部分。目前推薦算法仍存在以下幾個關鍵的問題有待解 決：1、數據的獲取。推薦系統的數據，特別是從用戶收集而來的數據，隱含了大量的 用戶信息。獲取用戶數據有兩種手段，即隱式方式和顯式方式。隱式方式是指不需要強 迫用戶通過提交表單或者給項目打分等手段，而是當用戶在系統中隨意瀏覽的過程中， 記錄下用戶的操作序列，對不同的操作賦予不同的權重，比

35、如瀏覽記為1,收藏記為3, 購買記為5,從而從中發(fā)掘用戶興趣；顯式方式是指通過用戶給瀏覽過的數據的打分和 評價，用分值構造評分矩陣，從中得到的用戶興趣數據。兩種方式相比，顯式獲取到的 數據更加精確，但是頻繁的讓用戶做出評價可能會導致用戶失去耐心；而隱式的獲取數 據具備良好的用戶友好性，但是由于用戶的操作過程誤操作率極大，因此數據的精確度 大大降低。2、相似度度量。推薦系統中的每一個用戶和項，都可以表示成空間中的向量，因 而相關用戶和項之間的相似度，是推薦的重要依據。后面介紹的推薦算法大多涉及到大 量的相似度的計算。常用的相似度度量標準有向量余弦、歐幾里德距離、皮爾遜相關系 數和改進的向量余弦。

36、3、用戶的評分估計。評分矩陣r既隱含了大量的用戶興趣信息，又是做出推薦時 的依據，但是這個矩陣在通常情況下是一個稀疏矩陣。由于相對于數據庫中眾多的項目， 每一個用戶能夠做出評價的項目數量是相當有限的，因此造成評價矩陣中絕大多數元素 都保持初始狀態(tài)0,這一現象叫做評價矩陣的稀疏問題。稀疏矩陣是推薦問題不可避免 的問題。對用戶評分進行估計，用估計值填充稀疏矩陣是解決這個問題的方法之一，此 外，評分的估計值也可以為推薦項與用戶的關聯程度提供一個量化標準。4、冷啟動問題。冷啟動問題是針對新加入系統的用戶和項提出的。一個新加入系 統的用戶，由于沒有歷史記錄，推薦無從入手，因此也無法做出有效推薦。對每一個

37、用 戶，系統也都必須要經過一段時間的學習，才能充分了解用戶的興趣；同理，對于新添 加的項也是如此。系統中的新添加項，由于沒有用戶對其評分，因而算法無法將其加入 推薦列表。個性化推薦技術經過十多年的研究，已經取得了許多研究成果，也提出了一些相關 的推薦算法，下面介紹幾種常用的推薦算法。2.2基于關聯規(guī)則的推薦算法關聯規(guī)則反映的是事務之間的聯系。關聯規(guī)則的主要任務就是根據最小支持度找出 頻繁項集，然后根據頻繁項集導出規(guī)則。設片和是項集中的兩項，如果集合億,滿 足最小支持度閾值，那么仁囲就是頻繁項集，s.nsb就是強關聯規(guī)則。根據關聯規(guī) 則的這種特性，我們可以認為，如果珞和具有強關聯關系，對陷感興趣

38、的用戶很可能 對感興趣。對于關聯規(guī)則算法，最核心的問題就是尋找頻繁項集。而在算法實現上，最重要的 問題是減少掃描數據集的次數。因為候選的項集數據很大，重復掃描會造成很大的系統 負載，系統的穩(wěn)定性很難保證。另外，生成的候選項集的數量會更大，加重了存儲負擔。 因此在算法實現上應該盡量避免重復掃描數據集和產生盡可能少的候選項集。apriori 算法是種快速挖掘頻繁項集的算法【，它利用apriori性質對產生的候選項集進行剪 枝，即g是頻繁項集，它的所有非空子集也都是頻繁項集；反之，如果c-是非頻繁項 集，那么它的任意超集g必然不是頻繁項集。因此，包含非頻繁項集ci的超集不需要 再進行掃描和計算，即可

39、認定不是頻繁項集，利用這一性質，減少了存儲候選項集的空 間，但是由于仍需要重復掃描數據集，時間上沒有顯著提高。fp增長算法利用遞歸的 策略，通過構造fp樹的方法來存儲頻繁項集。由于不需要頻繁的掃描數據集，而且不 產生候選項集，fp樹算法【在時間和穩(wěn)定性上都有很好的優(yōu)化，但是由于采用遞歸的 策略，因此當處理數據集很大的時候，fp算法不能很有效的產生規(guī)則。eclat算法 采用的是與前兩種不同的垂直數據格式，并利用apriori算法挖掘事務項集。由此可知，關聯規(guī)則推薦算法不同于傳統的推薦算法，除了評分矩陣r = (q)襯外,它還要記錄用戶每一次與系統交互的操作序列。由于不需要對項目屬性進行具體分 析

40、，不需要相關的領域知識對數據項進行分類，而只是依靠事務數據庫中的關聯關系， 因此關聯規(guī)則很容易發(fā)現用戶的隱藏興趣；但同時，關聯規(guī)則算法在時間和空間上的效 率依賴于候選數據集的數量，在處理大數據集的數據時產生規(guī)則時間長，效率不高。關 聯規(guī)則算法可以在一定程度上解決系統冷啟動問題的制約，但另外對于推薦系統的最大 問題一評價矩陣稀疏性問題，關聯規(guī)則很難處理，個性化程度不強，目前針對關聯規(guī) 則算法的一些改進，在這方面也沒有明顯改善。2.3基于內容的推薦算法基于內容的推薦算法，用戶c對項$的效用函數”（c,$）是依據項之間的關聯來估計 的。當系統向用戶推薦某一項s時，會先在數據庫中查找用戶的評分記錄，找

41、出評分比 較高的幾項之間的共性，作為用戶的偏好，然后找岀與用戶偏好相似度比較高的項作為 推薦。比如前面提到的fab推薦系統，主要功能是向用戶推薦網頁文本，它首先從網絡 上抓取網頁，使用分詞工具處理文本，從每個網頁提取100個關鍵詞來表示網頁。并且 每個關鍵詞依據不同的標準，賦予不同的權重。常見的計算方法有tf-idf （詞頻/逆向文檔詞頻）】，它假設關鍵字的重要性與它 在文件中岀現的次數成正比，與它在所有文檔庫中出現的頻率成反比。這樣的假設是為 了防止因文本的長度不同，因為對于同一個關鍵詞，長文檔比短文檔有更高的出現頻率, 但是它未必是關鍵詞。珥=亠j（公式21）max,人珥就是關鍵詞何在文檔

42、勺中的詞頻，厶是心在文檔心中出現的次數，maxz.是 文檔心中出現次數最多的關鍵詞心出現的次數。（公式2-2）但是考慮到如果有一篇并不相關的文檔，對匕關鍵詞也有很高的詞頻，說明這個關 鍵詞在分類效果上就不是很好。所以要引入idf度量。關鍵詞&的逆向文檔頻率即：idfi =log 一nin是所有文檔的總數，旺是包含關鍵詞&的文檔總數。則該關鍵詞k,的tf-idf權重w?w嚴 tfgxldfj(公式 23)由此，就可以用tf-idf將一個文檔表示為一個k維向量。在此向量空間使用向量 余弦度量或者pearson度量，衡量文檔之間的相似度2.4協同過濾算法協同過濾的基本思想是對一大群人

43、進行分析，找出與目標用戶品味相近的一小群 人，考察他們的興趣差異，構造一個推薦候選集。根據信息過濾的對象不同，協同過濾 算法又分為基于用戶的協同過濾和基于項的協同過濾刖。1992年，david goldberg設計 出的tapestry系統【2】，是第一個基于協同過濾思想的推薦系統。2.4.1基于用戶的協同過濾基于用戶的協同過濾算法就是最初傳統的協同過濾算法，就是計算訓練樣本集中與 目標用戶的相似度s©,找出相似的k個鄰居，估計目標用戶對未評分項的打分，將推 薦項按照估計評分輸出推薦列表?；谟脩舻膮f同過濾算法的描述1312，：collaborative filtering(r, k

44、, 0); /n：目標用戶的鄰居集合l：推薦列表for(all ui,uj eu)sy =sim(ui9uj);endforfor(j=l to k)top®) t n;endforfor(人=1廣1)r廠遼姝t厶；endfor sort(l); end 算法2-1基于用戶的協咼過濾算壓algorithm】 collaborative filtering based on users最終得到目標用戶坷推薦列表l,并根據對目標用戶的有用程度心排序?；谟脩舻膮f同過濾算法是早期提出的推薦算法，因此該算法存在許多問題。前面 所提到的用戶冷啟動問題，在基于用戶的協同過濾算法中體現的尤為明顯。

45、對于一個新 用戶，甚至是那些評分項很少的用戶，即使系統中存在與其興趣相似的用戶，算法也很 難通過s"找到相似鄰居，推薦效果也不理想。2.4.2基于項的協同過濾基于項的協同過濾算法是對傳統協同過濾算法的改進0】。該算法考慮到項目之間 的相關性，即假設能夠引起用戶興趣的項，必然與該用戶做過較高評分的項具有一定的 相關性。因此可以通過尋找目標項的最近鄰居，把相近項的評分的平均值，或者加權平 均值當做目標用戶對該項的評分，將評分最高的幾項推薦給目標用戶。0 0 3、0 0 00 0 98 0 00 2 00 0®以矩陣r為例，通過計算項目之間的相似度，厶與厶具有很高的相似度。如 果

46、旳是目標用戶，系統可以挑選厶作為推薦項?？缹τ业墓烙嬙u分是依據厶、厶的評分 和彼此的相似度計算得到。2.5常見推薦算法的比較2.5.1基于內容的推薦算法的優(yōu)劣基于內容的推薦，對項目變動頻率較低的文本數據集的應用來說，是最恰當的推薦 算法，通過自動特征抽取技術，可以很快的提取出文檔的特征屬性，通過特征向量對文 檔對象進行度量。由于文檔對象的屬性多種多樣，彼此之前的差異性比較大，因此在文 檔對象的推薦中，基于內容推薦算法相對協同過濾算法有著無可比擬的優(yōu)越性。另外， 在項目的冷啟動問題上，基于內容的推薦算法由于使用自動提取特征屬性，因此不會受 到冷啟動的局限，這一點也是協同過濾算法無法做到的。但是，

47、基于內容的推薦算法還有很多局限性。比如在處理多媒體數據，圖像和聲音、 視頻流，自動特征抽取就很難發(fā)揮作用。即使是文檔對象，兩個不同的文檔有可能使用 同樣的一組特征向量表示，但實際上他們是不同的。即使用關鍵字表示文檔，推薦系統 依然很難區(qū)分兩篇長度和關鍵字一樣，但內容千差萬別的文章。此外，數據的過擬合問題。推薦系統只會推薦那些對用戶的效用函數較髙的項。也 就是說，推薦系統對用戶做出的推薦，基本上都是與用戶已經瀏覽或者評分的那些項相 類似的，這樣就帶來一種數據過擬合問題，如果用戶沒有對數據項集中進行廣泛的瀏覽, 那么推薦系統就無法對用戶的所有興趣做出推薦，而總是對用戶最初瀏覽的項進行類似 的重復推

48、薦。這是因為系統的數據不完備性造成的。這一問題不僅僅存在于基于內容的 推薦算法中，但在基于內容的推薦算法中顯得尤為突出。因此在一些情況下，如果推薦 結果中存在與用戶已瀏覽項相似度很高的項，我們就放棄推薦這一項。比如標題不同但 是內容主題相同的文檔。文獻23提出一種方法，將于用戶興趣相似度較高和較低的項 全部過濾掉?？傊?，推薦系統也應該推薦一些用戶不是特別感興趣的可選項。新用戶問題。一個新注冊的用戶，必須對數據項進行一定量的評分，系統才能真正 理解用戶的興趣，給用戶可靠的推薦。一個新用戶，系統無法準確掌握用戶的興趣，無 法做出精確的推薦。2.5.2協同過濾算法的優(yōu)劣協同過濾推薦算法適用于目前大部

49、分的推薦系統，相比基于內容的推薦算法更適用 更優(yōu)越。同時因為使用協同評分的策略，可以對任意項做出推薦，即使是與用戶興趣不 相關的項。也可以處理文檔對象御。但是協同過濾算法也有他的局限。與基于內容的推薦算法一樣，協同過濾也存在新 用戶問題。新用戶的系統冷啟動問題，在協同過濾算法中依然存在。另外，項目的增加 也是協同過濾算法的一大缺憾。由于協同過濾算法完全依靠用戶的偏好作為推薦，因此, 對于新產生的項，只有當一部分用戶對它進行評分，系統才會把它作為推薦。評價矩陣的稀疏性。協同過濾算法的推薦系統，其推薦精度很大程度依賴于用戶對 項的評價數量。但是目前存在的推薦系統，由于項目集規(guī)模龐大，而每一個用戶的

50、興趣又相對集中，因而造成評價數據存在大量空缺值，成為一個稀疏矩陣。對于矩陣的稀疏 程度的度量，提出一個矩陣的稀疏度spa(r)的概念，即空缺項占所有矩陣元素的比例。spa(r) = (公式 2-4)mxn早期提出的基于項的協同過濾算法，就是針對稀疏矩陣問題提出的一種改進。解決 稀疏矩陣的推薦精度問題，還可以通過小規(guī)模樣本進行有效的預測。還可以根據用戶模 型計算用戶間的相似度。當兩個用戶對相同的項評分相似，即在人口統計學上屬于一類, 這時就可以認為兩個用戶是相似的。協同過濾推薦算法中，用戶對項目的評分屬于顯性反饋，這種反饋對用戶來說很不 公平，推薦過程不僅需要用戶提供個人信息，而且需要對許多項目

51、進行評價；而基于內 容的推薦可以省去繁瑣的評分過程，僅僅通過挖掘用戶的瀏覽行為和點擊等操作，就可 以很好的獲得所需要的信息。2.6推薦系統的工作流程推薦系統的工作一般分為如下幾個步驟：數據采集，數據預處理，訓練分類，接收 用戶輸入，推薦策略的選擇，得出推薦推薦結果，可視化展示結果。數據采集數據預處理相似度計算推薦策略推薦結果圖23推薦系統的一般工作流程fig. 2-3 the common flow of work of recommender system數據采集做出推薦的基礎就是要采集與用戶興趣相關的信息，比如用戶的瀏覽記錄、購買記 錄、査看詳情記錄、添加刪除書簽、下載記錄等。用戶的操作包

52、含了用戶的興趣。因此 在一個好的推薦系統中，數據釆集的方式和數量尤為關鍵。獲取用戶信息一般分為顯式 和隱式的過程。顯式過程獲取方式直接，數據精確，但是需要用戶對項和興趣進行評價 和描述，有些涉及用戶個人隱私，所以過多的顯式獲取會降低用戶的滿意度；隱式過去 更簡單更直接，用戶進入系統的一切操作都可以看做是對用戶興趣的描述，都可以拿來 作為推薦依據，但是隱式獲取的數據準確性大大降低。一般采用顯式和隱式結合的方式 來采集數據。數據預處理采集到的原始數據一般需要進行預處理。比如進行數據的標準化，規(guī)范化，離群點 和消除噪聲數據的消除等操作。相似度計算相似度計算是找到最近鄰居的重要依據。目前大部分推薦算法

53、都需要進行相似度計 算，而且相似度計算的準確與否，會影響到推薦的性能。因此相似度是推薦算法的關鍵 步驟。通常相似度計算方法有如下幾種：歐幾里德距離、余弦相似度、改進余弦相似度、 pearson相似系數等。選用何種相似度度量方式，要根據數據的特性選擇。推薦策略推薦策略是指推薦算法的選擇。如同上節(jié)所分析的，推薦算法有其固有的優(yōu)點和不 足，如何設計合適的推薦算法應用到系統當中，應當確定在設計系統模型之前。評判推 薦算法的優(yōu)劣，應當從以下幾個方面考慮：推薦的精確度、多樣性和f-measure221o精 確度(precision)反映了推薦系統的結果對用戶的有用程度，覆蓋率性(coverage)反映的是

54、 推薦的結果對用戶興趣的覆蓋率，f-measure則是信息檢索領域的一種度量方法，結合 了精確度和多樣性二者的度量。設u是用戶興趣的集合，r是系統推薦的集合【2鐵咖 percision =1（公式2-5）r0ucqn erage（公式2-6）_2x percision x coveragef 一 measure =percision + cov erage（公式2-7）推薦結果推薦系統的結果呈現，應當用一些可視化和知識表示的技術，對推薦結果進行可視 化的表示，在不同維度上向用戶形象的展現推薦結果。2.7本章小結本章詳細分析了常見的推薦算法和推薦模型理論，闡述了傳統推薦算法存在的問 題，通過算法

55、的比較，分別指出傳統推薦算法用于推薦技術時的優(yōu)點和局限性，并簡要介紹了目前彌補這些弊端所采取的措施，為后面章節(jié)推薦算法的改進指出了目標。最后 介紹了推薦系統模型的工作流程，以及判斷系統優(yōu)劣性的常用評判標準。第三章 混合策略的推薦算法通過以上對傳統推薦算法的介紹可以看出，盡管推薦策略各有不同，但是大多算法 都涉及到相似度計算。因此，相似度的度量是推薦算法的重要步驟。另外，在實際應用 中，也應根據實際情況選擇合適的推薦算法。常見的推薦算法各有各的缺陷，單純使用 一種推薦算法已無法滿足實際需要珂。為了彌補傳統算法的缺陷，常用的方法是釆用混 合策略的推薦算法，即采用多種推薦算法相結合。因此本章擬采用協

56、同過濾與數據挖掘 算法的結合，設計一個混合策略的推薦算法。3.1概述混合推薦算法有多種實現途徑。通常主要有以下幾種方法：1、分別實現協同過濾和基于內容，然后將兩種結果合并起來【創(chuàng)。一個推薦系統可以包含多個獨立的子系統，各個子系統分別作出評價，然后匯總起 來，在主推薦系統中，按照一定的規(guī)則或者權重集成評價數據。比如dailyleamer推薦 系統，是一種類似元推薦引擎。它同時連接多個推薦系統，并統計各個推薦系統的結果和數據統計。對用戶做推薦時，會給置信度較高的子系統和其他子系統返回的評價結果 分別賦予不同的權重，將匯總之后的推薦結果返回給用戶。這樣的結合，推薦結果是兩 種算法返回結果的簡單的匯總，但是算法的應用范圍擴大了很多。2、在協同過濾算法中加入一些基于內容的特點。斯坦福大學的fab推薦系統】，嚴格來說是一個基于內容的協同過濾推薦系統。與 傳統的協同過濾算法的相比，加入基于內容的特點之后不僅對項做出打分，而且還計算 用戶之間的相似度。推薦的結果既保留了評價矩陣中與用戶興趣相符的髙分項，而且還 加入了與用戶興趣不相符的高分項，這樣有助于幫助用戶找到潛在興趣。和傳統的協同 過濾算法相比，這樣既保留了協同過濾的優(yōu)越性，又在一定程度上克服了評價稀疏性的 問題。3