1. 關聯分析

關聯分析是一類非常有用的數據挖掘方法，能從數據中挖掘出潛在的關聯關系。比如，在著名的購物籃事務（market basket transactions）問題中，

?

關聯分析則被用來找出此類規則：顧客在買了某種商品時也會買另一種商品。在上述例子中，大部分都知道關聯規則：{Diapers} → {Beer}；即顧客在買完尿布之后通常會買啤酒。后來通過調查分析，原來妻子囑咐丈夫給孩子買尿布時，丈夫在買完尿布后通常會買自己喜歡的啤酒。但是，如何衡量這種關聯規則是否靠譜呢？下面給出了度量標準。

支持度與置信度

?

對于靠譜的關聯規則，其支持度與置信度均應大于設定的閾值。那么，關聯分析問題即等價于：對給定的支持度閾值min_sup、置信度閾值min_conf，找出所有的滿足下列條件的關聯規則：

支持度>=min_sup

置信度>=min_conf

把支持度大于閾值的項集稱為頻繁項集（frequent itemset）。因此，關聯規則分析可分為下列兩個步驟：

生成頻繁項集F=X∪Y；

在頻繁項集F中，找出所有置信度大于最小置信度的關聯規則X?Y。

暴力方法

若（對于所有事務集合）項的個數為d，則所有關聯規則的數量：

?

如果采用暴力方法，窮舉所有的關聯規則，找出符合要求的規則，其時間復雜度將達到指數級。因此，我們需要找出復雜度更低的算法用于關聯分析。

2. Apriori算法Agrawal與Srikant提出Apriori算法，用于做快速的關聯規則分析。

頻繁項集生成

根據支持度的定義，得到如下的先驗定理：

定理1：如果一個項集是頻繁的，那么其所有的子集（subsets）也一定是頻繁的。

這個比較容易證明，因為某項集的子集的支持度一定不小于該項集。

定理2：如果一個項集是非頻繁的，那么其所有的超集（supersets）也一定是非頻繁的。

定理2是上一條定理的逆反定理。根據定理2，可以對項集樹進行如下剪枝：

?

關聯規則生成

關聯規則是由頻繁項集生成的，即對于FkFk，找出項集hmhm，使得規則fk?hm?hmfk?hm?hm的置信度大于置信度閾值。同樣地，根據置信度定義得到如下定理：

定理3：如果規則X?Y?X不滿足置信度閾值，則對于X的子集X′，規則X′?Y?X′也不滿足置信度閾值。

根據定理3，可對規則樹進行如下剪枝：

?

關聯規則的生成算法如下：

?