一種改進(jìn)的關(guān)聯(lián)規(guī)則算法

徐晶晶

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

1 Apriori算法分析

1.1 Apriori算法概述

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

1.2 Apriori算法的核心思想

（1）自動(dòng)連接步

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

（2）剪枝步

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

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

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

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

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

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

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

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

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

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

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

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

2.1 New_Apriori算法思想

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

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

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

[Infrequent_support= Total transaction – min_sup+1]

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

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

2.2 New_Apriori算法方法

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

輸出：L中的頻繁項(xiàng)集

方法：

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

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

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

b）Prune（CK+1）

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

d）if support_count= min_sup

or Infrequent_count= InfrequentSupport 停止掃描

e）when support_count= min_sup ，該項(xiàng)集為頻繁項(xiàng)集，保留該項(xiàng)集

Infrequent_count= InfrequentSupport，該項(xiàng)集為不頻繁項(xiàng)集，刪除該項(xiàng)集

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

end

return UkLK

end procedure

3 改進(jìn)算法實(shí)例說(shuō)明

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

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

同樣地，對(duì)候選項(xiàng)集{I2}，{I3}，{I4}，{I5}依次進(jìn)行掃描，如表2所示。

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

候選項(xiàng)集C2的掃描過(guò)程如下表3所示：

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

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

4 實(shí)驗(yàn)分析與結(jié)果展示

為了驗(yàn)證改進(jìn)的算法的性能，筆者將改進(jìn)前和改進(jìn)后的Apriori算法進(jìn)行了對(duì)比試驗(yàn)。

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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ù)挖掘的學(xué)生學(xué)業(yè)預(yù)警研究[J]. 電腦知識(shí)與技術(shù)， 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] 劉麗娟. 改進(jìn)的Apriori算法的研究及應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(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ā)超， 王志堅(jiān)， 葉楓，等. 關(guān)聯(lián)規(guī)則挖掘算法Apriori的研究改進(jìn)[J]. 計(jì)算機(jī)科學(xué)與探索， 2015， 9（9）：1075-1083.

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