医药信息分析与决策第8章 关联规则

第8章 关联规则,主要内容,关联规则概述关联规则算法关联规则应用案例,8.1 关联规则概述,8.1.1啤酒与尿布,在美国沃尔玛超市的货架上，尿片和啤酒赫然地摆在一起出售。为啥？每逢周末，啤酒和尿片的销量都很大有孩子的家庭中，太太经常嘱咐丈夫下班后要买尿片，而丈夫们在买完尿片以后又顺手买啤酒,8.1.1啤酒与尿布,搞清原因后，沃尔玛的工作人员打破常规，尝试将啤酒和尿片摆在一起，结果使得啤酒和尿片的销量双双激增，为商家带来了大量的利润在顾客同一次购物活动中，对其所购买商品组成的相关性进行研究的方法学,8.1.2 基本概念与规则度量,项目与项集:数据库中不可分割的最小信息单位，称为项目，用符号 i表示。项目的集合称为项目集，简称项集。设集合 是项集， I中项目的个数为 n ，则集合 称为 n -项集。例如，集合啤酒，尿布，牛奶是一个3-项集。,8.1.2 基本概念与规则度量,事务与事务集: 设 是由数据库中所有项目构成的集合，一次处理所含项目的集合用 表示，是 I 的子集，称为一个事务。事务的集合 包括 k 个事务，称为事务集。,8.1.2 基本概念与规则度量,关联规则: 关联规则是形如 的蕴含式，其中事务 X, Y 分别是 I 的真子集，并且 。 X称为规则的前提， Y称为规则的结果。关联规则反映 X中的项目出现时， Y中的项目也跟着出现的规律。,8.1.2 基本概念与规则度量,关联规则的支持度（support）:关联规则的支持度是事务集中同时包含X 和Y的事务数与所有事务数之比,记为support ( )，即： support ( ) = support = 。支持度反映了 X和 Y中所含项在事务集中同时出现的频率。,8.1.2 基本概念与规则度量,关联规则的置信度（confidence）:关联规则的置信度是事务集中包含 X和 Y 的事务数与所有包含X的事务数之比，记为confidence( )， 即：置信度反映了包含X 的事务中，出现Y 的条件概率。,8.1.2 基本概念与规则度量,最小支持度与最小置信度: 用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈值，当support ( ) 、confidence( ) 分别大于等于各自的阈值时，认为 是有价值的，被称为最小支持度阈值(minsupport)和最小置信度阈值(mincontinence)。其中，minsupport描述了关联规则的最低重要程度，minconfidence规定了关联规则必须满足的最低可靠性。,8.1.2 基本概念与规则度量,频繁项集: 设 为项目的集合，且 ， ， 对于给定的最小支持度minsupport，若 的支持度support minsupport，则称 为频繁项目集，否则，称 为非频繁项目集。,8.1.2 基本概念与规则度量,强关联规则: 关联规则称为强关联规则， 必须 且 同时成立，否 则称为弱关联规则。,8.1.2 基本概念与规则度量,性质1. 设X 和 Y是数据集 中的项目子集（1）若 ，则support (X ) support (Y)（2）若 ，且 X是非频繁项目集，则Y也是非频繁项目集，即任意弱项目集的超集都是弱项集。（3）若 ，如果 Y是频繁项目集，则 X也是频繁项目集，即任意大项集的子集都是大项集。,8.2 关联规则算法,8.2.1关联规则挖掘过程 关联规则挖掘问题可分解为以下两个子问题: 1.找频繁项目集:找出事务数据库 中所有大于或等于用户指定最小支持度的项目集(itemset)，即频繁项目集。本章中项目集的支持度可简单地用包含该项目集的数目来表示。2.利用频繁项目集生成所需要的关联规则。 对每一频繁项目集 ,找到其所有非空子集 ,如果比 率： 称为强关联规则。,8.2.2 Apriori算法,1.Apriori算法基本思想。 Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori 算法 使用称为逐层收索的迭代方法，首先寻找1-项频繁集的集合，集合 记做L1， L1用于寻找两项频繁集合L2，L2 用于寻找L3，如此下去，直到不能找K项频繁集合K项频繁集候选集：每个项都有K个元素，用C表示K项频繁集：每一项都满足最小支持度的项，每个项中有K个元素，用L表示。,2. 产生频繁项集的过程,连接步C1(1-项频繁集候选集):扫描数据库,对每个单独的项进行计数得到C1。 L1(1-项频繁集):从C1中删除支持度小于sup的项得到L1。 Ck+1(K+1项频繁集候选集)：CK+1由Lk与自身连接得到，即CK+1=Lk*Lk连接的条件是，参与连接的两个K项集合前k-1项相同，第k项不同。,2. 产生频繁项集的过程,剪枝步从CK+1删除K项子集不在LK中的项、并利用以下性质删除支持度小于sup的项。Apriori 性质： 任何K+1项频繁集的任意K项子集必须是频繁的支持度计算 C为CK中的一项，T是事务集中的一条事务，如果CT，C的支持度加1，遍历整个数据库，可以得到C的支持度 例：C1=I1,I2，T2=I1,I2,I3 c.sup+,3.Apriori算法的主要步骤,(1) 扫描全部数据，产生候选1-项集的集合C1；(2) 根据最小支持度，由候选1-项集的集合C1产生频繁1-项集的集合L1；(3) 对k1，重复执行步骤(4)、(5)、(6)；(4) 由Lk执行连接和剪枝操作，产生候选（k+1）-项集的集合Ck+1；(5) 根据最小支持度，由候选（ k+1 ）-项集的集合Ck+1，产生频繁（ k+1 ）-项集的集合Lk+1；(6) 若L，则 k=k+1 ，跳往 (4)；否则, 跳往步骤(7)；(7) 根据最小置信度，由频繁项集产生强关联规则，结束。,4. Apriori算法的举例,表8.1 数据库 的事务集,4. Apriori算法的举例,表8.2 候选1-项集C1,表8.3 频繁1-项集L1,1) 第一次扫描,4. Apriori算法的举例,表8.4 候选2-项集C2,表8.5 剪枝后的C2,表8.6 频繁2-项集L2,2）第二次扫描,4. Apriori算法的举例,表8.7 候选3-项集C3,表8.8 剪枝后的C3,表8.9 频繁3-项集L3,3）第三次扫描,4. Apriori算法的举例,4）第四次扫描算法使用L3L3产生候选4-项集的集合C4。L3L3=I1，I2，I3，I5，根据Apriori性质，因为它的子集I2，I3，I5不是频繁的，所以这个项集被删除。这样C4= ，因此算法终止，找出了所有的频繁项集。,5.Apriori算法的优缺点,Apriori算法使用Apriori性质来生成候选项集的方法，大大压缩了频繁集的大小，取得了很好的性能。但存在以下缺点： (1) 产生大量的频繁集。(2) 重复扫描事务数据库。Apriori算法会产生大量的频繁集，当频繁1-项集L1 有1 000 个时，候选2-项集C2个数将会超过100万。这种空间复杂度以指数形式增长，使得Apriori算法的执行效率很低。,6.由频繁项集产生关联规则,一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。对于置信度可以用下式，其中条件概率用项集支持度计数表示。,其中，support_count(AB)是包含AB的事务数，support_count(A)是包含项集A的事务数。,6.由频繁项集产生关联规则,关联规则产生如下：对于每个频繁项集l，产生l的所有非空子集；对于l的每个非空子集s,如果 则输出规则“S=(l-s)”,其中min_conf是最小置信度阈值。,6.由频繁项集产生关联规则,例题：上例中频繁项集L3中的频繁事务Ti=I1,I2,I5。设最小置信度阈值为70%。可由Ti产生哪些强关联规则？解：Ti的非空子集为： I1，I2，I1，I5及I2，I5 ，I1，I2，I5 。,6.由频繁项集产生关联规,对于每一子集，可求出置信度如下： ：confidence=24=50% ：confidence=22=100% ：confidence=22=100% ：confidence=26=33% ：confidence=27=29% ：confidence=22=100%由于最小置信度为70%，则只有上面第2、3和最后一个规则可以输出，因为只有这些产生强关联规则。,8.2.3 关联规则分类,1.基于规则中处理的变量的类别。 关联规则处理的变量可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如：性别=“女”=职业=“秘书” ，是布尔型关联规则；性别=“女”=avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。,8.2.3 关联规则分类,2.基于规则中数据的抽象层次。 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=Sony打印机，是一个细节数据上的单层关联规则；台式机=Sony打印机，是一个较高层次和细节层次之间的多层关联规则。,8.2.3 关联规则分类,3.基于规则中涉及到的数据的维数。 关联规则中的数据，可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=尿布，这条规则只涉及到用户的购买的物品；性别=“女”=职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。,8.3 关联规则应用案例,表8.10癫痫病药方,8.3 关联规则应用案例,8.3 关联规则应用案例,8.3 关联规则应用案例,8.3 关联规则应用案例,本案例获取的规则、项集及根据强关联规则生成的关系网络可由图8.4至图8.6所示的浏览窗口进行查看。本案例所产生的强关联规则为： 奥卡西平片 丙 戊酸纳缓释片。,思考题,考虑如下的频繁3-项集：1, 2, 3，1, 2,