《(精品)第五章_____关联规则挖掘.ppt》由会员分享，可在线阅读，更多相关《(精品)第五章_____关联规则挖掘.ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 关联挖掘关联挖掘 5.1概述概述一一.关联规则挖掘关联规则挖掘:在在交交易易数数据据、关关系系数数据据或或其其他他信信息息载载体体中中，查查找找存存在在于于项项目目集集合或对象集合之间的合或对象集合之间的频繁频繁模式、关联、相关性、或因果结构模式、关联、相关性、或因果结构。关联规则与传统的分类规则的区别关联规则与传统的分类规则的区别:在在某某条条规规则则中中以以前前提提条条件件出出现现的的属属性性可可以以出出现现在在第第二二条条规规则的结论中。则的结论中。传传统统的的分分类类规规则则通通常常将将规规则则的的结结果果限限定定为为一一个个单单一一的的属属性性值，关联规则生成器允许其结
2、果包含一个或多个属性值。值，关联规则生成器允许其结果包含一个或多个属性值。举例：举例：规则形式：规则形式：“H Head Bodysupport,confidence”.buys(x,“diapers”)buys(x,“beers”)0.5%,60%major(x,“CS”)takes(x,“DB”)grade(x,“A”)1%,75%应用应用：顾客购物分析、目录设计、商品广告邮寄分析、追加销售、顾客购物分析、目录设计、商品广告邮寄分析、追加销售、商品货架设计、仓储规划、网络故障分析以及根据购买模式对用商品货架设计、仓储规划、网络故障分析以及根据购买模式对用户进行分类户进行分类给定给定:(1)
3、交易数据库交易数据库(2)每笔交易是每笔交易是：一个项目列表一个项目列表(消费者一次购买活动中购买的消费者一次购买活动中购买的商品商品)查找查找:所有所有描述一个项目集合与其他项目集合相关性的规则描述一个项目集合与其他项目集合相关性的规则应用应用*护理用品护理用品(商店应该怎样提高护理用品的销售？商店应该怎样提高护理用品的销售？)家用电器家用电器 *(其他商品的库存有什么影响其他商品的库存有什么影响?)规则度量：支持度与可信度规则度量：支持度与可信度 查找所有的规则查找所有的规则X&Y Z 具有最小具有最小支持度支持度和和可信度可信度支持度支持度s:一次交易中包含一次交易中包含X、Y、Z的的可
4、能可能性性可信度可信度c,包含包含X、Y的交易中也包的交易中也包含含Z的的条件概率条件概率设最小支持度为设最小支持度为50%,最小可信度最小可信度为为 50%,则可得到则可得到A C (50%,66.6%)C A (50%,100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户二、关联规则挖掘分类二、关联规则挖掘分类1、根据规则中所处理的根据规则中所处理的值类型划分值类型划分：如如果果规规则则考考虑虑的的关关联联是是项项的的在在与与不不在在，则则它它是是布布尔尔关关联联规规则则(Booleanassociationrule)。例如，规则例如，规则Buys(X,”
5、computer”)Buys(X,”financial_management_software”)support=2%,confidence=60%5.1是由购物篮分析得到的布尔关联规则。是由购物篮分析得到的布尔关联规则。如果规则描述的是量化的项或属性之间的关联，则它是量化如果规则描述的是量化的项或属性之间的关联，则它是量化关联规则关联规则(quantitativeassociationrule)。如如:age(X，“3039”)income(X，“42K48K”)buys(X，“computer”)(5.2)注意，量化属性注意，量化属性age和和income已离散化。已离散化。2、根据规则中
6、涉及的数据维划分：根据规则中涉及的数据维划分：如果关联规则中的项或属性每个只涉及一个维，则它是单如果关联规则中的项或属性每个只涉及一个维，则它是单维关联规则维关联规则 (5.1)(5.1)是单维关联规则，因为它只涉及一个维是单维关联规则，因为它只涉及一个维buysbuys。如果规则涉及两个或多个维，则它是多维关联规则，如果规则涉及两个或多个维，则它是多维关联规则，(5(52)2)是一个多维关联规则，因为它涉及三个维是一个多维关联规则，因为它涉及三个维age,age,，incomeincome和和buysbuys。age(X，“3039”)income(X，“42K48K”)buys(X，“ca
7、r”)3、根据规则集所涉及的抽象层划分：根据规则集所涉及的抽象层划分：有有些些挖挖掘掘关关联联规规则则的的方方法法可可以以在在不不同同的的抽抽象象层层发发现现规规则则。例例如，假定挖掘的关联规则集包含下面规则：如，假定挖掘的关联规则集包含下面规则：age(X，“3039”)buys(X,”notebook_computer”)age(X，“3039”)buys(X,”computer”)，(5.3)购买的商品涉及不同的抽象层购买的商品涉及不同的抽象层,所挖掘的规则称为所挖掘的规则称为-多层关联规则。多层关联规则。反之，如果在给定的规则集中，规则不涉及不同抽象层的项反之，如果在给定的规则集中，规
8、则不涉及不同抽象层的项或属性，则该集合包含单层关联规则或属性，则该集合包含单层关联规则5.1三三三三.购物分析 作为商家主管，想更加了解顾客的购物习惯。尤其希望作为商家主管，想更加了解顾客的购物习惯。尤其希望了解在一次购物过程中，那些商品会在一起被购买，这就需了解在一次购物过程中，那些商品会在一起被购买，这就需要进行市场货物分析要进行市场货物分析，即对顾客在商场购物交易记录数据进，即对顾客在商场购物交易记录数据进行分析。所分析的结果可帮助商家制定有效的营销策略行分析。所分析的结果可帮助商家制定有效的营销策略 如如果果把把商商店店中中所所有有销销售售商商品品设设为为一一个个集集合合，则则每每种种
9、商商品品（Item)Item)可可看看成成一一个个布布尔尔变变量量，表表示示该该商商品品是是否被购买。每次购物可用一个布尔向量表示。否被购买。每次购物可用一个布尔向量表示。这这样样就就可可以以分分析析布布尔尔向向量量，得得到到反反映映商商品品频频繁繁关关联联或或同同时时购购买买的的购购买买模模式式。这这些些模模式式可可以以用用关关联联规规则则的的形形式式表表示示。例例如如，购购买买计计算算机机也也趋趋向向于于同同时时购购买买财财务管理软件可以用以下关联规则表示：务管理软件可以用以下关联规则表示：Buys(X,”computer”)Buys(X,”computer”)Buys(X,”Buys(X
10、,”financial_management_software”)”)supportsupport=2%,=2%,confidenceconfidence=60%5.1=60%5.1规则的支持度和置信度是两个规则兴趣度度量规则的支持度和置信度是两个规则兴趣度度量,分别反映发现规分别反映发现规则的则的有用性有用性和和确定性确定性。如果关联规则满足最小支持度阈值和最小置信度阈值，则该关联如果关联规则满足最小支持度阈值和最小置信度阈值，则该关联规则被认为是规则被认为是有趣的有趣的。另外有趣的模式：另外有趣的模式：（1 1）规则显示出某个商品的销售额上升，而销售额的上升是与）规则显示出某个商品的销售额
11、上升，而销售额的上升是与一个或多个其它商品关联的结果。可利用这个信息来促销因相互一个或多个其它商品关联的结果。可利用这个信息来促销因相互关联而销售额增加的商品关联而销售额增加的商品（2 2）规则显示出某个关联的置信度低于所期望的值）规则显示出某个关联的置信度低于所期望的值 -关联规则列出的商品在争夺同一市场关联规则列出的商品在争夺同一市场 典型的关联规则算法典型的关联规则算法是是R.AgrawalR.Agrawal等等19941994年提出年提出的的AprioriApriori算法算法。Apriori算法是一种最有影响的挖掘布尔关联规则频繁算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。项
12、集的算法。5 5 5 52 2 2 2 由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则一、基本概念(表示)设设I=i1,i2,I=i1,i2,imim 是是数据项的集合。数据项的集合。D D是是数数据据库库中中与与任任务务相相关关的的事事务务的的集集合合，其其中中每每个个事事务务T T是是数数据据项项I I的子集，即的子集，即 T T I I 每一个事务有一个标识符，称作每一个事务有一个标识符，称作TIDTID。关联规则是形如关联规则是形如 “A A B B”的蕴含式，的蕴含式，其中其中 “A A I I，B B
13、 I I，且且A A B=B=“。规则规则“A A B B”在事务集在事务集D D中成立，中成立，且且具有支持度具有支持度s s和信任度和信任度c.c.5-2项项的的集集合合同同时时满满足足最最小小支支持持度度阈阈值值（min_supmin_sup）和和最最小小置置信信度度阈阈值值（min_confmin_conf）的规则称作的规则称作强规则强规则。项的集合称为项集项的集合称为项集(itemsetitemset)。包含包含k k个项的项集称为个项的项集称为k-k-项集。项集。集合集合computercomputer，financial_management_softwarefinancial_
14、management_software是一个是一个2-2-项集。项集。项集的项集的出现频率出现频率是包含项集的事务数是包含项集的事务数(支持计数或计数支持计数或计数)。如如果果项项集集的的出出现现频频率率大大于于或或等等于于min_sup与与D中中事事务务总数的乘积总数的乘积,则称该项集满足最小支持度则称该项集满足最小支持度min_sup。如如果果项项集集满满足足最最小小支支持持度度，则则称称它它为为频频繁繁项项集集(frequentitemset)。频繁频繁k-项集的集合通常记作项集的集合通常记作Lk。关联规则挖掘关联规则挖掘一个例子一个例子对于对于AC：support=support(A、
15、C)=50%confidence=support(C)/support(A)=66.6%最小支持度 50%最小可信度 50%二、Apriori算法算法1、Apriori算法分两步进行：算法分两步进行：（1 1）找出所有频繁数据项集，即找出所有支持度超过指定阈找出所有频繁数据项集，即找出所有支持度超过指定阈值的数据项集值的数据项集 （2 2）利用频繁数据项集，生成侯选的关联规则，并验证其可）利用频繁数据项集，生成侯选的关联规则，并验证其可信度。信度。如果可信度超过指定阈值，则该侯选关联规则为要找的关联规如果可信度超过指定阈值，则该侯选关联规则为要找的关联规则则2、Apriori的基本思想的基本思
16、想:频繁项集的任何子集也一定是频繁的频繁项集的任何子集也一定是频繁的频繁项集性质的频繁项集性质的先验知识（先验知识（priori）3、Apriori算法：使用候选项集找频繁项集算法：使用候选项集找频繁项集Apriori使使用用一一种种称称作作逐逐层层搜搜索索的的迭迭代代方方法法，利利用用k-项项集集来来产产生生(k+1)-项集。项集。首先，找出频繁首先，找出频繁1-项集的集合。该集合记作项集的集合。该集合记作L1。然然后后利利用用L1找找频频繁繁2-项项集集的的集集合合L2，如如此此不不断断循循环环下下去去，直直到到不能找到频繁不能找到频繁k-项集项集。每挖掘一层每挖掘一层Lk,就需要扫描整个
17、数据库。就需要扫描整个数据库。（1）连接步：为）连接步：为找找Lk，通过通过Lk-1与自己连接产生候选与自己连接产生候选k-项集的集项集的集合。合。该候选项集的集合记作该候选项集的集合记作Ck。设设l1和和l2是是Lk-1中的两个项集。中的两个项集。记号记号li(j)表示表示li的第的第j项项为为方方便便，假假定定交交易易数数据据库库中中的的交交易易记记录录已已按按字字典典次次序序排排序序。把把Lk-1的连接操作记为：的连接操作记为：Lk-1 Lk-1其中元素可连接的条件是其中元素可连接的条件是，它们前它们前(k-2)个项相同（个项相同（k=2)。即：即：l11=l21 l12=l22.l1k
18、-2=l2k-2 l1k-1 l2k-1（2 2）剪枝步剪枝步(删除）删除）：C Ck k是是L Lk k的的超超集集；即即其其中中的的各各元元素素不不一一定定都都是是频频繁项集，但所有的频繁繁项集，但所有的频繁k-k-项集都包含在其中。项集都包含在其中。即：即：L Lk k C Ck k 扫扫描描数数据据库库，可可以以确确定定C Ck k中中每每个个候候选选项项集集的的支支持持频频度度，从从而而确确定定L Lk k 中中各各元元素素(频频繁繁k-k-项项集集，即即所所有有频频度度不不小小于于最最小支持度）。小支持度）。然然而而C Ck k 中中的的项项集集可可能能很很大大，这这样样所所涉涉及
19、及的的计计算算量量就就很很大大。为压缩，可以使用为压缩，可以使用如果一个候选如果一个候选k-k-项集的项集的(k-1)-(k-1)-子集不属于子集不属于L Lk-1k-1，则该候选不可能成为频繁则该候选不可能成为频繁k-k-项集项集L Lk k是的元素是的元素,从而可以由中删除。从而可以由中删除。可可以以利利用用HASHHASH表表来来保保存存所所有有频频繁繁项项集集以以便便能能快快速速完完成成这这一一子子集测试工作。集测试工作。例例5.15.1 交交易易记记录录事事务务数数据据库库有有9 9个个事事务务。用用AprioriApriori算算法法寻寻找找D D中的频繁项集中的频繁项集。5-31
20、)1)计算计算C C1 1并计数并计数.在在算算法法的的第第一一次次迭迭代代，每每个个项项都都是是候候选选1-1-项项集集的的集集合合的的成成员。扫描所有的事务，对每个事务出现次数计数。员。扫描所有的事务，对每个事务出现次数计数。2)2)确定确定L L1 1.假假定定最最小小事事务务支支持持计计数数为为2 2（即即min_sup=2/9=22%min_sup=2/9=22%）。可可以以确确定定频频繁繁1-1-项项集集的的集集合合L L1 1。它它由由具具有有最最小小支支持持度度的的候候选选1-1-项集组成。项集组成。3 3）生成）生成C C2 2为为发发现现频频繁繁2-2-项项集集的的集集合合
21、，算算法法使使用用产产生生候候选选2-2-项项集集的集合。由个的集合。由个2-2-项集组成。项集组成。4 4）计算）计算C C2 2中成员出现的次数中成员出现的次数 扫描扫描D D中事务，计算中每个候选项集的支持计数，中事务，计算中每个候选项集的支持计数，5 5）由）由C C2 2确定确定L L2 2确确定定频频繁繁2-2-项项集集的的集集合合，它它具具有有最最小小支支持持度度的的中中的的候候选选2-2-项集组成。项集组成。6 6）候选）候选3-3-项集的集合的产生如下表项集的集合的产生如下表5-25-2所示：所示：表5-2 7)7)扫扫描描D D中中事事务务，以以确确定定L L3 3，它它由
22、由具具有有最最小小支支持持度度的的C C3 3中中的的候选候选3-3-项集组成项集组成 8)8)算算法法使使用用L3 L3产产生生候候选选4-4-项项集集的的集集合合C C4 4。C4=I1C4=I1，I2I2，I3I3，I5I5，因因为为它它的的子子集集I2,I3I2,I3，I5I5不不是是频频繁繁的的，这个项集被剪去，这个项集被剪去，这样这样C C4 4=，因此算法终止因此算法终止，找出了所有的频繁项集。，找出了所有的频繁项集。4.14.1三、三、由频繁项集产生关联规则由频繁项集产生关联规则 对对于于置置信信度度，可可以以用用下下式式计计算算，其其中中条条件件概概率率用用项项集集支支持持度
23、度计计数表示数表示：5.4产生关联规则的步骤产生关联规则的步骤(1)对于每个频繁项对于每个频繁项集集l，产生产生l的所有非空子集。的所有非空子集。(2)对于对于l的每个非空子集的每个非空子集s，如果，如果，则输出规则则输出规则其中其中，min_conf是最小置信度阈值。是最小置信度阈值。由由于于规规则则是是通通过过频频繁繁项项集集直直接接产产生生的的，因因此此关关联联规规则则涉涉及及的的所所有有项项集集都都自自动动满满足足最最小小支支持持度度。频频繁繁项项集集连连同同它它们们的的支支持持度度可可预预先先存存放放在在散散列表（列表（HASH表）中，使得它们可以快速被访问。表）中，使得它们可以快速
24、被访问。例例5.25.2 假假定定数数据据包包含含频频繁繁集集l=I1,I2,I5l=I1,I2,I5 (计计数数2)2)，可可以由以由l l产生哪些关联规则？产生哪些关联规则？l l的非空子集有的非空子集有:I1,I2,I1,I5,I2,I5,I1,I2I1,I2,I1,I5,I2,I5,I1,I2和和I5I5，其其频频繁繁数数分别为：分别为：4 4，2 2，2 2，6 6，7 7，2 2 结果关联规则如下，每个都列出置信度结果关联规则如下，每个都列出置信度（1）I1 I2I5，confidence=24=50（2）I1 I5I2，confidence=22=100（3）I2 I5I1，co
25、nfidence=22=100（4）I1I2 I5，confidence=26=33（5）I2I1 I5，confidence=27=29（6）I5I2 I，confidence=22=100如如果果最最小小置置信信度度阈阈值值为为70，则则只只有有第第2、3和和最最后后一一个个规规则则可以输出，因为只有这些是产生的强规则。可以输出，因为只有这些是产生的强规则。四、描述关联规则的属性四、描述关联规则的属性1 1、可信度（、可信度（confidence)confidence)设事务集设事务集W W中支持物品集中支持物品集A A的事务中，有的事务中，有c%c%的事务同的事务同时也支持时也支持B B
26、，c%c%称为关联规则称为关联规则A-A-B B的可信度的可信度2 2、支持度（、支持度（support)support)设事务集设事务集W W中有中有s%s%的事务同时支持物品集的事务同时支持物品集A A和和B B，s%s%称为称为关联规则关联规则A-A-B B的支持度的支持度 3、期望可信度、期望可信度设事务集设事务集W中有中有e%的事务支持支持物品集的事务支持支持物品集B,e%称为称为关联规则关联规则A-B的期望可信度的期望可信度4、作用度（、作用度（lift)作用度（作用度（lift)是可信度与与期望可信度的比值是可信度与与期望可信度的比值四个参数的计算公式四个参数的计算公式四个参数的
27、计算公式四个参数的计算公式名称名称描述描述公式公式可信度可信度在物品集在物品集A出现的前提下，出现的前提下，B出现的出现的概率概率P（B|A）支持度支持度物品集物品集A，B同时出现的概率同时出现的概率P（AB）期望可信度期望可信度物品集物品集B出现的概率出现的概率P（B）作用度作用度可信度与期望可信度的比值可信度与期望可信度的比值P（B|A）/P（B）可信度可信度是对关联规则是对关联规则准确性准确性的度量的度量支持度支持度是对关联规则是对关联规则重要性重要性的度量的度量支持度支持度说明这条规则在所有的事务中有多大的说明这条规则在所有的事务中有多大的代表代表性。性。显然支持度越大，关联规则越重要
28、，应用范围就越广。显然支持度越大，关联规则越重要，应用范围就越广。有些关联规则可信度虽然很高，但支持度却很低，说明该关联有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很少，因此也不重要规则实用的机会很少，因此也不重要期望可信度描述了在没有物品期望可信度描述了在没有物品A的作用下，物品集的作用下，物品集B本身的支持度；本身的支持度；作用度描述了物品集作用度描述了物品集A对物品集对物品集B的影响。的影响。一般情况下，有用的关联规则的作用度都应该大于一般情况下，有用的关联规则的作用度都应该大于1，只有关联，只有关联规则的可信度大于期望可信度，才说明规则的可信度大于期望可信度，才
29、说明A的出现对的出现对B有促进有促进,也说也说明它们之间某种程度的相关性。明它们之间某种程度的相关性。定义属性论域上的模糊集来软化边界定义属性论域上的模糊集来软化边界 陆陆建建江江等等“数数据据库库中中广广义义模模糊糊关关联联规规则则的的挖挖掘掘”（工工程程数数学学学报）学报）模模糊糊集集可可以以在在集集合合元元素素和和非非集集合合元元素素之之间间提提供供平平滑滑的的变变迁迁，使使得得几几乎乎所所有有边边界界附附近近的的元元素素不不会会再再被被排排斥斥在在外外，同同时时也也不不会会被被过分强调过分强调Apriori算法算法例子（数值属性离散化）例子（数值属性离散化）数据库 D扫描 DC1L1L
30、2C2C2扫描 DC3L3扫描 D2 2、非事务数据库中关联规则的挖掘、非事务数据库中关联规则的挖掘 有些数据不像售货数据那样很容易就能看出一个事务是许多有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但其本质上仍可以像对售货数据一样处理。物品的集合，但其本质上仍可以像对售货数据一样处理。比如人寿保险。比如人寿保险。一个保单就可看成一个事务。一个保单就可看成一个事务。保单记录：保单记录：年龄、性别、健康状况、工作单位、工作地址、工资水平、年龄、性别、健康状况、工作单位、工作地址、工资水平、是否索赔是否索赔等。等。这些信息就可以看作是事务中的物品。这些信息就可以看作是事务中的物品
31、。关联规则在保险业中的应用举例关联规则在保险业中的应用举例 这这是是一一份份保保单单数数据，据，一一条条记记录录存存储储了了一一个个投投保保人人的的一一些些基基本本信信息息以以及及其其索索赔赔次次数。数。通通过过数数据据挖挖掘掘找找出出索索赔赔过过的的投投保保人人有有什什么么特特征，征，没没索索赔赔过过的的投投保保人人有有什什么么特特征征。主主要要关关心心索索赔赔次次数数以以及及与与此此相相关关的的信信息，息，可可以以认认为为保保单单号、号、单单位位代代号、号、单单位位名名称称是是一一些些无无关关信信息，息，因因此此从从源源数数据据中中挑挑选选年年龄龄、年年工工资资、单单位位类类别别、单单位位
32、地地区区、索索赔赔次次数数这这几几列列做做进进一一步步的的分分析。析。注注意意到到年年龄、龄、年年工工资资是是数数值值数数据（据（连连续续数数据据)为为了了离离散散化，化，我我们们根根据据数数据据值值的的范范围围对对数数据据进进行行分分组：组：年年龄龄分分为为(，40,(40，50,(50，60,(60，70,(70.五五个个组，组，年年工工资资分分为（，为（，6000,(6000，10000,(10000，)三三个个组。组。关关联联规规则则挖挖掘掘的的任任务务是：是：给给定定一一个个事事务务数数据据库库D，求求出出所所有有满满足足最最小小支支持持度度和和最最小小可可信信度度的的关关联联规规则
33、则。需需要要指指定定最最小小支支持持度度和和最最小小可可信信度。度。默默认认的的最最小小支支持持度度为为1。要要求求的的最最小小支支持持度度越越高，高，挖挖掘掘出出的的规规则则越越少，少，挖挖掘掘的的过过程程也也越越快。快。默默认认的的最最小小可可信信度度为为50。这这里里最最小小支支持持度度和和最最小小可可信信度度都都取取默默认认值值.-单单位位类类别别=3是是否否索索赔赔=0；-此此规规则则的的四四个个参参数数的的具具体体数数值值分分别别是：是：支支持持度度为为60.77，可可信信度度是是85.18，期期望望可可信信度度是是84.00，作作用用度度是是1.03。-这这条条规规则则告告诉诉我
34、我们：们：在在所所有有的的投投保保人人中，中，60.77的的投投保保人人单单位位类类别别是是3并并且且没没有有索索赔赔过；过；有有84.00的的投投保保人人没没有有索索赔赔过；过；在在单单位位类类别别是是3的的投投保保人人当当中，中，共共有有85.18的的投投保保人人没没有有索索赔赔过；过；作作用用度度是是1.03，说说明明“单单位位类类别别=3”这这个个条条件件对对投投保保人人是是否否索索赔赔没没有有太太大大的的影影响响，因因为为有有没没有有这这个个条条件，件，投投保保人人的的索索赔赔率率并并没没有有太太大大的的区区别。别。-以以上上挖挖掘掘得得到到的的关关联联规规则，则，LHS和和RHS中
35、中都都只只包包含含一一种种物物品（品（条条件），件），是是1对对1的的单单路路规规则；则；如如果果允允许许LHS和和RHS中中包包含含多多种种物物品，品，用用同同样样的的数数据据和和限限制制条条件件可可以以得得到到多多路路规规则，则，用用记记录录浏浏览览器器来来观观察察结结果，果，如如表表3所所示。示。其其中，中，行行是是一一条条关关联联规规则，则，各各列列分分别别给给出出了了关关联联规规则则的的LHS、RHS及及四四个个参参数数的的值。值。从从表表3可可以以看看出出:单单位位类类别别是是3并并且且年年龄龄在在40岁岁到到50岁岁的的投投保保人人当当中，中，93.1没没有有索索赔赔过，过，明明
36、显显高高于于期期望望可可信信度；度；。如如果果有有客客观观原原因因存存在（在（例例如，如，3这这种种类类别别的的单单位位可可能能压压力力不不大，大，不不很很疲疲劳，劳，故故而而发发病病率率不不高），高），那那么么保保险险公公司司就就可可以以多多针针对对满满足足这这些些条条件件的的潜潜在在客客户户开开展展工工作作,从从而而可可以以减减少少风风险，险，提提高高公公司司盈盈利。利。3、算法效率的改进、算法效率的改进算法算法AprioriInput:DB，minsupOutput:Result=所有的频繁项集，和它们的支持度所有的频繁项集，和它们的支持度方法方法Result:=;Result:=;k:
37、=1;k:=1;C1:=C1:=所有的所有的1 1项集项集While(CWhile(Ck k)do)do begin begin 为为C Ck k每一个中的项集生成一个计数器；每一个中的项集生成一个计数器；for(i=1;i=|for(i=1;i1)所占用的空间所占用的空间 例如，当扫描数据库中每个事务以便从候选例如，当扫描数据库中每个事务以便从候选l-l-项集项集C1C1产产生频繁生频繁l-l-项集项集L1L1时，就可以为时，就可以为每个事务产生所有的每个事务产生所有的2-2-项集项集，将它们散列将它们散列(即映射即映射)到散列表结构的不同桶（栏目）中，并到散列表结构的不同桶（栏目）中，并增
38、加对应的桶计数增加对应的桶计数5-45-3（2）事务压缩）事务压缩(压缩进一步迭代扫描的事务数）：压缩进一步迭代扫描的事务数）：减少在后面的循环中所需要扫描的交易记录数减少在后面的循环中所需要扫描的交易记录数不不包包含含任任何何k-项项集集的的事事务务不不可可能能包包含含任任何何(k+1)-项项集集。这这样样，这这种种事事务务出出现现时时，可可以以加加上上标标记记或或删删除除，因因为为以以后后产产生生j-项项集集(jk)，扫描数据库时不再需要它们。扫描数据库时不再需要它们。（3 3）划分数据）划分数据 该该思思想想是是先先把把数数据据库库从从逻逻辑辑上上分分成成多多个个互互不不相相交交的的块块
39、，每每次次单单独独考考虑虑一一个个分分块块并并对对其其生生成成所所有有局局部部频频繁繁项项集集(1ocal(1ocal frequent frequent itemsetitemset)。然然后后合合并并生生成成所所有有可可能能的的频频繁繁项项集集，最最后后计算其支持度。计算其支持度。块块大大小小的的选选择择是是要要使使每每个个分分块块可可放放入入内内存存。这这个个方方法法高高度度并并行行，把把每每一一块块分分别别分分配配给给某某一一个个处处理理器器生生成成频频繁繁集集。产产生生频频繁繁集集的每一个循环结束后，处理器之间的每一个循环结束后，处理器之间通过通信通过通信产生产生k k项集。项集。通
40、通信信过过程程是是执执行行时时间间的的主主要要瓶瓶颈颈，另另外外，每每个个独独立立处处理理器器生生成频繁集的时间也是一个瓶颈成频繁集的时间也是一个瓶颈（4 4）选样）选样(在给定数据的一个子集挖掘在给定数据的一个子集挖掘)：选样方法的基本思想是：选取给定数据库选样方法的基本思想是：选取给定数据库D D的随机样本的随机样本S S，然然后，后，在在S S而不是而不是在在D D中搜索频繁项集。中搜索频繁项集。牺牲牺牲精度换取有效性精度换取有效性。样本。样本S S的大小可以放入在内存的大小可以放入在内存（5）动态项集计数）动态项集计数(在扫描的不同点添加候选项集在扫描的不同点添加候选项集)：Aprio
41、riApriori仅在每次完整的数据库扫描之前确定新的候选。仅在每次完整的数据库扫描之前确定新的候选。该该技技术术动动态态地地评评估估已已被被计计数数的的所所有有项项集集的的支支持持度度，如如果果一一个个项项集集的的所所有有子子集集已已被被确确定定为为频频繁繁的的，则则添添加加它它作作为为新新的的候候选选。结结果果算算法需要的数据库扫描比法需要的数据库扫描比AprioriApriori少。少。5.3 5.3 5.3 5.3 多层关联规则多层关联规则多层关联规则多层关联规则一、一、多层关联规则多层关联规则 对对于于许许多多应应用用，由由于于数数据据在在多多维维空空间间的的多多样样性性，在在低低层
42、层或或原原始始层层的的数数据据项项之之间间很很难难找找出出强强关关联联规规则则。在在较较高高的的概概念念层层发发现现的的强强关关联联规规则则可可能能提提供供普普遍遍意意义义的知识。的知识。多层关联规则多层关联规则项通常具有层次项通常具有层次底层的项通常支持度也低底层的项通常支持度也低某些特定层的规则可能更有意某些特定层的规则可能更有意义义交易数据库可以按照维或层编交易数据库可以按照维或层编码码食品面包牛奶脱脂奶光明统一酸奶白黄挖掘多层关联规则挖掘多层关联规则n自上而下，深度优先的方法：自上而下，深度优先的方法：先找高层的先找高层的“强强”规则：规则：牛奶牛奶面包面包20%,60%.再找他们底层
43、的再找他们底层的“弱弱”规则：规则：酸奶酸奶黄面包黄面包6%,50%.n多层关联规则的变种多层关联规则的变种层次交叉的关联规则层次交叉的关联规则：酸奶酸奶 挪亚面包房挪亚面包房 黄面包黄面包不同种分层方法间的关联规则不同种分层方法间的关联规则：酸奶酸奶挪亚面包房挪亚面包房面包面包多层挖掘的例子多层挖掘的例子5-35-6 表表5-3中的项在图中的项在图5-6概念分层的最低层。在这种原始层概念分层的最低层。在这种原始层很难找出有趣的购买模式。很难找出有趣的购买模式。例如，例如，“IBMdesktopcomputer”和和“Sonyb/w(黑白黑白)printer”每个都在很少一部分事务中出现，可能
44、很难找到涉及它们的强每个都在很少一部分事务中出现，可能很难找到涉及它们的强关联规则。很少有人同时购买它们，使得关联规则。很少有人同时购买它们，使得“IBMdesktopcomputer,Sonyb/wprinter”不太可能满足最小支持度不太可能满足最小支持度 然然 而而，若若 将将“Sony b/w printer”概概 化化 到到“b/wprinter”，则则 在在“IBM desktop computer”和和“b/wprinter”之之间间比比在在“IBMdesktopcomputer”和和“Sonyb/wprinter”可可望望更更容容易易发发现现强强关关联联。类类似似地地，许许多多
45、人人同同时时购购买买“computer”和和“printer”，不不是是同同时时购购买买特特定定的的“IBMdesktopcomputer”和和“Sonyb/wprinter”。换换句句话话说说，包包含含更更一一般般项项的的项项集集，如如“IBM desktopcompute，b/wprinter”和和“computer,printer”，比比之之于于仅仅包包含含原原始始层层数数据据的的项项集集，如如“IBMdesktopcomputer,Sonybwprinter”，更更可可能能满满足足最最小小支支持持度度。因因此此，在在多多个个概概念念层层的的项项之间找有趣的关联比仅在原始层数据之间更容易
46、找。之间找有趣的关联比仅在原始层数据之间更容易找。二、挖掘多层关联规则的方法二、挖掘多层关联规则的方法 一一般般地地，可可以以采采用用自自顶顶向向下下策策略略，由由概概念念层层l开开始始向向下下，到到较较低低的的更更特特定定的的概概念念层层，对对每每个个概概念念层层的的计计算算频频繁繁项项集累加计数，直到不能再找到频繁项集。集累加计数，直到不能再找到频繁项集。即即：一一旦旦找找出出概概念念层层1的的所所有有频频繁繁项项集集，就就开开始始在在第第2层层找找频频繁繁项项集集，如如此此下下去去。对对于于每每一一层层，可可以以使使用用发发现现频频繁繁项项集集的的任任何何算算法法，如如Apriori或它
47、的变形。或它的变形。多多层层关关联联规规则则基基本本上上可可以以沿沿用用“支支持持度度可可信信度度”的的框框架，只是在支持度的设置上有一些特殊的要考虑的内容。架，只是在支持度的设置上有一些特殊的要考虑的内容。多层关联规则可以分为如下规则多层关联规则可以分为如下规则1、同层关联规则（1）支持度不变支持度不变:在各层之间使用统一的支持度在各层之间使用统一的支持度对于所有层使用一致的最小支持度对于所有层使用一致的最小支持度(称作一致支持度称作一致支持度)：在每一：在每一层挖掘时，使用相同的最小支持度阈值。层挖掘时，使用相同的最小支持度阈值。例例 如如，在在 图图 5-7中中，整整 个个 使使 用用
48、最最 小小 支支 持持 度度 5%（对对 于于 从从“computer”到到“laptop computer”）。发发现现“computer”和和“laptopcomputer”都是频繁的，但都是频繁的，但“desktopcomputer”不是。不是。图5-7支持度不变的优缺点支持度不变的优缺点优点优点：l一个最小支持度阈值一个最小支持度阈值.l如果一个项集的父项集不具有最小支持度，那它本身也不如果一个项集的父项集不具有最小支持度，那它本身也不可能满足最小支持度。可能满足最小支持度。缺点缺点：底层项不会成为频繁集，如果支持度底层项不会成为频繁集，如果支持度l太高太高丢失底层关联规则丢失底层关联
49、规则l太低太低生成太多的高层关联规则生成太多的高层关联规则（2）在较低层使用递减的最小支持度）在较低层使用递减的最小支持度(称作递减支持度称作递减支持度)：每每个个抽抽象象层层有有它它自自己己的的最最小小支支持持度度阈阈值值。抽抽象象层层越越低低，对对应应的的阈阈值值越越小小。例例如如，在在图图58，层层1和和层层2的的最最小小支支持持度度阈阈值值分分别别 为为 5%和和 3%，用用 这这 种种 方方 法法，“computer”、“laptopcomputer”和和“desktopcomputer”都是频繁的。都是频繁的。图5-8支持度递减支持度递减:随着层次的降低支持度递减随着层次的降低支持
50、度递减4种搜索策略：种搜索策略：l层与层独立层与层独立l用用k-项集跨层过滤项集跨层过滤l用项跨层过滤用项跨层过滤l用项进行可控跨层过滤用项进行可控跨层过滤逐逐层层独独立立：这这是是完完全全的的宽宽度度搜搜索索，不不任任何何利利用用频频繁繁项项集集的的背背景景知知识识来来帮帮助助剪剪去去项项集集。无无论论该该节节点点父父节节点点是是否否频频繁繁，都都要对每个结点进行检查。要对每个结点进行检查。利用单项进行垮利用单项进行垮层过滤：层过滤：当当且且仅仅当当父父结结点点在在第第(i-1)层层是是频频繁繁的的，才才检检查查个个第第i层层的的项项。换换句句话话说说，如如果果一一个个节节点点是是频频繁繁的