数据挖掘4关联规则资料

数据挖掘发现知识的类型概念描述（广义知识）关联知识分类知识预测型知识偏差型知识从数据分析角度出发，数据挖掘可以分为两种类型描述性数据挖掘:以简洁概述的方式表达数据中的存在的一些有意义的性质预测性数据挖掘:分析数据，建立一个或一组模型，并试图预测新数据集的行为Chapter4AssociationRule&RoughSet4.1关联规则概述4.2经典的关联规则挖掘算法4.3从事物数据库中挖掘多层关联规则WhatIsFrequentPatternAnalysis?Frequentpattern:apattern(asetofitems,subsequences,substructures,etc.)thatoccursfrequentlyinadatasetFirstproposedbyAgrawal,Imielinski,andSwami[AIS93]inthecontextoffrequentitemsetsandassociationruleminingMotivation:FindinginherentregularitiesindataWhatproductswereoftenpurchasedtogether?—Beeranddiapers?!WhatarethesubsequentpurchasesafterbuyingaPC?WhatkindsofDNAaresensitivetothisnewdrug?Canweautomaticallyclassifywebdocuments?ApplicationsBasketdataanalysis,cross-marketing,catalogdesign,salecampaignanalysis,Weblog(clickstream)analysis,andDNAsequenceanalysis.关联规则模式是属于描述型模式，发现关联规则的算法属于无监督学习的方法。关联规则的意义和度量关联规则挖掘的主要对象是事务数据库（transactionDB），针对的应用大多是售货数据，一般情况下，一个事务由如下几个部分组成：事务处理时间，一组顾客购买的物品，物品的数量及金额，顾客的标识号。在事务数据库中，考察一些涉及到许多物品（项）的事务：事务1中出现了物品甲，事务2中出现了物品乙，事务3中同时出现了物品甲和乙，then，物品甲和物品乙在事务中的出现相互之间是否有一定的规律？在数据库知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大影响。例如某超级市场的销售系统，记录了5个顾客的购物清单流水号所购物品清单1球鞋、手套、网球拍2摩托车、手套、头盔3球鞋、摩托车、手套、头盔4头盔5摩托车、头盔购买摩托车的人很大可能同时购买头盔有些数据不像售货数据那样很容易就能看出一个事务是哪些物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。例如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40岁以上，工作在A区的投保人当中，有45％的人曾经向保险公司索赔过。在这条规则中，“年龄在40岁以上”是物品甲，“工作在A区”是物品乙，“向保险公司索赔过”则是物品丙。可以看出来，A区可能污染比较严重，环境比较差，导致工作在该区的人健康状况不好，索赔率也相对比较高。事务与项集设：R={I1，I2，…，In}是一组项集（项目集，属性集，itemset）W是一组与R相关的事务集。W中的每个事务T是一组项（属性）。假设有一个项集A，一个事务T，如果A∈T，则称事务T支持项集A。例如：R={I1,I2,I3,I4,I5,I6,I7}事务集W：事务T1I1,I2,I5事务T2I1,I5,I7事务T3I2,I4,I6,I7事务T4I3,I7事务T5I5,I6假设有项集A={I1,I5}，则称事务T1，事务T2支持项集A。规则表示由事务与项集表，最终得到的关联规则是如下形式的一种蕴涵式：TIDItemSetT1牛奶，面包，黄油T2牛奶，面包，啤酒T3面包，黄油，啤酒T4黄油，酱油，餐巾纸T5餐巾纸，拖把R＝{牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把}A={面包}，B＝{黄油}？？？A={面包}，B＝{拖把}？？？A={餐巾纸，牛奶}，B＝{黄油}？？？……＝，且，是两组项集，、其中BARBRABA,BAHowtoevaluatethisrule?描述关联规则属性的四个参数(1)可信度（condifence），设W中支持物品集A的事务中，有c％的事务同时也支持物品集B，c％称为关联规则的可信度。是对关联规则的准确度的衡量。(2)支持度（support），设W中有s％的事务同时支持物品集A和B，s％称为关联规则的支持度。是对关联规则重要性（或适用范围）的衡量。支持度说明了这条规则在所有事务中有多大代表性，支持度越大，关联规则越重要，应用越广泛。(3)期望可信度（expectedconfidence）,设W中有e％的事务支持物品集B，e％称为关联规则的期望可信度。描述的是在没有任何条件影响时，物品集B在所有事务中出现的概率。或者说是在没有物品集A的作用下，物品集B本身的支持度。(4)作用度（lift），是可信度与期望可信度的比值。描述的是物品集A的出现对物品集B的出现有多大影响。通过可信度对期望可信度的比值反映了在加入“物品集A出现”的这个条件后，物品集B的出现概率发生了多大的变化。作用度越大，说明物品集B受物品集A的影响越大。四个参数的计算公式可信度（condifence）在物品集A出现的前提下，B出现的概率P(B|A)支持度（support）物品集A、B同时出现的概率P(B∩A)期望可信度（expectedconfidence）物品集B出现的概率P(B)作用度（lift）可信度对期望可信度的比值P(B|A)/P(A)一般情况下，有用的关联规则的作用度都应该大于1，只有关联规则的可信度大于期望可信度，才说明A的出现对B的出现有促进作用，也说明了它们之间有某种程度的相关性。如果作用度不大于1，则此关联规则就没意义了。BackTIDItemSetT1牛奶，面包，黄油T2牛奶，面包，啤酒T3面包，黄油，啤酒T4黄油，酱油，餐巾纸T5餐巾纸，拖把R＝{牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把}Howtoevaluatethisrule?A={面包}，B＝{黄油}支持度：2/5;可信度：2/3;期望可信度：3/5;作用度：10/9规则:AB(40%,67%)A={面包}，B＝{拖把}支持度：0;可信度：0;期望可信度：1/5;作用度：0规则:AB(0%,0%)A={餐巾纸，牛奶}，B＝{黄油}支持度：0;可信度：0;期望可信度：3/5;作用度：0规则:AB(0%,0%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerChapter4AssociationRule&RoughSet4.1关联规则概述4.2经典的关联规则挖掘算法4.3从事物数据库中挖掘多层关联规则4.2经典的关联规则挖掘算法关联规则的挖掘就是在事务数据库D中找出具有用户给定的最小支持度min-sup和最小可信度min-conf的关联规则。1.关联规则的挖掘过程:(1)找出存在于事务数据库中的所有频繁项集。项集X的支持度不小于用户给定的最小支持度，则称x为频繁项集（frequentitemset）或大物品集（largeitemset）。第二步比较容易，目前大多数研究集中在第一个子问题上。(2)利用频繁集生成关联规则。对于每个频繁集A，若2.关联规则方法的分类（1）一般处理的是离散化数据，根据离散化结果，可分为(2)根据规则中涉及的数据维数（项数，属性数）(3)根据规则集所涉及的抽象层)__,()48,...42,()39,...,30,(1_softwarecomputerTVresolutionhighxbuysKKxincomexage量化关联规则：布尔关联规则：型根据规则处理的值的类层次单层：不涉及不同概念层次多层，涉及不同的概念象层根据规则集所涉及的抽)...,()...,()30,(:)1_,(),(xbuysxincomexagesofterxbuyscomputerxbuys多维关联规则单维关联规则：根据数据维数3.经典的关联规则挖掘算法（单维、单层、布尔型的关联规则挖掘）•Aprior算法•FP_增长树算法3.1Aprior算法：寻找频繁集，用k-1项集（Lk-1）探索k项集（Lk），即频繁集的子集必须是频繁项集，是宽度优先算法。先找出所有的1－项集（含有一个项的项集），记为C1，找出所有的频繁1－项集，记为L1。然后根据频繁1－项集确定候选2－项集的集合C2，从C2中找出所有的频繁2－项集，记为L2。然后再根据频繁2－项集确定候选3－项集的集合，记为C3，从C3中找出所有的频繁3－项集，记为L3。如此下去直到不再有候选项集。TIDItemSetT1牛奶，面包，黄油T2牛奶，面包，啤酒T3面包，黄油，啤酒T4黄油，酱油，餐巾纸T5餐巾纸，拖把C1：牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把L1：面包，黄油HowtoreceiveLkfromLk－1？Apriori算法中的关键步骤是由Lk-1找Lk，该步骤可分为两步：第1步（连接）：为找Lk，通过Lk-1与自己连接产生候选K-项集的集合。将该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集，记号li[j]表示li的第j项。执行连接Lk-1和Lk-1，其中Lk-1的元素是可连接，如果它们前（k-2）个项相同而且第（k-1）项不同（为简单计，设l1[k-1]l2[k-1]），即：l1[1]=l2[1]∧l1[2]=l2[2]∧……∧l1[k-2]=l2[k-2]∧l1[k-1]l2[k-1]则Lk-1的元素l1和l2是可连接的。连接l1和l2产生的结果的项集是l1[1]l1[2]……l1[k-1]l2[k-1]。第2步（剪枝）：Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。HowtoreceiveLkfromLk－1？ExampleTIDItemsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3TransactionaldatabaseDItemsetSupportI16I27I36I42I52ScanDC1ItemsetSupportI16I27I36I42I52L1CalculatesupportJoinL1*L1Min_sup＝2PruneItemsetI1,I2I1,I3I1,I4I1,I5I2,I3I2,I4I2,I5I3,I4I3,I5I4,I5ItemsetSupportCountI1,I24I1,I34I1,I41I1,I52I2,I34I2,I42I2,I52I3,I40I3,I51I4,I50C2ScanDC2ItemsetSupportCountI1,I24I1,I34I1,I52I2,I34I2,I42I2,I52Calcula