1. 關(guān)聯(lián)分析

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

?

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

支持度與置信度

?

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

支持度>=min_sup

置信度>=min_conf

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

生成頻繁項(xiàng)集F=X∪Y；

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

暴力方法

若（對(duì)于所有事務(wù)集合）項(xiàng)的個(gè)數(shù)為d，則所有關(guān)聯(lián)規(guī)則的數(shù)量：

?

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

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

頻繁項(xiàng)集生成

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

定理1：如果一個(gè)項(xiàng)集是頻繁的，那么其所有的子集（subsets）也一定是頻繁的。

這個(gè)比較容易證明，因?yàn)槟稠?xiàng)集的子集的支持度一定不小于該項(xiàng)集。

定理2：如果一個(gè)項(xiàng)集是非頻繁的，那么其所有的超集（supersets）也一定是非頻繁的。

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

?

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

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

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

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

?

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

?