沈慧娟 曹曉麗

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

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

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2020）10-00-05

0 引 言

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

如今，關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究的一個(gè)重要分支，學(xué)會(huì)數(shù)據(jù)挖掘的一個(gè)重要問(wèn)題就是從數(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)域的研究熱點(diǎn)，亦是數(shù)據(jù)挖掘的重要分支，被學(xué)術(shù)界廣泛深入研究，目前獲得了長(zhǎng)足的發(fā)展。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法流程如圖1所示。

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

class Apriori{

private：

//存儲(chǔ)所有事務(wù)及其項(xiàng)

map >Ti;

//存儲(chǔ)頻繁項(xiàng)集

map，unsigned int> Li;

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

Unsigned int min_sup;//最小支持度

public：

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

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

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

void Input_T（）;//輸入所有事務(wù)的項(xiàng)集

//找出頻繁項(xiàng)集

map，unsigned int> find_L（）;

//連接頻繁k-1項(xiàng)集，得到頻繁k項(xiàng)集

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

//輸出頻繁項(xiàng)集

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

};

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

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

以某超市某天的一個(gè)簡(jiǎn)單交易清單為例（表1），該表形象地說(shuō)明了Apriori算法的執(zhí)行過(guò)程，清單中包括5個(gè)事務(wù)和5個(gè)項(xiàng)，即i1，i2，i3，i4，i5。

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

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

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

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

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

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的項(xiàng)集，用以確保任一頻集的所有非空子集亦頻繁。圖2所示為發(fā)現(xiàn)頻繁項(xiàng)集的過(guò)程。

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

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

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

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

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

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

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

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

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

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

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

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

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

計(jì)算頻繁2-項(xiàng)集的置信度，具體如下：

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

6 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

[6]尹遠(yuǎn)，朱璐偉，文凱.基于差異點(diǎn)集的頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2020，41（3）：716-720.

[7]黃劍，李明奇，郭文強(qiáng).基于Hadoop的Apriori改進(jìn)算法[J].計(jì)算機(jī)科學(xué)，2017，44（7）：262-266.

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

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

[10]李廣璞，黃妙華.頻繁項(xiàng)集挖掘的研究進(jìn)展及主流方法[J].計(jì)算機(jī)科學(xué)，2018，45（11A）：1-11.

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

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

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

[14]梁燕紅.改進(jìn)的Apriori算法在網(wǎng)絡(luò)教學(xué)中的應(yīng)用[J].玉林師范學(xué)院學(xué)報(bào)，2012，33（2）：130-133.

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

[16]葉根梅.Apriori算法改進(jìn)及其在高校網(wǎng)絡(luò)教學(xué)平臺(tái)的應(yīng)用[J].河池學(xué)院學(xué)報(bào)，2019，39（2）：73-76.