同好推薦算法的實(shí)踐

林雪云

福建師范大學(xué)福清分校,福建 福清 350300

當(dāng)前，書目推薦已經(jīng)成為圖書館書目檢索系統(tǒng)中必不可少的欄目.甚至不止是圖書館，網(wǎng)絡(luò)上各種各樣的讀書網(wǎng)址中都會有著書目推薦的專欄，書目推薦專欄已成為各網(wǎng)站爭奪讀者和點(diǎn)擊率的關(guān)鍵所在.因?yàn)榇蟊姛o論是否承認(rèn)都有著一定的從眾心理，這也是同好推薦備受歡迎的原因之一.

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

通過對手機(jī)社區(qū)用戶圖書下載行為進(jìn)行分析，然后產(chǎn)生相應(yīng)的圖書推薦，從而讓用戶方便的找到自己喜歡看的書.

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

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

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

2 數(shù)據(jù)庫查詢計(jì)算的傳統(tǒng)算法

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

產(chǎn)生用戶的同好推薦： 獲取這個用戶看過哪些書； 獲取看過這些書的所有用戶；獲取這些用戶都還看過哪些書；計(jì)算每本書對應(yīng)的用戶數(shù)；按每本書對應(yīng)的用戶數(shù)倒序輸出.

2.1 傳統(tǒng)算法問題分析

傳統(tǒng)算法優(yōu)點(diǎn)：算法容易理解；在支持子查詢的數(shù)據(jù)庫容易實(shí)現(xiàn).

傳統(tǒng)算法缺點(diǎn)：只能在支持子查詢的數(shù)據(jù)庫實(shí)現(xiàn)，如mssql可以，mysql就不行；每計(jì)算一次書的推薦(或用戶的推薦)，都涉及嵌套查詢，而統(tǒng)計(jì)數(shù)據(jù)通常都是很大(這樣才準(zhǔn)確)，導(dǎo)致了計(jì)算速度很慢；每次查詢結(jié)果不能復(fù)用.

2.2 基于矩陣模型的創(chuàng)新算法

伴隨著大數(shù)據(jù)時代的到來[4]，傳統(tǒng)的查詢算法已經(jīng)遠(yuǎn)遠(yuǎn)無法滿足當(dāng)今世界的需求，傳統(tǒng)的查詢算法中往往伴隨著子查詢等等，在數(shù)據(jù)量較大的數(shù)據(jù)庫中往往造成運(yùn)行速度緩慢等嚴(yán)重問題，改變以往的子查詢算法就成為重中之重.

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

針對編號為101的圖書進(jìn)行矩陣統(tǒng)計(jì)，矩陣圖的橫向和縱向都是書籍編號，按從小到大排列.橫向和縱向的交叉點(diǎn)就是表示下載橫向編號的書同時下載了縱向編號的書的用戶數(shù)，即兩書之間的同好度.因?yàn)橥枚仁窍嗷サ模灾挥昧司仃嚨纳先莵泶鎯?某本書的同好推薦只需要將這些數(shù)值倒序排列就可以了.

2.2.2 程序?qū)崿F(xiàn) 1)這邊考慮用一個字典表來保存兩書之間的同好度，字典的鍵值是【兩書籍中的小編號+“$”+兩書籍中的大編號】,鍵值就是兩書之間的同好度，如果用二維數(shù)組來表示矩陣有兩個缺點(diǎn)：其一浪費(fèi)存儲空間，因?yàn)樯厦嬲f明過矩陣的下半部分是沒有數(shù)據(jù)的，其二不方便查找數(shù)據(jù)，要建立書籍ID和矩陣索引之間的關(guān)系才能定位相應(yīng)的數(shù)據(jù).

2)要產(chǎn)生一個書籍的推薦可以開始一個循環(huán)，開始值為所有書籍的最小編號，結(jié)束值為最大編號.

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

4)記錄相關(guān)度.

5)倒序輸出相關(guān)度，從而產(chǎn)生推薦.

2.2.3 算法優(yōu)點(diǎn) 相比在數(shù)據(jù)庫中計(jì)算，可以清楚的看到，只要計(jì)算一次兩書之間的相關(guān)度就可以在后面的計(jì)算重復(fù)使用，可以大大提高計(jì)算速度.通過按圖書編號從小到大來計(jì)算每本圖書和其他圖書之間的同好度，實(shí)驗(yàn)就可以只計(jì)算編號比當(dāng)前編號大的圖書的同好度，提高計(jì)算速度.

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

(1)假設(shè)實(shí)驗(yàn)要產(chǎn)生20本書作為某個用戶的推薦.

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

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

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

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

3 實(shí)驗(yàn)評價

3.1 評價標(biāo)準(zhǔn)

評價標(biāo)準(zhǔn)1：數(shù)據(jù)量時間(平均一條數(shù)據(jù)所花費(fèi)的時間)比：

(1)

式(1)中n為數(shù)據(jù)量.

P1越大表明傳統(tǒng)算法相對于創(chuàng)新算法而言耗時更多.

評價標(biāo)準(zhǔn)2：耗時穩(wěn)定性比：

(2)

P2越大表明傳統(tǒng)算法相對于創(chuàng)新算法而言更加不穩(wěn)定[9].

其中tij中j=1對應(yīng)傳統(tǒng)算法，j=2對應(yīng)創(chuàng)新算法，i=1...12對應(yīng)月份分為1...12.

3.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用手機(jī)社區(qū)用戶近一年的下載數(shù)據(jù)，經(jīng)過數(shù)據(jù)清洗、轉(zhuǎn)換后，有效數(shù)據(jù)集1.2億行.實(shí)驗(yàn)機(jī)器：操作系統(tǒng)Win 7，處理器為英特爾酷睿i5-2500，主頻是3.3GHZ，內(nèi)存為8Gb.

3.3 實(shí)驗(yàn)過程

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

表1 實(shí)驗(yàn)數(shù)據(jù)Tabel 1 Experimental data

改進(jìn)算法的離線計(jì)算，計(jì)算的結(jié)果在后續(xù)的推薦中可以重復(fù)利用.

隨機(jī)抽取150個用戶，計(jì)算推薦的平均時間，具體如圖1所示，新舊算法耗時表如表2所示，新舊算法P1指標(biāo)如表3所示，月數(shù)與P1的關(guān)系如圖2所示.

圖1 新舊算法實(shí)驗(yàn)分析Fig.1 Experimental analysis of the new and old algorithm注：t1 t2

表2 傳統(tǒng)算法和創(chuàng)新算法耗時Tabel 2 Time-consuming of traditional algorithms and innovative algorithms

表3 傳統(tǒng)算法和創(chuàng)新算法P1指標(biāo)Tabel 3 P1indicators of traditional algorithms and innovative algorithms

圖2 月數(shù)與P1的關(guān)系Fig.2 Relationship of months and P1注：P1

由表3可知，當(dāng)數(shù)據(jù)量增大時，傳統(tǒng)算法的耗時相對于創(chuàng)新算法是線性增長，隨著數(shù)據(jù)量的繼續(xù)增加，傳統(tǒng)算法的耗時將遠(yuǎn)大于創(chuàng)新算法.

由公式(2)可得傳統(tǒng)算法與創(chuàng)新算法穩(wěn)定性對比表，即表4所示.

表4 傳統(tǒng)算法和創(chuàng)新算法穩(wěn)定性對比Tabel 4 Stability compared to traditional algorithms and innovative algorithms

創(chuàng)新算法的耗時平均值僅為傳統(tǒng)算法的1/20，說明創(chuàng)新算法的耗時遠(yuǎn)小于傳統(tǒng)算法.同時，創(chuàng)新算法的方差為傳統(tǒng)算法的1/32135，說明創(chuàng)新算法的穩(wěn)定性遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)算法.即創(chuàng)新算法相對于傳統(tǒng)算法而言更能長久保持低耗時.

3.4 實(shí)驗(yàn)結(jié)果

從上述實(shí)驗(yàn)結(jié)果可以看出：

①基于矩陣的創(chuàng)新算法效率明顯比傳統(tǒng)算法高.

②隨著數(shù)據(jù)量的不斷增大，傳統(tǒng)算法線性下降，而基于矩陣的創(chuàng)新算法，由于可以重復(fù)利用計(jì)算結(jié)果，效率基本一致.

③隨著數(shù)據(jù)量的不斷增大，創(chuàng)新算法的穩(wěn)定性遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)算法.

4 結(jié) 語

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

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

致 謝

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

[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] 李濤.數(shù)據(jù)挖掘的應(yīng)用與實(shí)踐:大數(shù)據(jù)時代的案例分析[M].廈門：廈門大學(xué)出版社，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] 王楊. 基于屬性關(guān)聯(lián)度的啟發(fā)式約簡算法 [J].計(jì)算機(jī)與數(shù)字工程, 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ì)算機(jī)應(yīng)用新領(lǐng)域-數(shù)據(jù)挖掘前景及應(yīng)用探究[J].計(jì)算機(jī)光盤軟件與應(yīng)用, 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] 吳昉,宋培義.數(shù)據(jù)挖掘的應(yīng)用[J].貴州科學(xué),2012,30(3):54-56.

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