关联分析高级概念ppt课件

关联分析 高级概念 第7章关联分析 高级概念 关联分析处理事务数据 RulesDiscovered Diaper Beer 处理分类属性 我们可能发现关于因特网用户特征的有趣信息 网上购物 是 关注隐私 是 许多应用包含对称二元属性和标称属性 表7 1显示的因特网调查数据包含对称二元属性 如 性别 家庭计算机 网上聊天 网上购物和关注隐私 还包括标称属性 如文化程度和州 处理分类属性 为了提取这样的模式 我们需要将标称属性和对称二元属性转换成 项 使得已有的关联规则挖掘算法可以使用 这种类型的变化可以通过为每个不同的属性 值对创建一个新的项来实现 例如 标称属性文化程度可以用三个二元项取代文化程度 大学文化程度 研究生文化程度 高中类似的 对称二元属性性别可以转换成一对二元项 性别 男 性别 女 处理分类属性 将关联分析用于二元化后的数据时 需要考虑如下问题 1 有些属性值可能不够频繁 不能成为频繁模式的一部分 如 州名 解决办法 将相关的属性值分组 形成少数类别 例如 每个州名都可以用对应的地理区域取代 例如 分别用中西部 太平洋西北部 西南部和东海岸取代 处理分类属性 将关联分析用于二元化后的数据时 需要考虑如下问题 2 某些属性值的频率可能比其他属性高很多 如 假定85 的被调查人都有家庭计算机 如果为每个频繁出现在数据中的属性值创建一个二元项 我们可能产生许多冗余模式 家庭计算机 是 网上购物 是 关注隐私 是 解决办法 使用处理具有宽支持度的极差数据集的技术 处理分类属性 将关联分析用于二元化后的数据时 需要考虑如下问题 3 计算时间可能增加 特别是当新创建的项变成频繁项时 因为会产生更多的候选项集 解决办法 避免产生包含多个来自同一个属性的项的候选项集 例如 不必产生诸如 州 X 州 Y 的候选项集 因为该项集支持度为零 处理连续属性 因特网调查数据可能还包含连续属性 如表7 3所示 挖掘连续属性可能揭示数据的内在联系 如 年收入超过120k的用户属于45 60年龄组 或 拥有超过3个email帐号并且每周上网超过15小时的用户通常关注个人隐私 包含连续属性的关联规则通常称作量化关联规则 quantiativeassociationrule 对连续数据进行关联分析的方法 基于离散化的方法非离散化方法基于统计学的方法 基于离散化的方法 离散化是处理连续属性最常用的方法 这种方法将连续属性的邻近值分组 形成有限个区间 例如 年龄属性可以划分为如下区间 12 16 16 20 20 24 56 60 离散化技术 等宽 等频 聚类表7 4显示了离散化和二元化后的因特网调查数据 属性离散化的一个关键在于划分每个属性的区间个数和宽度 然而 确定正确的区间是困难的 如果支持度阈值 5 置信度阈值 65 我们可以从表中推出年龄和网上聊天隐含强规则 16 24 网上聊天 是 s 8 8 c 81 5 44 60 网上聊天 否 s 16 8 c 70 区间宽度对关联分析结果的影响 1 如果区间太宽 则可能因为缺乏置信度而失去某些规则例如 当区间宽度为24岁时 上面的两个规则变为 16 36 网上聊天 是 s 30 57 7 36 60 网上聊天 否 s 28 58 3 区间宽度对关联分析结果的影响 2 如果区间太窄 则可能因为缺乏支持度而失去某些规则例如 当区间宽度为4岁时 上面的两个规则变为 16 20 网上聊天 是 s 4 4 84 6 20 24 网上聊天 是 s 4 4 78 6 3 当区间宽度为8岁时 上面的两个规则变为 44 52 网上聊天 否 s 8 4 70 52 60 网上聊天 否 s 8 4 70 12 20 网上聊天 是 s 9 2 60 5 20 28 网上聊天 是 s 9 2 60 0 非离散化方法 有一些应用 分析者更感兴趣的是发现连续属性之间的关系 例如 找出表7 6所示文本文档中词的关联 在文本挖掘中 分析者更感兴趣的是发现词之间的关联 例如 数据和挖掘 而不是词频区间 例如 数据 1 4 挖掘 2 3 之间的关联 一种方法是将数据变换成0 1矩阵 其中 如果规范化词频超过某个阈值t 则值为1 否则为0 该方法缺点是阈值难确定 另一种方法是采用min apriori方法 S word1 word2 min 0 3 0 6 min 0 1 0 2 min 0 4 0 2 min 0 2 0 0 6Min apriori中支持度s随着词的规范化频率增加而增大 随包含该词的文档个数增加而单调递增 处理概念分层 概念分层是定义在一个特定的域中的各种实体或概念的多层组织 概念分层可以用有向无环图表示 概念分层主要优点 1 位于层次结构较下层的项 如 AC适配器 可能没有足够的支持度 但是 作为概念分层结构中它们的父母结点 如 便携机配件 具有较高支持度 2 在较低层发现的规则倾向于过于特殊 可能不如较高层的规则令人感兴趣 如 脱脂牛奶 普通面包 脱脂牛奶 白面包 等过于特殊 实现概念分层的方法每个事务t用它的扩展事务t 取代 其中 t 包含t中所有项和它们的对应祖先 如 事务 DVD 普通面包 可以扩展为 DVD 普通面包 家电 电子产品 面包 食品 然后对扩展的数据库使用如Apriori等已有的算法来发现跨越多个概念层的规则 概念分层主要缺点 1 处于较高层的项比处于较低层的项趋向于具有较高的支持度计数 2 概念分层的引入增加了关联分析的计算时间 3 概念分层的引入可能产生冗余规则 规则X Y是冗余的 如果存在一个更一般的规则X Y 其中X 是X的祖先 Y 是Y的祖先 并且两个规则具有非常相似的置信度 例如 面包 牛奶 白面包 脱脂牛奶 序列模式 购物篮数据常常包含关于商品何时被顾客购买的时间信息 可以使用这种信息 将顾客在一段时间内的购物拼接成事务序列 然而 迄今为止所讨论的关联模式概念都只强调同时出现关系 而忽略数据中的序列信息 对于识别动态系统的重现特征 或预测特定事件的未来发生 序列信息可能是非常有价值的 序列模式 将与对象A有关的所有事件按时间增序排列 就得到A的一个序列 sequence SequenceDatabase 一般地 序列是元素 element 的有序列表 可以记作s 其中每个ej是一个或多个事件的集族 即ej i1 i2 ik Sequence E1E2 E1E3 E2 E3E4 E2 Element Transaction Event Item 序列数据的例子 子序列 Subsequence 序列t是另一个序列s的子序列 subsequence 如果t中每个有序元素都是s中一个有序元素的子集 序列模式发现 SequentialPatternMining 设D是包含一个或多个数据序列的数据集 序列s的支持度是包含s的所有数据序列所占的比例 如果序列s的支持度大于或等于用户指定的阈值minsup 则称s是一个序列模式 或频繁序列 定义7 1序列模式发现 给定序列数据库D和用户指定的最小支持度阈值minsup 序列模式发现的任务是找出支持度大于或等于minsup的所有序列 例子 Minsup 50 ExamplesofFrequentSubsequences s 60 s 60 s 80 s 80 s 80 s 60 s 60 s 60 s 60 提取序列模式 蛮力方法 给定n个事件的集族 i1 i2 i3 in候选1 序列 候选2 序列 候选3 序列 候选序列的个数比候选项集的个数大得多 产生更多候选的原因有下面两个一个项在项集中最多出现一次 但一个事件可以在序列中出现多次 给定两个项i1和i2 只能产生一个候选2 项集 i1 i2 但却可以产生许多候选2 序列 如 次序在序列中是重要的 但在项集中不重要 例如 1 2 和 2 1 表示同一个项集 而和对应于不同的序列 因此必须分别产生 先验原理对序列数据成立 包含特定k 序列的任何数据序列必然包含该k 序列的所有 k 1 序列 序列模式发现的类Apriori算法 候选产生 一对频繁 k 1 序列合并 产生候选k 序列 为了避免重复产生候选 传统的Apriori算法仅当前k 1项相同时才合并一对频繁k 项集 类似的方法可以用于序列 例子通过合并和得到 由于事件3和事件4属于第二个序列的不同元素 它们在合并后序列中也属于不同的元素 通过合并和得到 由于事件3和事件4属于第二个序列的相同元素 4被合并到第一个序列的最后一个元素中 候选剪枝一个候选k 序列被剪枝 如果它的 k 1 序列最少有一个是非频繁的 例如 假设是一个候选4 序列 我们需要检查和是否是频繁3 序列 由于它们都不是频繁的 因此可以删除候选 支持度计数在支持度计数期间 算法将枚举属于一个特定数据序列的所有候选k 序列 计数之后 算法将识别出频繁k 序列 并可以丢弃其支持度计数小于最小支持度阈值minsup的候选 图7 6 时限约束 模式的事件和元素都施加时限约束 例子 学生A 学生B 感兴趣的模式是 意思是说注册数据挖掘课程的学生必须先选修数据库系统和统计学方面的课程 显然 该模式被这两个学生支持 尽管他们都没有同时选修统计学和数据库系统 相比之下 一个10年之前选修了统计学课程的学生不能认为支持该模式 因为这些课程的时间间隔太长了 图7 7解释了可以施加在模式上的某些时限约束 最大跨度约束 最大跨度约束指定整个序列中所允许的事件的最晚和最早发生时间的最大时间差 假定最大时间跨度maxspan 3 下面的表包含了给定的数据序列支持和不支持的序列模式 一般 maxspan越长 在数据序列中检测到模式的可能性就越大 然而 较长的maxspan也可能捕获不真实的模式可能涉及陈旧事件 最大跨度约束影响序列模式发现算法的支持度计数 施加最大时间跨度约束之后 有些数据序列就不再支持候选模式 最小间隔和最大间隔约束 时限约束也可以通过限制序列中两个相继元素之间的时间差来指定 如果最大时间差 maxgap 是一周 则元素中的事件必须在前一个元素的事件出现后的一周之内出现 如果最小时间差 mingap 是0 则元素中的事件必须在前一个元素的事件出现之后出现 假定maxgap 3 mingap 1 下表给出了模式通过或未通过最大间隔和最小间隔约束的例子 与最大跨度一样 这些约束也影响序列模式发现算法的支持度计数 因为当最小间隔和最大间隔约束存在时 有些数据序列就不再支持候选模式 使用最大间隔约束可能违反先验原理 为了解释这一点 考虑图7 5中的数据集 如果没有最小间隔或最大间隔约束 和的支持度都是60 然而 如果mingap 0 maxgap 1 则的支持度下降至40 而的支持度仍然是60 这与先验原理相违背 例子 Minsup 50 ExamplesofFrequentSubsequences s 60 s 60 s 80 s 80 s 80 s 60 s 60 s 60 s 60 定义7 2邻接子序列序列s是序列w 的邻接子序列 contiguoussubsequence 如果下列条件之一成立 1 s是从e1或ek中删除一个事件后由w得到 2 s是从至少包含两个事件的任意ei w中删除一个事件后由w得到 3 s是t的邻接子序列 而t是w的邻接子序列 定义7 3修订的先验原理如果一个k 序列是频繁的 则它的所有邻接 k 1 子序列也一定是频繁的 在候选剪枝阶段 并非所有的k 序列都需要检查 因为它们中的一些可能违反最大间隔约束 例如 如果maxgap 1 则不必检查候选的子序列是否是频繁的 因为元素 2 3 和 5 之间的时间差大于一个时间单位 我们只需要考察的邻接子序列 包括 和 窗口大小约束 最后 元素sj中的事件不必同时出现 可以定义一个窗口大小阈值 ws 来指定序列模式的任意元素中事件最晚和最早出现之间的最大允许时间差 窗口大小为0表明模式同一元素中的所有事件必须同时出现 下面的例子使用ws 2 mingap 0 maxgap 3 maxspan 子图模式 关联分析方法应用到远比项集和序列更复杂实体 例子包括化学化合物 3 D蛋白质结构 网络拓扑和树结构的XML文档 这些实体可以用图形表示建模 在这种类型的数据上进行数据挖掘的任务是 在图的集合中发现一组公共子结构 这样的任务称作频繁子图挖掘 图与子图 定义7 5支持度给定一个图的集族 子图g的支持度定义为包含它的所有图所占的百分比 即例7 2考虑5个图G1到G5 如图7 10所示 右上角的图g1是G1 G3 G4 G5的子图 因此s g1 4 5 80 类似地 我们由s g2 60 因为g2是G1 G2和G3的子图 而s g3 40 因为g3是G1和G3的子图 频繁子图挖掘 定义7 6频繁子图挖掘给定图的集合和支持度阈值minsup 频繁子图挖掘的目标是找出所有使得s g minsup的子图g 本章的讨论主要关注无向连通图 undirected connectedgraph 挖掘频繁子图是一项计算量很大的任务 因为搜索空间是指数的 为了解释这项任务的复杂性 考虑一个包含d个实体的数据集 在频繁项集挖掘中 每个实体是一个项 待考察的搜索空间是2d 这是可能产生的候选项集的个数 在频繁子图挖掘中 每个实体是一个顶点 并且最多可以有d 1条到其他顶点的边 假定顶点的标号是唯一的 则子图的总数是其中 是选择i个顶点形成子图的方法数 而是子图的顶点之间边的最大值 表7 8对不同的d比较了项集和子图的个数 挖掘频繁子图的一种蛮力方法是 产生所有的连通子图作为候选 并计算它们各自的支持度 考虑图7 11a中显示的图 假定顶点标号选自集合 a b 而边的标号选自集合 p q 则具有一个到三个顶点的连通子图列在图7 11b中 候选子图的个数比传统的关联规则挖掘中的候选项集的个数大得多 其原因 一个项在一个项集中至多出现一次 而一个顶点标号可能在一个图中出现多次 相同的顶点标号对可以有多种边标号选择 把事务转化为图 把图转化为事务 频繁子图挖掘算法的一般结构 一种挖掘频繁子图的类Apriori算法由以下步骤组成候选产生 合并频繁 k 1 子图对 得到候选k 子图 候选剪枝 丢弃包含非频繁的 k 1 子图的所有候选k 子图 支持度计数 统计 中包含每个候选的图的个数 候选删除 丢弃支持度小于minsup的所有候选子图 候选产生 在候选产生阶段 一对频繁 k 1 子图合并成一个候选k 子图 如何定义子图的大小k 在图7 11显示的例子中 k是图中的顶点个数 通过添加一个顶点 迭代的扩展子图的方法称作顶点增长 vertexgrowing K也可以是图中边的个数 添加一条边到已有的子图中来扩展子图的方法称作边增长 edgegrowing 为了避免产生重复的候选 可以对合并施加附加的条件 两个 k 1 子图必须共享一个共同的 k 2 子图 共同的 k 2 子图称作核 core 通过顶点增长产生候选 用邻接矩阵表示图 顶点增长方法可以看成合并一对 k 1 k 1 的邻接矩阵 产生k k邻接矩阵的过程 通过顶点增长合并子图的过程 邻接矩阵M1与另一个邻接矩阵M2合并 如果删除M1和M2的最后一行和最后一列得到的子矩阵相同 结果矩阵是M1 添加上M2的最后一行和最后一列 新矩阵的其余项或者为0 或者用连接顶点对的合法的边标号替换 VertexGrowing a r a r 结果图包含的边比原来的图多一条或两条 d e 可以相连或不相连 由于该边的标号未知 我们需要对 d e 考虑所有可能的边标号 从而大大增加了候选子图的个数 通过边增长产生候选 在候选产生期间 边增长将一个新的边插入一个已经存在的频繁子图中 与顶点增长不同 结果子图的顶点个数不一定增加 通过边增长产生候选子图的过程概括如下 一个频繁子图g1与另一个频繁子图g2合并 仅当从g1删除一条边得到的子图与从g2删除一条边得到的子图拓扑等价 合并后 结果子图是g1 添加g2的那条额外的边 a 顶点拓扑等价 topologicallyequivalent 加入一条新边到v1与加入该边到v2产生的图相同 则v1和v2两顶点拓扑等价 顶点拓扑等价的概念能够帮助我们理解 在边增长时为什么能够产生多个候选子图 如果a和c拓扑等价 我们将它们记作a c 对于核外边的点 如果它们的标号相同 我们将它们记作b d 当与一对 k 1 子图相关联的核有多个时 还可能产生多个候选子图 候选剪枝 产生候选k 子图后 需要剪去 k 1 子图非频繁的候选 候选剪枝可以通过如下步骤实现 相继从k 子图删除一条边 并检查对应的 k 1 子图是否连通且频繁 如果不是 则该候选k 子图可以丢弃 为了检查 k 1 子图是否频繁 需要将它与其他频繁 k 1 子图匹配 判定两个图是否拓扑等价称为图同构 graphisomorphism 问题 为了解释图同构问题的困难性 考虑图7 19中的两个图 同构图 处理图同构 处理图同构问题的标准方法是 将每一个图都映射到一个唯一的串表达式 称作代码 code 或规范标号 canonicallabel 规范标号具有如下性质 如果两个图是同构的 则它们的代号一定相同 这个性质使得我们可以通过比较图的规范标号来检查图同构 构造图的规范标号的第一步是找出图的邻接矩阵表示 一个图可以有多种邻接矩阵表示 因为存在多种确定顶点次序的方法 数学上讲 每个排列都对应于初始邻接矩阵与一个对应的排列矩阵的乘积 如下面的例子所示 例子 考虑下面的矩阵 其中 P13是通过交换单位矩阵的第一行和第三行得到的 为了交换M的第一和第三行 和列 排列矩阵与M相乘 M右乘P13交换M的第一列和第三列 而M左乘P 13交换M的第一行和第三行 第二步是确定每个邻接矩阵的串表示 由于邻接矩阵是对称的 因此只需要根据矩阵的上三角部分构造串表示就足够了 在图7 21所示的例子中 代码是通过逐列连接矩阵的上三角元素得到的 最后一步是比较图的所有串表达式 并选出具有最小 最大 字典次序值的串 支持度计数 支持度计数一般是开销很大的操作 因为对于每个G 必须确定包含在G中的所有候选子图 加快该操作的一种方法是 维护一个与每个频繁 k 1 子图相关联的图ID表 一旦一个新的候选k 子图通过合并一对频繁 k 1 子图而产生 就对它们的对应图ID表求交集 最后 子图同构检查就在表中的图上进行 确定它们是否包含特定的子图 非频繁模式 迄今为止 关联分析都基于这样的前提 项在事务中出现比不出现更重要 因此 数据库中很少出现的模式不是令人感兴趣的 并使用支持度度量将其删除 这种模式称为非频繁模式 定义7 7非频繁模式非频繁模式是一个项集或规则 其支持度小于阈值minsup 尽管绝大部分非频繁模式都是让人不感兴趣的 但是其中的一些可能对于分析是有用的 特别是涉及到数据中的负相关性 例如 DVD和VCR一起销售的情况很少 因为购买DVD的人多半不会购买VCR 反之亦然 这种负相关模式有助于识别竞争项 competingitem 竞争项的例子包括茶与咖啡 黄油与人造黄油 普通与节食苏打 台式机与便携式计算机 某些非频繁模式也可能暗示数据中出现了某些有趣的罕见事件或例外情况 例如 如果 火灾 yes 是频繁的 但 火灾 yes 报警 on 是非频繁的 而后者是一个有趣的非频繁模式 因为它可能指出警报系统的故障 为了检测这种不寻常情况 必须确定模式的期望支持度 使得如果一个模式的支持度明显低于期望支持度 则可以声明它是一个有趣的非频繁模式 负模式 设I i1 i2 id 是项的集合 负项ik表示项ik不在给定的事务中出现 例如 如果事务中不包含咖啡 则咖啡是一个值为1的负项 定义7 8负项集负项集X是一个具有如下性质的项集 1 X A B 其中A是正项的集合 而B是负项的集合 B 1 2 s X minsup 定义7 9负关联规则负关联规则是一个具有如下性质的关联规则 1 规则是从一个负项集提取的 2 规则的支持度大于或等于minsup 3 规则的置信度大于或等于minconf本章中 负项集和负关联规则统称负模式 负相关模式 定义7 10负相关项集项集X x1 x2 xk 是负相关的 如果定义7 11负相关关联规则关联规则X Y是负相关的 如果s X Y s X s Y 其中 X和Y是不相交的项集 即X Y 负相关的完全条件可以表述如下 负相关条件也可以用正项集和负项集的支持度表示 设和分别表示X和Y的对应负项集 由于负相关条件可以表述如下 负相关项集和负相关关联规则统称负相关模式 negativelycorrelatedpattern 非频繁模式 负模式和负相关模式比较 非频繁模式 负模式和负相关模式是三个密切相关的概念 尽管非频繁模式和负相关模式只涉及包含正项的项集或模式 而负模式涉及包含正项和负项的项集或模式 但是这三个概念之间存在一定的共性 如图7 22所示 首先 许多非频繁模式有对应的负模式 如果x y是非频繁的 则除非minsup太高 否则它很可能有对应的负项集 例如 假定minsup 0 25 如果x y是非频繁的 则表中的其它几种组合至少有一种是频繁的 挖掘有趣的非频繁模式的技术 原则上讲 非频繁项集是未被标准的频繁项集产生算法 如Apriori和FP增长 提取的所有项集 这些项集对应于图7 23所示的频繁项集边界之下的那些项集 由于非频繁模式的数量可能是指数级的 特别是对于稀疏的 高维的数据 因此 为挖掘非频繁模式而开发的技术着力于发现有趣的非频繁模式 例如 负相关模式 基于挖掘负模式的技术 一种方法是将每个项看作对称的二元变量 通过用负项增广 将事务数据二元化 然后使用Apriori算法等 可以导出所有的负项集 仅当只有少量变量被视为对称的二元变量时 该方法才是可行的 如果每个项都必须视为对称的二元变量 则可能导致计算复杂度增加 1 当每个项都用对应的负项增广时 项的个数就加倍 待探测的项集格比2d大得多 2 当增加进负项后 基于支持度的剪枝不再有效 对于每个变量x x或的支持度大于等于50 因此 即使支持度阈值达到50 仍有一半的项是频繁的 3 当增加进负项后 每个事务的宽度增加 当包含负项后 事务的宽度增加到d 另一种方法不是用负项增广数据 而是根据对应的正项集计算负项集的支持度 例如 的支持度可以用如下方法计算 基于支持度期望的技术 该方法要求仅当非频繁模式的支持度显著小于期望支持度时 才认为它是有趣的 本节介绍两种计算期望支持度的方法 基于概念分层的支持度期望基于间接关联的支持度期望 计算期望支持度的一种方法是利用概念分层来推导例如 由于火腿和熏肉属于相同的产品族 我们预期火腿和薄片食物之间的关联与熏肉和薄片食物之间的关联类似 如果任何一对的真实支持度小于期望支持度 则非频繁模式是有趣的 计算期望支持度的公式 假定项集 C G 是频繁的 用s 表示模式的实际支持度 而表示 期望支持度 C和G的子女或兄弟的期望支持度可以用如下公式计算 节食碳酸饮料和薄片食物的期望支持度可以使用公式 7 8 计算 因为这两项分别是碳酸饮料和点心的子女 如果节食碳酸饮料薄片食物的实际支持度明显低于它们的期望值 则节食碳酸饮料和薄片食物形成一个有趣的非频繁模式 基于间接关联的支持度期望 本节提供一种确定商品对期望支持度的方法 考察通常与这两个商品一起购买的其他商品 假定节食和普通碳酸饮料都经常与薄片食品和点心一起购买 这两种商品可望是相关的 并且它们的支持度应当较高 因为他们的实际支持度低 节食和普通碳酸饮料形成了一个有趣的非频繁模式 这样的模式称作间接关联 indirectassociation 模式 间接关联的一个高层解释见图7 27 项a和b对应于节食和普通碳酸饮料 而Y称作中介集 mediatorset 包含诸如薄片食物和点心等商品 间接关联形式定义在下面给出 定义7 12间接关联一对项a b是通过中介集Y间接关联的 如果下列条件成立 1 s a b ts 项对支持度条件 中介支持度和依赖条件用来确保Y中的项形成a和b的近邻 可以使用6 7 1节介绍的兴趣因子 余弦或IS Jaccard和其他依赖度量 间接关联可以用如下方法产生 首先 使用诸如Apriori和FP增长等标准算法产生频繁项集 然后 合并每对频繁k 项集得到候选间接关联 a b Y 其中a和b是一对项 而Y是它们的公共中介 例如 p q r 和 p q s 是频繁3 项集 则通过合并这对频繁项集得到候选间接关联 r s p q 一旦产生候选 就要验证它是否满足定义7 12中的项对支持度和中介依赖条件 中介支持度条件不必验证 因为候选间接关联是通过合并一对频繁项集得到的