关联规则基本概念.doc

关联规则基本概念 设I i1,i2,…im 是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得。每个事务有一个标识符，称作TID。设A是一个项集，事务T包含A当且仅当。关联规则是诸如AB的蕴涵式，其中，，并且。 （1）支持度与置信度 规则的支持度和置信度是两个规则兴趣度量值，它们分别表示发现规则的有用性和确定性。规则AB在事务级中D中成立，具有支持度s，其中s是D中事务包含（即A和B二者）的百分比，它是概率。规则AB在事务集中具有置信度c，其中D中包含A的事务同时也包含B的百分比是c。这是条件概率。即是 （7.21） 即：关联模式的支持度是模式为真的任务相关的元组（或事务）所占的百分比。对于关联规则 AB（其中A和B是项目的集合），支持度定义为： （7.22） 即：每个发现模式都应当由一个表示其有效性或“值得信赖性”的确定性度量。对于关联规则AB（其中A和B是项目的集合），其确定性度量置信度定义为： 同时满足最小支持度阈值（min_sup）和最小置信度阈值（min_conf）的规则称作强规则，我们用0%和100%之间的值而不是用0到1之间的值表示支持度和置信度。 如果我们想象全域是商品的集合，则每种商品有一个布尔变量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表示： computerfinancial_management_software[support 2%,confidence 60%] 上面关联规则的支持度2%意味分析中的全部事务的2%同时购买计算机和购买财务管理软件，置信度60%以为购买计算机的顾客60%也购买财务管理软件。如果关联规则满足最小支持度阈值和最小值信度阈值，则这个关联规则被认为是有趣的。这些阈值可以由用户或领域专家设定。 （2）期望可信度（ce） 设D中有e%的事务支持项集B，e%称为关联规则AB 的期望可信度。期望可信度描述了在没有任何条件影响时，项集B在所有事务中出现的概率有多大。如果某天共有1000个顾客到商场购买商品，其中有200个顾客购买了冰箱，则上述的关联规则的期望可信度就是20%。 （3）作用度（lift） 作用度是置信度与期望可信度的比值。作用度描述项集A的出现对项集B的出现有多大的影响。因为项集B在所有事务中出现的概率是期望可信度；而项集B在项集A出现的事务中出现的概率是置信度，通过置信度对期望可信度的比值反映了在加入“项集A出现”的这个条件后，项集B的出现概率发生了多大的变化。在上例中，如果购买微波炉的顾客70%也购买冰箱，则所用度就是。 用P A 表示事务中出现项集A的概率，表示在出现项集A的事务中出现B的概率，则以上四个参数可用公式表示，如表7.7所示： 表7.7 各参数的含义及计算公式 名称 描述 公式 置信度（c） 在A出现的前提下，B出现的概率 支持度（s） A和B同时出现的概率 期望可信度（ce） B出现的概率 P B 作用度（lift） 置信度对期望可信度的比值 置信度是对关联规则准确度的测量，支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则越重要。有些关联规则虽然置信度很高，但支持度却很低，说明关联规则实用的机会很小，因此也不重要。 期望可信度描述了在没有项集A的作用下，项集B本身的支持度；作用度描述了项集A对项集B的影响力的大小。作用度越大，说明项集B受项集A的影响越大。一般情况下，有用的关联规则的作用度都应该大于1，只有关联规则的置信度大于期望可信度，才说明了A的出现对B的出现有促进作用，也说明了它们之间某种程度的相关性，如果作用度不大于1，则此关联规则就没有意义了。 项的集合称为项集（itemset），包含k个项的项集称为k-项集。集合 computer, financial_management_software 是一个2-项集。项集的出现频率是包含项集的事务数，简称项集的频率、支持计数或计数。如果项集的出现频率大于等于min_sup与D中事务总数的乘积，项集满足最小支持度min_sup。如果项集满足最小支持度，则称它为频繁项集。频繁k-项集的集合通常记作L。 “如何由大型数据库挖掘关联规则？”关联规则的挖掘是一个两步的过程： 1）找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持度计数一样。 2）由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。 如果愿意，也可以使用附加的兴趣度度量。这两步中，第二步是在第一步的基础上进行的，工作量非常小。关联