Apriori算法在大數據集上的高效應用

陳邦豪

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

關鍵詞：Apriori算法； 數據挖掘； 電影推薦； 大數據集

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

引言

產品推薦是一項在大數據集中進行應用的重要技術。如網上商店經常基于此來向潛在用戶推薦潛在的產品。 而一個好的建議算法可以帶來更高的銷售業績，據統計每年至少有上億用戶網上購買，通過向人們推薦更多產品，有著更為可觀的潛在收益。

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

1 相關介紹

1.1 Apriori算法簡述

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

1.2 選擇參數

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

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

找出頻繁項集后，根據置信度選取關聯規則。可以設定最小置信度，返回一部分規則，或者返回所有規則，讓用戶自己選。本文中設定最小置信度，只返回高于其規則。置信度過低將會導致規則支持度高，正確率低；置信度過高，導致正確率高，但是返回的規則少。

2 算法應用

2.1 獲取數據集

在網上下載包含100萬條數據的MovieLens數據集。在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 加載數據

MovieLens數據集非常規整，但是有幾點跟 pandas.read_csv 方法的默認設置有出入，所以要調整參數設置。數據集每行的幾個數據之間用制表符而不是逗號分隔。其次，沒有表頭，這表示數據集的第一行就是數據部分。

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

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]

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

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

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

在對稀疏矩陣進行計算時，關注的通常不是那些不存在的數據，不會去比較眾多的0值，相反關注的是現有數據，并對其進行比較。

3 算法的實現及結果分析

本文中算法實現的目標是生成如下形式的規則：如果用戶喜歡某些電影，那么該用戶也會喜歡這部電影。作為對上述規則的擴展，還將討論喜歡某幾部電影的用戶，是否喜歡另一部電影。為此創建新特征 Favorable ，若用戶喜歡該電影，值為 True 。

在數據集中看一下這個新特征。all_ratings[10：15]，得出結果見表2。

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

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

for k，v in favorable_ratings

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

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

3.1 Apriori算法過程

Apriori算法是親和性分析的一部分，專門用于查找數據集中的頻繁項集。基本流程是從前一步找到的頻繁項集中找到新的備選集合，接著檢測備選集合的頻繁程度是否夠高，算法迭代步驟如下：

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

（2）查找現有頻繁項集的超集，發現新的頻繁項集，并用其生成新的備選項集。

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

（4）存儲新發現的頻繁項集，返回步驟（2）。

（5）返回發現的所有頻繁項集。

整個過程如圖1所示。

3.2 算法實現

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

還需要確定項集要成為頻繁項集所需的最小支持度。這個值需要根據數據集的具體情況來設定，可自行嘗試其它值，建議每次僅改動10個百分點，即使這樣也會使算法運行時間變動很大！設置最小支持度。

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

接著，用一個函數來實現步驟（2）和（3），其接收新發現的頻繁項集，創建超集，檢測頻繁程度。通過函數聲明及字典初始化代碼。

通過以往數據結果，要盡量減少遍歷數據的次數，因此每次調用函數時，再遍歷數據。這樣做效果不是很明顯（因為數據集相對較小），但是數據集較大的情況下，就很有必要。

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

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

如果找到頻繁項集，程序輸出信息，告知會再次運行。因為算法運行時間很長，所以每隔一段時間輸出一下狀態是很有必要的。最后，循環結束，對只有一個元素的項集不再保留，刪除長度為1的項集。

最后返回了不同長度的1 718個頻繁項集。會發現隨著項集長度的增加，項集數隨著可用規則的增加而增長一段時間后才開始變少，減少是因為項集達不到最低支持度要求。項集的減少是Apriori算法的優點之一。如果搜索所有可能的項集（不只是頻繁項集的超集），判斷多余項集的頻繁程度需要成千上萬次查詢。

3.3 抽取關聯規則

Apriori算法結束后，得到了一系列頻繁項集，這還不是真正意義上的關聯規則，。頻繁項集是一組達到最小支持度的項目，而關聯規則由前提和結論組成。可以從頻繁項集中抽取出關聯規則，把其中幾部電影作為前提，另一部電影作為結論組成如下形式的規則：如果用戶喜歡前提中的所有電影，那么也會喜歡結論中的電影。

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

通過查看前5條規則。得出如下結果：

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

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

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

遍歷所有用戶及其喜歡的電影數據，在這個過程中遍歷每條關聯規則。測試每條規則的前提對用戶是否適用。如果前提符合，看一下用戶是否喜歡結論中的電影。如果是的話，規則適用，反之，規則不適用。用規則應驗的次數除以前提條件出現的總次數，計算每條規則的置信度。結果如下：

3.4 評估分析

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

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

4 結束語

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

參考文獻

[1] HAN J W，KAMBER M，PEI J. 數據挖掘： 概念與技術[M]. 3版. 范明， 孟小峰， 譯.北京： 機械工業出版社， 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] 劉獨玉， 楊晉浩， 鐘守銘. 關聯規則挖掘研究綜述[J]. 成都大學學報： 自然科學版， 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] 張宗郁， 張亞平， 張靜遠，等. 改進關聯規則算法在高校教學管理中的應用[J]. 計 算 機 工 程， 2012， 38（2）： 75-77，81.

[6] 胡志偉. 增量關聯規則算法在手機病毒挖掘中的應用研究與實現[D]. 北京：北京郵電大學， 2012.

[7] 邵佳煒. 基于關聯矩陣和學習自動機的電影推薦研究[J]. 電腦知識與技術 ， 2012， 8（8）： 1721-1722.