數據挖掘算法基礎-關聯規則

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

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

頻繁模式中同時滿足最小支持度閾值和最小置信度閾值的為強關聯規則。

綜上，關聯規則挖掘主要分為兩步：

1.      找出所有頻繁項集。每個項集出現頻次大于最小支持計數。

2.      由頻繁項集得到強關聯規則。這些規則同時滿足最小支持度閾值和最小置信度閾值。

Apriori

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

針對水平數據{TID:item_set}

發現頻繁集的過程

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

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

3.       自連接產生候選項集

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

由頻繁項集得到強關聯規則的過程

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

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

3.      則產生強規則：

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

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

FP-Growth

頻繁模式樹增長算法，產生FP數，由樹遞歸推演得到頻繁模式。

針對水平數據{TID:item_set}

發現頻繁集的過程

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

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

3.      創建數的根節點，用null標記

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

5.      結點不存在時，新建結點，結點計數賦值為1；結點已存在時，結點計數加1

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

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

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

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

Eclat

等價類變換

垂直數據格式{item:TID_set}

發現頻繁集的過程

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

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

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

判斷規則的有效性

提升度：

Lift=1，A和B獨立不相關，lift<1，A和B負相關，lift>1，A和B正相關。

相關性分析：

全置信度：

最大置信度：

Kulczynski(Kulc)：

余弦：

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