關聯規則學習

關聯規則學習(英語: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