基于關(guān)聯(lián)規(guī)則的Apriori改進(jìn)算法的研究綜述

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

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

關(guān)鍵詞：大數(shù)據(jù);數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;Apriori算法改進(jìn)

中圖分類號(hào)：TP3

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）34-0216-02

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

1 基于Apriori算法本身的改進(jìn)，減少掃描次數(shù)

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

Apriori算法中掃描數(shù)據(jù)庫計(jì)數(shù)部分所占時(shí)間比例最大，其次是項(xiàng)集連接和篩選剪枝，故優(yōu)先減少掃描計(jì)數(shù)在整個(gè)算法中的時(shí)間開銷，有的研究人員在改進(jìn)算法中對(duì)計(jì)算候選項(xiàng)集支持度的部分做出改進(jìn)，掃描計(jì)數(shù)階段的時(shí)間復(fù)雜度增加了一個(gè)變量，變量和迭代次數(shù)成反比關(guān)系，即隨著迭代次數(shù)的增加，目標(biāo)事務(wù)在事務(wù)數(shù)據(jù)庫中所占的比例越來越小，時(shí)間復(fù)雜度隨之下降[2]。稀疏型數(shù)據(jù)中，變量的下降速度會(huì)非常快，因此處理稀疏型數(shù)據(jù)的效果較好。

2 轉(zhuǎn)換存儲(chǔ)方式的改進(jìn)

2.1 基于前綴項(xiàng)集的存儲(chǔ)方式改進(jìn)

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

2.2 基于矩陣的存儲(chǔ)方式改進(jìn)

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

3 基于減少數(shù)據(jù)的改進(jìn)

對(duì)于指定行業(yè)的數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則算法改進(jìn)，例如醫(yī)院的大數(shù)據(jù)等，有明顯的行業(yè)數(shù)據(jù)特點(diǎn)，根據(jù)行業(yè)的數(shù)據(jù)特點(diǎn)與屬性產(chǎn)生關(guān)聯(lián)規(guī)則，對(duì)信息進(jìn)行提取，確定醫(yī)療大數(shù)據(jù)中項(xiàng)集間的關(guān)聯(lián)關(guān)系，同樣能提高醫(yī)療大數(shù)據(jù)預(yù)處理的水平[5]。

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

4 基于平臺(tái)與編程模型的改進(jìn)

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

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

Spark是對(duì)早前Map-Reduce編程框架的擴(kuò)展，相較于Ma-pReduce，Spark機(jī)制對(duì)處理大數(shù)據(jù)集以及數(shù)據(jù)迭代更具有優(yōu)勢(shì)，基于Spark的性能優(yōu)勢(shì)，有的研究人員利用分布式框架Spark解決單機(jī)內(nèi)存資源限制、性能缺陷的問題[9]，增強(qiáng)了強(qiáng)關(guān)聯(lián)規(guī)則挖掘時(shí)數(shù)據(jù)的實(shí)時(shí)性，從整體上提高了關(guān)聯(lián)規(guī)則挖掘的效率。

5 總結(jié)

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

參考文獻(xiàn)：

[1]陳維興，曲睿，孫毅剛，基于改進(jìn)Apriori算法的地面空調(diào)間歇故障預(yù)測(cè)[J].計(jì)算機(jī)應(yīng)用，2016，36（12）：3505-3510.

[2]徐開勇，龔雪容，成茂才.基于改進(jìn)Apriori算法的審計(jì)日志關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)應(yīng)用，2016，36（07）：1847-1851.

[3]于守健，周羿陽.基于前綴項(xiàng)集的Apriori算法改進(jìn)[J]，計(jì)算機(jī)應(yīng)用與軟件，2017，34（02）：290-294.

[4]謝志明，王鵬.基于MapReduce架構(gòu)的并行矩陣Apriori算法[J].計(jì)算機(jī)應(yīng)用研究，2017，34（02）：401-404.

[5]岳根霞.基于關(guān)聯(lián)規(guī)則的醫(yī)療大數(shù)據(jù)挖掘算法[J].微電子學(xué)與計(jì)算機(jī)，2019，36（04）：105-108.

[6]朱付保，白慶春，湯萌萌，等.基于改進(jìn)Apriori算法的鐵路軌道質(zhì)量分析與評(píng)價(jià)[J].微電子學(xué)與計(jì)算機(jī)，2015，32（10）：159-162.

[7]劉麗娟，改進(jìn)的Apriori算法的研究及應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2017，38（12）：3324-3328.

[8]王英博，馬菁，柴佳佳，等.基于Hadoop平臺(tái)的改進(jìn)關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)工程，2016，42（10）：69-74+79.

[9]李融，楊淙鈞，高澤，等.基于Spark的精準(zhǔn)關(guān)聯(lián)規(guī)則挖掘算法實(shí)現(xiàn)[J].信息技術(shù)，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）.

【通聯(lián)編輯：王力】

收稿日期：2019-08-26

基金項(xiàng)目：碩士研究生創(chuàng)新資助項(xiàng)目（校級(jí)項(xiàng)目，編號(hào)：YKY-2019-07）

作者簡(jiǎn)介：彭新宇（1996-），女，河北衡水人，北華航天工業(yè)學(xué)院在讀碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)，軟件測(cè)試;李叢煊（1996-），女，河北石家莊人，北華航天工業(yè)學(xué)院在讀碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)，軟件測(cè)試;郭金盈（1996-），女，河北滄州人，北華航天工業(yè)學(xué)院在讀碩士研究生，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)，遙感信息安全;赫彥文（1997—），女，河北張家口人，北華航天工業(yè)學(xué)院在讀碩士研究生，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)，軟件測(cè)試。