摘要：關(guān)聯(lián)規(guī)則挖掘是一種重要的數(shù)據(jù)挖掘技術(shù)，緣自“啤酒與尿布”問題出現(xiàn)這項技術(shù)以來，已有許多學者提出了多種關(guān)聯(lián)規(guī)則挖掘算法。這些關(guān)聯(lián)規(guī)則挖掘算法主要分為以Apriori為代表的“產(chǎn)生一測試”范型和以FP-growth為代表的采用復(fù)雜數(shù)據(jù)結(jié)構(gòu)壓縮存儲空間的范型。文章將這兩種代表算法進行了對比分析。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；數(shù)據(jù)庫；支持度；可信度

0 引言

關(guān)聯(lián)規(guī)則挖掘就是通過計算大型事務(wù)數(shù)據(jù)集中單個項或者多個項組成的項集出現(xiàn)的頻率和各個項集出現(xiàn)的條件概率，找出數(shù)據(jù)集中存在的頻繁模式和隱含的關(guān)聯(lián)規(guī)則，從而預(yù)測事物的發(fā)展趨勢。關(guān)聯(lián)規(guī)則挖掘本身不是預(yù)測過程，挖掘出來的規(guī)則有預(yù)測作用。

自從1993年Rakesh Agrawal研究零售交易數(shù)據(jù)而提出關(guān)聯(lián)規(guī)則挖掘以來，這種以研究數(shù)據(jù)庫中各屬性之間關(guān)系為主的數(shù)據(jù)挖掘方法已經(jīng)逐步被應(yīng)用于零售、保險、銀行等商業(yè)領(lǐng)域，同時正在或即將被應(yīng)用于其他所有需要分析大量數(shù)據(jù)的領(lǐng)域。

1 基本概念

關(guān)聯(lián)規(guī)則挖掘主要關(guān)注頻繁模式研究，所以本文中也只討論針對頻繁模式的關(guān)聯(lián)規(guī)則挖掘。

設(shè)I={i₁，i₂，…i_m}是項集，其中i_k(k=1，2，…，m)可以是購物籃中的物品，也可以是保險公司的顧客。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是事務(wù)集，其中每個事務(wù)T是項集，使得TCI。設(shè)A是一個項集，且ACT。

關(guān)聯(lián)規(guī)則是如下形式的邏輯蘊涵：A→B，ACI，BcI，且AnB=φ。關(guān)聯(lián)規(guī)則具有如下兩個重要的屬性：

支持度：P(AUB)，即A和B這兩個項集在事務(wù)集D中同時出現(xiàn)的概率。

置信度：P(B I A)，即在出現(xiàn)項集A的事務(wù)集D中，項集B也同時出現(xiàn)的概率。

同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強規(guī)則。給定一個事務(wù)集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強規(guī)則的問題。

2 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘從總體上說分兩步實現(xiàn)，一是找出頻繁項集，二是通過頻繁項集推出關(guān)聯(lián)規(guī)則。

找頻繁項集就是掃描全部數(shù)據(jù)，找出數(shù)據(jù)集中支持度大于或等于用戶定義的最小支持度min_sup的所有項集。找出的這些項集就稱為頻繁項集。對于找出的頻繁項集L，選擇L的所有非空子集x，可能存在規(guī)則X→L→X，通過計算這條規(guī)則的置信度support(L)／support(X)，如果其大于或者等于最小置信度，就推出這條規(guī)則。 理論上含有m個項的一行記錄能產(chǎn)生2^m個項集，所以找頻繁項集的數(shù)學計算量很大。許多研究人員提出的挖掘算法也主要關(guān)注找頻繁項集的過程。究其原因，筆者認為有兩點：一是找頻繁項集確實需要很大的計算量，所以都希望能提出新的算法或者改進算法以提高效率，很多最初的挖掘算法也的確存在改進的空間。二是頻繁項集對各個行業(yè)、各個數(shù)據(jù)挖掘人員的意義是一致的，針對同—個數(shù)據(jù)集，各種算法挖掘出的頻繁項集結(jié)果都應(yīng)該是一致的，所以廣大研究者有“共同語言”。關(guān)聯(lián)規(guī)則挖掘初期，用戶主要關(guān)注的是頻繁項集，對于關(guān)聯(lián)規(guī)則沒有太細致的要求。而推導關(guān)聯(lián)規(guī)則這一步的計算量主要在后期的規(guī)則剪枝和篩選，而且針對不同應(yīng)用的規(guī)則剪枝差別很大。 現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘的算法很多，最經(jīng)典的是Agrawal提出的Apriori算法，比較著名的還有韓家煒提出的FP-growth算法。以Apfiofi為代表的很多算法采用“產(chǎn)生一測試”范型，就是先產(chǎn)生可能的頻繁項集(即候選集)，通過驗證確定真正的頻集，產(chǎn)生可能的規(guī)則，再通過計算置信度確定要推出的規(guī)則。而FP增長算法是采用分治策略，將—個問題逐步化為更小的問題。

下面分別具體介紹Apfiofi算法和FP增長算法。

3 Apriori算法

3.1 先驗原理 如果一個項集是頻繁的，則它的所有子集一定也是頻繁的；如果—個項集是非頻繁的，則它的所有超集也是非頻繁的。

3.2 Apriori算法的頻繁項集產(chǎn)生

Apriofi算法是利用先驗原理在掃描數(shù)據(jù)庫找頻繁項集時進行剪枝，使用逐層迭代的方法產(chǎn)生候選項集和頻繁項集。算法執(zhí)行過程是：首先掃描數(shù)據(jù)庫一遍，根據(jù)最小支持度確定頻繁l項集。由2個頻繁1項集合成為一個候選2項集，再對候選2項集進行支持度剪枝，得到頻繁2項集。再用頻繁2項集合并為候選3項集，進而生成頻繁3項集。用如此方法迭代，直到不能產(chǎn)生出項更多的滿足最小支持度的頻繁項集。迭代過程中由兩個前k-2項相同的頻繁k-1項集合并成一個候選k項集(k>=2)，要求各項集中的項按字典序排列，合并后前項集的最后一項作為新項集的倒數(shù)第2項，后項集的最后一項作為新項集的最后一項。

3.3 基于置信度的剪枝

如果規(guī)則X→Y－x不滿足置信度閾值，則形如X'→Y－x’的規(guī)則一定也不滿足置信度閾值，其中x'x的子集。

3.4 Apriori算法中規(guī)則的產(chǎn)生

Apriori算法使用一種逐層方法來產(chǎn)生關(guān)聯(lián)規(guī)則，其中每層對應(yīng)于規(guī)則后件中的項數(shù)。初始，提取規(guī)則后件只含一個項的所有高置信度規(guī)則，然后，使用這些規(guī)則來產(chǎn)生新的候選規(guī)則。例如，如果{acd}→和{abd}→{c}是兩個高置信度的規(guī)則，則通過合并這兩個規(guī)則的后件產(chǎn)生候選規(guī)則{ad}→{bc}，即前件取交集，后件取并集。假設(shè)規(guī)則{bcd}→{a}具有低置信度，則可以丟棄后件包含a的所有規(guī)則，包括{cd}→{ab}，{bd}→{ac}和5xzp3pp→{abc}。

3.5 Aprior算法的優(yōu)缺點

Agrawal于1994年提出的Apfiofi算法和用迭代的方法很好地解決了找頻繁項集的問題，而且執(zhí)行效率也比較高，因為在迭代過程中遇到非頻繁的項集，在下一輪計算中可以直接排除掉該項集的超集，這樣能高效地減少計算量。同時，使用置信度逐層剪枝的方法在規(guī)則剪枝中也很有效。Apriori算法的總體性能比較穩(wěn)健，而且在關(guān)聯(lián)規(guī)則挖掘提出沒多久就出現(xiàn)，對使用和研究關(guān)聯(lián)規(guī)則極大地起到了示范和引領(lǐng)作用。

Agrawal在文章[3]中還提出了AprioriTid算法，就是在第一次掃描數(shù)據(jù)庫后再計算支持度時不用再掃數(shù)據(jù)庫D，而只用事務(wù)的TID編號來計數(shù)；還提出了結(jié)合Apfiofi和AprioriTid的ApfiofiHybfid算法。不過后面的這兩種算法相對Apfiofi優(yōu)勢并不是特別明顯，而且適用性也不廣泛，所以沒有被推廣。

Apfiofi算法的缺點是需要多次掃描數(shù)據(jù)庫，產(chǎn)生含k項的最大頻繁項集需要掃描數(shù)據(jù)庫k次或者k+1次，耗費大量運算時間。因為當時計算機的內(nèi)存普遍比較小，數(shù)據(jù)庫D的數(shù)據(jù)量大，不能全部讀入主存來運算，因此Apfiofi算法在執(zhí)行過程中需要多次掃描磁盤中的數(shù)據(jù)庫。

4 其他“產(chǎn)生一測試”算法

鑒于Apriori需要多次掃描數(shù)據(jù)庫，時間開銷比較大，其他很多算法在挖掘準確性方面參照它，而希望在運行時間上有所突破。以下介紹的算法都主要是針對找頻繁項集提出新意，都不需要多次掃描數(shù)據(jù)庫。

4.1 Partition算法

Partition算法的思想是：掃描數(shù)據(jù)庫D一次，將D分成若干小的塊，分別把這些小塊讀入內(nèi)存中，用level-wise(逐層，同Apfiofi中的逐層迭代)的方法來發(fā)現(xiàn)小塊數(shù)據(jù)中的局部頻繁項集，然后再將各小塊的局部頻繁項集合并成為全局的候選項集，再掃描一次數(shù)據(jù)庫，計算支持度，從而確定最終的頻繁項集。

Partition算法找頻繁項集的整個過程只需要掃描數(shù)據(jù)庫兩次。

4.2 Sampling算法

Sampling算法，是芬蘭赫爾辛基大學的Hannu Toivonen于1996年提出的針對大型數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則挖掘算法，整個算法執(zhí)行過程只掃描數(shù)據(jù)庫一次。

Sampling的思想是：隨機取數(shù)據(jù)庫D的一小部分作為sample，將sample讀入內(nèi)存進行處理，用level-wise方法挖掘出sample中的頻繁項集s，將s與sample中s的負邊界集的合集作為新的s，s成為整個數(shù)據(jù)庫的候選項集。掃描一次數(shù)據(jù)庫，計算s中各項集的支持度，確定數(shù)據(jù)庫D的頻繁項集。負邊界集(Negative Border)是指Sample中不存在于s中的最小項集。

Sampling算法計算的數(shù)據(jù)量小，也只掃描數(shù)據(jù)庫一次，因此執(zhí)行時間很少。在挖掘結(jié)果的準確性方面與Apriofi有一些差距。通過原文作者設(shè)計的一些實驗證明，這種取樣挖掘的方法總體的挖掘性能很好，特別是針對大型海量數(shù)據(jù)，有一定的研究意義。

5 FP-growth算法

5.1 FP增長算法概述

FP增長算法采用完全不同的方法來發(fā)現(xiàn)頻繁項集。該算法不同于Apfiori算法的“產(chǎn)生一測試”范型，而是使用一種稱作FP樹的緊湊數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)，并直接從該結(jié)構(gòu)中提取頻繁項集。Apfiofi使用的是寬度優(yōu)先的方法遍歷數(shù)據(jù)庫中的項集格。

5.2 FP樹表示法

FP樹是一種輸入數(shù)據(jù)的壓縮表示，它通過逐個讀入事務(wù)，并把每個事務(wù)映射到FP樹中的一條路徑來構(gòu)造。因為不同的事務(wù)可能會有相同的項，按照字典序的前綴表示方法，一些事務(wù)的路徑可能會部分重疊，這樣就壓縮了存儲空間。很明顯，重疊越多，壓縮效果越好。如果FP樹足夠小，能夠存放在內(nèi)存中，就可以直接從內(nèi)存中的結(jié)構(gòu)提取頻繁項集。FP樹以前綴排序方式建樹，根結(jié)點是nun，然后以支持度遞減的順序選擇項加入到樹中。

5.3 FP增長算法的頻繁項集產(chǎn)生

FP增長算法依據(jù)后綴排序方法從FP樹的葉結(jié)點開始依據(jù)結(jié)尾項自底向上找頻繁項集。FP增長算法采用分治策略將問題分解為較小的子問題，從而發(fā)現(xiàn)以某個特定后綴結(jié)尾的所有頻繁項集。例如，為了發(fā)現(xiàn)所有以e結(jié)尾的頻繁項集，必須檢查項集{e}本身是否頻繁。如果它是頻繁的，則考慮發(fā)現(xiàn)以de結(jié)尾的頻繁項集子問題，接下來是ce和ae。依次，每一個子問題可以進一步劃分為更小的子問題。通過合并這些子問題得到的結(jié)果，就可以找到所有以e結(jié)尾的頻繁項集。

5.4 FP增長算法的性能

FP增長算法展示了使用事務(wù)數(shù)據(jù)集的壓縮表示來有效地產(chǎn)生頻繁項集。對于某些事務(wù)數(shù)據(jù)集，F(xiàn)P增長算法比標準的Apriori算法要快幾個數(shù)量級。FP增長算法的運行性能依賴于數(shù)據(jù)集的壓縮因子(compaction factor)。如果生成的前綴樹非常茂盛，則算法的性能顯著下降，因為算法必須產(chǎn)生大量的子問題，并且需要合并每個子問題返回的結(jié)果。

5.5 Apriori與FP growth算法的對比

從對Apfiofi和FP growth算法的分析可以看出，對于項集稠密分布的數(shù)據(jù)集(即多數(shù)項的支持度比較高的數(shù)據(jù)集)，使用FP樹存儲能壓縮很多空間，因此適宜用FP增長算法挖掘；對于項集稀疏分布的數(shù)據(jù)集(即大多項的支持度比較小的數(shù)據(jù)集)，使用Apfiofi算法挖掘比較合宜，因為在找頻繁項集的迭代過程中能剪枝掉大量非頻繁項集。 從易用性方面分析，Apriori算法能用于各種關(guān)聯(lián)規(guī)則挖掘場合；而FP增長算法雖然運算性能比較高，但由于其執(zhí)行過程較復(fù)雜，需要建FP前綴樹和條件FP樹，對于數(shù)據(jù)項分布不集中的海量數(shù)據(jù)集，構(gòu)建的FP樹會非常龐大，算法的總體執(zhí)行效率會比較低。

6 關(guān)聯(lián)規(guī)則挖掘算法評價

已有的關(guān)聯(lián)規(guī)則挖掘算法主要有Apriori、FP growth、基于抽樣的方法、基于劃分的方法和基于散列的方法等。大部分算法都采用以Apriori為代表的“產(chǎn)生一測試”范型。簡單地說，“產(chǎn)生－測試”范型，就是在對數(shù)據(jù)作一定分析的基礎(chǔ)上，先假設(shè)一種情況，再通過數(shù)學計算來測試，最終確定挖掘出的頻繁模式。而FP樹為代表的高性能算法主要是采用比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，壓縮存儲空間，直接從數(shù)據(jù)集中“抓取”出頻繁項集。它們也有“測試”過程，就是測試支持度、置信度，但是沒有“產(chǎn)生”或者說“候選假設(shè)”過程。 關(guān)聯(lián)規(guī)則挖掘是一項實用的數(shù)據(jù)挖掘技術(shù)，已經(jīng)存在的各種流行算法并沒有絕對的高下之分。像基于抽樣的方法，雖然執(zhí)行速度快，但同時損失了精確性；Apriori算法運算速度可能會比某些算法差，但總體性能穩(wěn)健，而且可以用于各種環(huán)境，挖掘準確性高，易于理解。在具體的挖掘?qū)嵺`可以借鑒多種算法思想，采用適合自己情況的算法。