Apriori算法在大數(shù)據(jù)集上的高效應(yīng)用

陳邦豪

摘 要：Apriori算法是經(jīng)典的挖掘頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法。本文通過實(shí)例使用Python語言將Apriori算法用到電影推薦上，從大量電影打分?jǐn)?shù)據(jù)形成的大數(shù)據(jù)集中找到可用于電影推薦的關(guān)聯(lián)規(guī)則。整個(gè)過程由兩個(gè)階段構(gòu)成，先借助Apriori算法尋找數(shù)據(jù)中的頻繁項(xiàng)集，然后根據(jù)找到的頻繁項(xiàng)集，生成關(guān)聯(lián)規(guī)則。由此算法得到結(jié)果更高效、快捷、靈活，也取得了良好的電影推薦效果。同時(shí)也為下一步針對Apriori算法的改進(jìn)及更大范圍的應(yīng)用提供了方向，具有較大的應(yīng)用價(jià)值。

關(guān)鍵詞：Apriori算法； 數(shù)據(jù)挖掘； 電影推薦； 大數(shù)據(jù)集

Abstract： Apriori algorithm is a classical data mining algorithm for mining frequent itemsets and association rules. This article uses Python language to apply Apriori algorithm to movie recommendations. It can be used for movie recommendation from large data sets formed by a large number of movie scoring data， and association rules are given out. The whole process is divided into two major stages. First， the Apriori algorithm is used to find frequent itemsets in the data. Then， based on the found frequent itemsets， an association rule is generated. The result of this algorithm is more efficient， faster， and more flexible. It also achieves good movie recommendations. At the same time， it also provides direction for the improvement of the Apriori algorithm and a wider range of applications in the next step， and has great application value.

Key words： Apriori algorithm； data mining； movie recommendation； large data set

引言

產(chǎn)品推薦是一項(xiàng)在大數(shù)據(jù)集中進(jìn)行應(yīng)用的重要技術(shù)。如網(wǎng)上商店經(jīng)?；诖藖硐驖撛谟脩敉扑]潛在的產(chǎn)品。 而一個(gè)好的建議算法可以帶來更高的銷售業(yè)績，據(jù)統(tǒng)計(jì)每年至少有上億用戶網(wǎng)上購買，通過向人們推薦更多產(chǎn)品，有著更為可觀的潛在收益。

本文中Apriori算法是通過數(shù)據(jù)集中頻繁出現(xiàn)的數(shù)據(jù)中選取共同出現(xiàn)的數(shù)據(jù)組成頻繁項(xiàng)集（frequent itemset），避免了出現(xiàn)因復(fù)雜度呈指數(shù)級增長的問題。一旦找到頻繁項(xiàng)集，生成關(guān)聯(lián)規(guī)則就很容易了。近年來，如何高效的處理大數(shù)據(jù)集并從中獲取有價(jià)值的信息一直是一個(gè)焦點(diǎn)問題，而本文通過實(shí)例就Apriori算法如何高效的應(yīng)用在大數(shù)據(jù)集中展開研究。

1 相關(guān)介紹

1.1 Apriori算法簡述

Apriori算法背后的原理簡潔卻不失巧妙。首先，確保了規(guī)則在數(shù)據(jù)集中有足夠的支持度。Apriori算法的一個(gè)重要參數(shù)就是最小支持度。比如，要生成包含商品A、B的頻繁項(xiàng)集（A， B），要求支持度至少為30，那么A和B都必須至少在數(shù)據(jù)集中出現(xiàn)30次。更大的頻繁項(xiàng)集也要遵守該項(xiàng)約定，比如要生成頻繁項(xiàng)集（A， B， C， D），那么子集（A， B， C）必須是頻繁項(xiàng)集（當(dāng)然D也要滿足最小支持度標(biāo)準(zhǔn)）。生成頻繁項(xiàng)集后，將不再考慮其它可能的卻不夠頻繁的項(xiàng)集（這樣的集合有很多），從而大大減少測試新規(guī)則所需的時(shí)間。

1.2 選擇參數(shù)

挖掘親和性分析所用的關(guān)聯(lián)規(guī)則之前，先用Apriori算法生成頻繁項(xiàng)集。接著，通過檢測頻繁項(xiàng)集中前提和結(jié)論的組合，生成關(guān)聯(lián)規(guī)則（例如，如果用戶喜歡電影X，那么該用戶很可能喜歡電影Y）。

首先，需要為Apriori算法指定一個(gè)項(xiàng)集成為頻繁項(xiàng)集所需的最小支持度，任何小于最小支持度的項(xiàng)集將不再考慮。如果最小支持度值過小，Apriori算法要檢測大量的項(xiàng)集，會(huì)拖慢運(yùn)行速度；最小支持度值過大的話，則只有很少的頻繁項(xiàng)集。

找出頻繁項(xiàng)集后，根據(jù)置信度選取關(guān)聯(lián)規(guī)則?？梢栽O(shè)定最小置信度，返回一部分規(guī)則，或者返回所有規(guī)則，讓用戶自己選。本文中設(shè)定最小置信度，只返回高于其規(guī)則。置信度過低將會(huì)導(dǎo)致規(guī)則支持度高，正確率低；置信度過高，導(dǎo)致正確率高，但是返回的規(guī)則少。

2 算法應(yīng)用

2.1 獲取數(shù)據(jù)集

在網(wǎng)上下載包含100萬條數(shù)據(jù)的MovieLens數(shù)據(jù)集。在IPython Notebook筆記本，輸入以下代碼：

import os

import pandas as pd

data_folder = os.path.join（os.path.expanduser（"～"），"Data"，"m1-100k"）

ratings_filename=os.path.join（data_folder."u.data"）

2.2 用 pandas 加載數(shù)據(jù)

MovieLens數(shù)據(jù)集非常規(guī)整，但是有幾點(diǎn)跟 pandas.read_csv 方法的默認(rèn)設(shè)置有出入，所以要調(diào)整參數(shù)設(shè)置。數(shù)據(jù)集每行的幾個(gè)數(shù)據(jù)之間用制表符而不是逗號分隔。其次，沒有表頭，這表示數(shù)據(jù)集的第一行就是數(shù)據(jù)部分。

加載數(shù)據(jù)集時(shí)，把分隔符設(shè)置為制表符，告訴pandas不要把第一行作為表頭（ header=None ），設(shè)置好各列的名稱。解析時(shí)間戳數(shù)據(jù)如下：

all_ratings=pd.read_csv（ratings_filename，delimiter="＼＼t"，

header=None，names=["UserID"，"MovieID"，"Rating"， Datetime]）

all_ratings["Datetime"]=pd.to_datetime（all-ratings['Date time']， unit='s'）

all_ratings[：5]

這是一個(gè)稀疏數(shù)據(jù)集，可以將每一行想象成巨大特征矩陣的一個(gè)格子，在這個(gè)矩陣中，每一行表示一個(gè)用戶，每一列為一部電影。第一列為每位用戶給第一部電影打的分?jǐn)?shù)，第二列為每位用戶給第二部電影打的分?jǐn)?shù)，以此類推。

數(shù)據(jù)集中有1 000名用戶和1 700部電影，這就意味著整個(gè)矩陣很大。將矩陣讀到內(nèi)存中及在其基礎(chǔ)上進(jìn)行計(jì)算可能存在難度。然而，這個(gè)矩陣的很多格子都是空的，也就是對大部分用戶來說，人們只給少數(shù)幾部電影打過分。比如用戶#213沒有為電影#675打過分。用表1中的格式也能表示矩陣，且更為緊湊。序號為0的那一行表示，用戶#196為電影#242打了3分（滿分是5分）。

任何沒有出現(xiàn)在數(shù)據(jù)集中的用戶和電影組合表示自己實(shí)際上是不存在的。這比起在內(nèi)存中保存大量的0，節(jié)省了很多空間。這種格式叫作稀疏矩陣（sparse matrix）。根據(jù)經(jīng)驗(yàn)，如果數(shù)據(jù)集中60%或以上的數(shù)據(jù)為0，就應(yīng)該考慮使用稀疏矩陣，從而節(jié)省空間。

在對稀疏矩陣進(jìn)行計(jì)算時(shí)，關(guān)注的通常不是那些不存在的數(shù)據(jù)，不會(huì)去比較眾多的0值，相反關(guān)注的是現(xiàn)有數(shù)據(jù)，并對其進(jìn)行比較。

3 算法的實(shí)現(xiàn)及結(jié)果分析

本文中算法實(shí)現(xiàn)的目標(biāo)是生成如下形式的規(guī)則：如果用戶喜歡某些電影，那么該用戶也會(huì)喜歡這部電影。作為對上述規(guī)則的擴(kuò)展，還將討論喜歡某幾部電影的用戶，是否喜歡另一部電影。為此創(chuàng)建新特征 Favorable ，若用戶喜歡該電影，值為 True 。

在數(shù)據(jù)集中看一下這個(gè)新特征。all_ratings[10：15]，得出結(jié)果見表2。

從數(shù)據(jù)集中選取一部分?jǐn)?shù)據(jù)用作訓(xùn)練集，這能有效減少搜索空間，提升Apriori算法的速度。接下來，新建一個(gè)數(shù)據(jù)集，只包括用戶喜歡某部電影的數(shù)據(jù)行。在生成項(xiàng)集時(shí)，需要知道每個(gè)用戶各喜歡哪些電影，按照User ID進(jìn)行分組，并遍歷每個(gè)用戶看過的每一部電影。

favorable_reviews_by_users=dict（（k，frozenset（v.values））

for k，v in favorable_ratings

groupby（"UserID"）["MovieID"]）

上面把 v.values 存儲(chǔ)為 frozenset ，便于快速判斷用戶是否為某部電影打過分。對于這種操作，集合比列表速度快，在后面還會(huì)用到。最后，創(chuàng)建一個(gè)數(shù)據(jù)框，以便了解每部電影的影迷數(shù)量。查看最受歡迎的5部電影， 輸出結(jié)果見表3。

3.1 Apriori算法過程

Apriori算法是親和性分析的一部分，專門用于查找數(shù)據(jù)集中的頻繁項(xiàng)集?；玖鞒淌菑那耙徊秸业降念l繁項(xiàng)集中找到新的備選集合，接著檢測備選集合的頻繁程度是否夠高，算法迭代步驟如下：

（1）把各項(xiàng)目放到只包含自己的項(xiàng)集中，生成最初的頻繁項(xiàng)集。只使用達(dá)到最小支持度的項(xiàng)目。

（2）查找現(xiàn)有頻繁項(xiàng)集的超集，發(fā)現(xiàn)新的頻繁項(xiàng)集，并用其生成新的備選項(xiàng)集。

（3）測試新生成的備選項(xiàng)集的頻繁程度，如果不夠頻繁，則舍棄。如果沒有新的頻繁項(xiàng)集，跳到最后一步。

（4）存儲(chǔ)新發(fā)現(xiàn)的頻繁項(xiàng)集，返回步驟（2）。

（5）返回發(fā)現(xiàn)的所有頻繁項(xiàng)集。

整個(gè)過程如圖1所示。

3.2 算法實(shí)現(xiàn)

Apriori算法在進(jìn)行第一次迭代后，可以找到的項(xiàng)集長度為2，是步驟（1）中創(chuàng)建的項(xiàng)集的超集。第二次迭代（經(jīng)過步驟（4））中，新發(fā)現(xiàn)的項(xiàng)集長度為3。這有助于快速識別步驟（2）所需的項(xiàng)集。把發(fā)現(xiàn)的頻繁項(xiàng)集保存到以項(xiàng)集長度為鍵的字典中，便于根據(jù)長度查找，這樣就可以找到最新發(fā)現(xiàn)的頻繁項(xiàng)集。下面的代碼初始化一個(gè)字典。

還需要確定項(xiàng)集要成為頻繁項(xiàng)集所需的最小支持度。這個(gè)值需要根據(jù)數(shù)據(jù)集的具體情況來設(shè)定，可自行嘗試其它值，建議每次僅改動(dòng)10個(gè)百分點(diǎn)，即使這樣也會(huì)使算法運(yùn)行時(shí)間變動(dòng)很大！設(shè)置最小支持度。

先來實(shí)現(xiàn)Apriori算法的第一步，為每一部電影生成只包含其自己的項(xiàng)集，檢測其是否夠頻繁。電影編號使用 frozenset。此外，也可以用作字典的鍵（普通集合不可以）。

接著，用一個(gè)函數(shù)來實(shí)現(xiàn)步驟（2）和（3），其接收新發(fā)現(xiàn)的頻繁項(xiàng)集，創(chuàng)建超集，檢測頻繁程度。通過函數(shù)聲明及字典初始化代碼。

通過以往數(shù)據(jù)結(jié)果，要盡量減少遍歷數(shù)據(jù)的次數(shù)，因此每次調(diào)用函數(shù)時(shí)，再遍歷數(shù)據(jù)。這樣做效果不是很明顯（因?yàn)閿?shù)據(jù)集相對較?。?，但是數(shù)據(jù)集較大的情況下，就很有必要。

接下來，以確定當(dāng)前評分項(xiàng)集的子集為判斷的依據(jù)來遍歷之前找到的項(xiàng)集。 如果是，則表示用戶已經(jīng)評過了子集中的電影；遍歷用戶已評過但不出現(xiàn)在項(xiàng)目集中的影片，使用其來生成超集并更新項(xiàng)目集的計(jì)數(shù)。

函數(shù)最后檢測達(dá)到支持度要求的項(xiàng)集，判斷頻繁程度是否滿足，并返回其中的頻繁項(xiàng)集。創(chuàng)建循環(huán)，運(yùn)行Apriori算法，存儲(chǔ)算法運(yùn)行過程中發(fā)現(xiàn)的新項(xiàng)集。循環(huán)體中，k表示即將發(fā)現(xiàn)的頻繁項(xiàng)集的長度，用鍵k1可以從 frequent_itemsets 字典中獲取剛發(fā)現(xiàn)的頻繁項(xiàng)集。新發(fā)現(xiàn)的頻繁項(xiàng)集以長度為鍵，將其保存到字典中。如果在上述循環(huán)中沒能找到任何新的頻繁項(xiàng)集，就跳出循環(huán)（輸出信息，告知沒能找到長度為k的頻繁項(xiàng)集）

如果找到頻繁項(xiàng)集，程序輸出信息，告知會(huì)再次運(yùn)行。因?yàn)樗惴ㄟ\(yùn)行時(shí)間很長，所以每隔一段時(shí)間輸出一下狀態(tài)是很有必要的。最后，循環(huán)結(jié)束，對只有一個(gè)元素的項(xiàng)集不再保留，刪除長度為1的項(xiàng)集。

最后返回了不同長度的1 718個(gè)頻繁項(xiàng)集。會(huì)發(fā)現(xiàn)隨著項(xiàng)集長度的增加，項(xiàng)集數(shù)隨著可用規(guī)則的增加而增長一段時(shí)間后才開始變少，減少是因?yàn)轫?xiàng)集達(dá)不到最低支持度要求。項(xiàng)集的減少是Apriori算法的優(yōu)點(diǎn)之一。如果搜索所有可能的項(xiàng)集（不只是頻繁項(xiàng)集的超集），判斷多余項(xiàng)集的頻繁程度需要成千上萬次查詢。

3.3 抽取關(guān)聯(lián)規(guī)則

Apriori算法結(jié)束后，得到了一系列頻繁項(xiàng)集，這還不是真正意義上的關(guān)聯(lián)規(guī)則，。頻繁項(xiàng)集是一組達(dá)到最小支持度的項(xiàng)目，而關(guān)聯(lián)規(guī)則由前提和結(jié)論組成?？梢詮念l繁項(xiàng)集中抽取出關(guān)聯(lián)規(guī)則，把其中幾部電影作為前提，另一部電影作為結(jié)論組成如下形式的規(guī)則：如果用戶喜歡前提中的所有電影，那么也會(huì)喜歡結(jié)論中的電影。

每一個(gè)項(xiàng)集都可用這種方式生成一條規(guī)則。通過遍歷不同長度的頻繁項(xiàng)集，為每個(gè)項(xiàng)集生成規(guī)則。然后，遍歷項(xiàng)集中的每一部電影，把其作為結(jié)論。項(xiàng)集中的其它電影作為前提，用前提和結(jié)論組成備選規(guī)則。這樣就能得到大量備選規(guī)則。

通過查看前5條規(guī)則。得出如下結(jié)果：

[（frozenset（{79}）， 258）， （frozenset（{258}）， 79）， （frozenset（{50}）， 64）， （frozenset（{64}）， 50）， （frozenset（{127}）， 181）]

在上述這些規(guī)則中，第一部分（ frozenset ）是作為規(guī)則前提的電影編號，后面的數(shù)字表示作為結(jié)論的電影編號。第一組數(shù)據(jù)表示如果用戶喜歡電影79，那很可能喜歡電影258。接下來，計(jì)算每條規(guī)則的置信度。需要先創(chuàng)建2個(gè)字典，用來存儲(chǔ)規(guī)則應(yīng)驗(yàn)（正例）和規(guī)則不適用（反例）的次數(shù)。代碼如下：

correct_counts = defaultdict（int）；incorrect_counts = defaultdict（int）

遍歷所有用戶及其喜歡的電影數(shù)據(jù)，在這個(gè)過程中遍歷每條關(guān)聯(lián)規(guī)則。測試每條規(guī)則的前提對用戶是否適用。如果前提符合，看一下用戶是否喜歡結(jié)論中的電影。如果是的話，規(guī)則適用，反之，規(guī)則不適用。用規(guī)則應(yīng)驗(yàn)的次數(shù)除以前提條件出現(xiàn)的總次數(shù)，計(jì)算每條規(guī)則的置信度。結(jié)果如下：

3.4 評估分析

首先，抽取所有沒有用于訓(xùn)練的數(shù)據(jù)作為測試集。訓(xùn)練集采用前200名用戶的打分?jǐn)?shù)據(jù)，其余作為測試集的數(shù)據(jù)。就訓(xùn)練集來說，會(huì)為該數(shù)據(jù)集中的每一位用戶獲取最喜歡的電影。，方法跟之前相似。唯一的不同就是這次使用的是測試數(shù)據(jù)而不是訓(xùn)練數(shù)據(jù)。接下來，計(jì)算所有應(yīng)驗(yàn)規(guī)則的置信度。最后輸出用電影名稱而不是電影編號表示的最佳關(guān)聯(lián)規(guī)則。代碼如下：

從以上實(shí)驗(yàn)結(jié)果的數(shù)據(jù)中可以得出，基于第二條規(guī)則，在訓(xùn)練集中置信度為1，但在測試集上正確率只有60%。但前10條規(guī)則中，其它幾條規(guī)則在測試集上置信度也很高，所以實(shí)驗(yàn)結(jié)果表明用Apriori算法來推薦電影效果不錯(cuò)。

4 結(jié)束語

本文把親和性分析中的Apriori算法用到電影推薦上，從大量電影打分?jǐn)?shù)據(jù)中找到可用于電影推薦的關(guān)聯(lián)規(guī)則。借助Apriori算法尋找數(shù)據(jù)中的頻繁項(xiàng)集。不難看出，在數(shù)據(jù)挖掘中：雖然解決該問題可以用一些更笨的方法如層次分析法，但通過該算法較大的改善了由于時(shí)間復(fù)雜度呈指數(shù)級增長出現(xiàn)的問題。不過該算法離大規(guī)模數(shù)據(jù)集中的應(yīng)用仍需要較大的改進(jìn)，所以進(jìn)一步的研究方向?qū)?huì)放在如何在更小的時(shí)間復(fù)雜度內(nèi)更好提升Apriori算法的精度。同時(shí)已存在的較大改進(jìn)空間及應(yīng)用范圍，如結(jié)合 Apriori的性質(zhì)，提出的VGApriori（Vector-Graph Apriori） 算法是基于位向量和無向圖的或基于數(shù)據(jù)庫及其屬性列DPApriori-N算法。

參考文獻(xiàn)

[1] HAN J W，KAMBER M，PEI J. 數(shù)據(jù)挖掘： 概念與技術(shù)[M]. 3版. 范明， 孟小峰， 譯.北京： 機(jī)械工業(yè)出版社， 2012.

[2] AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in very large databases[C]//Proceedings of the ACM SIGMOD Conference on Management of Data. Washington D C， USA： ACM， 1993： 207-216.

[3] 劉獨(dú)玉， 楊晉浩， 鐘守銘. 關(guān)聯(lián)規(guī)則挖掘研究綜述[J]. 成都大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2006， 25（1）： 54-58.

[4] HILLS J， BAGNALL A， IGLESIA B D L， et al. BruteSuppression：A size reduction method for Apriori rule sets [J]. Journal of Intelligent Information Systems， 2013，40（3） ： 431-454.

[5] 張宗郁， 張亞平， 張靜遠(yuǎn)，等. 改進(jìn)關(guān)聯(lián)規(guī)則算法在高校教學(xué)管理中的應(yīng)用[J]. 計(jì) 算 機(jī) 工 程， 2012， 38（2）： 75-77，81.

[6] 胡志偉. 增量關(guān)聯(lián)規(guī)則算法在手機(jī)病毒挖掘中的應(yīng)用研究與實(shí)現(xiàn)[D]. 北京：北京郵電大學(xué)， 2012.

[7] 邵佳煒. 基于關(guān)聯(lián)矩陣和學(xué)習(xí)自動(dòng)機(jī)的電影推薦研究[J]. 電腦知識與技術(shù) ， 2012， 8（8）： 1721-1722.