基于頻集的Apriori關聯規則算法的應用研究

沈慧娟 曹曉麗

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

關鍵詞：Apriori;關聯規則;數據挖掘;剪枝;強關聯;C++

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

0 引 言

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

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

1 關聯規則挖掘算法的形式化定義

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

關聯規則是形如X→Y的蘊涵式，其中XI，YI，且X∩Y=?。

2 關聯規則挖掘算法的發現步驟

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

發現關聯規則的步驟即首先找出所有頻集，然后再由這些頻集產生滿足最小置信度閾值[9]的強關聯規則。

3 關聯規則挖掘算法的演變

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

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

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

4 基于頻集的Apriori算法描述與C++實現

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

（1）給定min_sup和min_conf，并輸入數據庫;

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

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

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

算法流程如圖1所示。

用C++實現可形式化描述：

class Apriori{

private：

//存儲所有事務及其項

map >Ti;

//存儲頻繁項集

map，unsigned int> Li;

Unsigned int n;//事務數

Unsigned int min_sup;//最小支持度

public：

//構造函數，給定事務數及最小支持度

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

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

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

首先，掃描數據庫，得出各項的支持度計數分別為4，2，3，3，2，由項集的支持度指定項集的支持度計數與事務總數的比值[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及支持度。

上述操作需經歷連接和剪枝[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所示為發現頻繁項集的過程。

若min_conf =0.6，則{i1}→{i3}和{i3}→{i1}均為強關聯規則[13]。

5 Apriori關聯規則算法的應用

Apriori算法憑借簡單、易理解、數據要求低等諸多優點被廣泛應用于商業、網絡、教育等領域。

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

（2）網絡方面，利用Apriori算法快速發現網絡用戶的異常行為模式，快速鎖定攻擊者，為提高入侵檢測系統的檢測性提供幫助。

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

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

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

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

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

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

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

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

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

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

6 結 語

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

參考文獻

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

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

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

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

[5]劉雯婷，周軍.基于緩沖區技術的增量數據關聯規則挖掘算法[J].遼寧工業大學學報（自然科學版），2020，40（2）：71-74.

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

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

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

[9]丁燕妮.模糊多維關聯規則的研究與應用[D].北京：中國地質大學，2019.

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

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

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

[13]方蓉.基于關聯規則的數據挖掘算法的分析及應用[J].電子測試，2016，23（1）：36-38.

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

[15]趙楊.關聯規則技術在網絡學習評價中的應用研究[D].桂林：廣西師范大學，2014.

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