韓潞潞 劉念 王楓
摘 要:如今,推薦系統(tǒng)在國(guó)內(nèi)各大網(wǎng)站應(yīng)用非常廣泛,可以讓用戶在更短的時(shí)間內(nèi)去獲得需要的信息,提高用戶的體驗(yàn)。傳統(tǒng)的推薦系統(tǒng)多采用協(xié)同過濾算法來進(jìn)行推薦,由于其在計(jì)算項(xiàng)目相似度時(shí)沒有考慮到項(xiàng)目之間的內(nèi)在聯(lián)系,但是現(xiàn)實(shí)生活中項(xiàng)目之間是可以分類的,具有一定的內(nèi)在聯(lián)系。所以針對(duì)此問題本文提出了一種改進(jìn)算法。改進(jìn)算法的重點(diǎn)在于應(yīng)用關(guān)聯(lián)規(guī)則算法(FP-growth),挖掘出項(xiàng)目之間的強(qiáng)關(guān)聯(lián)規(guī)則,然后在具有強(qiáng)關(guān)聯(lián)規(guī)則的項(xiàng)目之間進(jìn)行重點(diǎn)推薦。將本算法在雅虎音樂數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證,結(jié)果證明,改進(jìn)的算法提高了推薦的準(zhǔn)確性。
關(guān)鍵詞:Python 協(xié)同過濾 FP-growth
中圖分類號(hào):TP31 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1672-3791(2018)01(b)-0023-03
隨著近幾年移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展,手機(jī)作為移動(dòng)互聯(lián)網(wǎng)的終端設(shè)備,幾乎成為人人必備的電子產(chǎn)品。人們通過手機(jī)可以進(jìn)行各種活動(dòng),例如手機(jī)支付、網(wǎng)上購(gòu)物、新聞瀏覽和在線學(xué)習(xí)等,手機(jī)已經(jīng)成為人們獲取信息和產(chǎn)生信息的主要媒介。而且,伴隨著移動(dòng)互聯(lián)網(wǎng)的快速普及,信息出現(xiàn)爆炸式的增長(zhǎng),使得人們從海量信息中準(zhǔn)確發(fā)現(xiàn)自己感興趣的項(xiàng)目也越來越困難,于是,項(xiàng)目推薦問題已經(jīng)變的越來越突出[1]。
目前常用的推薦算法是協(xié)同過濾算法。協(xié)同過濾算法以其簡(jiǎn)單的思想理念廣受研究者的喜愛。然而由于移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展,信息積累越來越多,也越來越復(fù)雜。此時(shí)如果使用傳統(tǒng)的協(xié)同過濾算法,使得其構(gòu)建的矩陣越來越大,同時(shí)矩陣也越來越稀疏。因?yàn)殡y以在大矩陣中找到高質(zhì)量的最近鄰,所以使得推薦系統(tǒng)的準(zhǔn)確性快速下降。
隨著推薦問題越來越明顯,如何在海量數(shù)據(jù)集中尋找到用戶喜歡的信息已經(jīng)變的越來越重要。因此也吸引了很多研究者投入推薦算法的研究中,同時(shí)也取得了很多成就。有的人通過將多維稀疏向量轉(zhuǎn)換成三維特征向量,然后采用云模型方法來進(jìn)行推薦[2]。
由于現(xiàn)實(shí)生活中項(xiàng)目之間是可以分類的,具有一定的內(nèi)在聯(lián)系。所以針對(duì)此問題提出了一種改進(jìn)算法。改進(jìn)算法首先應(yīng)用關(guān)聯(lián)規(guī)則算法(FP-growth),挖掘出項(xiàng)目之間的強(qiáng)關(guān)聯(lián)規(guī)則,然后在具有強(qiáng)關(guān)聯(lián)規(guī)則的項(xiàng)目之間來產(chǎn)生推薦,從而提高推薦的準(zhǔn)確性。
1 技術(shù)簡(jiǎn)介
1.1 關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則是形如X=>Y的形式,其在一定程度上可以表示喜歡X的人也在很大的程度上喜歡Y,即如果一個(gè)人購(gòu)買了項(xiàng)目X,那他也會(huì)在很大程度上去購(gòu)買Y。Apriori算法作為關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法之一,是由RAgrawal和RSrikant在1994年提出的,該算法的基本原理是:如果一個(gè)項(xiàng)集是非頻繁集,那么它的所有超集也是非頻繁集[3]。后來,在Apriori算法的基礎(chǔ)上,Luan Ru-peng[4]等人通過挖據(jù)數(shù)據(jù)集中項(xiàng)集之間的關(guān)系提出了FP-growth算法。FP-growth是目前比較流行的算法,是基于Apriori構(gòu)建的。FP-growth算法的優(yōu)勢(shì)在于建立FP樹時(shí)只需要掃描兩次數(shù)據(jù)集,因而FP-growth算法執(zhí)行效率要比Apriori高很多。FP-growth在很多領(lǐng)域都有其優(yōu)勢(shì),如推薦系統(tǒng),社交網(wǎng)絡(luò)等[5]。
1.2 Python
Python作為一門動(dòng)態(tài)語(yǔ)言,以其簡(jiǎn)潔方便的語(yǔ)法和豐富的類庫(kù)深受研究者的喜愛?;邶嫶蟮拈_源社區(qū)的支持,使得其包含的類庫(kù)越來越多,越來越高效。從而可以使得研究人員從細(xì)節(jié)中解脫出來,可以更加專注于個(gè)人領(lǐng)域知識(shí)的研究。本論文中所涉及的算法采用Python語(yǔ)言來進(jìn)行實(shí)現(xiàn),提高了效率。
2 結(jié)合關(guān)聯(lián)規(guī)則的協(xié)同過濾改進(jìn)算法
2.1 相似度的計(jì)算方法
計(jì)算相似度的方法主要有以下3種。
(1)余弦相似度。
sim(Ii,Ij)=cos(Ii,Ij)= (1)
(2)person相關(guān)系數(shù)。
sim(Ii,Ij)=person(Ii,Ij)= (2)
(3)修正的余弦相似度。
sim(Ii,Ij)=cos(Ii,Ij)= (3)
其中Ii,Ij表示項(xiàng)目i和j,UAij表示同時(shí)對(duì)i和j進(jìn)行過評(píng)分的用戶集合,Wk,i表示用戶k對(duì)項(xiàng)目i的評(píng)分,Wk,j表示用戶k對(duì)項(xiàng)目j的評(píng)分,Ii表示用戶對(duì)項(xiàng)目i的評(píng)分的平均值,Ij表示用戶對(duì)項(xiàng)目j的評(píng)分的平均值,Uk表示用戶k已評(píng)分項(xiàng)目的平均值。
2.2 協(xié)同過濾算法問題
協(xié)同過濾算法首先在數(shù)據(jù)集上采用2.1節(jié)中相應(yīng)的相似度的計(jì)算方法來構(gòu)建用戶-項(xiàng)目偏好矩陣,然后求出目標(biāo)用戶的鄰居用戶,最后根據(jù)其相鄰的用戶的偏好信息來進(jìn)行推薦。在表1中,是5個(gè)用戶對(duì)6個(gè)項(xiàng)目的評(píng)價(jià),其中項(xiàng)目I1,I3,I6是屬于流行音樂,I2,I4,I5是屬于古典音樂。用戶項(xiàng)目評(píng)價(jià)矩陣如表1所示。
現(xiàn)在要預(yù)測(cè)C5,6的值,首先我們根據(jù)2.1節(jié)中列出的person相似度計(jì)算方法,然后根據(jù)表2中列出的信息可以求得U5用戶與其他用戶的相似度,如表2所示。
從表2中可以知道,U4的相似度最高,因此選擇U4作為U5的最近鄰。經(jīng)過對(duì)原始數(shù)據(jù)的分析,選擇U4作為最近鄰,是因?yàn)樗cU5在古典音樂方面的行為極其相似。用古典音樂的相似性來推薦屬于流行音樂的項(xiàng)目,推薦結(jié)果也將受到質(zhì)疑。也就是說,我們拿那些在其他類別上與我們有相似愛好的項(xiàng)目去推薦這個(gè)類別的項(xiàng)目,推薦精準(zhǔn)度將大打折扣。
2.3 結(jié)合關(guān)聯(lián)規(guī)則的協(xié)同過濾算法
通過2.2節(jié)的分析,可以得出協(xié)同過濾算法在類別具有明顯差別的數(shù)據(jù)集中推薦效果并不好,因?yàn)槠錄]有考慮項(xiàng)目之間的類別差異,只是適用于在類別不明顯的數(shù)據(jù)集中進(jìn)行推薦。然而,現(xiàn)實(shí)生活中,由于人們的關(guān)注點(diǎn)不同,而項(xiàng)目的目標(biāo)人群也不同,因此在大多數(shù)應(yīng)用場(chǎng)景下,項(xiàng)目之間是具有明顯差異的?,F(xiàn)實(shí)生活中絕大多數(shù)用戶感興趣的項(xiàng)目往往只是在可數(shù)的幾個(gè)類別中,如果在同類別的項(xiàng)目之間進(jìn)行推薦,可以提高推薦的準(zhǔn)確性。
首先,將項(xiàng)目進(jìn)行關(guān)聯(lián)分析,然后找出與預(yù)測(cè)項(xiàng)目同類別的其他項(xiàng)目,形成具有一定相關(guān)關(guān)系的集合。然后,在該集合中尋找該項(xiàng)目的近鄰。
經(jīng)過分析,由于項(xiàng)目是可以進(jìn)行分類的、是具有一定的類別性的,而協(xié)同過濾算法在類別明顯的數(shù)據(jù)集上推薦精準(zhǔn)度不高,從而提出了一種改進(jìn)策略。
2.4 算法設(shè)計(jì)
改進(jìn)算法首先使用FP-growth對(duì)項(xiàng)目進(jìn)行分類。然后在此結(jié)果上再進(jìn)行推薦。其流程如下:
(1)事務(wù)集合。在用戶-項(xiàng)目矩陣中,假設(shè)I={I1,I2,…,In}是項(xiàng)目所在的集合,n為項(xiàng)目總的數(shù)目,用戶Ui評(píng)價(jià)過的項(xiàng)目集合記為Ti,將其組合形成數(shù)據(jù)集T={T1,T2,…,Tk}。
(2)強(qiáng)關(guān)聯(lián)規(guī)則。對(duì)(1)產(chǎn)生的事務(wù)數(shù)據(jù)集T作為FP-growth的輸入,然后依據(jù)經(jīng)驗(yàn)設(shè)定閥值,求出頻繁集,得到具有強(qiáng)關(guān)聯(lián)規(guī)則的項(xiàng)目集合。
(3)計(jì)算推薦值。根據(jù)上一步產(chǎn)生的結(jié)果,求出用戶對(duì)項(xiàng)目的預(yù)測(cè)值。①遍歷上一步形成的結(jié)果,查詢所有包含項(xiàng)目j的頻繁項(xiàng)集,求并集形成相關(guān)項(xiàng)目類U,然后在原始數(shù)據(jù)集中提取出所有用戶對(duì)項(xiàng)目集合U的評(píng)價(jià)信息,形成基于相關(guān)項(xiàng)目的用戶-項(xiàng)目矩陣。②在①形成的矩陣中計(jì)算項(xiàng)目的相似度。采用person相似度計(jì)算公式(見公式2)。
(4)形成推薦。計(jì)算項(xiàng)目預(yù)測(cè)值的公式如公式(4)所示。
Predictionm,j= (4)
其中Umi代表用戶m對(duì)項(xiàng)目i的評(píng)分,sim(i,j)代表項(xiàng)目i和j的之間的相似度。
根據(jù)公式(4)來計(jì)算出該用戶對(duì)未評(píng)分過的項(xiàng)目的預(yù)測(cè)值,取預(yù)測(cè)值最高的前幾個(gè)推薦給用戶。
3 實(shí)驗(yàn)方案設(shè)計(jì)
3.1 實(shí)驗(yàn)數(shù)據(jù)集
本實(shí)驗(yàn)數(shù)據(jù)來源是雅虎音樂公開提供的數(shù)據(jù)集。雅虎音樂是第一個(gè)提供給個(gè)人的網(wǎng)絡(luò)音樂電臺(tái),其數(shù)據(jù)庫(kù)中保存了成千上萬(wàn)首的歌曲。它是在線流媒體的先鋒。雅虎音樂是曾經(jīng)排名最高的在線音樂網(wǎng)站。用戶可以將歌曲、藝術(shù)家、專輯甚至流派進(jìn)行評(píng)分。這些評(píng)分使得雅虎音樂可以根據(jù)音樂的類別或其他相似用戶推薦的音樂來匹配這個(gè)用戶的音樂愛好。
數(shù)據(jù)集收集了在1999—2010年期間1,000,990用戶對(duì)624,961音樂項(xiàng)目的262,810,175評(píng)分記錄。在整個(gè)數(shù)據(jù)集中,每個(gè)用戶和每個(gè)項(xiàng)目至少包含20條的記錄數(shù)。數(shù)據(jù)集被劃分為訓(xùn)練集和測(cè)試集,測(cè)試集中包含了每個(gè)用戶至少對(duì)6個(gè)項(xiàng)目的評(píng)分記錄。
圖1所示展示了每個(gè)項(xiàng)目評(píng)級(jí)數(shù)量的分布和每個(gè)用戶評(píng)級(jí)數(shù)量的分布。這兩個(gè)分布圖表現(xiàn)出明顯的冪律特征的長(zhǎng)尾流行項(xiàng)目和非?;钴S的用戶,具有很強(qiáng)的稀疏性。
3.2 數(shù)據(jù)預(yù)處理
為了方便實(shí)驗(yàn),對(duì)數(shù)據(jù)進(jìn)行以下的處理:(1)對(duì)原始數(shù)據(jù)進(jìn)行轉(zhuǎn)換,去掉和本實(shí)驗(yàn)無關(guān)的標(biāo)簽(例如時(shí)間字段),形成原始數(shù)據(jù)集。(2)為了尋找頻繁項(xiàng)集,需要把數(shù)據(jù)轉(zhuǎn)換成FP-growth算法需要的數(shù)據(jù)格式(用戶對(duì)項(xiàng)目的事務(wù)信息)形成新的文件,成為FP-growth算法的輸入。
3.3 實(shí)驗(yàn)方案
(1)將用戶對(duì)項(xiàng)目的事務(wù)信息作為輸入,設(shè)置最小支持度作為FP-growth算法的輸入,最后把形成的頻繁項(xiàng)集存入mysql數(shù)據(jù)庫(kù)中。(2)遍歷測(cè)試數(shù)據(jù)集,對(duì)于測(cè)試數(shù)據(jù)集的每一項(xiàng),把用戶和相應(yīng)的項(xiàng)目作為輸入,查詢mysql數(shù)據(jù)庫(kù),然后形成與該項(xiàng)目關(guān)聯(lián)的項(xiàng)目集合。(3)遍歷原始數(shù)據(jù)集,找出用戶對(duì)上一步形成的項(xiàng)目集合評(píng)分的數(shù)據(jù),形成用戶和關(guān)聯(lián)項(xiàng)目的評(píng)分矩陣。(4)把該矩陣和第二步用戶的編號(hào)來作為輸入,用皮爾森相似度來計(jì)算項(xiàng)目與項(xiàng)目之間的相似度。(5)根據(jù)用戶對(duì)最近鄰項(xiàng)目的評(píng)分來預(yù)測(cè)對(duì)該項(xiàng)目的評(píng)分。(6)把測(cè)試數(shù)據(jù)集中該用戶對(duì)該項(xiàng)目的評(píng)分與該預(yù)測(cè)值求差值的平方。(7)求出數(shù)據(jù)集的RMSE(均方根誤差)。
3.4 算法評(píng)價(jià)指標(biāo)
根據(jù)常用的推薦系統(tǒng)性能指標(biāo)以及大多數(shù)社會(huì)推薦系統(tǒng)的研究論文中利用的評(píng)測(cè)指標(biāo),本論文采用均方根誤差、覆蓋率和準(zhǔn)確率來對(duì)算法來進(jìn)行性能優(yōu)劣的評(píng)估。
3.5 實(shí)驗(yàn)結(jié)果與分析
本文采用基于用戶的協(xié)同過濾(User-CF)算法和基于項(xiàng)目的協(xié)同過濾(Item-CF)算法來作為對(duì)比實(shí)驗(yàn),得出結(jié)果并進(jìn)行比較。最終的結(jié)果如表3所示。
由于本實(shí)驗(yàn)的數(shù)據(jù)集采用的是百分制的評(píng)分,所以均方根誤差比較大。通過與Item-CF和User-CF這兩個(gè)算法的實(shí)驗(yàn)結(jié)果比較可知,使用關(guān)聯(lián)分析和傳統(tǒng)的協(xié)同過濾算法的結(jié)合有效地降低了預(yù)測(cè)評(píng)分誤差,提高了推薦的準(zhǔn)確性。這是因?yàn)槔藐P(guān)聯(lián)分析之后,在相似的項(xiàng)目之間進(jìn)行推薦,將使得預(yù)測(cè)評(píng)分更加客觀、合理。
4 結(jié)語(yǔ)
本文針對(duì)傳統(tǒng)協(xié)同過濾算法的不足,結(jié)合FP-growth去挖掘項(xiàng)目之間的內(nèi)在聯(lián)系。在本算法中,最小支持度閥值需要根據(jù)經(jīng)驗(yàn)或者迭代來尋找最優(yōu)解。下一步工作是考慮如何改進(jìn)FP-growth中輸入?yún)?shù)最小支持度的設(shè)定,以及如何在數(shù)據(jù)集上找到最優(yōu)的最小支持度參數(shù)。
參考文獻(xiàn)
[1] 歐立奇.協(xié)同過濾在電子商務(wù)推薦系統(tǒng)中的應(yīng)用研究[D].西安:西北大學(xué),2006.
[2] LuoR,Xue Q.Study on the user preferences based on cloud model[A].2009 2nd International Conference on Power Electronics and Intelligent Transportation System(PEITS)[C].2009(3):268-270.
[3] 陳小華,趙捧未.基于關(guān)聯(lián)規(guī)則的個(gè)性化信息檢索系統(tǒng)研究[J].情報(bào)科學(xué),2006(6):915-918.
[4] Luan Ru-peng,Zhang Qian,Zhang Jun-feng,et al.An association rule discovery algorithm applicable to Web log mining[J].Computer Applications and Software,2013,30(1):114-116,225.
[5] 衛(wèi)華.數(shù)據(jù)挖掘在電子商務(wù)推薦系統(tǒng)中的應(yīng)用與研究[D].西安:西安科技大學(xué),2013.