基于關聯規則的Apriori改進算法的研究綜述

彭新宇 李叢煊 郭金盈 赫彥文

摘要：關聯規則挖掘是數據挖掘的重要技術之一，Apriori算法作為關聯規則的基本算法，簡單、易理解、數據要求低，但是存在效率低的問題，效率低的原因有兩點，Apriori算法1/0負載較大且會產生龐大的候選集，一些研究人員針對這些問題提出了等轉換數據存儲方式、減少掃描數據庫次數等改進方法，由此介紹近幾年研究人員對Apriori改進算法的研究概況，并對關聯規則的Apriori算法未來的研究方向進行了探討。

關鍵詞：大數據;數據挖掘;關聯規則;Apriori算法改進

中圖分類號：TP3

文獻標識碼：A

文章編號：1009-3044（2019）34-0216-02

數據挖掘一般是指從大量的數據中挖掘隱藏于其中的有著特殊關系性。關聯規則為數據挖掘的重要技術，該技術通過大型關系數據集中發現數據項之間的相關性。關聯規則的挖掘過程分為兩個階段：第一個階段從大量的數據集中選出達到要求的候選項集合，第二個階段從候選項集合中發現符合要求的頻繁項集，最終便得到有關聯的項集并產生關聯規則，在核心思想的指導下，Apriori算法應運而生，Apriori算法是一種發現頻繁項集的基本算法，這個算法存在兩個方面的問題，一個方面是多次掃描事務數據庫，1/0負載很高，另一個方面生成候選集時，候選集的數量呈指數式增長，是可能生成龐大的候選集[1]，因此Apriori算法存在進步的空間，基于以上背景，國內外的許多研究人員提出了Apriori改進算法并將改進算法投入到應用中，改進包括對算法、數據、平臺等方式的改進，接下來會對Apriori算法不同改進方式的研究概況進行介紹。

1 基于Apriori算法本身的改進，減少掃描次數

為解決需要頻繁掃描事務集的問題，有的研究人員也采用了基于累加數組的方法來獲得頻繁項集，該方法根據事務集生成一維數組，在生成數組的同時就能統計出支持度并生成頻繁l一項集（1]，任意兩兩頻繁1-項集的數組，對應項做累加求和運算得到候選集L2，統計出支持度并生成2-項集，對上述過程迭代循環，最終得到符合要求的所有頻繁項集。改進算法只需要掃描事務集一次，通過建模公式減少了剪枝這個步驟，通過公式計算的方式減少了候選項集。

Apriori算法中掃描數據庫計數部分所占時間比例最大，其次是項集連接和篩選剪枝，故優先減少掃描計數在整個算法中的時間開銷，有的研究人員在改進算法中對計算候選項集支持度的部分做出改進，掃描計數階段的時間復雜度增加了一個變量，變量和迭代次數成反比關系，即隨著迭代次數的增加，目標事務在事務數據庫中所占的比例越來越小，時間復雜度隨之下降[2]。稀疏型數據中，變量的下降速度會非?？?，因此處理稀疏型數據的效果較好。

2 轉換存儲方式的改進

2.1 基于前綴項集的存儲方式改進

Apriori算法不斷進行查找進行連接，浪費了大量時間，查找效率低，因此有研究人員提出利用哈希表可以快速查找的特性，采用前綴項集的存儲方式來提高算法中生成候選集與頻繁項集的查找效率[3]，對于數據項集，采用類似Map結構的哈希表來保存，生成候選集Ln時，其中key代表前綴n-l項的數據值，value代表第n項數據值，在連接步中，對有相同前綴的value值中任意兩個項進行合并，即可得到新的候選集，在剪枝步中，因頻繁項集的子集也必須是頻繁項集，故只考慮（k+1）一項候選集中同時包含用于連接的兩個k一項集尾項的可能的k一項子集即可，再遍歷原始數據庫，找出滿足最小支持度的頻繁項集，該過程進行迭代即可得到最終的關聯項集，該存儲方式使得在連接步驟和剪枝步驟的運行時間有了很大程度的降低。

2.2 基于矩陣的存儲方式改進

基于矩陣的Apriori算法也是對數據存儲方式的改進，該算法將事務數據庫D轉換為矩陣。每一事務以矩陣的行來表示即行維度，事務中的項用列來表示即列維度，當要對數據進行挖掘時就可以直接調用轉換為矩陣中的信息[4]，在行列指定的位置處若存在數據則為1，否則記為0，修改矩陣中對應位置的頻次，計算出各項的支持度得到候選集，刪除事務長度小于最小置信度的事務對應的行與列。免去了對D再次掃描的過程，節省了1/0的開銷和時間。在基于矩陣的Apriori算法上，有的研究人員進一步進行改進，將矩陣看成是行向量的集合，根據向量的操作規則，在矩陣中只需要使用“與”操作就可以快速地產生項目集的支持頻度[4]，這兩種基于矩陣的改進算法都只需對事務數據庫掃描兩次，但前者會產生大量臨時鍵值對，后者臨時鍵值對較少，高效利用了并行化，更好地提高了算法的效率。

3 基于減少數據的改進

對于指定行業的數據挖掘關聯規則算法改進，例如醫院的大數據等，有明顯的行業數據特點，根據行業的數據特點與屬性產生關聯規則，對信息進行提取，確定醫療大數據中項集間的關聯關系，同樣能提高醫療大數據預處理的水平[5]。

對大批量的原始數據集首先進行清洗，清除無效、噪音數據，使得原始數據得到一定程度的減少并結合數據挖掘的分類方法[6]，采用決策樹的分類算法對原始數據集進行分類，為數據找到一種準確的模型進行分塊處理，從分層的大量數據隨機抽取樣本，從每層數據中抽取出簡單隨機均值方差為指定值的樣本作為數據集，將數據分為多塊，對每一塊的數據集掃描出每塊的頻繁項集，集合所有的局部頻繁項集，掃描一次頻繁項集，構成候選項集得到頻繁項集，從頻繁項集中獲取關聯規則，從中得到有價值的關聯規則。

4 基于平臺與編程模型的改進

有的研究人員針對關聯規則挖掘1/0負載嚴重與內存受限的問題，提出利用Hadoop平臺編程模型MapReduce實現并行化的方法來改進關聯規則算法[7]，Hadoop平臺具有可靠性、擴展性、高效性、容錯性等優點，MapReduce是對大規模數據進行并行計算的一種編程模型和計算框架，封裝了并行處理、數據分布、負載均衡等復雜的細節，在Hadoop平臺上運行MapRe-duce程序時，若某一個節點計算失敗，Hadoop系統會把它的計算任務重新分配到其他計算節點，利用Map0和Reduce0來從海量數據中快速尋找出頻繁項集，在Map階段主要利用k-l項頻繁項集的連接操作得出候選項集，計算其讀取的部分數據中的k項候選集的支持數，在Reduce階段主要將相同key的值合并，并且進行剪枝操作，篩選符合要求的頻繁項集，通過k次迭代計算頻繁項目集。由頻繁項集生成關聯規則，使Apriori算法處理海量數據不再受到單機運算能力的限制。

但是上述改進辦法仍存在一些缺陷，MapReduce編程框架只能保存到Hadoop分布式文件系統中，每次提交計算任務時都需重啟資源，MapReduce編程框架不適合多次迭代，需要多次遍歷原始數據集，僅考慮了頻繁項集的計算并未考慮強關聯規則的挖掘，因此有的研究人員基于以上的研究做出了進一步的改進，針對之前的研究未將強關聯規則的挖掘考慮的問題提出了解決方法，將頻繁項目集數據導人支持高速讀取的Redis數據庫中，從而實時獲取任何頻繁項集支持度嘲，該改進方式更適用于大型的數據集。

Spark是對早前Map-Reduce編程框架的擴展，相較于Ma-pReduce，Spark機制對處理大數據集以及數據迭代更具有優勢，基于Spark的性能優勢，有的研究人員利用分布式框架Spark解決單機內存資源限制、性能缺陷的問題[9]，增強了強關聯規則挖掘時數據的實時性，從整體上提高了關聯規則挖掘的效率。

5 總結

從上述的改進方式可以看出，對Apriori算法的改進由原來對算法本身的改進逐步轉變為對數據集的存儲方式的改進，并利用一些框架進行提升效率，這些改進使得Apriori算法的效率大幅度提升，接下來的研究方向可能轉向與其他算法、技術的融合或各種改進方式綜合使用，例如利用平臺的優勢.結合遺傳、分類等算法對Apriori算法進行改進提升，Apriori算法是否還有上升進步的空間，我們拭目以待。

參考文獻：

[1]陳維興，曲睿，孫毅剛，基于改進Apriori算法的地面空調間歇故障預測[J].計算機應用，2016，36（12）：3505-3510.

[2]徐開勇，龔雪容，成茂才.基于改進Apriori算法的審計日志關聯規則挖掘[J].計算機應用，2016，36（07）：1847-1851.

[3]于守健，周羿陽.基于前綴項集的Apriori算法改進[J]，計算機應用與軟件，2017，34（02）：290-294.

[4]謝志明，王鵬.基于MapReduce架構的并行矩陣Apriori算法[J].計算機應用研究，2017，34（02）：401-404.

[5]岳根霞.基于關聯規則的醫療大數據挖掘算法[J].微電子學與計算機，2019，36（04）：105-108.

[6]朱付保，白慶春，湯萌萌，等.基于改進Apriori算法的鐵路軌道質量分析與評價[J].微電子學與計算機，2015，32（10）：159-162.

[7]劉麗娟，改進的Apriori算法的研究及應用[J].計算機工程與設計，2017，38（12）：3324-3328.

[8]王英博，馬菁，柴佳佳，等.基于Hadoop平臺的改進關聯規則挖掘算法[J].計算機工程，2016，42（10）：69-74+79.

[9]李融，楊淙鈞，高澤，等.基于Spark的精準關聯規則挖掘算法實現[J].信息技術，2018（02）：153-158.

[10] S.M. Shafaei，M. Loghavi，S. Kamgar. Feasibility of implemen-tation of intelligent simulation configurations Based on datamining methodologies for prediction of tractor wheel slip[Jl. In-formation Processing in Agriculture，2019，6（2）.

【通聯編輯：王力】

收稿日期：2019-08-26

基金項目：碩士研究生創新資助項目（校級項目，編號：YKY-2019-07）

作者簡介：彭新宇（1996-），女，河北衡水人，北華航天工業學院在讀碩士研究生，主要研究方向為計算機應用技術，軟件測試;李叢煊（1996-），女，河北石家莊人，北華航天工業學院在讀碩士研究生，主要研究方向為計算機應用技術，軟件測試;郭金盈（1996-），女，河北滄州人，北華航天工業學院在讀碩士研究生，研究方向為計算機應用技術，遙感信息安全;赫彥文（1997—），女，河北張家口人，北華航天工業學院在讀碩士研究生，研究方向為計算機應用技術，軟件測試。