基于頻集的Apriori關(guān)聯(lián)規(guī)則算法的應用研究

沈慧娟 曹曉麗

摘 要：大數(shù)據(jù)時代，數(shù)據(jù)被源源不斷地創(chuàng)造著，人們逐漸陷入“數(shù)據(jù)豐富而信息貧乏”的尷尬境地。那么，如何從繁雜的大數(shù)據(jù)中找出有價值的信息和知識成為人們的迫切需求。文章從數(shù)據(jù)挖掘的意義及關(guān)聯(lián)規(guī)則算法演變?nèi)胧?，對關(guān)聯(lián)規(guī)則中較為典型的Apriori算法進行了深入分析與研究，詳細闡明了Apriori算法的基本思想及挖掘過程，利用Apriori算法對電大系統(tǒng)1 369位學生關(guān)于網(wǎng)上教學滿意度的調(diào)研數(shù)據(jù)進行挖掘分析，經(jīng)歷了數(shù)據(jù)掃描、計數(shù)、比較、剪枝、連接等一系列操作，找出了數(shù)據(jù)間的強關(guān)聯(lián)規(guī)則，并由此推出數(shù)據(jù)關(guān)系，為改進網(wǎng)上教學提供了很好的參考依據(jù)。

關(guān)鍵詞：Apriori;關(guān)聯(lián)規(guī)則;數(shù)據(jù)挖掘;剪枝;強關(guān)聯(lián);C++

中圖分類號：TP311文獻標識碼：A文章編號：2095-1302（2020）10-00-05

0 引 言

大數(shù)據(jù)時代，伴隨著計算機軟硬件及數(shù)據(jù)庫技術(shù)的飛速發(fā)展，人類積累的數(shù)據(jù)量正呈指數(shù)級增長，并曾一度因數(shù)據(jù)分析技術(shù)缺乏和數(shù)據(jù)質(zhì)量不符合要求而產(chǎn)生“數(shù)據(jù)豐富而信息貧乏”的現(xiàn)象。能夠解決這一現(xiàn)象的有效方法[1]便是數(shù)據(jù)挖掘（Data Mining），即從大型數(shù)據(jù)庫中的大量原始數(shù)據(jù)中提取出人們感興趣的、隱含的、未知的、具有潛在價值的信息和知識。

如今，關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究的一個重要分支，學會數(shù)據(jù)挖掘的一個重要問題就是從數(shù)據(jù)中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則[2]。IBM公司Almaden研究中心的R.Agrawal等人于1993年首先提出關(guān)聯(lián)規(guī)則挖掘概念[3]及相關(guān)算法。關(guān)聯(lián)規(guī)則挖掘算法成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點，亦是數(shù)據(jù)挖掘的重要分支，被學術(shù)界廣泛深入研究，目前獲得了長足的發(fā)展。

1 關(guān)聯(lián)規(guī)則挖掘算法的形式化定義

設T={T1， T2， ...， Tm}是一個構(gòu)成關(guān)聯(lián)規(guī)則事務數(shù)據(jù)庫（Transaction Database）[5]的事務集，其中Ti（i=1， 2， ...， m）表示T的第i條記錄;I={I1， I2， ...， In}是T中所有項的集合，包含k（k=1， 2， ...， n）個項的項集是k-項集，即I的一個子集與一個唯一的標識符T_id相聯(lián)系。

關(guān)聯(lián)規(guī)則是形如X→Y的蘊涵式，其中XI，YI，且X∩Y=?。

2 關(guān)聯(lián)規(guī)則挖掘算法的發(fā)現(xiàn)步驟

若人為設定一個最小支持度閾值min_sup和一個最小置信度閾值min_conf，則支持度不小于min_sup的項集為頻繁項集（或頻集），置信度不小于min_conf的規(guī)則為強關(guān)聯(lián)規(guī)則。

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的步驟即首先找出所有頻集，然后再由這些頻集產(chǎn)生滿足最小置信度閾值[9]的強關(guān)聯(lián)規(guī)則。

3 關(guān)聯(lián)規(guī)則挖掘算法的演變

關(guān)聯(lián)規(guī)則的第一個算法AIS[4]是Agrawal等人提出關(guān)聯(lián)規(guī)則模型時給出的求解算法，基本思想是通過掃描事務數(shù)據(jù)庫產(chǎn)生頻集并計數(shù)[5]，若上一步的頻集出現(xiàn)在被掃描的當前事務中，則用事務中的項擴展這些項集獲得新的候選集，但該算法的一大缺陷是產(chǎn)生了過多的小候選集。之后，Cumulate和Stratify，Houstsma等人提出用SQL語句計算頻集的關(guān)聯(lián)規(guī)則算法—SETM算法[4]，基本思想是將候選的產(chǎn)生與計數(shù)分開，用SQL中的JOIN操作產(chǎn)生候選，然后以線性結(jié)構(gòu)保存候選副本及產(chǎn)生事務的T_id，并以此獲得事務包含的頻集，這是一種將關(guān)聯(lián)規(guī)則挖掘轉(zhuǎn)化為SQL語句執(zhí)行的算法。

用AIS和SERM算法構(gòu)造候選項集時需要通過掃描數(shù)據(jù)庫得到，而數(shù)據(jù)庫中的非頻繁項集較多，尋找出頻集必須掃描不需要的非頻集，因此浪費了大量的時間和空間，導致挖掘效率不理想。為改進該算法，1994年Agrawal等人又設計出一個新的關(guān)聯(lián)規(guī)則算法—Apriori[6]，該算法依據(jù)頻集的所有非空子集也必頻繁的特性，通過連接和剪枝逐步縮小數(shù)據(jù)量的方法找出頻集，節(jié)省了時間和空間，提高了挖掘效率，成為關(guān)聯(lián)規(guī)則挖掘算法中的經(jīng)典。

隨后的幾年，一些研究人員又在Apriori算法的基礎上進行了深入研究和分析，陸續(xù)產(chǎn)生了FP-Tree，GSP，CBA等一系列改進算法，進一步提高了執(zhí)行效率，為關(guān)聯(lián)規(guī)則挖掘技術(shù)的應用奠定了基礎。

4 基于頻集的Apriori算法描述與C++實現(xiàn)

Apriori算法的核心問題是獲得頻繁項集，采用逐層搜索迭代法[7]，描述如下：

（1）給定min_sup和min_conf，并輸入數(shù)據(jù)庫;

（2）掃描數(shù)據(jù)庫中的所有數(shù)據(jù)項，得到候選1-項集，計算所有項的支持度[8]，剔除所有支持度小于min_sup的項，得到頻繁1-項集，記作L1;

（3）對L1執(zhí)行連接操作，即L1 JOIN L1，得到候選2-項集，同樣計算所有項的支持度，剔除所有支持度小于min_sup的項，得到頻繁2-項集，記作L2;

（4）按步驟（3）重復執(zhí)行，直到頻繁項集為空。

算法流程如圖1所示。

用C++實現(xiàn)可形式化描述：

class Apriori{

private：

//存儲所有事務及其項

map >Ti;

//存儲頻繁項集

map，unsigned int> Li;

Unsigned int n;//事務數(shù)

Unsigned int min_sup;//最小支持度

public：

//構(gòu)造函數(shù)，給定事務數(shù)及最小支持度

Apriori（unsigned int is=0，unsigned int mv=0）

{ ?n=is; ?min_sup=mv; }

void Input_T（）;//輸入所有事務的項集

//找出頻繁項集

map，unsigned int> find_L（）;

//連接頻繁k-1項集，得到頻繁k項集

map，unsigned int> apri_gen（unsigned int K，map，unsigned int>Li）;

//輸出頻繁項集

void Output_T（unsigned int K，map，unsigned int> outmap）;

};

上述過程中，找出頻繁項集是Apriori算法的關(guān)鍵[6]。尋找頻繁項集的過程實際上是對項集的子集進行搜索并判斷其是否滿足最小支持度的過程。邏輯上，可以將頻繁項集的生成過程組織成一棵樹，然后以一定的方法遍歷該樹，并適當剪枝[10]，根據(jù)給定的最小支持度，由頻繁k-1-項集生成頻繁k-項集，直到頻集為空。

最后，從每個頻繁項集L中找到非空子集x，對每個x得到一條關(guān)聯(lián)規(guī)則“x→L-x”，計算并比較它們的置信度，不低于min_conf的關(guān)聯(lián)規(guī)則為強關(guān)聯(lián)規(guī)則[11]。

以某超市某天的一個簡單交易清單為例（表1），該表形象地說明了Apriori算法的執(zhí)行過程，清單中包括5個事務和5個項，即i1，i2，i3，i4，i5。

首先，掃描數(shù)據(jù)庫，得出各項的支持度計數(shù)分別為4，2，3，3，2，由項集的支持度指定項集的支持度計數(shù)與事務總數(shù)的比值[12]，得到表2所列候選1-項集C1的支持度。

將Support與min_sup比較，剔除所有小于min_sup的項集，若給定min_sup=0.5，可得到表3所列的頻繁1-項集L1及支持度。

連接L1L1，得出表4所列的候選2-項集及支持度。

將Support與min_sup比較，剔除所有小于min-sup的項集，便得到表5所列的頻繁2-項集L2及支持度。

上述操作需經(jīng)歷連接和剪枝[13]，其中連接的原則是保證前k-2項相同，猶如下列代碼：

select p.i1，p.i2，…，p.ik-1，q.ik-1

from Lk-1.p，Lk-1.q

where p.i1=q.i1，…，p.ik-2=q.ik-2，p.ik-1

剪枝是剔除所有小于min-sup的項集，用以確保任一頻集的所有非空子集亦頻繁。圖2所示為發(fā)現(xiàn)頻繁項集的過程。

若min_conf =0.6，則{i1}→{i3}和{i3}→{i1}均為強關(guān)聯(lián)規(guī)則[13]。

5 Apriori關(guān)聯(lián)規(guī)則算法的應用

Apriori算法憑借簡單、易理解、數(shù)據(jù)要求低等諸多優(yōu)點被廣泛應用于商業(yè)、網(wǎng)絡、教育等領(lǐng)域。

（1）商業(yè)方面，部分購物網(wǎng)站利用Apriori算法對消費者的消費習慣進行分析和挖掘，為商戶瞄準目標客戶、增加收入提供參考依據(jù)。

（2）網(wǎng)絡方面，利用Apriori算法快速發(fā)現(xiàn)網(wǎng)絡用戶的異常行為模式，快速鎖定攻擊者，為提高入侵檢測系統(tǒng)的檢測性提供幫助。

（3）教育教學方面，利用Apriori算法可以對收集的與學生學習相關(guān)的數(shù)據(jù)，如網(wǎng)絡教學反饋、學生登錄次數(shù)與學習時長、網(wǎng)上測評結(jié)果等進行關(guān)聯(lián)性分析和挖掘，找出數(shù)據(jù)相關(guān)性，對網(wǎng)上教學進行重組和配置，為提高網(wǎng)上教學效果、實現(xiàn)網(wǎng)絡教學個性化設計提供參考依據(jù)[14]。

用Apriori算法對1 369位學生針對國家開放大學網(wǎng)上教學平臺滿意度調(diào)查數(shù)據(jù)進行分析與挖掘[15]，內(nèi)容涉及學習網(wǎng)的界面操作是否方便、能否實時開展師生視音頻在線交流、課程教學設計是否合理、數(shù)字化教學資源能否滿足學生需求、考核方式是否合理、教師網(wǎng)上教學能力、網(wǎng)上實踐實訓環(huán)節(jié)是否達到預期效果等。設定min_sup=0.12，min_conf=0.45，調(diào)查內(nèi)容分別用A，B，C，D，E，F(xiàn)，G表示。

首先，掃描數(shù)據(jù)庫，得出候選1-項集C1及各項的支持度計數(shù)和支持度，見表6所列。

將C1中各項的支持度與最小支持度閾值比較，剔除小于min_sup的項集，得到頻繁1-項集，見表7所列。

對L1執(zhí)行連接操作，如L1L1，掃描數(shù)據(jù)庫，得到候選2-項集及各項的支持度計數(shù)和支持度，見表8所列。

繼續(xù)與最小支持度閾值比較，剔除小于min_sup的項集，得出頻繁2-項集L2，見表9所列。

執(zhí)行連接操作，如L2L2，掃描數(shù)據(jù)庫，得出候選3-項集及各項的支持度計數(shù)和支持度，見表10所列。

C3中的所有項都小于min_sup，故未找到頻繁3-項集，尋找頻繁項集的操作到此為止。

計算頻繁2-項集的置信度，具體如下：

將小于min_conf的項集全部剔除，得到強關(guān)聯(lián)規(guī)則E→A和D→B。由此得出結(jié)論：多數(shù)學生認為網(wǎng)上課程考核方式不合理和學習網(wǎng)界面操作不方便，以及數(shù)字化教學資源無法滿足需要并無法開展師生實時視頻、音頻等在線交流，這為改進網(wǎng)上教學平臺設計[16]、解決課程繁多但組織隨意、教學資源不合理等問題提供了參考依據(jù)。

6 結(jié) 語

Apriori算法可以使用戶從找到的頻繁項集中選擇某些感興趣的項，以求發(fā)現(xiàn)某些新奇的、有價值的或反常的規(guī)則。且算法通過連接和剪枝大大縮小了數(shù)據(jù)規(guī)模，與AIS和SERM相比，算法效率得到大幅提高，但終因數(shù)據(jù)庫需多次掃描帶來的開銷以及迭代過程中產(chǎn)生的大量頻繁項集導致算法在挖掘效率上未能很好地滿足人們的需求。盡管如此，與其他數(shù)據(jù)挖掘方法相比，Apriori算法憑借簡單易懂、無復雜推導規(guī)則表達形式等原因備受推崇。隨著對數(shù)據(jù)挖掘算法研究的不斷深入，會有更多更好的挖掘算法出現(xiàn)，以便更好地滿足大數(shù)據(jù)時代的需求。

參考文獻

[1]劉言哲，柳炳祥.基于Apriori算法的國家經(jīng)濟數(shù)據(jù)分析[J].中國管理信息化，2020，23（4）：148-150.

[2]溫亮明，郭蕾，王曉東，等.基于關(guān)聯(lián)規(guī)則的國內(nèi)外數(shù)據(jù)期刊載文特征比較分析：以《Scientific Data》和《中國科學數(shù)據(jù)》為例[J].情報科學，2019，37（1）：112-121.

[3]王平水.關(guān)聯(lián)規(guī)則挖掘算法研究[J].計算機工程與應用， 2010，46（30）：115-116

[4]郭鵬，蔡騁.基于聚類和關(guān)聯(lián)算法的學生成績挖掘與分析[J].計算機工程與應用，2019，55（17）：169-179.

[5]劉雯婷，周軍.基于緩沖區(qū)技術(shù)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法[J].遼寧工業(yè)大學學報（自然科學版），2020，40（2）：71-74.

[6]尹遠，朱璐偉，文凱.基于差異點集的頻繁項集挖掘算法[J].計算機工程與設計，2020，41（3）：716-720.

[7]黃劍，李明奇，郭文強.基于Hadoop的Apriori改進算法[J].計算機科學，2017，44（7）：262-266.

[8]余曉平，劉麗婭，朱東芹.基于項集的多支持度關(guān)聯(lián)規(guī)則挖掘算法[J].微計算機信息，2009，25（33）：147-148.

[9]丁燕妮.模糊多維關(guān)聯(lián)規(guī)則的研究與應用[D].北京：中國地質(zhì)大學，2019.

[10]李廣璞，黃妙華.頻繁項集挖掘的研究進展及主流方法[J].計算機科學，2018，45（11A）：1-11.

[11]熊桂喜，劉謝.改進的Apriori算法在交通事故分析中的應用[J].微計算機信息，2010，26（25）：205-207.

[12]劉海濤.一種改進的數(shù)據(jù)挖掘算法[J].科技通報，2016，32（11）：142-147.

[13]方蓉.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法的分析及應用[J].電子測試，2016，23（1）：36-38.

[14]梁燕紅.改進的Apriori算法在網(wǎng)絡教學中的應用[J].玉林師范學院學報，2012，33（2）：130-133.

[15]趙楊.關(guān)聯(lián)規(guī)則技術(shù)在網(wǎng)絡學習評價中的應用研究[D].桂林：廣西師范大學，2014.

[16]葉根梅.Apriori算法改進及其在高校網(wǎng)絡教學平臺的應用[J].河池學院學報，2019，39（2）：73-76.