基于關聯規則挖掘的Apriori改進算法

白瑩瑩++申晨晨

摘 要關聯規則挖掘是數據挖掘技術的一個重要分支，其中Apriori算法是最經典和最有影響力的算法。本文在討論和分析了關聯規則挖掘的基本概念后，提出了一種減少掃描數據庫次數的改進算法。改進后的算法分析證明，它可以有效地提高數據挖掘的性能。

【關鍵詞】關聯規則挖掘 數據挖掘 Apriori算法

數據挖掘是從大量數據中挖掘有趣模式和知識的過程，數據源包括數據庫、數據倉庫、Web、其他信息存儲庫或動態地流入系統的數據 ?，F今計算機技術與數據庫技術在飛速地發展，如何從海量的數據中快速準確地找出有用的信息是數據挖掘問題中的一項重要研究內容。

在1994年，由Agrawal提出的Apriori算法，是關聯規則里的一項基本算法，它的基本思想是重復掃描數據庫，由長度為k的頻繁項集進行迭代計算產生長度為k+1的候選集，再對數據庫進行掃描判斷其是否為頻繁項集。

在過往的研究當中，許多文獻提出了基于Apriori算法的改進。林佳雄等人提出的基于數組向量的Apriori算法改進 ，該算法改進了連接比較的次數、減少不必要事務的掃描和提高了算法對內存空間的利用效率。曹瑩等人提出的基于向量矩陣優化頻繁項的改進Apriori算法 ，趙學健等人的一種正交鏈表存儲的改進Apriori算法，該算法Apriori算法復雜的自連接和剪枝過程進行了優化，簡化了頻繁項目集的生成過程，提高了Apriori算法的時間效率 。

1 關聯規則挖掘的概況

關聯規則挖掘是數據挖掘中的一個很重要的課題，顧名思義，它是從數據背后發現事物之間可能存在的關聯或者聯系。最早是為了發現超市交易數據庫中不同的商品之間的關系。目的在于發現數據項之間的潛在關系，通過它提取出的信息將有助于人們把握和預測行業發展規律，從而更好地制定發展計劃和規避風險。

那么問題如下所述：假設I={i1，i2，...im}是所有項目的集合，D是一個數據庫，事務T是一個子項（TI）。每個T都有自己獨特的標識 。A是由項目組成的集合，即項集。T包含A，當且僅當AT。如果項集A的項目數為k，則稱為k維項目集。項集A的出現頻率是包含項集的事務數，簡稱為項集的支持度。如果項集支持度超過由用戶給定的最小支持度閾值，則稱為頻繁項集，簡稱頻繁集。

關聯規則是形如的蘊涵式，其中，X稱為關聯規則的先導，Y稱為后繼。其中，關聯規則X與Y存在支持度和置信度。關聯規則在D中的支持度（support）是D中事務同時包含X和Y的百分比，即概率。置信度（confidence）是D中事務已經包含X的情況下，包含Y的百分比，即條件概率。如果滿足最小支持度閾值和最小置信度閾值，則認為關聯規則是有趣的。

2 Apriori算法

2.1 核心思想

最著名的關聯規則挖掘算法是Apriori算法，它是一種以概率為基礎的關聯規則算法，能實現從少到多，從簡單到復雜尋找極大頻繁集。Apriori算法主要利用了向下封閉屬性：如果一個項集是頻繁項目集，那么它的非空子集必定是頻繁項目集。在運算過程中首先生成1-頻繁項目集，再利用1-頻繁項目集生成2-頻繁項目集，然后根據2-頻繁項目集生成3-頻繁項目集，依次類推，直至生成所有的頻繁項目集。最后從頻繁項目集中找出符合條件的關聯規則。

2.2 算法過程

Apriori算法采用遞推的方法來生成所需的頻繁集，主要步驟如下：

（1）制定最小支持度及最小置信度；

（2）Apriori算法使用了候選項集的概念，通過掃描數據庫產生候選項目集，如果候選項目集的支持度不小于最小支持度，則該候選項目集為頻繁項目集；

（3）從數據庫中讀入所有事務數據，得出候選1項集C1及相應的支持度數據，通過將每個1項集的支持度與最小支持度比較，得出頻繁項集合L1，然后將這些頻繁1項集兩兩連接，產生候選2項集和C2；

（4）然后再次掃描數據庫得到候選2項集合C2的支持度，將2項集的支持度與最小支持度比較，確定頻繁2項集。類似地，利用這些頻繁2項集L2產生候選3項集和確定頻繁3項集，以此類推；

（5）反復掃描數據庫，與最小支持度比較，產生更高項的頻繁項集合，再結合產生下一級候選項集，直到不再產生出新的候選項集為止；

3 Apriori算法的改進及分析

3.1 改進算法的思想

關聯規則是其支持度和置信度分別滿足用戶給定閾值的規則，發現關聯規則需要如下兩步驟：

（1）找出所有的頻繁集，其最后出現的頻率和預定義的最小支持度是相同的。

（2）強關聯規則是由頻繁集產生的，它必須滿足最小支持度和最小置信度。

但是Apriori算法由于需要多次掃描數據庫，而造成過重的I/0負擔，因此改進算法將通過減少數據庫掃描次數的方式來減輕I/0負擔。

改進算法的思想就是利用頻繁k+1項集中的任一元素，一定可以表示成頻繁k項集中某一元素與頻繁1項集中某一元素的交集這一性質來產生頻繁集，從而減少掃描數據庫的次數。

改進算法先對事務數據庫進行掃描，得到1項集L1={l1，l2，...，ln}，對1項集L1進行剪枝，得到頻繁1項集M1={l|cardl≥sup且l∈L1}，然后由頻繁1項集M1中元素求得2項集L2={l|l=li∪lj，li∈M1且i≠j}，對L2進行剪枝得到頻繁2項集M2={l|cardl≥sup且l∈L2}，再由M2中元素與M1中元素產生3項集L3，通過剪枝得到頻繁3項集M3，以此類推，可求得頻繁k項集Mk，直到頻繁k項集中項數小于k，則由性質2可知，頻繁k項集Mk無法產生頻繁k+1項集，迭代停止。

3.2 改進算法分析

根據上面改進的算法，對該算法進行分析。表1為事務數據庫，設最小支持度為20%，則最小支持度計數等于2。

從表1中可知：i1={D1， D4， D5， D6， D7， D8， D9}，i2={D1， D2， D3， D4， D8， D9， D10}，i3={D3， D5， D6， D7， D8， D9}，i4={D2， D4， D10}，i5={D1， D9}，所以M1={i1，i2，i3，i4，i5}，利用頻繁1項集M1，可以生產C25個2項集，i1={D1， D2， D3， D4， D5， D6， D7， D8， D9}

即：L2={l12， l13， l14， l15， l23， l24， l25， l34，l35，l45}，l12={D1，D4，D7，D8}，l13={D5，D6，D7，D8，D9}，l14={D4}，l15={D1，D8}，l23={D3，D8，D9}，l24={D2，D4，D10}，l25={D1，D8}，l35={D8}，l34=l35=φ。

對2項集進行剪枝，可得到頻繁2項集M2={l12， l13， l15， l23， l24， l25}。利用頻繁2項集M2與頻繁1項集M1，可以得到頻繁3項集M3={l123， l125}。

根據頻繁項集的性質2，頻繁項集M3中的項數為2，其無法產生頻繁4項集，因此迭代停止。計算結果見表2。

3.3 實驗與分析

實驗所用到的數據選用本校教職工的一次調查問卷，數據庫中共有1694條記錄，用來證明文中的改進算法具有有效性。我們把它與Apriori算法進行比較，部分記錄如表3所示。由于在這次調查中，教師只需要在36個選項中，選出最符合自己意愿的某幾個選項，因此數據的存儲采用簡單二維表，可以節省存儲空間。

圖1是改進算法與Apriori經典算法在不同支持度下執行時間對比。

由圖1可以看出，改進算法在效率上優于Apriori算法，并且在最小支持度較小時，改進算法的執行時間相對于Apriori算法具有明顯優勢，但是隨著最小支持度的增加，兩種算法的執行時間均大幅減少，Apriori算法與改進算法的執行時間開銷非常接近，這是因為隨著最小支持度的增加，迭代次數減少，運算過程中產生的頻繁項集的數量均大幅度減少，使得算法的執行時間減少。

4 結論與思考

由于Apriori算法多次掃描事務數據庫，需要很大的I/O負載，因此在改進的算法中，以項集中存在的集合數量與最小支持度計數進行對比，進而判斷其是否為頻繁項集，這樣就不用對數據庫進行多次掃描。雖然改進算法減少了I/0次數，提高了算法的執行效率，但是算法在執行過程中，由于需要保存大量的數據，而需要占用較多的內存空間，因此如何對數據量較大的數據庫執行本算法，還有待進一步的研究與改進。

參考文獻

[1]Han J.W.，Kamber M.Data Mining：Concepts and Techniques，數據挖掘：概念與技術[M].范明，孟小峰等譯.北京：機械工業出版社，2001.

[2]林佳雄，黃戰.基于數組向量的Apriori算法改進[J].計算機應用與軟件，2011（05）：248.

[3]曹瑩，苗志剛.基于向量矩陣優化頻繁項的改進Apriori算法[J].吉林大學學報，2016（02）：349.

[4]趙學健，孫知信，袁源，陳勇.一種正交鏈表存儲的改進Apriori算法[J].計算機技術與發展，2016（10）：2291.

[5]朱惠.關聯規則中Apriori算法的研究與改進[D].安徽：安徽理工學，2014.

[6]朱翼.基于數組的Apriori算法的改進研究[D].哈爾濱：哈爾濱師范學，2014.

作者簡介

白瑩瑩（1992-）女，陜西省寶雞市人。工作于西安工程大學計算機科學學院。主要研究方向為智能信息處理。

申晨晨（1993-）男，安徽省阜陽市人。工作于西安工程大學計算機科學學院。主要研究方向為系統仿真與系統控制。

作者單位

西安工程大學計算機科學學院 陜西省西安市710048