数据仓库与数据挖掘基础第6章关联规则

数据仓库与数据挖掘基础第6章关联规则2024/3/28数据仓库与数据挖掘基础第6章关联规则关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则挖掘的一个典型的例子是购物篮分析。第六章挖掘大型数据库中的

关联规则数据仓库与数据挖掘基础第6章关联规则第一节关联规则挖掘顾客1顾客4顾客3顾客2牛奶面包谷类牛奶面包糖鸡旦牛奶面包黄油糖鸡旦市场分析员1、购物篮分析数据仓库与数据挖掘基础第6章关联规则问题：什么商品组或集合顾客多半会在一次购物时同时购买？回答：需要分析商店的顾客事务零售数据，并在其上运行购物篮分析。分析的结果可以用于市场规划、广告策划、分类设计。例如，购物篮分析可以帮助经理设计不同的商店布局，以及规划什么商品降价。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则1、购物篮分析策略一：经常购买的商品可以放近一些，以便进一步刺激这些商品一起销售。策略二：将经常购买的商品放在商店的两端，可能诱发买这些商品的顾客一路挑选其他商品。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则1、购物篮分析可以想象全域是商店中可利用的商品的集合，则每钟商品有一个布尔变量，表示该商品的有无。每个篮子可以用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示：第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则1、购物篮分析规则的支持度和置信度是两个规则兴趣度度量，反映规则的有用性和确定性，上述规则的支持度2%意味分析中的全部事务的2%同时购买计算机和操作系统软件。置信度60%意味购买计算机的顾客60%也购买操作系统软件。关联规则被认为是有趣的，如果它满足最小支持度阈值和最小置信度阈值。这些阈值可由用户和领域专家设定。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则2、基本概念设I={i1，i2，…，im}是项的集合，。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得TI。每一个事务有一个标识符TID。设A是一个项集，事务T包含A，当且仅当AT。关联规则是形如AB的蕴涵式，其中AI，BI，且AB=Ø。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则2、基本概念项的集合称为项集，包含K个项的项集称为K-项集。集合{computer，software}是一个2-项集。项集的出现频率是包含项集的事务数简称为频率、支持计数或计数。项集满足最小支持度，若项集的出现频率大于或等于最小支持度与D中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则2、基本概念关联规则的挖掘包含两个基本步骤：找出所有频繁项集：这些项集出现的频繁性至少和预定义的最小支持计数一样。由频繁项集产生强关联规则：这些规则必须满足最小支持度和最小置信度。挖掘关联规则的总体性能由第一步决定。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则3、关联规则挖掘的分类标准购物篮分析只是关联规则挖掘的一种形式。根据下列标准，关联规则有多种分类方法：根据规则中所处理的值的类型：若规则考虑项的在与不在，则它是布尔关联规则；若规则描述的是量化的项或属性之间的关联，则它是量化关联规则。如，下列为一个量化关联规则：第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则3、关联规则挖掘的分类标准根据规则中涉及的数据维：若关联规则中的项或属性每个只涉及一个维，则它是单维关联规则；若关联规则涉及两个或多个维，则它是多维关联规则。如第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则3、关联规则挖掘的分类标准根据规则集所涉及的抽象层：有些挖掘关联规则的方法可以在不同的抽象层发现规则。如，第一节关联规则挖掘购买的商品涉及不同的抽象层，称所挖掘的规则集由多层关联规则组成。否则，规则只涉及单一抽象层的项或属性，则该集合包含单层关联规则。数据仓库与数据挖掘基础第6章关联规则3、关联规则挖掘的分类标准根据关联规则的各种扩充：关联规则可以扩充到相关分析，以识别项是否相关。用最大模式（最大的频繁模式）或频繁闭项集显著压缩挖掘所产生的频繁项集数。第一节关联规则挖掘数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则1、Apriori算法Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，通过侯选项集找频繁项集。基本思路：Apriori使用一种称作逐层搜索的迭代方法，K-项集用于探索（K+1）-项集。首先，找出频繁1-项集的集合，记为L1；L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到找到频繁K-项集。找每个LK需要一次数据库扫描。其过程包括：连接和剪枝两个方面。数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则1、Apriori算法例如，设已有包含9个事务的事务数据库，即|D|=9，各事务按字典次序存放，设最小事务支持度计数为2。TID项ID的列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则1、Apriori算法项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2侯选集C1频繁集L1扫描D，对每个侯选1-项集计数比较侯选支持度计数与最小支持度计数设最小事务支持度计数为2，2/9=22%数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则1、Apriori算法项集{I1，I2}{I1，I3}{I1，I4}{I1，I5}{I2，I3}{I2，I4}{I2，I5}{I3，I4}{I3，I5}{I4，I5}由L1产生侯选2-项集C2扫描D，对每个侯选2-项集计数C2项集支持度计数{I1，I2}4{I1，I3}4{I1，I4}1{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2{I3，I4}0{I3，I5}1{I4，I5}0数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则1、Apriori算法由L2L2比较侯选支持度计数与最小支持度计数，得到频繁项集L2项集支持度计数{I1，I2}4{I1，I3}4{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2项集{I1，I2，I3}{I1，I2，I5}{I1，I3，I5}{I2，I3，I4}{I2，I3，I5}{I2，I4，I5}数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则1、Apriori算法扫描D，对每个侯选3-项集计数C3由L2产生侯选3-项集C3项集{I1，I2，I3}{I1，I2，I5}项集支持度计数{I1，I2，I3}2{I1，I2，I5}2比较侯选支持度计数与最小支持度计数，得到L3项集支持度计数{I1，I2，I3}2{I1，I2，I5}2由于L3L3产生的C4={{I1，I2，I3，I5}}的子集{I2，I3，I5}不是频繁的，所以C4=Ø，算法终止。数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则2、由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集，由它们可以产生强关联规则（满足最小支持度和最小置信度）。对于置信度，可以用项集支持度计数表示：其中，Support_count(A

B)是包含项集A

B的事务数，Support_count(A)是包含项集A的事务数。数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则2、由频繁项集产生关联规则可以产生关联规则如下：对于每个频繁集l，产生l的所有非空子集；对于l的每个非空子集s；若则输出规则：s(l-s)。其中min_confidence是最小置信度阈值。数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则2、由频繁项集产生关联规则例如，按照前例的事务数据库，设数据包含频繁项集l={I1，I2，I5}，则l的非空子集有：{I1，I2}，{I1，I5}，{I2，I5}，{I1}，{I2}，{I5}。可得到关联规则如：数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则2、由频繁项集产生关联规则如果最小置信度预值为70%，则规则2、3和6可以输出，因为这些规则满足强关联规则条件。规则编号关联规则置信度1I1I2I5Conf=2/4=50%2I1I5I2Conf=2/2=100%3I2I5I1Conf=2/2=100%4I1

I2I5Conf=2/6=33%5I2

I1I5Conf=2/7=29%6I5

I1I2Conf=2/2=100%数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则3、冰山查询冰山查询在数据挖掘中经常使用，特别是对购物篮分析，apriori算法可以用来提高冰山查询的效率。冰山查询（icebergquery）在一个属性或属性集上计算一个聚集函数，以找出大于某个指定阈值的聚集值。

数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则3、冰山查询给定关系R，它具有属性a_1，a_2，…，a_n和b，一个聚集函数agg_fuc，冰山查询形如：SelectR.a_1，R.a_2，…，R.a_n，agg_fuc(R.b)FromrelationRGroupbyR.a_1，R.a_2，…，R.a_nHavingagg_fuc(R.b)>=threshold给定大量输入元组，满足having子句中阈值的输出元组数量相对很少。输入数据集为“冰山”，输出结果为“冰山顶”。数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则3、冰山查询例，设给定销售数据，期望产生一个顾客-商品对的列表，要求这些顾客购买商品数量达到5件或更多，则冰山查询表示如：SelectP.cust_ID，P.item_ID，SUM(P.qty)FromPurchasesPGroupbyP.cust_ID，P.item_IDHavingSUM(P.qty)>=5数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则3、冰山查询可以采用apriori算法，不考虑每个顾客购买的每种商品的数量，按照以下步骤：产生cust_list，总共购买5件以上商品的顾客表：

SelectP.cust_IDFromPurchasesPGroupbyP.cust_IDHavingSUM(P.qty)>=5数据仓库与数据挖掘基础第6章关联规则第二节挖掘事务数据库的单维布尔关联规则3、冰山查询可以采用apriori算法，不考虑每个顾客购买的每种商品的数量，按照以下步骤：产生item_list，被顾客购买数量5件以上商品表：

SelectP.item_IDFromPurchasesPGroupbyP.item_IDHavingSUM(P.qty)>=5数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则1、多层关联规则由于许多应用环境下，多维数据空间数据的稀疏性，在低层或原始层的数据项之间很难找出强关联规则。而在较高的概念层寻找强关联规则可以得到具有普遍意义的知识。对于某用户代表普遍意义的知识，对另一用户可能是新颖的。所以，DMS应当提供一种能力，在多个抽象层挖掘关联规则，并容易在不同的抽象空间转换。数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则1、多层关联规则例如，给定某事务的任务相关数据集D，它是计算机部的销售数据，对每个事务TID给出了购买的商品。TID购买的商品T1IBM台式机，HP激光打印机T2教学软件，财务软件，操作系统软件T3双飞燕鼠标，康柏键盘，IBM台式机T4DEC服务器，操作系统软件，OFFICE软件T5IBM笔记本电脑，佳能喷墨彩色打印机数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则1、多层关联规则商品的概念分层如：计算机类商品软件计算机计算机辅件打印机台式机笔记本应用系统彩色黑白鼠标键盘IBM…康柏财务操作系统佳能HP双飞燕康柏数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则1、多层关联规则概念分层定义了由低层概念到更一般的高层概念的映射序列，可以通过将数据内的低层概念用概念分层的高层概念替换，对数据概化。例中概念分层为4层，记为0，1，2和3。在最低的原始层很难找出有趣的购买模式，如{IBM台式机，HP激光打印机}不太可能满足最小支持度。而{计算机，打印机}更容易满足最小支持度。数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法问题：如何使用概念分层有效挖掘多层关联规则。考察一些基于支持度-置信度框架的方法。对于所有层使用一致的最小支持度在较低层使用递减的最小支持度逐层独立层交叉单项过滤层交叉K-项集过滤数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法对于所有层使用一致的最小支持度：在每一层挖掘时，使用相同的最小支持度阈值。如整个使用最小支持度阈值5%。计算机[support=10%]台式机[support=4%]笔记本[support=6%]层1min_sup=5%层2min_sup=5%数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法在较低层使用递减的最小支持度：在每个抽象层有自己的最小支持度阈值。抽象层越低，对应的阈值越小。如层1和层2的最小支持度阈值分别为5%和3%。计算机[support=10%]台式机[support=4%]笔记本[support=6%]层1min_sup=5%层2min_sup=3%数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝。考察每个节点，不管它的父节点是否是频繁的。计算机[support=10%]台式机[support=4%]笔记本[support=6%]层1min_sup=12%层2min_sup=3%数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的。根据递减支持度，如果父节点是频繁的，它的子女将被考察；否则，它的子孙将由搜索中剪枝。计算机[support=10%]台式机（未考察）笔记本（未考察）层1min_sup=12%层2min_sup=3%数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法层交叉k-项集过滤：一个第i层的k-项集被考察，当且仅当它在第（i-1）层的对应父节点k-项集是频繁的。计算机，打印机[support=8%]台式机，彩色打印机[support=4%]笔记本，黑白打印机[support=2%]层1min_sup=5%层2min_sup=3%数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法

逐层独立策略的条件宽松，而层交叉k-项集过滤策略的限制太强，层交叉单项过滤策略是一个折衷。进一步改进为受控层交叉单项过滤策略。通过设置一个层传递阈值，用于向较低层“传递”相对频繁的项。数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法

受控的层交叉单项过滤策略：如果满足层传递阈值，则允许考察不满足最小支持度阈值项的子女。计算机[support=10%]台式机[support=4%]笔记本[support=6%]层1min_sup=12%Level_pass_sup=8%层2min_sup=3%数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则2、挖掘多层关联规则的方法

交叉层关联规则：规则中的项不属于同一概念层，挖掘交叉层i与j层关联规则应当使用较低层j的最小支持度阈值，使得j层的项可以包含在分析中。前面所讨论的5种方法属于发现的频繁项集的所有项都属于同一概念层1层。如

计算机软件或台式机彩色打印机对于不属于同一概念层（1层和2层）的规则：计算机彩色打印机数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则3、检查冗余的多层关联规则概念分层在数据挖掘中允许不同的抽象层的知识发现，如多层关联规则。然而，当挖掘多层关联规则时，由于项之间的“祖先”关系，有些发现的规则将是冗余的。数据仓库与数据挖掘基础第6章关联规则第三节挖掘事务数据库的多层关联规则3、检查冗余的多层关联规则例如，考虑下面的规则：台式机彩色打印机[sup=8%，conf=70%]...(1)IBM台式机彩色打印机[sup=2%，conf=72%]…(2)不难发现规则R1是R2的祖先，若将R2中的项用它在概念分层中的祖先替换，就可以得到R1。定义：如果根据规则的祖先，一个规则的支持度和置信度都接近于“期望”值，则规则被认为是冗余的。冗余的规则应当删除。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则1、多维关联规则考察关联规则

buys（X，”IBM台式机”）

buys（X，”HP激光打印机”）其中，X表示变量，代表顾客，谓词buys在多维数据库中称作维，上述规则为单维关联规则或维内关联规则。这种规则通常由事务数据或从事务数据库挖掘。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则1、多维关联规则关系数据库和数据仓库中的数据的存储是多维的。如购物顾客的信息可能包括年龄、职业、收入和地址等。将数据库的每个属性或数据仓库的每个维看作一个谓词，这样就可以挖掘多维关联规则，如age（X，”23…33”）

occupation（X，”teacher”）

buys（X，”laptop”）涉及两个以上维或谓词的关联规则称为多维关联规则。每个谓词不重复出现，称为不重复谓词。具有不重复谓词的关联规则称作维间关联规则。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则1、多维关联规则对于规则形如age（X，”23…33”）buys（X，”laptop”）

buys（X，”b/wprinter”）包含某些谓词的多次出现的关联规则称为混合多维关联规则。数据库属性可能是分类的或量化的。分类属性是指具有有限个不同值，值之间无序，又称标称属性，如（age，brand，color）。量化属性是数值的，并在值之间具有一个隐含的序，如（age，income，price）。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则1、多维关联规则挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：使用预定义的概念分层对量化属性离散化，该方法称为使用量化属性的静态离散化挖掘多维关联规则；根据数据的分布，将量化的属性离散化到“箱”，这种方法挖掘的关联规则称为量化关联规则；量化属性离散化，以符合区间数据的语义，这种量化关联规则称作基于距离的关联规则。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则2、使用量化属性挖掘多维关联规则（age）（buys）（income）（age，income）（age，buys）（income，buys）（age，income，buys）（）0-D顶点方体1-D方体2-D方体3-D基本方体数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则3、挖掘量化关联规则量化关联规则是多维关联规则，其中数值属性动态离散化，以满足某种挖掘标准，如最大挖掘规则的置信度。量化关联规则如：age（X，”23…33”）

income（X，”32k…42k”）

buys（X，”laptop”）这种规则包含左边两个量化维（量化属性），右边一个分类属性，称为2-维量化关联规则。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则3、挖掘量化关联规则对于量化关联规则可以通过关联规则聚类系统ARCS（associationruleclusteringsystem）方法找出关联规则。ARCS的基本步骤有：分箱：等宽分箱、等深分箱、基于同质的分箱找频繁谓词集关联规则聚类数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则4、挖掘基于距离的关联规则关联规则的一个缺点是它们不允许近似的属性值，而往往在一些情形下，需要考察属性值的接近性，支持度和置信度均不支持这种近似，所以需要引入基于距离的关联规则挖掘。这种规则紧扣区间数据的语义，并允许数据值的近似。量化关联规则无法实现，因为未考察数据点之间或区间之间的相对距离。数据仓库与数据挖掘基础第6章关联规则第四节挖掘关系数据库和数据仓库的多维关联规则4、挖掘基于距离的关联规则通常使用一个两遍算法挖掘基于距离的关联规则。第一遍使用聚类找出区间或簇；第二遍搜索频繁地一起出现的簇组得到基于距离的关联规则。数据仓库与数据挖掘基础第6章关联规则第五节关联挖掘到关联分析问题：挖掘了关联规则后，数据挖掘系统如何