1. 關聯(lián)分析

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

?

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

支持度與置信度

?

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

支持度>=min_sup

置信度>=min_conf

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

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

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

暴力方法

若（對于所有事務集合）項的個數(shù)為d，則所有關聯(lián)規(guī)則的數(shù)量：

?

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

2. Apriori算法Agrawal與Srikant提出Apriori算法，用于做快速的關聯(lián)規(guī)則分析。

頻繁項集生成

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

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

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

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

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

?

關聯(lián)規(guī)則生成

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

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

根據(jù)定理3，可對規(guī)則樹進行如下剪枝：

?

關聯(lián)規(guī)則的生成算法如下：

?