《数据挖掘——第三章关联规则挖掘)》由会员分享，可在线阅读，更多相关《数据挖掘——第三章关联规则挖掘)（87页珍藏版）》请在金锄头文库上搜索。
1、关联规则挖掘技术,关联关系一个来自沃尔玛超市的真实案例，尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的稍量大幅增加了。这可不是一个笑话，而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来，美国的妇女通常在家照顾孩子，所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发砚为商家带来了大量的利润，但是如何从浩如烟海却又杂乱无章的数据中，发现啤酒和尿布销售之间的联系呢？这又给了我们什么样的启示呢？,购物篮分析“啤酒和尿布”的故事是营销届的神话，“啤酒”和“尿布”两个看上去没有关系的商品摆放在一起
2、进行销售、并获得了很好的销售收益，这种现象就是卖场中商品之间的关联性，研究“啤酒与尿布”关联的方法就是购物篮分析，购物篮分析是沃尔玛秘而不宣的独门武器，购物篮分析可以帮助我们在门店的销售过程中找到具有关联关系的商品，并以此获得销售收益的增长！,D=牛肉，鸡肉，牛奶，奶酪，靴子，衣服，,t1: 牛肉、鸡肉、牛奶 t2: 牛肉、奶酪 t3: 奶酪、靴子 t4: 牛肉、鸡肉、奶酪 t5: 牛肉、鸡肉、衣服、奶酪、牛奶t6: 鸡肉、衣服、牛奶 t7: 鸡肉、牛奶、衣服如何从客户购物篮中找出具有关联关系的商品组合呢？,关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一
3、定的关联关系，那么，其中一个事物就能够通过其他事物预测到。 典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。,关联规则简介,关联规则(Association Rule Mining)挖掘是数据挖掘中最活跃的研究方法之一 最早是由R.Agrawal等人提出的 其目的是为了发现超市交易数据库中不同商品之间的关联关系。 一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。 经典的关联规则挖掘算法：Apriori算法和FP-growth算法,关联规则挖掘 ,1.1关联规则挖掘的基本概念
4、,1. 购物篮分析引发关联规则挖掘的例子 问题：“什么商品组或集合顾客多半会在一次购物中同时购买？” 购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，通过对购物篮清单的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。,例1购买计算机与购买财务管理软件的关联规则可表示为： computer financial_management_softwaresupport=2%,confidence=60% support为支持度，confidence为置信度。该规则表示：在所分析的全部事务中，有2的事务同时购买计算机和财务管
5、理软件；在购买计算机的顾客中60也购买了财务管理软件。,理解：关联分析中的三个重要的概念 举例： 10000个人购买了产品，其中购买A产品的人是1000个，购买B产品的人是2000个，AB同时购买的人是800个。,支持度指的是关联的产品（假定A产品和B产品关联）同时购 买的人数占总人数的比例，即800/10000=8%，有8%的用户 同时购买了A和B两个产品；,可信度指的是在购买了一个产品之后购买另外一个产品的可能 性，如购买了A产品之后购买B产品的可信度=800/1000=80%,支持度,可信度,定义42关联规则 XY对事物集D的支持度（support）定义为D中包含有事务X和Y的百分比。关
6、联规则XY对事务集合D的置信度（confidence）定义为D中包含有X的事务数与同时包含Y的百分比。即： l support(XY)(包含X和Y的事务数/事务总数)100l confidence(XY)(包含X和Y的事务数/包含X的事务数)100,定义43置信度和支持度均大于给定阈值（即最小置信度阈值和最小支持度阈值）。即：support(XY) min_supconfidence(XY) min_conf 的关联规则称为强规则；否则称为弱规则。数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。,强规则XY对应的项集（XY）必定是频繁集。因此，可以
7、把关联规则挖掘划分为以下两个子问题： 根据最小支持度找出事务集D中的所有频繁项集。核心 根据频繁项集和最小置信度产生关联规则。较易,规则度量：支持度与可信度,查找所有的规则 X & Y Z 具有最小支持度和可信度 支持度, s, 一次交易中包含X 、 Y 、 Z的可能性 可信度, c, 包含X 、 Y的交易中也包含Z的条件概率,设最小支持度为50%, 最小可信度为 50%, 则可得到 A C (50%, 66.6%) C A (50%, 100%),Let min_support = 50%, min_conf = 50%:,For rule A C: support = support(AC
8、) = 50% confidence = support(AC)/support(A) = 66.6%,Min. support 50% Min. confidence 50%,关联规则就是支持度和信任度分别满足用户给定阈值的规则。 发现关联规则需要经历如下两个步骤： 找出所有频繁项集。 由频繁项集生成满足最小信任度阈值的规则。,以商场超市的市场数据库为例，形式化地描述关联规则。 定义41 设I=i1，i2，,im是项的集合，表示各种商品的集合；D= t1，t2，,tn为交易集，表示每笔交易的集合（是全体事务的集合）。其中每一个事务T都是项的集合，且有TI。每个事务都有一个相关的唯一标识符和它
9、对应，也就是事务标识符或TID。 设X为一个由项目构成的集合，称为项集，当且仅当XT时我们说事务T包含X。 项集X在在事务数据库DB中出现的次数占总事务的百分比叫做项集的支持度。 如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。,关联规则是形如XY的蕴含式，其中XI，YI且XY=，则X称为规则的条件，Y称为规则的结果。 如果事务数据库DB中有s%的事务包含XY，则称关联规则XY的支持度为s%。支持度是一个概率值。,2. 关联规则 关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出
10、项目集中的项目之间的相关性。 项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系。,表4-1,3. 关联规则挖掘 关联规则挖掘：给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和最小支持度。,例 购买商品事务如下表所示，设最小支持度为50%, 最小可信度为 50%, 则可得到以下关联规则：A C (50%, 66.6%)C A (50%, 100%),支持度,可信度,表4-2,4.关联规则挖掘的分类 （1） 基于规则中处理的变量的类别基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。 布尔型关联规则：如果
11、规则考虑的关联是项“在”或“不在”，则关联规则是布尔型的。例如，由购物篮分析得出的关联规则。 量化型关联规则：如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。,例如： 以下是量化型关联规则的一个例子（其中X为表示顾客的变量，量化属性age 和income已经离散化）： age(X,“3039”)income(“42K48K”)buys(X,“high_resolution_TV”)量化型关联规则中也可以包含多种变量。例如： 性别=“女”=职业=“秘书” ，是布尔型关联规则； 性别=“女”=avg（月收入）=2300，涉及的收入是数值类型，所以是一个量化型关联规则。,（2）基于
12、规则中数据的抽象层次基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。 单层的关联规则：所有的变量都不涉及不同抽象层次的项或属性。例如：buys(X, “computer”) buys(X, “printer”)顾客X购买的商品不涉及不同抽象层次（“computer” 和“printer”在同一个抽象层），因此是单层关联规则。 多层的关联规则：变量涉及不同抽象层次的项或属性。例如：age(X,“3039”) buys(X, “laptop computer”)age(X,“3039”) buys(X, “computer”) 顾客X购买的商品涉及不同抽象层次（“computer”
13、在比“laptop computer”高的抽象层），因此是多层关联规则。,（3）基于规则中涉及到的数据的维数 基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。 单维关联规则：处理单个维中属性间的关系，即在单维的关联规则中，只涉及到数据的一个维。例如：用户购买的物品：“咖啡=砂糖”，这条规则只涉及到用户的购买的物品。 多维关联规则：处理多个维中属性之间的关系，即在多维的关联规则中，要处理的数据将会涉及多个维。例如：性别=“女”=职业=“秘书”，这条规则就涉及到两个维中字段的信息，是两个维上的一条关联规则。,给出了关联规则的分类之后，就可以考虑某个具体的关联规则挖掘算法适用于哪一类规
14、则的挖掘，某类关联规则又可以用哪些不同的方法进行处理。 最简单的是单维、单层、布尔型的关联规则。,1. 术语 关联规则挖掘即给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和最小支持度。,4.2关联规则挖掘的过程,定义44在关联规则挖掘算法中，把项目的集合称为项集（itemset），包含有k个项目的项集称为k-项集。包含项集的事务数称为项集的出现频率，简称为项集的频率或支持度计数。如果项集的出现频率大于或等于最小支持度s与D中事务总数的乘积，则称该项集满足最小支持度s。如果项集满足最小支持度，则称该项集为频繁项集（frequent items
15、et）。,例一个食品连锁店保留着每周的事务记录，其中每一条事务表示在一项收款机业务中卖出的项目。连锁店的管理会收到一个事务汇总报告，报告表明了每种项目的销售量是多少。此外，他们要定期了解哪些项目经常被顾客一起购买。他们发现顾客购买了花生酱后，100%地会购买面包。而且，顾客购买了花生酱后，有33%也购买果冻。不过，所有事务中大约只有50%包含花生酱。被用于在其中寻找关联规则的数据库可以看作为一个元组集合，每个元组包含一组项目。一个元组可能是：花生酱、面包、果冻 包含三个项目：花生酱、面包、果冻 每个项目表示购买的一种产品 一个元组是一次购买的产品列表,表4-3,项目的个数成指数增长：从5个项目
16、的集合得到31个项目集合（忽略空集）,表4-4,2关联规则的挖掘过程,最常用的关联规则挖掘方法被分解为下面两步： 第1步：找出所有的频繁项集，即找出支持度大于或等于给定的最小支持度阈值的所有项集。可以从1到k递归查找k-频繁项集。第2步：由频繁项集产生强关联规则，即找出满足最小支持度和最小置信度的关联规则。,找出满足定义的大项目集,从大项目集（频繁项目集）生成关联规则,定义45大（频繁）项目集是出现次数大于阈值S的项目集。用符号L表示大项目集组成的整个集合，用表示一个特定的大项目集。一旦找出大项目集，则对于任何有趣的关联规则XY，在频繁项目集的集合中一定有XY。,任何大项目集的子集也是大的,4.3 大项目集,关联规则中使用了大量的符号，这些符号汇总如下。 一个特定符号所带的下标表示所考虑的集合的大小，例如，lk表示一个大小为k的项目集。 一些算法将事务集合分为若干个分区，在这种情况下，用p表示分区的数目，用上标表明分区的编号。例如，Di表示D的第i个分区。,
