關(guān)聯(lián)規(guī)則挖掘頻繁項算法的應(yīng)用

（徐州醫(yī)藥高等職業(yè)學(xué)校，江蘇徐州，221116）

關(guān)聯(lián)規(guī)則挖掘頻繁項算法的應(yīng)用

呂淑玲

（徐州醫(yī)藥高等職業(yè)學(xué)校，江蘇徐州，221116）

關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘中是一種簡單但很實用的規(guī)則，Apriori算法和FP-Growth算法是關(guān)聯(lián)規(guī)則中的典型算法，本文介紹了關(guān)聯(lián)規(guī)則和兩種典型算法的概念，利用實例對比兩種算法在挖掘頻繁項集中的區(qū)別，分析算法的優(yōu)劣，從而確定算法的應(yīng)用。

關(guān)聯(lián)規(guī)則；頻繁項；Aprior算法；FP-Growth算法

關(guān)聯(lián)規(guī)則挖掘是在海量數(shù)據(jù)上進(jìn)行的。頻繁項集的產(chǎn)生需要訪問數(shù)據(jù)庫中所存儲的大量數(shù)據(jù)，用什么算法迅速高效地在數(shù)據(jù)集中找出所有的頻繁項集是數(shù)據(jù)挖掘的核心問題?，F(xiàn)給定一個任務(wù)用兩種算法舉例對比：

例：事務(wù)數(shù)據(jù)庫中，包含有十個事務(wù)，已知最小支持度為30%，根據(jù)支持度的定義得到，最小支持?jǐn)?shù)=事務(wù)數(shù)×最小支持度=10×30%=3。

1 Apriori法舉例，過程如下

（1）對數(shù)據(jù)庫進(jìn)行瀏覽，計算每個1-項集的支持?jǐn)?shù)，得到候選1-項集C1，將候選1-項集的支持?jǐn)?shù)與最小支持?jǐn)?shù)3比較，將大于或等于3的項集保留，得到頻繁1-項集F1

（2）對頻繁1-項集進(jìn)行自連接和剪枝運算，得到候選2-項集。

①連接：項集{A}分別與{B}、{C}、{D}、{E}連接后組成新的項集；項集{B}分別與{C}、{D}、{E}連接后組成新的項集；項集{C}分別與{D}、{E}連接后組成新的項集；項集{D}與{E}連接后組成新的項集。

②剪枝：依據(jù)頻繁項集的所有子集都是頻繁的，對產(chǎn)生的每個項集進(jìn)行判斷，本例中所得到的所有項集都滿足此要求。

（3）瀏覽事務(wù)數(shù)據(jù)庫，得出每個候選2-項集的支持?jǐn)?shù)。

（4）與最小支持?jǐn)?shù)3比較，保留支持?jǐn)?shù)大于或等于3的頻繁項集，去掉支持?jǐn)?shù)小于3的非頻繁項集，得到頻繁2-項集F2。

（5）對頻繁2-項集F2進(jìn)行自連接和剪枝運算，得到候選3-項集。

自連接：為了避免重復(fù)，將項集中的內(nèi)容按字典順序排序，當(dāng)兩個項集中前面的項都相同，而只有最后一項不同時，才進(jìn)行連接。例如，項集{A,B}和項集{A,C}，第一項相同（都是A），而第二項卻不同，這時將兩項連接后組成一個新的3-項集{A,B,C}。但是項集{A,B}和{B,C}的第一項不同，就不進(jìn)行連接，這樣可以避免產(chǎn)生重復(fù)項集{A,B,C}。對頻繁2-項集進(jìn)行自連接后，得到結(jié)果。

2 FP-Growth算法舉例，過程如下

（1）掃描事務(wù)數(shù)據(jù)庫，得到頻繁1-項集，并將頻繁1-項集按支持?jǐn)?shù)從大到小排序，對于支持?jǐn)?shù)相同的按字典順序排序。

（2）構(gòu)造FP樹

①建立樹的根結(jié)點，用null代表。

②讀入第一個事分T01,按DBCAE的次序?qū)κ聞?wù)中所包含的項進(jìn)行排序，得到{D,B,C,A},創(chuàng)建標(biāo)記為D、B、C、A的結(jié)點，形成路徑null→D→B→C→A,將路徑上結(jié)點的計數(shù)值設(shè)為1。

③讀入第二個事務(wù)T02，對各項進(jìn)行排序，得到{D,B,C},由于路徑null→D→B→C與第一個事務(wù)的路徑前部分相同，所以，這里不再增加新結(jié)點，而是將D、B、C各個結(jié)點的計數(shù)值自動加1進(jìn)行更新。

依次讀入第十個事務(wù)T10，得到與事務(wù)數(shù)據(jù)庫對應(yīng)的FP樹。

（3）利用FP樹得到全部的頻繁項集

對構(gòu)造的FP樹，采用分而治之的策略，根據(jù)項集支持?jǐn)?shù)從小到大的順序，依次對E、A、C、B、D構(gòu)造條件FP樹，從而找到全部的頻繁項集。

①首先，發(fā)現(xiàn)以E結(jié)尾的頻繁項集。

a.收集包含E的所有路徑，這些路徑稱為前綴路徑。

b.遍歷E結(jié)點，對支持?jǐn)?shù)進(jìn)行累加，得到E的支持?jǐn)?shù)5，5大于等于最小支持?jǐn)?shù)3成立，所以{E}是頻繁項集。

c.構(gòu)造E的條件FP樹。

更新前綴路徑上的支持?jǐn)?shù)，因為某些計數(shù)中包含有那些不含項E的事務(wù)，因此，必須將該路徑上的結(jié)點D、B、C的計數(shù)信息進(jìn)行修改，以反映真實的事務(wù)數(shù)。給出了修改了支持?jǐn)?shù)之后包含E的前綴路徑。

②刪除結(jié)點E，修剪前綴路徑，因為發(fā)現(xiàn)以AE、CE、BE、DE結(jié)尾的頻繁項集的問題不再需要E的信息。

③結(jié)點C只出現(xiàn)2次，它的支持?jǐn)?shù)為2，說明只有2個事物包含CE。由于最小支持?jǐn)?shù)為3，因此{(lán)C、E}是非頻繁的。因為以CE結(jié)尾的項集一定也是非頻繁的，所在以其后的分析中可以忽略C。這樣得到E的條件FP樹。

（4）利用E的條件FP樹，得到以E結(jié)尾的頻繁項集。

為了發(fā)現(xiàn)以AE結(jié)尾的頻繁項集，從E的條件FP樹中得到結(jié)點A的所有前綴路徑，此時與E的條件FP樹相同，通過把與結(jié)點A相關(guān)聯(lián)的計數(shù)值累加求和，得到{A、E}的支持?jǐn)?shù)3，該值大于等于最小支持?jǐn)?shù)3的要求，所以{A、E}是頻繁項集。按照前面介紹的方法，更新支持度計數(shù)，去掉結(jié)點A，并刪除非頻繁項B之后，得到AE的條件FP樹。在AE的條件FP樹中，只包含一個結(jié)點D，且支持?jǐn)?shù)3滿足最小支持?jǐn)?shù)的要求，所以{D、A、E}是頻繁項集。

先從E的條件FP樹中得到B的所有前綴路徑，得到頻繁項集{B、E}，再構(gòu)造BE的條件FP樹，得到頻繁項集{D、B、E}。最后，發(fā)現(xiàn)以DE結(jié)尾的頻繁項集{D、E}。

至此，我們已經(jīng)得到了以E結(jié)尾的所有頻繁項集。同樣，我們可以得到A、C、B、D的頻繁項集。

為了避免重復(fù)，Apriori采用了自連接和剪枝技術(shù)；為了提高訪問數(shù)據(jù)庫的效率，又采用了Hash樹求解候選項集的支持?jǐn)?shù)。盡管如此對海量數(shù)據(jù)庫來說，這個算法還存在不盡人意的地方。

FP-Growth算法即頻繁模式樹增長算法（frequent pattern tree growth），是一種新的挖掘頻繁項集的算法。該算法中引入FP樹和條件FP樹的概念，利用FP樹將事務(wù)數(shù)據(jù)庫中的所有事物實現(xiàn)壓縮存儲，利用條件FP樹得到頻繁項集。在FP-Growth算法中只需要對數(shù)據(jù)庫進(jìn)行兩次掃描，一次是為了得到頻繁1-項集，一次是為了建立FP樹。掃描數(shù)據(jù)庫的次數(shù)要遠(yuǎn)遠(yuǎn)小于Apriori算法。與Apriori算法通過候選項集來產(chǎn)生頻繁項集不同，F(xiàn)P算法并不產(chǎn)生候選項集，而是利用了條件FP樹直接生成頻繁項集，在大數(shù)據(jù)挖掘中，大大提高了工作效率。

Association rule mining algorithm for frequent item Applications

Lv Shuling
（Xuzhou pharmaceutical higher vocational schools，Xuzhou，Jiangsu，221116）

The association rule in data mining is a simple but very practical rule,Apriori algorithm and FP-Growth algorithm is a typical association rules algorithm, this paper introduces the concept of association rules and two typical algorithms,use two examples contrast algorithms in mining frequent item set difference, the pros and cons analysis algorithm to determine the application of the algorithm.

association rule；frequent item；Aprior algorithm；FP-Growth algorithm

呂淑玲（1974-），女，碩士，講師，研究方向關(guān)聯(lián)規(guī)則算法的應(yīng)用。