本页使用了标题或全文手工转换

关联规则学习

维基百科,自由的百科全书
(重定向自关联式规则
跳转至: 导航搜索

关联规则学习英语: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)t是I的非空子集,即,每一个交易都与一个唯一的标识符TID(Transaction ID)对应。关联规则是形如蕴涵式,其中分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。关联规则在D中的支持度(support)是D中事务包含的百分比,即概率置信度(confidence)是包含X的事务中同时包含Y的百分比,即条件概率。如果同时满足最小支持度阈值最小置信度阈值,则认为关联规则是有趣的。这些阈值由用户或者专家设定。

用一个简单的例子说明。表1是顾客购买记录的数据库D,包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则:网球拍网球,事务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演算法所使用的前置統計量包括了:

  • 最大規則物件數:規則中物件組所包含的最大物件數量,在微軟關聯規則參數為Maximum_Itemset_Size
  • 最小支援:規則中物件或是物件組必頇符合的最低案例數,在微軟關聯規則參數為Minimum_Support。
  • 最小信心水準:計算規則所必須符合的最低信心水準門檻,在微軟關聯規則參數為Minimum_Probability。

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. doi:10.1145/170035.170072. ISBN 0897915925. 
  3. ^ 3.0 3.1 J. Han, M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann: 2000