查看“︁关联规则学习”︁的源代码

{{machine learning bar}}
{{NoteTA
|G1=IT
}}
'''关联规则学习'''（{{lang-en|'''Association rule learning'''}}）是一种在大型数据库中发现变量之间的有趣性关系的方法。它的目的是利用一些有趣性的量度来识别数据库中发现的强规则。<ref name="piatetsky">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.</ref>  基于强规则的概念，Rakesh Agrawal等人<ref name="mining">{{Cite book | last1 = Agrawal | first1 = R. | last2 = Imieliński | first2 = T. | last3 = Swami | first3 = A. | doi = 10.1145/170035.170072 | chapter = Mining association rules between sets of items in large databases | title = Proceedings of the 1993 ACM SIGMOD international conference on Management of data  - SIGMOD '93 | pages = 207 | year = 1993 | isbn = 0897915925 | pmid =  | pmc = }}</ref>引入了关联规则以发现由超市的[[銷售時點情報系統|POS]]系统记录的大批交易数据中产品之间的规律性。例如，从销售数据中发现的规则 {洋葱, 馬鈴薯}→{汉堡} 会表明如果顾客一起买洋葱和馬鈴薯，他们也有可能买汉堡的肉。此类信息可以作为做出促销[[定价策略|定价]]或[[置入性行銷|产品-{zh-cn:植入;zh-tw:置入;}-]]等营销活动决定的根据。除了上面{{le|购物篮分析|market basket analysis}}中的例子以外， 关联规则如今还被用在许多应用领域中，包括{{le|网络用法探勘|Web usage mining}}、[[入侵检测系统|入侵检测]]、{{le|连续生产|Continuous production}}及[[生物信息学]]中。与{{le|序列探勘|sequence mining}}相比，关联规则学习通常不考虑在事务中、或事务间的项目的顺序。

==基本概念==
{|class="wikitable" style="float: right;"
|+ 表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
|-
|}
根据韩家炜等<ref name="data mining">J. Han, M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann: 2000</ref>，关联规则定义为：

假设 <math>I=\{I_1, I_2,\ldots,I_m\}</math> 是'''-{zh-hans:项目;zh-hant:項目}-'''的集合（項集）。给定一个交易数据库 <math>D=\{t_1, t_2,\ldots,t_n\}</math>，其中每个'''交易'''（Transaction） <math>t</math> 是 <math>I</math> 的子集，即 <math>t\subseteq I</math>，每一个交易都与一个唯一的标识符TID（Transaction ID）对应。'''关联规则'''是形如 <math>X \Rightarrow Y</math> 的[[蕴涵]]式，其中 <math>X, Y \subseteq I</math> 且 <math>X \cap Y = \emptyset</math>， <math>X</math> 和 <math>Y</math> 分别称为关联规则的'''先导'''（antecedent 或 left-hand-side, LHS）和'''后继'''（consequent 或 right-hand-side, RHS）。关联规则 <math>X \Rightarrow Y</math> 在 <math>D</math> 中的'''支持度'''（support）是 <math>D</math> 中交易包含 <math>X \cup Y</math> 的百分比，即[[概率]] <math>P(X \cup Y | D)</math>；'''置信度'''（confidence）是包含 <math>X</math> 的交易中同时包含 <math>Y</math> 的百分比，即[[条件概率]] <math>P \left ( Y | X \right )</math>。如果同时满足'''最小支持度阈值'''和'''最小置信度阈值'''，则认为关联规则是有利或有用的。这些阈值由用户或者专家设定。

用一个简单的例子说明。表1是顾客购买记录的数据库D，包含6个交易。项集 <math>I=</math>{网球拍,网球,运动鞋,羽毛球}。考虑关联规则：网球拍<math> \Rightarrow </math>网球，交易1,2,3,4,6包含网球拍，交易1,2,6同时包含网球拍和网球，支持度<math>support= \frac{3}{6} = 0.5</math>，置信度<math>confident= \frac{3}{5} = 0.6</math>。若给定最小支持度<math> \alpha =0.5</math>，最小置信度<math> \beta =0.6</math>，关联规则网球拍<math> \Rightarrow </math>网球是有趣的，认为购买网球拍和购买网球之间存在强关联。


==分类==
关联规则有以下常见分类<ref name="data mining"></ref>：

'''根据关联规则所处理的值的类型'''
*如果考虑关联规则中的数据项是否出现，则这种关联规则是'''[[布尔关联规则]]'''（Boolean association rules）。例如上面的例子。
*如果关联规则中的数据项是数量型的，这种关联规则是'''[[数量关联规则]]'''（quantitative association rules）。例如年龄("20-25")<math>\Rightarrow</math>购买("网球拍")，年龄是一个数量型的数据项。在这种关联规则中，一般将数量'''离散化'''（discretize）为区间。

'''根据关联规则所涉及的数据维数'''
*如果关联规则各项只涉及一个维，则它是'''单维关联规则'''（single-dimensional association rules），例如购买("网球拍")<math>\Rightarrow</math>购买("网球")只涉及“购买”一个维度。
*如果关联规则涉及两个或两个以上维度，则它是'''多维关联规则'''（multi-dimensional association rules），例如年龄("20-25")<math>\Rightarrow</math>购买("网球拍")涉及“年龄”和“购买”两个维度。

'''根据关联规则所涉及的抽象层次'''
*如果不涉及不同层次的数据项，得到的是'''单层关联规则'''（single-level association rules）。
*在不同抽象层次中挖掘出的关联规则称为'''[[广义关联规则]]'''（generalized association rules）。例如年龄("20-25")<math>\Rightarrow</math>购买("HEAD网球拍")和年龄("20-25")<math>\Rightarrow</math>购买("网球拍")是广义关联规则，因为"HEAD网球拍"和"网球拍"属于不同的抽象层次。

==算法==
===Apriori 演算法===
{{main|先验算法}}
Apriori演算法所使用的前置统计量包括：
* 最大规则物件数：规则中物件组所包含的最大物件数量；
* 最小支援：规则中物件或是物件组必须符合的最低案例数；
* 最小信心水准：计算规则所必须符合的最低信心水准门槛。

===F-P算法===

==参考文献==
<references />

[[Category:數據挖掘]]