关联规则基本算法及其应用1
需积分: 0 142 浏览量
2022-08-08
20:52:14
上传
评论
收藏 522KB DOCX 举报
关联规则基本算法及其应用
1．关联规则挖掘
1.1 关联规则提出背景
1993 年，Agrawal 等人在首先提出关联规则概念，同时给出了相应的挖掘算法 AIS，但
是性能较差。1994 年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名
的 Apriori 算法，至今 Apriori 仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研
究人员对关联规则的挖掘问题进行了大量的研究。关联规则挖掘在数据挖掘中是一个重要的
课题，最近几年已被业界所广泛研究。
关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。假设
分店经理想更多的了解顾客的购物习惯（如下图）。特别是，想知道哪些商品顾客可能会在
一次购物时同时购买？为回答该问题，可以对商店的顾客事物零售数量进行购物篮分析。该
过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关
联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而帮助他们开发更好的营
销策略。
1.2 关联规则的基本概念
关 联 规 则 定 义 为 ： 假 设
1 2
{ , ,... }
m
I i i i=
是 项 的 集 合 ， 给 定 一 个 交 易 数 据 库
， 其中每个事务(Transaction)t 是 I 的非空子集，即 ，每一个交易都与
一个唯一的标识符 TID(Transaction ID)对应。关联规则是形如 的蕴涵式， 其中
且 ， 和 分别称为关联规则的先导(antecedent 或 left-hand-side,
LHS)和后继(consequent 或 right-hand-side, RHS)。关联规则 在 D 中的支持度(support)
是 D 中事务包含 X∩Y 的百分比，即概率 P(X∩Y)；置信度(confidence)是包含 X 的事务中
同时包含 Y 的百分比，即条件概率 。如果满足最小支持度阈值和最小置信度阈值，
则称关联规则是有趣的。这些阈值由用户或者专家设定。
用一个简单的例子说明。
1 2
D={t ,t ,...,t }
m
t IÎ
X YÞ
X,Y IÎ
X Y
f
Ç =
X
Y
X YÞ
( | )P Y X
评论0
最新资源