基于Python的關(guān)聯(lián)規(guī)則算法在推薦領(lǐng)域的應(yīng)用研究

韓潞潞 劉念 王楓

摘 要：如今，推薦系統(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.