林雪云

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

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

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

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

1 同好推薦算法及問(wèn)題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

2)要產(chǎn)生一個(gè)書(shū)籍的推薦可以開(kāi)始一個(gè)循環(huán)，開(kāi)始值為所有書(shū)籍的最小編號(hào)，結(jié)束值為最大編號(hào).

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

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

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

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

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

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

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

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

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

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

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

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

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

(1)

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

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

評(píng)價(jià)標(biāo)準(zhǔn)2：耗時(shí)穩(wěn)定性比：

(2)

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

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

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

實(shí)驗(yàn)使用手機(jī)社區(qū)用戶近一年的下載數(shù)據(jù)，經(jīng)過(guò)數(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)過(guò)程

將實(shí)驗(yàn)數(shù)據(jù)按1～12個(gè)月的順序遞增，依次測(cè)試：1個(gè)月，2個(gè)月，……，12個(gè)月不同數(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個(gè)用戶，計(jì)算推薦的平均時(shí)間，具體如圖1所示，新舊算法耗時(shí)表如表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)新算法耗時(shí)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ù)量增大時(shí)，傳統(tǒng)算法的耗時(shí)相對(duì)于創(chuàng)新算法是線性增長(zhǎng)，隨著數(shù)據(jù)量的繼續(xù)增加，傳統(tǒng)算法的耗時(shí)將遠(yuǎn)大于創(chuàng)新算法.

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

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

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

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é) 語(yǔ)

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

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

致 謝

感謝福建省自然科學(xué)基金委員會(huì)和福建師范大學(xué)福清分?？蒲谢鸬馁Y助！

[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ù)時(shí)代的案例分析[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ā)式約簡(jiǎn)算法 [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ī)光盤(pán)軟件與應(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)