關聯規則挖掘研究

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

關鍵詞：數據挖掘；關聯規則；數據庫；支持度；可信度

0 引言

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

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

1 基本概念

關聯規則挖掘主要關注頻繁模式研究，所以本文中也只討論針對頻繁模式的關聯規則挖掘。

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

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

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

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

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

2 關聯規則挖掘

關聯規則挖掘從總體上說分兩步實現，一是找出頻繁項集，二是通過頻繁項集推出關聯規則。

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

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

3 Apriori算法

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

3.2 Apriori算法的頻繁項集產生

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

3.3 基于置信度的剪枝

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

3.4 Apriori算法中規則的產生

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

3.5 Aprior算法的優缺點

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

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

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

4 其他“產生一測試”算法

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

4.1 Partition算法

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

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

4.2 Sampling算法

Sampling算法，是芬蘭赫爾辛基大學的Hannu Toivonen于1996年提出的針對大型數據庫的關聯規則挖掘算法，整個算法執行過程只掃描數據庫一次。

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

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

5 FP-growth算法

5.1 FP增長算法概述

FP增長算法采用完全不同的方法來發現頻繁項集。該算法不同于Apfiori算法的“產生一測試”范型，而是使用一種稱作FP樹的緊湊數據結構組織數據，并直接從該結構中提取頻繁項集。Apfiofi使用的是寬度優先的方法遍歷數據庫中的項集格。

5.2 FP樹表示法

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

5.3 FP增長算法的頻繁項集產生

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

5.4 FP增長算法的性能

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

5.5 Apriori與FP growth算法的對比

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

6 關聯規則挖掘算法評價

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