第八章集合论方法.ppt

频繁模式挖掘过程 从FP-树中来挖掘频繁模式，先从L表中最后一项开始。E在FP-树有两个分枝，路经为BAE:1和BACE:1。 以E为后缀，它的两个对应前缀路径是（BA:1）和（BAC:1），它们形成E的条件模式基。它的条件FP-树只包含单个路径B:2,A:2；不包含C，因为它的支持度计数为1，小于最小支持度计数。 该单个路径产生频繁模式的所有组合：{BE:2，AE:2，BAE:2}。 * 频繁模式挖掘过程 对于D， 它的两个前缀形成条件模式基{（BA:1）,（B:1）}，产生一个单节点的条件 FP-树（B:2），并导出一个频繁模式{BD:2}。 对于C，它的条件模式基是{（BA:2）,（B:2），（A:2）}，它的条件FP-树有两个分枝（B:4，A:2）和（A:2）。它的频繁模式集为：{BC:4，AC:4，BAC:2}。 对于A，它的条件模式基是{（B:4）}，它的FP-树只包含一个节点（B:4），产生一个频繁模式{BA:4}。 * 利用FP-树挖掘频繁模式 项 条件模式基 条件FP-树 频繁模式 E BA:1，BAC:1 (B:2,A:2) BE:2,AE:2,BAE:2 D BA:1,B:1 (B:2) BD:2 C BA:2,B:2,A:2 (B:4,A:2)(A:2) BC:4,AC:4,BAC:2 A B:4 (B:4) BA:4 * 粗糙集概述 现实生活中有很多含糊现象不能简单用真假来表示，如何处理这些现象就成为一个研究领域。早在1904年谓词逻辑的创始人G.Frege就提出了含糊（Vague）一词，他把它归结到边界上，也就是说在全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分类 * 模糊集 1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者有领域专家给出的，所以有相当的主观性 * 粗糙集 20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集Rough Set，他把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它具有确定的公式描述，完全由数据决定，所以更有客观性。 * 粗糙集的研究 粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了研究，使其在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越多受到关注。 * 粗糙集的基本定义 知识的分类观点 粗糙集理论假定知识是一种对对象进行分类的能力。而只是必须与具体或抽象世界特定部分相关的各种分类模式联系在一起。这种特定部分称之为所讨论的全域或者论域Universe * Apriori基本方法 Apriori 使用一种称作逐层有哪些信誉好的足球投注网站的迭代方法，“K-项集”用于探索“K+1-项集”。 首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3， 如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。 * Apriori 性质 性质：频繁项集的所有非空子集都必须也是频繁的。 如果项集B不满足最小支持度阈值min-sup，则B不是频繁的，即 P（B）min-sup 如果项A添加到B，则结果项集（即BA）不可能比B更频繁出现。因此，BA也不是频繁的，即 P（BA）min-sup。 * Apriori性质 “K-项集”产生“K+1-项集” 设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1 有公式： CK+1=LKLK={XY，其中X，Y LK， |XY|=K+1} 其中C1是1-项集的集合，取自所有事务中的单项元素。 * 举例 如 L1={{A}，{B}} C2={A}{B}={A，B}，且|AB|=2 L2={{A，B}，{A，C}} C3={A，B}{A，C}={A，B，C}，且 |ABC|=3 * Apriori 算法中候选项集与频繁项集的产生实例 事务ID 事务的项目集 T1 A,B,E T2 B,D T3 B,C T4 A,B,D T5 A,C T6 B,C T7 A,C T8 A,B,C,E T9 A,B,C * 过程举例 1) 在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数 2) 假定最小事务支持计数为2 （即min-sup=2/9=22%），可以确定频繁1-项