关联规则学习

关联规则学习(英語: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