徐晶晶

摘要： 該文對關聯(lián)規(guī)則算法進行了分析研究，并針對傳統(tǒng)的Apriori算法在對海量數(shù)據(jù)進行處理時的效率低，I/O負擔過重，產(chǎn)生大量候選項集導致計算量過大等問題，提出了一種改進方法New_Apriori算法。通過對項集的支持度計數(shù)進行條件判斷，來減少對事務數(shù)據(jù)庫的掃描次數(shù)和CPU的計算時間，從而提高算法的執(zhí)行效率。通過實例和實驗對Apriori算法和New_Apriori算法進行對比分析，驗證了算法的可行性，結果表明New_Apriori算法的執(zhí)行效率更高，能夠滿足大數(shù)據(jù)處理需求。

關鍵詞：Apriori；關聯(lián)規(guī)則；大數(shù)據(jù)

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）18-0257-04

Improved Association Rule Algorithm

XU Jing-jing

（College of Computer and information Technology， Henan Normal University， Xinxiang 453007， China）

Abstract： This paper analyzes and studies the Association Rule Algorithm， and it proposes an improved method that is New_Apriori Algorithm to solve problems. During the processing of traditional Apriori algorithm， the low efficiency of it and the heavy burden of I/O will produce a large amount of candidate items， which can be solved by the New_Apriori Algorithm. The new method reduces the number of scanning times of the transaction database and the calculation time of CPU by judging the condition by counting the degree of Support_count， thus it can improve the executive efficiency of itself. The feasibility of the New_Apriori Algorithm is verified by comparison and analysis of Apriori and New_Apriori Algorithm through examples and experiments， and the results show that the executive efficiency of New_Apriori Algorithm is higher which can meet the demand of large data processing.

Key words： Apriori； Association rules； Big Data

隨著云計算和互聯(lián)網(wǎng)的飛速發(fā)展，各行業(yè)的數(shù)據(jù)都在呈爆炸性增長[1]。大數(shù)據(jù)時代的到來，使得大數(shù)據(jù)技術越來越受關注，利用數(shù)據(jù)挖掘技術找到海量數(shù)據(jù)當中隱藏的、有價值的信息已經(jīng)成為當前信息社會的一筆重要財富。關聯(lián)規(guī)則挖掘算法就是數(shù)據(jù)挖掘當中的一個重要分析方法，在大數(shù)據(jù)背景下，關聯(lián)規(guī)則挖掘算法能夠幫助人們從海量數(shù)據(jù)中發(fā)現(xiàn)許多潛在的又有價值的信息。最經(jīng)典的就是購物籃分析，幫助超市發(fā)現(xiàn)啤酒和尿不濕的消費規(guī)律。在教育行業(yè)，利用關聯(lián)規(guī)則算法找到學生成績與課程之間的關系、挖掘在線學習的學生的行為偏好對學生進行合理的資源推薦[2]；在金融行業(yè)挖掘客戶的行為需求和習慣、以及購買意向；在醫(yī)學界挖掘疾病和藥物之間的關系等。最經(jīng)典的關聯(lián)分析算法就是Apriori算法，在1994年由Agrwal和R.Srikant提出來的，是一種布爾關聯(lián)規(guī)則挖掘頻繁項集的一種原創(chuàng)性算法[3]。該算法的重點工作就是在挖掘過程中找出所有的頻繁項集，算法的性能決定了頻繁項集挖掘的性能[4]。在深度挖掘和使用的過程中，發(fā)現(xiàn)該算法還存在以下不足：（1）在挖掘頻繁項集的過程中，總是先產(chǎn)生候選項集，再對候選項集的支持度和最小置信度進行計算比較，最終找到需要的所有頻繁項集。候選項集的支持度計數(shù)每增加1，都會對事務數(shù)據(jù)庫掃描一次，這樣就增加了I/O的開銷，當候選項集非常多時，算法的時間和空間開銷會更大，降低了算法的效率。（2）在算法不斷進行當中，會產(chǎn)生大量的候選項集，其中有很多無關的項集也進行了連接，連接步的過程開銷增大，后剪枝的工作量也隨之增加，不利于算法的執(zhí)行。因此本文提出了一種改進的關聯(lián)規(guī)則挖掘算法New_Apriori，通過對頻繁項計數(shù)和不頻繁計數(shù)最小閾值的判斷，來減少對事務的掃描次數(shù)，減少了CPU的計算時間，提高算法的運行效率，有效地減輕了I/O負擔。

1 Apriori算法分析

1.1 Apriori算法概述

Apriori算法使用一種被稱作逐層搜索的迭代方法[5-6]，通過k項集來生產(chǎn)（k+1）項集的候選項集，經(jīng)過掃描數(shù)據(jù)集庫，將計算（k+1）項集的候選項集的支持計數(shù)，其中滿足最小支持度的項集則為頻繁項集，一直找到所有的頻繁項集為止，每找到一個頻繁項集都需要對數(shù)據(jù)庫進行一次完整的掃描[7]，頻繁項集的先驗性質，使得k項集可以用作去探索（k+1）項集，而不用重新地開始查找頻繁項集。

1.2 Apriori算法的核心思想

（1）自動連接步

[Lk]與[Lk+1]自動連接，產(chǎn)生候選項k+1項候選項集[Ck+1]；設[I1]和[I2]是[Lk]當中的兩個項集，[Ii[k]]表示[Ii]中的第k項，為了能實現(xiàn)Apriori算法，假定項集當中的所有項都按照字典序進行排序。對于k項集Ii，[Ii1

（2）剪枝步

[Lk]是[Ck]的真子集，[Ck]當中的項集也可以是不頻繁的，但是最終結果得到的所有頻繁項集都包含在[Ck]當中。在掃描事務數(shù)據(jù)庫時，通過計算[Ck]中的每個候選項集的計數(shù)，來確定得出頻繁項集[Lk]，當計數(shù)的值不小于預定義的最小支持度閾值時，該項集就是頻繁項集，屬于[Lk]當中。當[Ck]很大時，這樣涉及的計算量就非常大，所以要壓縮[Ck]，利用先驗性質，任何非頻繁項集都不是頻繁項集的子集，所以，如果一個候選項k項集中的（k-1）項集的子項集不在[Lk]項集當中，則該項集就是不頻繁的，就要從[Ck]當中刪除。

（3）產(chǎn)生有效的關聯(lián)規(guī)則

使用頻繁項集產(chǎn)生強關聯(lián)規(guī)則（依據(jù)：置信度）。

對于每個頻繁項集L，產(chǎn)生L的所有非空子集S，則對于規(guī)則[S→L-S]，如果

[ConfidenceS→L-S≥min_Confidence]（其中[min_Confidence]為最小置信度閾值），則稱規(guī)則[S→L-S]為強關聯(lián)規(guī)則。

注意：在這一階段中計算各個規(guī)則的置信度時不需要再對數(shù)據(jù)集進行掃描，直接運用第一階段產(chǎn)生頻繁項集時掃描得到的相應的計數(shù)即可。

滿足最小支持度和最小置信度的規(guī)則叫作“強關聯(lián)規(guī)則”，然而在強關聯(lián)規(guī)則里也分有效的強關聯(lián)規(guī)則和無效的強關聯(lián)規(guī)則。

如果[LiftS→L-S>1]，則規(guī)則[S→L-S]是有效的強關聯(lián)規(guī)則；

如果[LiftS→L-S<1]，則規(guī)則[S→L-S]是無效的強關聯(lián)規(guī)則；

如果[LiftS→L-S=1]，則規(guī)則表示S和（L-S）相互獨立。

也就是說，強關聯(lián)規(guī)則還需通過提升度的檢驗才能真正視之為有用的關聯(lián)規(guī)則，才能用于指導實踐，同時需注意的是，機器學習得到的關聯(lián)規(guī)則并無人的意識，有效的關聯(lián)規(guī)則中哪些對用戶是有實際價值的還需要分析人員做出最終判斷，得到最終的關聯(lián)結果。并且，關聯(lián)分析得到的關聯(lián)規(guī)則的前后項之間不是因果聯(lián)系，是一種可能同時發(fā)生的關聯(lián)性。

2 改進的關聯(lián)規(guī)則挖掘算法

2.1 New_Apriori算法思想

該方法的主要思想是減少事務掃描的次數(shù)。

（1）在掃描事務數(shù)據(jù)庫時，每當項集存在事務中一次，則該項集的支持度計數(shù)[（support_count）]就加1，當項集的支持度計數(shù)等于預定的最小支持度閾值（[min_sup]）時，該項集就是頻繁項集，停止對剩下事務的掃描，進入下一個項集的掃描。

（2）不頻繁項集支持度=總事務數(shù)-最小支持度閾值+1

[Infrequent_support= Total transaction – min_sup+1]

當掃描事務數(shù)據(jù)庫時，某項集不在事務中時，項集的不頻繁計數(shù)[（Infrequent_count]）增加1，當項集的不頻繁計數(shù)等于不頻繁項集支持度時，該項集為不頻繁項集，直接終止掃描，直接刪除該項集。如果最小支持度閾值很高時，這個不頻繁項集支持度就起著非常重要的作用，例如有個事務，[min_sup] = 9，則[Infrequent_support] = 2，因此，當掃描事務數(shù)據(jù)庫時，某項集的不頻繁項集計數(shù)達到2時，就可以中斷事務的掃描，將該項集定為不頻繁項集，并且將該項集直接刪除。

（3）雙向搜索：通常數(shù)據(jù)集的掃描是從上到下進行的。但是這里筆者對數(shù)據(jù)集的掃描是從上到下和從下到上依次進行到數(shù)據(jù)集的中間。

2.2 New_Apriori算法方法

輸入：事務數(shù)據(jù)庫D，最小支持度閾值[min_sup]

輸出：L中的頻繁項集

方法：

[Infrequent_support] = 總數(shù)事務數(shù) –[ min_sup] + 1；

For（k=1；Lk！= Φ；k++） do begin

a）Ck+1= 從Lk中產(chǎn)生候選項集

b）Prune（CK+1）

c）掃描事務從上到下和從下到上依次進行，增加CK+1中的所有候選項集的支持度計數(shù)和不頻繁項集支持度計數(shù)；

d）if support_count= min_sup

or Infrequent_count= InfrequentSupport 停止掃描

e）when support_count= min_sup ，該項集為頻繁項集，保留該項集

Infrequent_count= InfrequentSupport，該項集為不頻繁項集，刪除該項集

f） （Lk+1） = candidates in （Ck+1）

end

return UkLK

end procedure

3 改進算法實例說明

實例事務數(shù)據(jù)庫D：

這里對事務數(shù)據(jù)庫的掃描是從上到下和從下到上依次進行完成的，首先掃描事務T1，然后再掃描事務T9，每掃描一次，事務中存在該項集，項集的支持度計數(shù)就遞增1。當Support_conut 達到2時，就和預定的最小支持度閾值相同，這時停止對項集{I1}的掃描，該項集就是頻繁項集。

同樣地，對候選項集{I2}，{I3}，{I4}，{I5}依次進行掃描，如表2所示。

當對項集{I1、I4}的掃描時，不頻繁項集支持度（Infrequent_count）先滿足預定義的不頻繁項集支持（Infrequent_support）的值，停止掃描數(shù)據(jù)集，該項集被定為不頻繁項集，直接刪除該項集即可，減少了候選項集的掃描次數(shù)。如果此時的min_sup= 9，那么Infrequent_support=1，只需掃描事務T1時，Infrequent_count = 1→break，掃描終止，該項集被刪除，不用再次對掃描事務數(shù)據(jù)庫求其支持度計數(shù)，減少了對事務的掃描次數(shù)，大大地提高了算法的運行效率。

候選項集C2的掃描過程如下表3所示：

由L3?C4 = {{I1，I2，I3，I5}}；經(jīng)過剪枝，C4被刪除。算法終止，得到所有頻繁項集。

筆者用原始的Apriori算法進行了分析，統(tǒng)計出兩種算法掃描數(shù)據(jù)庫的總次數(shù)，然后進行對比分析，得知改進的Apriori算法與原始的相比，掃描次數(shù)明顯減少，因此降低了CPU的計算時間，提高了算法的運行效率。

4 實驗分析與結果展示

為了驗證改進的算法的性能，筆者將改進前和改進后的Apriori算法進行了對比試驗。

（1）選擇相同的數(shù)據(jù)集，比較改進前和改進后的算法在相同的支持度下產(chǎn)生頻繁項集所需的時間。結果如表6所示：

（2）選擇相同的數(shù)據(jù)集，將最小支持度閾值設置成不同的值進行試驗，比較改進前和改進后的Apriori算法在不一樣的支持度下，產(chǎn)生頻繁項集所需的時間。對比試驗的結果如圖1所示：

（3）選擇相同的數(shù)據(jù)集，在同一最小支持度閾值的情況下，比較數(shù)據(jù)集的事務掃描總數(shù)。如圖2所示：

通過上述試驗驗證，New_Apriori算法與傳統(tǒng)的算法相比，減少了對事物數(shù)據(jù)庫的掃描次數(shù)，提高了算法的運行效率，減少了CPU的執(zhí)行時間。

5 結束語

本文提出了一種改進的關聯(lián)規(guī)則算法New_Apriori算法，通過判斷項集的支持度計數(shù)是否滿足頻繁項集的最小支持度閾值或者是不頻繁項集的最小支持度的閾值來停止對事務數(shù)據(jù)庫的掃描，減少CPU的計算時間，從而提高了算法的執(zhí)行效率。當頻繁項集的最小支持度閾值很低時，項集的支持度計數(shù)達到最小支持度閾值時，停止對事務數(shù)據(jù)庫的掃描；當頻繁項集的最小支持度閾值很高時，基于不頻繁項集的最小支持度閾值，停止對事務數(shù)據(jù)庫的掃描。實驗證明，改進后的Apriori算法較之前的算法更具有優(yōu)勢，能夠滿足大數(shù)據(jù)分析對數(shù)據(jù)挖掘需求。

參考文獻：

[1] Casado R， Younas M. Emerging trends and technologies in big data processing[J]. Concurrency & Computation Practice & Experience， 2015， 27（8）：2078-2091.

[2] 邱鑫儀， 沈良忠. 基于數(shù)據(jù)挖掘的學生學業(yè)預警研究[J]. 電腦知識與技術， 2017， 13（36）：226-227.

[3] Yi K， Chen T， Cong G. Library personalized recommendation service method based on improved association rules[J]. Library Hi Tech， 2017.

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

[5] Oruganti S， Ding Q， Tabrizi N. Exploring HADOOP as a Platform for Distributed Association Rule Mining[J]. 2013：62-67.

[6] 周發(fā)超， 王志堅， 葉楓，等. 關聯(lián)規(guī)則挖掘算法Apriori的研究改進[J]. 計算機科學與探索， 2015， 9（9）：1075-1083.

[7] 王華， 劉萍. 改進的關聯(lián)規(guī)則算法在學生成績預警中的應用[J]. 計算機工程與設計， 2015（3）：679-682.