同好推薦算法的實踐

林雪云

福建師范大學福清分校,福建 福清 350300

當前，書目推薦已經成為圖書館書目檢索系統中必不可少的欄目.甚至不止是圖書館，網絡上各種各樣的讀書網址中都會有著書目推薦的專欄，書目推薦專欄已成為各網站爭奪讀者和點擊率的關鍵所在.因為大眾無論是否承認都有著一定的從眾心理，這也是同好推薦備受歡迎的原因之一.

現在國內外大部分公司都有著各自的推薦算法，例如：Amazon、 Netflix、lastfm、Pandora、Google，對于卓越亞馬遜而言，其書目推薦技術使用的是Amazon的同好推薦技術;而Amazon被稱為推薦之王，其銷量的百分之三十依靠的不是別的，就是它所使用的同好推薦技術帶來的，從中可以看出同好推薦算法革新的重要性[1].

通過對手機社區用戶圖書下載行為進行分析，然后產生相應的圖書推薦，從而讓用戶方便的找到自己喜歡看的書.

1 同好推薦算法及問題分析

所謂同好推薦算法就是通過對用戶以往行為的統計分析，利用一些數學算法預測分析出用戶在未來一段時間可能的行為策略[2].當前比較流行的同好推薦算法主要分為兩大方式：啟發式和基于模型的方式.啟發式的方法即對用戶行為先進行主觀預測再通過實際檢驗一步步接近用戶最真實的狀態.

而基于模型的方式則是從以往數據出發，通過對用戶以往的一些行為數據的統計分析，在本文的書目同好推薦中就是對用戶以往閱讀書籍的分析[3]，但書目同好推薦不僅僅局限于對單一用戶或單一書籍的統計分析，而是把過去所有用戶和所有書籍作為統計對象，于是不可避免的龐大數據源就出現了，而且這些數據相互交織，增加了對這些數據分析的難度.怎樣高效穩定的得到所需要的結果就成了重中之重.

2 數據庫查詢計算的傳統算法

產生書的推薦(喜歡這本書的人還喜歡什么書)步驟：1)獲取還有哪些人看過這本書； 2)獲取這些人還看過哪些書；3)計算每本書對應的用戶數；4)按每本書對應的用戶數倒序輸出.

產生用戶的同好推薦： 獲取這個用戶看過哪些書； 獲取看過這些書的所有用戶；獲取這些用戶都還看過哪些書；計算每本書對應的用戶數；按每本書對應的用戶數倒序輸出.

2.1 傳統算法問題分析

傳統算法優點：算法容易理解；在支持子查詢的數據庫容易實現.

傳統算法缺點：只能在支持子查詢的數據庫實現，如mssql可以，mysql就不行；每計算一次書的推薦(或用戶的推薦)，都涉及嵌套查詢，而統計數據通常都是很大(這樣才準確)，導致了計算速度很慢；每次查詢結果不能復用.

2.2 基于矩陣模型的創新算法

伴隨著大數據時代的到來[4]，傳統的查詢算法已經遠遠無法滿足當今世界的需求，傳統的查詢算法中往往伴隨著子查詢等等，在數據量較大的數據庫中往往造成運行速度緩慢等嚴重問題，改變以往的子查詢算法就成為重中之重.

2.2.1 算法描述 例如A、B、C三個用戶下載過編號為101的圖書，同時A用戶又下載過編號為105、109的書，B用戶又下載過編號為103、109的書， C用戶又下載過編號為102、105、106、109的圖書.那么，對A、C兩用戶而言，101和105這兩本書的同好度為2.這里解釋下同好度：兩書之間的同好度就是同時讀過這兩本書的用戶數[5].

針對編號為101的圖書進行矩陣統計，矩陣圖的橫向和縱向都是書籍編號，按從小到大排列.橫向和縱向的交叉點就是表示下載橫向編號的書同時下載了縱向編號的書的用戶數，即兩書之間的同好度.因為同好度是相互的，所以只用了矩陣的上三角來存儲.某本書的同好推薦只需要將這些數值倒序排列就可以了.

2.2.2 程序實現 1)這邊考慮用一個字典表來保存兩書之間的同好度，字典的鍵值是【兩書籍中的小編號+“$”+兩書籍中的大編號】,鍵值就是兩書之間的同好度，如果用二維數組來表示矩陣有兩個缺點：其一浪費存儲空間，因為上面說明過矩陣的下半部分是沒有數據的，其二不方便查找數據，要建立書籍ID和矩陣索引之間的關系才能定位相應的數據.

2)要產生一個書籍的推薦可以開始一個循環，開始值為所有書籍的最小編號，結束值為最大編號.

3)在循環體產生鍵值：【兩書籍中的小編號+“$”+兩書籍中的大編號】.

4)記錄相關度.

5)倒序輸出相關度，從而產生推薦.

2.2.3 算法優點 相比在數據庫中計算，可以清楚的看到，只要計算一次兩書之間的相關度就可以在后面的計算重復使用，可以大大提高計算速度.通過按圖書編號從小到大來計算每本圖書和其他圖書之間的同好度，實驗就可以只計算編號比當前編號大的圖書的同好度，提高計算速度.

2.2.4 算法拓展應用 用戶的同好推薦的實現基于圖書同好推薦，本文上述算法已經可以獲取每本書的相應的同好推薦，可以算出用戶看過的所有書的同好推薦，產生并集，然后按同好度倒序輸出[6].具體做法如下：

(1)假設實驗要產生20本書作為某個用戶的推薦.

(2)假設用戶看過10本書.

(3)程序產生這10本書相應的同好推薦，每本書對應2本(要排除用戶已經看過的書和其他書產生的推薦的書).

(4)對這20本書按同好度倒序輸出.

另外，還可以用于商品(如食品、服裝、電影等)的同好推薦，甚至于計算兩物品之間的關聯度[7]，用于分析事件發生的影響因素分析.例如:a事件的發生可能由于b或者c事件的發生，實驗即可將a,b,c看做3本圖書，把a事件發生且b事件發生記為1，從而得到a,b,c三者之間的同好度(即關聯度)，比較關聯度大小，即可知道a事件的主要影響因素[8].

3 實驗評價

3.1 評價標準

評價標準1：數據量時間(平均一條數據所花費的時間)比：

(1)

式(1)中n為數據量.

P1越大表明傳統算法相對于創新算法而言耗時更多.

評價標準2：耗時穩定性比：

(2)

P2越大表明傳統算法相對于創新算法而言更加不穩定[9].

其中tij中j=1對應傳統算法，j=2對應創新算法，i=1...12對應月份分為1...12.

3.2 實驗環境

實驗使用手機社區用戶近一年的下載數據，經過數據清洗、轉換后，有效數據集1.2億行.實驗機器：操作系統Win 7，處理器為英特爾酷睿i5-2500，主頻是3.3GHZ，內存為8Gb.

3.3 實驗過程

將實驗數據按1～12個月的順序遞增，依次測試：1個月，2個月，……，12個月不同數據量下新舊算法的推薦效率，實驗輸入數據如表1所示.

表1 實驗數據Tabel 1 Experimental data

改進算法的離線計算，計算的結果在后續的推薦中可以重復利用.

隨機抽取150個用戶，計算推薦的平均時間，具體如圖1所示，新舊算法耗時表如表2所示，新舊算法P1指標如表3所示，月數與P1的關系如圖2所示.

圖1 新舊算法實驗分析Fig.1 Experimental analysis of the new and old algorithm注：t1 t2

表2 傳統算法和創新算法耗時Tabel 2 Time-consuming of traditional algorithms and innovative algorithms

表3 傳統算法和創新算法P1指標Tabel 3 P1indicators of traditional algorithms and innovative algorithms

圖2 月數與P1的關系Fig.2 Relationship of months and P1注：P1

由表3可知，當數據量增大時，傳統算法的耗時相對于創新算法是線性增長，隨著數據量的繼續增加，傳統算法的耗時將遠大于創新算法.

由公式(2)可得傳統算法與創新算法穩定性對比表，即表4所示.

表4 傳統算法和創新算法穩定性對比Tabel 4 Stability compared to traditional algorithms and innovative algorithms

創新算法的耗時平均值僅為傳統算法的1/20，說明創新算法的耗時遠小于傳統算法.同時，創新算法的方差為傳統算法的1/32135，說明創新算法的穩定性遠遠優于傳統算法.即創新算法相對于傳統算法而言更能長久保持低耗時.

3.4 實驗結果

從上述實驗結果可以看出：

①基于矩陣的創新算法效率明顯比傳統算法高.

②隨著數據量的不斷增大，傳統算法線性下降，而基于矩陣的創新算法，由于可以重復利用計算結果，效率基本一致.

③隨著數據量的不斷增大，創新算法的穩定性遠遠優于傳統算法.

4 結 語

根據大數據量下同好度推薦存在的問題，針對傳統推薦算法在運算速度及穩定性不足等問題提出了基于矩陣模型的創新算法，該算法改進了傳統數據庫查詢的推薦算法，以提高運行效率.面對的大數據，基于矩陣的創新算法，可以采用離線計算的形式，提前計算物品與物品之間的同好度表.通過實驗表明，改進的算法對比傳統的推薦算法具有明顯的效率優勢，不僅在耗時上，更在于改進算法的穩定性上.

基于矩陣模型的推薦算法不足在于在第一步新建同好度表時的耗時偏大，對這部分內容的改進也是本法未來的改進方向.

致 謝

感謝福建省自然科學基金委員會和福建師范大學福清分校科研基金的資助！

[1] YOU Wen, YE Shui-sheng. A survey of collaborative filtering algorithm applied in E-Commerce recommender system [J]. Computer Technology and Development, 2006, 16(9): 70-72.

[2] HERLOCKER J L,KONSTAN J A, BORCHERS A, et al. An algorithmic framework for performing collaborative filtering [C]//Proc of the 22nd Annual Int. ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 1999:230-237.

[3] MELVILE P, MOONEY R J, NAGARAJAN R. Content-boosted collaborative filtering for lmproved recommendations [C]//Proc of the 18th National Conf on Artificial Intelligence. 2002:187-192.

[4] RESNICK P, IACOVOU N, SUCHAK M, et al. Group lens: An open architecture for collaborative filtering of net news [C]// Proc of the ACM CSCW 94 Conf on Computer-Supported Cooperative Work, New York: ACM, 1994: 175-186.

[5] GHANI R, FANO A. Building Recommender Systems Using a Knowledgebase of Product Semantics [EB/OL]. Http: www.accenture.com/ xdoc/en/services/technology/publications/recommender-ws02.pdf. 2002-10-28/2004-02-16.

[6] 李濤.數據挖掘的應用與實踐:大數據時代的案例分析[M].廈門：廈門大學出版社，2013.

LI Tao . Data mining application and practice: case analysis of the era of big data [M]. Xiamen:Xiamen University Press, 2013.(in Chinese)

[7] 王楊. 基于屬性關聯度的啟發式約簡算法 [J].計算機與數字工程, 2012(4):17-31.

WANG Yang. Heuristic reduction algorithm based on the properties of correlation [J]. Computer &Digital Engineering, 2012(4):17-31.(in Chinese)

[8] 劉臻.計算機應用新領域-數據挖掘前景及應用探究[J].計算機光盤軟件與應用, 2012(17): 134-136.

LIU Zhen. New areas of computer applications - data mining prospects and applications inquiry [J]. Computer CD Software and Application, 2012(17):134-136.(in Chinese)

[9] 吳昉,宋培義.數據挖掘的應用[J].貴州科學,2012,30(3):54-56.

WU Fang, Pei-yi SONG. Data mining applications [J]. Guizhou Science, 2012, 30 (3):54-56.(in Chinese)