數(shù)據(jù)挖掘算法基礎(chǔ)-關(guān)聯(lián)規(guī)則

數(shù)據(jù)挖掘中，被常拿來(lái)說(shuō)的啤酒尿布的例子就是一個(gè)很典型的運(yùn)用關(guān)聯(lián)算法來(lái)做購(gòu)物來(lái)分析的例子。常被用于交易數(shù)據(jù)、關(guān)系數(shù)據(jù)的分析，發(fā)現(xiàn)數(shù)據(jù)集中隱藏的頻繁模式，這些頻繁模式可以用關(guān)聯(lián)規(guī)則的形式表示，有效的關(guān)聯(lián)規(guī)則對(duì)商家的商品進(jìn)出貨擺放都有很大的指導(dǎo)意義。

設(shè) 是項(xiàng)的集合，數(shù)據(jù)集D是事務(wù)的集合，每項(xiàng)事務(wù)T是一個(gè)非空項(xiàng)集，且T是I的非空子集。每項(xiàng)事務(wù)都有一個(gè)唯一標(biāo)識(shí)符，定義為TID，A和B均為事務(wù)T中的非空子集，并且A和B無(wú)交集。則規(guī)則 成立，支持度s是D中同時(shí)包含A和B的事務(wù)所占的百分比，置信度c是包含A的事務(wù)中包含B的事務(wù)的百分比。如下：

頻繁模式中同時(shí)滿足最小支持度閾值和最小置信度閾值的為強(qiáng)關(guān)聯(lián)規(guī)則。

綜上，關(guān)聯(lián)規(guī)則挖掘主要分為兩步：

1.      找出所有頻繁項(xiàng)集。每個(gè)項(xiàng)集出現(xiàn)頻次大于最小支持計(jì)數(shù)。

2.      由頻繁項(xiàng)集得到強(qiáng)關(guān)聯(lián)規(guī)則。這些規(guī)則同時(shí)滿足最小支持度閾值和最小置信度閾值。

Apriori

Apriori先驗(yàn)算法，基于先驗(yàn)性質(zhì)：頻繁項(xiàng)集的所有非空子集也一定是頻繁的。

針對(duì)水平數(shù)據(jù){TID:item_set}

發(fā)現(xiàn)頻繁集的過(guò)程

1.      掃描找出候選項(xiàng)集（初始掃描D得到候選項(xiàng)集 ）

2.      計(jì)算支持度計(jì)數(shù)，與最小支持度計(jì)數(shù)比較得到頻繁項(xiàng)集

3.       自連接產(chǎn)生候選項(xiàng)集

4.      重復(fù)2-3的過(guò)程，直到得到最大頻繁項(xiàng)集 。

由頻繁項(xiàng)集得到強(qiáng)關(guān)聯(lián)規(guī)則的過(guò)程

1.      對(duì)中每一項(xiàng)L，取其所有非空子集

2.      若對(duì)于L的某一非空子集S，若置信度大于最小支持度閾值

3.      則產(chǎn)生強(qiáng)規(guī)則：

以下截圖為《數(shù)據(jù)挖掘：概念與技術(shù)》中第六章Apriori獲取頻繁集過(guò)程示例。

Apriori算法的缺陷：可能產(chǎn)生大量候選集，可能需要重復(fù)掃描整個(gè)數(shù)據(jù)庫(kù)匹配檢查一個(gè)很大的候選集合?？臻g時(shí)間的花費(fèi)會(huì)很大。

FP-Growth

頻繁模式樹(shù)增長(zhǎng)算法，產(chǎn)生FP數(shù)，由樹(shù)遞歸推演得到頻繁模式。

針對(duì)水平數(shù)據(jù){TID:item_set}

發(fā)現(xiàn)頻繁集的過(guò)程

1.      第一次掃描D，并對(duì)比最小支持度計(jì)數(shù)，取1項(xiàng)頻繁集L

2.      1項(xiàng)頻繁集L按支持度計(jì)數(shù)降序排列

3.      創(chuàng)建數(shù)的根節(jié)點(diǎn)，用null標(biāo)記

4.      第二次掃描D，D中每一項(xiàng)事務(wù)中的想都按L中的次序處理，為每個(gè)事務(wù)創(chuàng)建一個(gè)分支

5.      結(jié)點(diǎn)不存在時(shí)，新建結(jié)點(diǎn)，結(jié)點(diǎn)計(jì)數(shù)賦值為1；結(jié)點(diǎn)已存在時(shí)，結(jié)點(diǎn)計(jì)數(shù)加1

6.      從頻繁集L的最后一項(xiàng)開(kāi)始，對(duì)其每一項(xiàng)找到所有含該項(xiàng)的分支路徑。

7.      路徑中的結(jié)點(diǎn)計(jì)數(shù)即為該路徑下所有節(jié)點(diǎn)所組成的項(xiàng)集，在該分支的計(jì)數(shù)

8.      合并每一分支的項(xiàng)集，獲取頻繁集

以下截圖為《數(shù)據(jù)挖掘：概念與技術(shù)》中第六章FP-Growth獲取頻繁集過(guò)程示例。

Eclat

等價(jià)類變換

垂直數(shù)據(jù)格式{item:TID_set}

發(fā)現(xiàn)頻繁集的過(guò)程

1.      對(duì)每頻繁項(xiàng)的TID集取交集

2.      重復(fù)上述過(guò)程直至沒(méi)有更大頻繁集

以下截圖為《數(shù)據(jù)挖掘：概念與技術(shù)》中第六章Eclat獲取頻繁集過(guò)程示例。

判斷規(guī)則的有效性

提升度：

Lift=1，A和B獨(dú)立不相關(guān)，lift<1，A和B負(fù)相關(guān)，lift>1，A和B正相關(guān)。

相關(guān)性分析：

全置信度：

最大置信度：

Kulczynski(Kulc)：

余弦：

后面四項(xiàng)度量值取值范圍都是0~1，并且值越大A和B的聯(lián)系越緊密。