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

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

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

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

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

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

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

Apriori

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

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

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

1.      掃描找出候選項集（初始掃描D得到候選項集 ）

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

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

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

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

1.      對中每一項L，取其所有非空子集

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

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

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

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

FP-Growth

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

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

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

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

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

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

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

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

6.      從頻繁集L的最后一項開始，對其每一項找到所有含該項的分支路徑。

7.      路徑中的結(jié)點計數(shù)即為該路徑下所有節(jié)點所組成的項集，在該分支的計數(shù)

8.      合并每一分支的項集，獲取頻繁集

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

Eclat

等價類變換

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

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

1.      對每頻繁項的TID集取交集

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

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

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

提升度：

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

相關(guān)性分析：

全置信度：

最大置信度：

Kulczynski(Kulc)：

余弦：

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