韓潞潞 劉念 王楓

摘 要：如今，推薦系統(tǒng)在國內(nèi)各大網(wǎng)站應(yīng)用非常廣泛，可以讓用戶在更短的時間內(nèi)去獲得需要的信息，提高用戶的體驗。傳統(tǒng)的推薦系統(tǒng)多采用協(xié)同過濾算法來進(jìn)行推薦，由于其在計算項目相似度時沒有考慮到項目之間的內(nèi)在聯(lián)系，但是現(xiàn)實生活中項目之間是可以分類的，具有一定的內(nèi)在聯(lián)系。所以針對此問題本文提出了一種改進(jìn)算法。改進(jìn)算法的重點在于應(yīng)用關(guān)聯(lián)規(guī)則算法（FP-growth），挖掘出項目之間的強關(guān)聯(lián)規(guī)則，然后在具有強關(guān)聯(lián)規(guī)則的項目之間進(jìn)行重點推薦。將本算法在雅虎音樂數(shù)據(jù)集上進(jìn)行了實驗驗證，結(jié)果證明，改進(jìn)的算法提高了推薦的準(zhǔn)確性。

關(guān)鍵詞：Python 協(xié)同過濾 FP-growth

中圖分類號：TP31 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2018）01（b）-0023-03

隨著近幾年移動互聯(lián)網(wǎng)的快速發(fā)展，手機作為移動互聯(lián)網(wǎng)的終端設(shè)備，幾乎成為人人必備的電子產(chǎn)品。人們通過手機可以進(jìn)行各種活動，例如手機支付、網(wǎng)上購物、新聞瀏覽和在線學(xué)習(xí)等，手機已經(jīng)成為人們獲取信息和產(chǎn)生信息的主要媒介。而且，伴隨著移動互聯(lián)網(wǎng)的快速普及，信息出現(xiàn)爆炸式的增長，使得人們從海量信息中準(zhǔn)確發(fā)現(xiàn)自己感興趣的項目也越來越困難，于是，項目推薦問題已經(jīng)變的越來越突出[1]。

目前常用的推薦算法是協(xié)同過濾算法。協(xié)同過濾算法以其簡單的思想理念廣受研究者的喜愛。然而由于移動互聯(lián)網(wǎng)的快速發(fā)展，信息積累越來越多，也越來越復(fù)雜。此時如果使用傳統(tǒng)的協(xié)同過濾算法，使得其構(gòu)建的矩陣越來越大，同時矩陣也越來越稀疏。因為難以在大矩陣中找到高質(zhì)量的最近鄰，所以使得推薦系統(tǒng)的準(zhǔn)確性快速下降。

隨著推薦問題越來越明顯，如何在海量數(shù)據(jù)集中尋找到用戶喜歡的信息已經(jīng)變的越來越重要。因此也吸引了很多研究者投入推薦算法的研究中，同時也取得了很多成就。有的人通過將多維稀疏向量轉(zhuǎn)換成三維特征向量，然后采用云模型方法來進(jìn)行推薦[2]。

由于現(xiàn)實生活中項目之間是可以分類的，具有一定的內(nèi)在聯(lián)系。所以針對此問題提出了一種改進(jìn)算法。改進(jìn)算法首先應(yīng)用關(guān)聯(lián)規(guī)則算法（FP-growth），挖掘出項目之間的強關(guān)聯(lián)規(guī)則，然后在具有強關(guān)聯(lián)規(guī)則的項目之間來產(chǎn)生推薦，從而提高推薦的準(zhǔn)確性。

1 技術(shù)簡介

1.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是形如X=>Y的形式，其在一定程度上可以表示喜歡X的人也在很大的程度上喜歡Y，即如果一個人購買了項目X，那他也會在很大程度上去購買Y。Apriori算法作為關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法之一，是由RAgrawal和RSrikant在1994年提出的，該算法的基本原理是：如果一個項集是非頻繁集，那么它的所有超集也是非頻繁集[3]。后來，在Apriori算法的基礎(chǔ)上，Luan Ru-peng[4]等人通過挖據(jù)數(shù)據(jù)集中項集之間的關(guān)系提出了FP-growth算法。FP-growth是目前比較流行的算法，是基于Apriori構(gòu)建的。FP-growth算法的優(yōu)勢在于建立FP樹時只需要掃描兩次數(shù)據(jù)集，因而FP-growth算法執(zhí)行效率要比Apriori高很多。FP-growth在很多領(lǐng)域都有其優(yōu)勢，如推薦系統(tǒng)，社交網(wǎng)絡(luò)等[5]。

1.2 Python

Python作為一門動態(tài)語言，以其簡潔方便的語法和豐富的類庫深受研究者的喜愛?；邶嫶蟮拈_源社區(qū)的支持，使得其包含的類庫越來越多，越來越高效。從而可以使得研究人員從細(xì)節(jié)中解脫出來，可以更加專注于個人領(lǐng)域知識的研究。本論文中所涉及的算法采用Python語言來進(jìn)行實現(xiàn)，提高了效率。

2 結(jié)合關(guān)聯(lián)規(guī)則的協(xié)同過濾改進(jìn)算法

2.1 相似度的計算方法

計算相似度的方法主要有以下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表示項目i和j，UAij表示同時對i和j進(jìn)行過評分的用戶集合，Wk，i表示用戶k對項目i的評分，Wk，j表示用戶k對項目j的評分，Ii表示用戶對項目i的評分的平均值，Ij表示用戶對項目j的評分的平均值，Uk表示用戶k已評分項目的平均值。

2.2 協(xié)同過濾算法問題

協(xié)同過濾算法首先在數(shù)據(jù)集上采用2.1節(jié)中相應(yīng)的相似度的計算方法來構(gòu)建用戶-項目偏好矩陣，然后求出目標(biāo)用戶的鄰居用戶，最后根據(jù)其相鄰的用戶的偏好信息來進(jìn)行推薦。在表1中，是5個用戶對6個項目的評價，其中項目I1，I3，I6是屬于流行音樂，I2，I4，I5是屬于古典音樂。用戶項目評價矩陣如表1所示。

現(xiàn)在要預(yù)測C5，6的值，首先我們根據(jù)2.1節(jié)中列出的person相似度計算方法，然后根據(jù)表2中列出的信息可以求得U5用戶與其他用戶的相似度，如表2所示。

從表2中可以知道，U4的相似度最高，因此選擇U4作為U5的最近鄰。經(jīng)過對原始數(shù)據(jù)的分析，選擇U4作為最近鄰，是因為他與U5在古典音樂方面的行為極其相似。用古典音樂的相似性來推薦屬于流行音樂的項目，推薦結(jié)果也將受到質(zhì)疑。也就是說，我們拿那些在其他類別上與我們有相似愛好的項目去推薦這個類別的項目，推薦精準(zhǔn)度將大打折扣。

2.3 結(jié)合關(guān)聯(lián)規(guī)則的協(xié)同過濾算法

通過2.2節(jié)的分析，可以得出協(xié)同過濾算法在類別具有明顯差別的數(shù)據(jù)集中推薦效果并不好，因為其沒有考慮項目之間的類別差異，只是適用于在類別不明顯的數(shù)據(jù)集中進(jìn)行推薦。然而，現(xiàn)實生活中，由于人們的關(guān)注點不同，而項目的目標(biāo)人群也不同，因此在大多數(shù)應(yīng)用場景下，項目之間是具有明顯差異的?，F(xiàn)實生活中絕大多數(shù)用戶感興趣的項目往往只是在可數(shù)的幾個類別中，如果在同類別的項目之間進(jìn)行推薦，可以提高推薦的準(zhǔn)確性。

首先，將項目進(jìn)行關(guān)聯(lián)分析，然后找出與預(yù)測項目同類別的其他項目，形成具有一定相關(guān)關(guān)系的集合。然后，在該集合中尋找該項目的近鄰。

經(jīng)過分析，由于項目是可以進(jìn)行分類的、是具有一定的類別性的，而協(xié)同過濾算法在類別明顯的數(shù)據(jù)集上推薦精準(zhǔn)度不高，從而提出了一種改進(jìn)策略。

2.4 算法設(shè)計

改進(jìn)算法首先使用FP-growth對項目進(jìn)行分類。然后在此結(jié)果上再進(jìn)行推薦。其流程如下：

（1）事務(wù)集合。在用戶-項目矩陣中，假設(shè)I={I1，I2，…，In}是項目所在的集合，n為項目總的數(shù)目，用戶Ui評價過的項目集合記為Ti，將其組合形成數(shù)據(jù)集T={T1，T2，…，Tk}。

（2）強關(guān)聯(lián)規(guī)則。對（1）產(chǎn)生的事務(wù)數(shù)據(jù)集T作為FP-growth的輸入，然后依據(jù)經(jīng)驗設(shè)定閥值，求出頻繁集，得到具有強關(guān)聯(lián)規(guī)則的項目集合。

（3）計算推薦值。根據(jù)上一步產(chǎn)生的結(jié)果，求出用戶對項目的預(yù)測值。①遍歷上一步形成的結(jié)果，查詢所有包含項目j的頻繁項集，求并集形成相關(guān)項目類U，然后在原始數(shù)據(jù)集中提取出所有用戶對項目集合U的評價信息，形成基于相關(guān)項目的用戶-項目矩陣。②在①形成的矩陣中計算項目的相似度。采用person相似度計算公式（見公式2）。

（4）形成推薦。計算項目預(yù)測值的公式如公式（4）所示。

Predictionm，j= （4）

其中Umi代表用戶m對項目i的評分，sim（i，j）代表項目i和j的之間的相似度。

根據(jù)公式（4）來計算出該用戶對未評分過的項目的預(yù)測值，取預(yù)測值最高的前幾個推薦給用戶。

3 實驗方案設(shè)計

3.1 實驗數(shù)據(jù)集

本實驗數(shù)據(jù)來源是雅虎音樂公開提供的數(shù)據(jù)集。雅虎音樂是第一個提供給個人的網(wǎng)絡(luò)音樂電臺，其數(shù)據(jù)庫中保存了成千上萬首的歌曲。它是在線流媒體的先鋒。雅虎音樂是曾經(jīng)排名最高的在線音樂網(wǎng)站。用戶可以將歌曲、藝術(shù)家、專輯甚至流派進(jìn)行評分。這些評分使得雅虎音樂可以根據(jù)音樂的類別或其他相似用戶推薦的音樂來匹配這個用戶的音樂愛好。

數(shù)據(jù)集收集了在1999—2010年期間1，000，990用戶對624，961音樂項目的262，810，175評分記錄。在整個數(shù)據(jù)集中，每個用戶和每個項目至少包含20條的記錄數(shù)。數(shù)據(jù)集被劃分為訓(xùn)練集和測試集，測試集中包含了每個用戶至少對6個項目的評分記錄。

圖1所示展示了每個項目評級數(shù)量的分布和每個用戶評級數(shù)量的分布。這兩個分布圖表現(xiàn)出明顯的冪律特征的長尾流行項目和非?；钴S的用戶，具有很強的稀疏性。

3.2 數(shù)據(jù)預(yù)處理

為了方便實驗，對數(shù)據(jù)進(jìn)行以下的處理：（1）對原始數(shù)據(jù)進(jìn)行轉(zhuǎn)換，去掉和本實驗無關(guān)的標(biāo)簽（例如時間字段），形成原始數(shù)據(jù)集。（2）為了尋找頻繁項集，需要把數(shù)據(jù)轉(zhuǎn)換成FP-growth算法需要的數(shù)據(jù)格式（用戶對項目的事務(wù)信息）形成新的文件，成為FP-growth算法的輸入。

3.3 實驗方案

（1）將用戶對項目的事務(wù)信息作為輸入，設(shè)置最小支持度作為FP-growth算法的輸入，最后把形成的頻繁項集存入mysql數(shù)據(jù)庫中。（2）遍歷測試數(shù)據(jù)集，對于測試數(shù)據(jù)集的每一項，把用戶和相應(yīng)的項目作為輸入，查詢mysql數(shù)據(jù)庫，然后形成與該項目關(guān)聯(lián)的項目集合。（3）遍歷原始數(shù)據(jù)集，找出用戶對上一步形成的項目集合評分的數(shù)據(jù)，形成用戶和關(guān)聯(lián)項目的評分矩陣。（4）把該矩陣和第二步用戶的編號來作為輸入，用皮爾森相似度來計算項目與項目之間的相似度。（5）根據(jù)用戶對最近鄰項目的評分來預(yù)測對該項目的評分。（6）把測試數(shù)據(jù)集中該用戶對該項目的評分與該預(yù)測值求差值的平方。（7）求出數(shù)據(jù)集的RMSE（均方根誤差）。

3.4 算法評價指標(biāo)

根據(jù)常用的推薦系統(tǒng)性能指標(biāo)以及大多數(shù)社會推薦系統(tǒng)的研究論文中利用的評測指標(biāo)，本論文采用均方根誤差、覆蓋率和準(zhǔn)確率來對算法來進(jìn)行性能優(yōu)劣的評估。

3.5 實驗結(jié)果與分析

本文采用基于用戶的協(xié)同過濾（User-CF）算法和基于項目的協(xié)同過濾（Item-CF）算法來作為對比實驗，得出結(jié)果并進(jìn)行比較。最終的結(jié)果如表3所示。

由于本實驗的數(shù)據(jù)集采用的是百分制的評分，所以均方根誤差比較大。通過與Item-CF和User-CF這兩個算法的實驗結(jié)果比較可知，使用關(guān)聯(lián)分析和傳統(tǒng)的協(xié)同過濾算法的結(jié)合有效地降低了預(yù)測評分誤差，提高了推薦的準(zhǔn)確性。這是因為利用關(guān)聯(lián)分析之后，在相似的項目之間進(jìn)行推薦，將使得預(yù)測評分更加客觀、合理。

4 結(jié)語

本文針對傳統(tǒng)協(xié)同過濾算法的不足，結(jié)合FP-growth去挖掘項目之間的內(nèi)在聯(lián)系。在本算法中，最小支持度閥值需要根據(jù)經(jīng)驗或者迭代來尋找最優(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ī)則的個性化信息檢索系統(tǒng)研究[J].情報科學(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.