跳至內容

關聯規則學習

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

關聯規則學習(英語:Association rule learning)是一種在大型數據庫中發現變量之間的有趣性關係的方法。它的目的是利用一些有趣性的量度來識別數據庫中發現的強規則。[1] 基於強規則的概念,Rakesh Agrawal等人[2]引入了關聯規則以發現由超市的POS系統記錄的大批交易數據中產品之間的規律性。例如,從銷售數據中發現的規則 {洋蔥, 馬鈴薯}→{漢堡} 會表明如果顧客一起買洋蔥和馬鈴薯,他們也有可能買漢堡的肉。此類信息可以作為做出促銷定價產品置入等營銷活動決定的根據。除了上面購物籃分析英語market basket analysis中的例子以外, 關聯規則如今還被用在許多應用領域中,包括網絡用法探勘英語Web usage mining入侵檢測連續生產英語Continuous production生物信息學中。與序列探勘英語sequence mining相比,關聯規則學習通常不考慮在事務中、或事務間的項目的順序。

基本概念

表1:關聯規則的簡單例子
TID 網球拍 網球 運動鞋 羽毛球
1 1 1 1 0
2 1 1 0 0
3 1 0 0 0
4 1 0 1 0
5 0 1 1 1
6 1 1 0 0

根據韓家煒等[3],關聯規則定義為:

假設 項目的集合(項集)。給定一個交易數據庫 ,其中每個交易(Transaction) 的子集,即 ,每一個交易都與一個唯一的標識符TID(Transaction ID)對應。關聯規則是形如 蘊涵式,其中 分別稱為關聯規則的先導(antecedent 或 left-hand-side, LHS)和後繼(consequent 或 right-hand-side, RHS)。關聯規則 中的支持度(support)是 中交易包含 的百分比,即概率 置信度(confidence)是包含 的交易中同時包含 的百分比,即條件概率 。如果同時滿足最小支持度閾值最小置信度閾值,則認為關聯規則是有利或有用的。這些閾值由用戶或者專家設定。

用一個簡單的例子說明。表1是顧客購買記錄的數據庫D,包含6個交易。項集 {網球拍,網球,運動鞋,羽毛球}。考慮關聯規則:網球拍網球,交易1,2,3,4,6包含網球拍,交易1,2,6同時包含網球拍和網球,支持度,置信度。若給定最小支持度,最小置信度,關聯規則網球拍網球是有趣的,認為購買網球拍和購買網球之間存在強關聯。


分類

關聯規則有以下常見分類[3]

根據關聯規則所處理的值的類型

  • 如果考慮關聯規則中的數據項是否出現,則這種關聯規則是布爾關聯規則(Boolean association rules)。例如上面的例子。
  • 如果關聯規則中的數據項是數量型的,這種關聯規則是數量關聯規則(quantitative association rules)。例如年齡("20-25")購買("網球拍"),年齡是一個數量型的數據項。在這種關聯規則中,一般將數量離散化(discretize)為區間。

根據關聯規則所涉及的數據維數

  • 如果關聯規則各項只涉及一個維,則它是單維關聯規則(single-dimensional association rules),例如購買("網球拍")購買("網球")只涉及「購買」一個維度。
  • 如果關聯規則涉及兩個或兩個以上維度,則它是多維關聯規則(multi-dimensional association rules),例如年齡("20-25")購買("網球拍")涉及「年齡」和「購買」兩個維度。

根據關聯規則所涉及的抽象層次

  • 如果不涉及不同層次的數據項,得到的是單層關聯規則(single-level association rules)。
  • 在不同抽象層次中挖掘出的關聯規則稱為廣義關聯規則(generalized association rules)。例如年齡("20-25")購買("HEAD網球拍")和年齡("20-25")購買("網球拍")是廣義關聯規則,因為"HEAD網球拍"和"網球拍"屬於不同的抽象層次。

算法

Apriori 演算法

Apriori演算法所使用的前置統計量包括:

  • 最大規則物件數:規則中物件組所包含的最大物件數量;
  • 最小支援:規則中物件或是物件組必須符合的最低案例數;
  • 最小信心水準:計算規則所必須符合的最低信心水準門檻。

F-P算法

參考文獻

  1. ^ Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.
  2. ^ Agrawal, R.; Imieliński, T.; Swami, A. Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. 1993: 207. ISBN 0897915925. doi:10.1145/170035.170072. 
  3. ^ 3.0 3.1 J. Han, M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann: 2000