十大經典數據挖掘算法—Apriori

打開APP

十大經典數據挖掘算法—Apriori

發表於 2018-02-04 09:37:56

1. 關聯分析

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

 

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

支持度與置信度

 

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

支持度>=min_sup

置信度>=min_conf

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

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

在頻繁項集F中，找出所有置信度大於最小置信度的關聯規則X⟶Y。

暴力方法

若（對於所有事務集合）項的個數為d，則所有關聯規則的數量：

 

如果採用暴力方法，窮舉所有的關聯規則，找出符合要求的規則，其時間複雜度將達到指數級。因此，我們需要找出複雜度更低的算法用於關聯分析。

2. Apriori算法Agrawal與Srikant提出Apriori算法，用於做快速的關聯規則分析。

頻繁項集生成

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

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

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

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

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

 

關聯規則生成

關聯規則是由頻繁項集生成的，即對於FkFk，找出項集hmhm，使得規則fk−hm⟶hmfk−hm⟶hm的置信度大於置信度閾值。同樣地，根據置信度定義得到如下定理：

定理3：如果規則X⟶Y−X不滿足置信度閾值，則對於X的子集X′，規則X′⟶Y−X′也不滿足置信度閾值。

根據定理3，可對規則樹進行如下剪枝：

 

關聯規則的生成算法如下：

 

打開APP閱讀更多精彩內容

聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容圖片侵權或者其他問題，請聯繫本站作侵刪。 侵權投訴