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

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

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

中圖分類號：TP3

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

文章編號：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ī)則的挖掘過程分為兩個階段：第一個階段從大量的數(shù)據(jù)集中選出達(dá)到要求的候選項(xiàng)集合，第二個階段從候選項(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)集的基本算法，這個算法存在兩個方面的問題，一個方面是多次掃描事務(wù)數(shù)據(jù)庫，1/0負(fù)載很高，另一個方面生成候選集時，候選集的數(shù)量呈指數(shù)式增長，是可能生成龐大的候選集[1]，因此Apriori算法存在進(jìn)步的空間，基于以上背景，國內(nèi)外的許多研究人員提出了Apriori改進(jìn)算法并將改進(jìn)算法投入到應(yīng)用中，改進(jìn)包括對算法、數(shù)據(jù)、平臺等方式的改進(jìn)，接下來會對Apriori算法不同改進(jìn)方式的研究概況進(jìn)行介紹。

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

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

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

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

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

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

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

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

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

對于指定行業(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ī)則，對信息進(jìn)行提取，確定醫(yī)療大數(shù)據(jù)中項(xiàng)集間的關(guān)聯(lián)關(guān)系，同樣能提高醫(yī)療大數(shù)據(jù)預(yù)處理的水平[5]。

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

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

有的研究人員針對關(guān)聯(lián)規(guī)則挖掘1/0負(fù)載嚴(yán)重與內(nèi)存受限的問題，提出利用Hadoop平臺編程模型MapReduce實(shí)現(xiàn)并行化的方法來改進(jìn)關(guān)聯(lián)規(guī)則算法[7]，Hadoop平臺具有可靠性、擴(kuò)展性、高效性、容錯性等優(yōu)點(diǎn)，MapReduce是對大規(guī)模數(shù)據(jù)進(jìn)行并行計(jì)算的一種編程模型和計(jì)算框架，封裝了并行處理、數(shù)據(jù)分布、負(fù)載均衡等復(fù)雜的細(xì)節(jié)，在Hadoop平臺上運(yùn)行MapRe-duce程序時，若某一個節(jié)點(diǎn)計(jì)算失敗，Hadoop系統(tǒng)會把它的計(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ù)時都需重啟資源，MapReduce編程框架不適合多次迭代，需要多次遍歷原始數(shù)據(jù)集，僅考慮了頻繁項(xiàng)集的計(jì)算并未考慮強(qiáng)關(guān)聯(lián)規(guī)則的挖掘，因此有的研究人員基于以上的研究做出了進(jìn)一步的改進(jìn)，針對之前的研究未將強(qiáng)關(guān)聯(lián)規(guī)則的挖掘考慮的問題提出了解決方法，將頻繁項(xiàng)目集數(shù)據(jù)導(dǎo)人支持高速讀取的Redis數(shù)據(jù)庫中，從而實(shí)時獲取任何頻繁項(xiàng)集支持度嘲，該改進(jìn)方式更適用于大型的數(shù)據(jù)集。

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

5 總結(jié)

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

參考文獻(xiàn)：

[1]陳維興，曲睿，孫毅剛，基于改進(jìn)Apriori算法的地面空調(diào)間歇故障預(yù)測[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ì)量分析與評價[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平臺的改進(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)目（校級項(xiàng)目，編號：YKY-2019-07）

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