第8章频繁模式挖掘要点解析.ppt

五邑大学信息学院　　何国辉 8.1.4 关联规则挖掘的重要算法FP-Growth（续） Han等人引入“频繁模式增长”（简称FP-增长）的概念，可以不产生候选就能够找出所有的频繁项集。 韩家炜现为美国伊利诺伊大学计算机系正教授。韩教授于2003年获选美国计算机协会院士（ACM Fellow）（Citation: “For contributions in knowledge discovery and data mining”， 汉译： “对知识发现和数据挖掘做出贡献”）。 韩教授1978毕业于郑州大学计算机科学系，同年考入中科院研究生，1985年美国威斯康辛大学计算机系博士毕业。 8.1.4 关联规则挖掘的重要算法FP-Growth（续） FP-Growth算法的特点 把数据D压缩映射到一个小而紧凑的数据结构FP-Tree，即频繁模式树中，避免了多次扫描数据库D。 利用“模式分段增长”法避免产生大量的候选集。 采用分而治之的方法将数据挖掘任务分解成许多小任务，从而极大地缩小了搜素空间。 8.1.4 关联规则挖掘的重要算法FP-Growth（续） 【举例】使用FP-Growth算法重新对例8.4中图8.3所示的事务数据库进行关联规则挖掘，具体步骤分为： 构造FP-Tree 挖掘FP-Tree 1. 构造FP-Tree 对数据库的第一次扫描与Apriori算法相同，扫描结束后得到一个频繁项（1-项集）集合，以及频度。 设最小频度为2（与例8.4相同）。将所有的频繁1-项集按频度降序排序，结果集记作L。则L={b:4，e:3，a:2，c:2}。 构造FP-Tree： 首先创建树的根节点，用“null”标记。 对数据库做第二次扫描。数据库中每条交易中的数据项按L中的次序依次处理（即根据递减频度排序），并对每个交易创建一个分枝。 1. 构造FP-Tree（续） 所生成的FP-Tree为： 1. 构造FP-Tree（续） 所生成的FP-Tree为： 将对交易数据库的而频繁模式挖掘问题转换成针对该FP-Tree进行挖掘的问题。 null c:1 b:4 a:1 e:3 c:1 a:1 2. 挖掘FP-Tree 构造FP-Tree时是按照1-项集频度的降序进行的，对构造后的FP-Ｔree进行挖掘时，需要按照1-项集频度的升序进行。 对于每一个1-项集，首先构造它的条件数据库。 所谓条件数据库，是一个“子数据库”，由FP-Tree中与该1-项集一起出现的前缀路径组成。 具体实现：从数据项头表中首先找到该1-项集，然后顺着链表找到它在树中出现的位置，每找到一个位置，则得到从树根到该位置的一条路径，该路径就构成了条件数据库中的一部分。 2. 挖掘FP-Tree（续） 针对图8.6构造的FP-Tree树进行挖掘过程： 先从L中的最后一个数据项c（按频度的升序）开始，沿着c的节点链表，首先发现C出现在FP-Tree的一条分枝b:1 e:1 c:1上，则将该路径的前缀b:1 e:1放到c的条件数据库中； 再顺着c的链表走下去，发现c出现在FP-Tree的另一条分枝b:1 e:1 a:1 c:1上，则将该路径前缀b:1 e:1 a:1放到c的条件数据库中； 得到c的条件数据库为{b:1 e:1，b:1 e:1 a:1}，构造出的FP-Tree有两个节点b:2 e:2，b和e的频度均不小于2，是频繁的。 2. 挖掘FP-Tree（续） 得到该子数据库生成的频繁模式{b，e，be}。 将其与生成该子数据库的项目c连接后（称为增长模式），生成所有包含c的频繁模式，即{bc：2}，{ec：2}，{bec：2}。 依次类推... 8.1.5 其它关联规则挖掘方法 前面介绍的关联规则没有考虑数据对象的概念层次和蕴含多个谓词，实际生活中往往并非如此。如：惠普牌打印机-打印机-电子产品；或者数据库中不但记录了顾客购买商品的名称，而且还记录了数量、单价等，需要体现多种维度的关联关系。 多层关联规则 多维关联规则 1. 多层关联规则 挖掘方法：一般采用自顶向下的策略，从最一般的概念层（第0层）开始，到较具体的某特定概念层，在每个概念层上寻找频繁项集，直到不能找到频繁项集为止。 最小支持度的设置：采用逐层递减的支持度设置策略。 2. 多维关联规则 涉及数据表的多个字段。 二维关联规则：如：性别=“女”?职业=“护士”。 三维关联规则：如：年龄=“20...30”∧职业=“学生”?购买=“电脑”。 8.1.6 关联规则的兴趣度 按照前述方法产生的关联规则并非都有用。 举例：如下是从一个有5000名学生的学校的调查结果中进行挖掘的实例。提供早餐的零售商对这些学生每天早上所从事的活动进行了一次调查。数据表明：60%的学