基于關(guān)聯(lián)規(guī)則挖掘的Apriori改進算法

白瑩瑩++申晨晨

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

【關(guān)鍵詞】關(guān)聯(lián)規(guī)則挖掘 數(shù)據(jù)挖掘 Apriori算法

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

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

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

1 關(guān)聯(lián)規(guī)則挖掘的概況

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

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

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

2 Apriori算法

2.1 核心思想

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

2.2 算法過程

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

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

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

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

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

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

3 Apriori算法的改進及分析

3.1 改進算法的思想

關(guān)聯(lián)規(guī)則是其支持度和置信度分別滿足用戶給定閾值的規(guī)則，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要如下兩步驟：

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

（2）強關(guān)聯(lián)規(guī)則是由頻繁集產(chǎn)生的，它必須滿足最小支持度和最小置信度。

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

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

改進算法先對事務數(shù)據(jù)庫進行掃描，得到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中元素產(chǎn)生3項集L3，通過剪枝得到頻繁3項集M3，以此類推，可求得頻繁k項集Mk，直到頻繁k項集中項數(shù)小于k，則由性質(zhì)2可知，頻繁k項集Mk無法產(chǎn)生頻繁k+1項集，迭代停止。

3.2 改進算法分析

根據(jù)上面改進的算法，對該算法進行分析。表1為事務數(shù)據(jù)庫，設最小支持度為20%，則最小支持度計數(shù)等于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，可以生產(chǎn)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}。

根據(jù)頻繁項集的性質(zhì)2，頻繁項集M3中的項數(shù)為2，其無法產(chǎn)生頻繁4項集，因此迭代停止。計算結(jié)果見表2。

3.3 實驗與分析

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

圖1是改進算法與Apriori經(jīng)典算法在不同支持度下執(zhí)行時間對比。

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

4 結(jié)論與思考

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

參考文獻

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

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

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

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

[5]朱惠.關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進[D].安徽：安徽理工學，2014.

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

作者簡介

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

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

作者單位

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