標籤: 暫無標籤

關聯規則是形如X→Y的蘊涵式,其中且, X和Y分別稱為關聯規則的先導(antecedent或left-hand-side, LHS)和後繼(consequent或right-hand-side, RHS) 。

1簡介

定義
根據韓家煒等觀點,關聯規則定義為:
假設I是的集合。給定一個交易資料庫D,其中每個事務(Transaction)t是I的非空子集,即,每一個交易都與一個唯一的標識符TID(Transaction ID)對應。關聯規則在D中的支持度(support)是D中事務同時包含X、Y的百分比,即概率;置信度(confidence)是包含X的事務中同時又包含Y的百分比,即條件概率。如果滿足最小支持度閾值最小置信度閾值。這些閾值是根據挖掘需要人為設定。
兩個階段
關聯規則挖掘過程主要包含兩個階段:第一階段必須先從資料集合中找出所有的高頻項目組(Frequent Itemsets),第二階段再由這些高頻項目組中產生關聯規則(Association Rules)。
關聯規則挖掘的第一階段必須從原始資料集合中,找出所有高頻項目組(Large Itemsets)。高頻的意思是指某一項目組出現的頻率相對於所有記錄而言,必須達到某一水平。一項目組出現的頻率稱為支持度(Support),以一個包含A與B兩個項目的2-itemset為例,我們可以經由公式(1)求得包含{A,B}項目組的支持度,若支持度大於等於所設定的最小支持度(Minimum Support)門檻值時,則{A,B}稱為高頻項目組。一個滿足最小支持度的k-itemset,則稱為高頻k-項目組(Frequent k-itemset),一般表示為Large k或Frequent k。演算法並從Large k的項目組中再產生Large k+1,直到無法再找到更長的高頻項目組為止。
關聯規則挖掘的第二階段是要產生關聯規則(Association Rules)。從高頻項目組產生關聯規則,是利用前一步驟的高頻k-項目組來產生規則,在最小信賴度(Minimum Confidence)的條件門檻下,若一規則所求得的信賴度滿足最小信賴度,稱此規則為關聯規則。例如:經由高頻k-項目組{A,B}所產生的規則AB,其信賴度可經由公式(2)求得,若信賴度大於等於最小信賴度,則稱AB為關聯規則。
Apriori演算法
Apriori演算法:使用候選項集找頻繁項集
Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這裡,所有支持度大於最小支持度的項集稱為頻繁項集,簡稱頻集。
該演算法的基本思想是:首先找出所有的頻集,這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則,這些規則必須滿足最小支持度和最小可信度。然後使用第1步找到的頻集產生期望的規則,產生只包含集合的項的所有規則,其中每一條規則的右部只有一項,這裡採用的是中規則的定義。一旦這些規則被生成,那麼只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻集,使用了遞推的方法。
可能產生大量的候選集,以及可能需要重複掃描資料庫,是Apriori演算法的兩大缺點。
FP-樹頻集演算法
FP-樹頻集演算法
針對Apriori演算法的固有缺陷,J. Han等提出了不產生候選挖掘頻繁項集的方法:FP-樹頻集演算法。採用分而治之的策略,在經過第一遍掃描之後,把資料庫中的頻集壓縮進一棵頻繁模式樹(FP-tree),同時依然保留其中的關聯信息,隨後再將FP-tree分化成一些條件庫,每個庫和一個長度為1的頻集相關,然後再對這些條件庫分別進行挖掘。當原始數據量很大的時候,也可以結合劃分的方法,使得一個FP-tree可以放入主存中。實驗表明,FP-growth對不同長度的規則都有很好的適應性,同時在效率上較之Apriori演算法有巨大的提高。

2應用

研究
由於許多應用問題往往比超市購買問題更複雜,大量研究從不同的角度對關聯規則做了擴展,將更多的因素集成到關聯規則挖掘方法之中,以此豐富關聯規則的應用領域,拓寬支持管理決策的範圍。如考慮屬性之間的類別層次關係,時態關係,多表挖掘等。圍繞關聯規則的研究主要集中於兩個方面,即擴展經典關聯規則能夠解決問題的範圍,改善經典關聯規則挖掘演算法效率和規則興趣性。
上一篇[決策樹演算法]    下一篇 [學習理論]

相關評論

同義詞:暫無同義詞