基于Python的協(xié)同過(guò)濾算法的設(shè)計(jì)與實(shí)現(xiàn)

，

(1.濟(jì)南職業(yè)學(xué)院，山東 濟(jì)南 250014；2.山東廣播電視大學(xué)，山東 濟(jì)南 250014)

一、引言

隨著網(wǎng)絡(luò)的飛速發(fā)展，網(wǎng)絡(luò)信息飛速增長(zhǎng)，人們面臨著“信息過(guò)載”和“信息迷航”的問(wèn)題。借助于搜索引擎，人們可以從海量信息中查找到自己所需的信息。但是，搜索引擎只適用于在有明確需求的情況下幫人們查找信息，如果在沒(méi)有明確需求的情況下，搜索引擎則難以幫助人們有效地篩選信息。此時(shí)推薦技術(shù)應(yīng)運(yùn)而生，它通過(guò)研究用戶的興趣偏好，自動(dòng)建立起用戶和信息之間的聯(lián)系，從而幫助用戶從海量信息中去發(fā)掘自己潛在的需求。

推薦系統(tǒng)是建立在海量數(shù)據(jù)挖掘基礎(chǔ)上的，它通過(guò)分析用戶的歷史數(shù)據(jù)來(lái)了解用戶的需求和興趣，從而將用戶感興趣的信息、物品等主動(dòng)推薦給用戶，其本質(zhì)是建立用戶與物品之間的聯(lián)系。常用的推薦算法主要有專家推薦、基于統(tǒng)計(jì)的推薦、基于內(nèi)容的推薦和協(xié)同過(guò)濾推薦等。其中協(xié)同過(guò)濾推薦是推薦系統(tǒng)中應(yīng)用最早和最為成功的算法。

協(xié)同過(guò)濾算法的關(guān)鍵是計(jì)算相似度及求解推薦評(píng)分，在計(jì)算時(shí)需要用到矩陣的一些運(yùn)算。Python的第三方擴(kuò)展庫(kù)Numpy是一科學(xué)計(jì)算庫(kù)，提供了大量的數(shù)組及矩陣運(yùn)算，因此很多推薦系統(tǒng)中都是利用Numpy來(lái)實(shí)現(xiàn)協(xié)同過(guò)濾算法，但因協(xié)同過(guò)濾算法中涉及到的矩陣多是稀疏矩陣，采用普通的二維數(shù)組存放存在大量的無(wú)效存儲(chǔ)，空間利用率較低，同時(shí)利用Numpy擴(kuò)展庫(kù)也無(wú)法進(jìn)行算法的優(yōu)化，因此本文利用Python的內(nèi)置序列字典來(lái)存放稀疏矩陣，自行編制相應(yīng)的代碼來(lái)求解推薦評(píng)分，可有效提高算法的時(shí)間空間效率。

二、協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法分為基于用戶的協(xié)同過(guò)濾算法和基于物品的協(xié)同過(guò)濾算法。

基于用戶的協(xié)同過(guò)濾算法(簡(jiǎn)稱UserCF)，通過(guò)不同用戶對(duì)物品的評(píng)分來(lái)評(píng)測(cè)用戶之間的相似性，基于用戶之間的相似性做出推薦。簡(jiǎn)單說(shuō)就是給用戶推薦和他興趣相似的其他用戶喜歡的物品。

基于物品的協(xié)同過(guò)濾算法(簡(jiǎn)稱ItemCF)，通過(guò)用戶對(duì)不同物品的評(píng)分來(lái)評(píng)測(cè)物品之間的相似性，基于物品之間的相似性做出推薦。簡(jiǎn)單說(shuō)就是給用戶推薦和他之前喜歡的物品相似的物品。

UserCF算法和ItemCF算法最主要的區(qū)別在于：UserCF推薦的是那些和目標(biāo)用戶有共同興趣愛(ài)好的其他用戶所喜歡的物品，ItemCF算法則推薦那些和目標(biāo)用戶之前喜歡的物品類似的其他物品。因此，UserCF算法的推薦更偏向社會(huì)化，適合應(yīng)用于新聞推薦、微博話題推薦等應(yīng)用場(chǎng)景；而ItemCF算法的推薦則是更偏向于個(gè)性化，適合應(yīng)用于電子商務(wù)、電影、圖書(shū)等應(yīng)用場(chǎng)景。

UserCF算法和ItemCF算法思想類似，其實(shí)現(xiàn)過(guò)程也基本類似，唯一不同的是一個(gè)是計(jì)算用戶相似度，一個(gè)是計(jì)算物品相似度，本文以ItemCF算法為例詳細(xì)說(shuō)明其具體實(shí)現(xiàn)。

三、ItemCF的Python實(shí)現(xiàn)

(一)數(shù)據(jù)準(zhǔn)備

以一組用戶的觀影記錄作為測(cè)試數(shù)據(jù)集，共包括兩個(gè)數(shù)據(jù)文件，一個(gè)是rating.txt，存放的是用戶對(duì)電影的評(píng)分記錄，其數(shù)據(jù)如圖1所示，每一行用逗號(hào)分隔的3個(gè)數(shù)據(jù)項(xiàng)分別表示用戶ID、電影ID和評(píng)分。

圖1 評(píng)分?jǐn)?shù)據(jù)

另一個(gè)數(shù)據(jù)文件是movies.txt，存放的是電影信息，其數(shù)據(jù)如圖2所示，每一行用逗號(hào)分隔的3個(gè)數(shù)據(jù)項(xiàng)分別表示電影ID、電影名稱和上映時(shí)間，該數(shù)據(jù)文件主要用于推薦結(jié)果輸出。

圖2 電影信息數(shù)據(jù)

(二)具體實(shí)現(xiàn)過(guò)程

1.數(shù)據(jù)預(yù)處理

將數(shù)據(jù)集中的文件讀入并進(jìn)行一定的處理，將用戶評(píng)分記錄及電影信息分別存入相應(yīng)的字典中。其Python代碼如圖3所示。

圖3 數(shù)據(jù)預(yù)處理代碼

2.建立同現(xiàn)矩陣

ItemCF算法的關(guān)鍵是計(jì)算物品(此處為電影)的相似度，相似度的計(jì)算方法有很多，在此直接以同時(shí)出現(xiàn)的次數(shù)多少作為相似度的衡量，因此需要建立物品的同現(xiàn)矩陣M。

建立過(guò)程如下：

step1：列出每個(gè)用戶看過(guò)的電影列表，結(jié)果如圖4所示。

圖4 用戶看過(guò)的電影列表

step2：求出每個(gè)用戶的電影同現(xiàn)矩陣

例對(duì)用戶1，其看過(guò)的電影有11、12、13，因此在矩陣對(duì)應(yīng)的位置(11，12)(12，11)(11，13)(13，11)(12，13)(13，12)處寫(xiě)上1，其余為0。也即用戶1的同現(xiàn)矩陣如圖5所示。

圖5 用戶1的同現(xiàn)矩陣

step3：將所有用戶的同現(xiàn)矩陣相加，得到最終的同現(xiàn)矩陣，如圖6所示。

圖6 所有用戶的同現(xiàn)矩陣

利用Python來(lái)實(shí)現(xiàn)同現(xiàn)矩陣的建立，其代碼如圖7所示。

圖7 求解電影同現(xiàn)矩陣

3.計(jì)算推薦評(píng)分

計(jì)算每個(gè)用戶曾看過(guò)的電影的推薦評(píng)分。推薦評(píng)分=同現(xiàn)矩陣M*評(píng)分向量R。

評(píng)分向量即用戶對(duì)所有物品(電影)的評(píng)分，由評(píng)分記錄表可得出。

由前面計(jì)算出的同現(xiàn)矩陣和用戶1的評(píng)分向量可得出用戶1對(duì)電影104的推薦評(píng)分為：

U1：14=4.5*3+3.5*1=17

具體求解方法如圖8所示。

用戶ID電影ID1用戶評(píng)分電影ID2電影ID1與電影ID2的關(guān)聯(lián)權(quán)重得分=用戶評(píng)分?電影ID1與電影ID2的關(guān)聯(lián)權(quán)重1114.51434.5?3=13.51123.51413.5?1=3.511331400114014001150141011601430總分=13.5+3.5=17

圖8推薦評(píng)分求解過(guò)程

同樣方法可求得每個(gè)用戶對(duì)未曾看過(guò)的電影的推薦評(píng)分，其結(jié)果如圖9所示。圖中陰影部分為每個(gè)用戶未曾看過(guò)的電影中推薦評(píng)分最高的，也是要推薦的結(jié)果。

然后將推薦得分從高到低排序，實(shí)際應(yīng)用中通常采用Top-N推薦，即為目標(biāo)用戶提供一個(gè)長(zhǎng)度為N的推薦列表，使該推薦列表能夠盡量滿足用戶的興趣和需求。利用Python來(lái)計(jì)算推薦評(píng)分的代碼如圖10所示。

圖9 所有用戶對(duì)未曾觀看的電影的推薦得分

圖10 求解推薦評(píng)分

4.輸出推薦結(jié)果

求得推薦評(píng)分的前N項(xiàng)后就可將結(jié)果輸出給用戶。輸出推薦結(jié)果時(shí)，有時(shí)可能需要為某個(gè)指定用戶來(lái)輸出推薦結(jié)果，也可能需要為所有用戶都輸出推薦結(jié)果，為使程序更加靈活，可編制兩個(gè)不同的函數(shù)來(lái)滿足其需求。為一個(gè)指定用戶輸出推薦結(jié)果的Python代碼如圖11所示。

圖11 輸出推薦結(jié)果

例如要為用戶1推薦兩部電影可直接調(diào)用主函數(shù)：main_one(“rates.txt”，“movies.txt”，“1”，2)，程序運(yùn)行結(jié)果如圖12所示，與前面手工計(jì)算得出的結(jié)果相同。

圖12 用戶1的推薦結(jié)果

若想為每個(gè)用戶都輸出其推薦結(jié)果，其相應(yīng)的主函數(shù)代碼如圖13所示。

圖13 為每個(gè)用戶推薦結(jié)果

如要為每個(gè)用戶推薦1部電影，則可直接調(diào)用主函數(shù)：main_all(“rates.txt”，“movies.txt”，1)，運(yùn)行結(jié)果如圖14所示。

圖14 所有用戶的推薦結(jié)果

其輸出結(jié)果與前面手工求解的結(jié)果完全相同。

四、分析與測(cè)試

前面給出的測(cè)試數(shù)據(jù)集數(shù)據(jù)很少，主要應(yīng)用于系統(tǒng)開(kāi)發(fā)測(cè)試中。實(shí)際應(yīng)用中推薦系統(tǒng)所用的數(shù)據(jù)集通常為海量數(shù)據(jù)，為驗(yàn)證系統(tǒng)在海量數(shù)據(jù)中的使用，可以MovieLens(http：//grouplens.org/datasets/movielens)作為電影推薦系統(tǒng)中的實(shí)驗(yàn)數(shù)據(jù)來(lái)測(cè)試系統(tǒng)。MovieLens是GroupLens Research實(shí)驗(yàn)室的一個(gè)非商業(yè)性質(zhì)、以研究為目的的實(shí)驗(yàn)性項(xiàng)目，采集了一組從20世紀(jì)90年代末到21世紀(jì)初的電影評(píng)分?jǐn)?shù)據(jù)，包含大小不同的數(shù)據(jù)集，每個(gè)數(shù)據(jù)集中包括電影信息數(shù)據(jù)及電影評(píng)分記錄等。如MovieLens 1M數(shù)據(jù)集中存放了1000多名用戶對(duì)近2000部電影的評(píng)分記錄，每個(gè)用戶至少對(duì)20部電影進(jìn)行過(guò)評(píng)分，一共有100000多條電影評(píng)分記錄。當(dāng)數(shù)據(jù)量增大時(shí)，存儲(chǔ)同現(xiàn)矩陣所需要的空間也相應(yīng)增加，通過(guò)前述也可以看出同現(xiàn)矩陣是一稀疏矩陣，因此采用字典來(lái)存儲(chǔ)同現(xiàn)矩陣中的非零元素要比直接存儲(chǔ)整個(gè)同現(xiàn)矩陣節(jié)省空間。又因字典是Python的內(nèi)置對(duì)象，而numpy是第三方擴(kuò)展庫(kù)，需要安裝和導(dǎo)入相應(yīng)的模塊，因此同一算法采用內(nèi)置對(duì)象比用擴(kuò)展庫(kù)會(huì)獲得更優(yōu)的時(shí)間性能和空間性能。

五、結(jié)語(yǔ)

本文利用Python實(shí)現(xiàn)的協(xié)同過(guò)濾算法框架清晰，代碼簡(jiǎn)潔，同時(shí)因其用Python的內(nèi)置序列字典代替二維數(shù)組來(lái)存放稀疏矩陣，有效提高了算法的時(shí)間空間效率。