關聯規則學習

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

基本概念

表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

根據韓家煒等，關聯規則定義為：

假設 $I=\{I_{1},I_{2},\ldots ,I_{m}\}$ 是項目的集合（項集）。給定一個交易數據庫 $D=\{t_{1},t_{2},\ldots ,t_{n}\}$，其中每個交易（Transaction） $t$ 是 $I$ 的子集，即 $t\subseteq I$，每一個交易都與一個唯一的標識符TID（Transaction ID）對應。關聯規則是形如 $X\Rightarrow Y$ 的蘊涵式，其中 $X,Y\subseteq I$ 且 $X\cap Y=\emptyset$， $X$ 和 $Y$ 分別稱為關聯規則的先導（antecedent 或 left-hand-side, LHS）和後繼（consequent 或 right-hand-side, RHS）。關聯規則 $X\Rightarrow Y$ 在 $D$ 中的支持度（support）是 $D$ 中交易包含 $X\cup Y$ 的百分比，即概率 $P(X\cup Y|D)$；置信度（confidence）是包含 $X$ 的交易中同時包含 $Y$ 的百分比，即條件概率 $P\left(Y|X\right)$。如果同時滿足最小支持度閾值和最小置信度閾值，則認為關聯規則是有利或有用的。這些閾值由用戶或者專家設定。

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

分類

關聯規則有以下常見分類：

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

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

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

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

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

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

算法

Apriori 演算法

主條目：先驗算法

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

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