关联规则学习
关联规则学习(英語:Association rule learning)是一种在大型数据库中发现变量之间的有趣性关系的方法。它的目的是利用一些有趣性的量度来识别数据库中发现的强规则。[1] 基于强规则的概念,Rakesh Agrawal等人[2]引入了关联规则以发现由超市的POS系统记录的大批交易数据中产品之间的规律性。例如,从销售数据中发现的规则 {洋葱, 馬鈴薯}→{汉堡} 会表明如果顾客一起买洋葱和馬鈴薯,他们也有可能买汉堡的肉。此类信息可以作为做出促销定价或产品植入等营销活动决定的根据。除了上面购物篮分析中的例子以外, 关联规则如今还被用在许多应用领域中,包括网络用法探勘、入侵检测、连续生产及生物信息学中。与序列探勘相比,关联规则学习通常不考虑在事务中、或事务间的项目的顺序。
基本概念
编辑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算法
编辑参考文献
编辑- ^ 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.
- ^ 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.0 3.1 J. Han, M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann: 2000