【数据挖掘学习笔记】10.频繁模式挖掘基础
一、基本概念
频繁模式
– 频繁的出现在数据集中的模式
– 项集、子序或者子结构
动机
– 发现数据中蕴含的事物的内在规律
• 项(Item)
– 最小的处理单位 – 例如：Bread, Milk
• 事务(Transaction)
– 由事务号和项集组成 – 例如：<1, {Bread,Milk}>
• 事务数据库
– 由多个事务组成
• 项集(Itemset)
– 一个或多个项(item) 的集
• 例如：{Milk, Bread, Diaper}
– k-项集(k-itemset)
• 包含k个项的集合
• 包含关系
设 T 为一个事务，则 P 是一个集合，在这种情况下称事务 T 包含集合 P ，记作 T \supseteq P 或者 P \subseteq T 。
例如\{Milk, Bread, Diaper\} \subseteq T_4
• 关联规则(Association Rule)
– 项目集合：I={i₁,i₂,…,iₙ}
– 与任务相关的数据D是由数据库中的各个事务构成的数据集合；其中每个具体事务T都是一个项目集合，并满足条件T⊆I
– 每个具体事务通过唯一的事务标识符TID来进行标识；
– 设A和B分别为两个项目集，则有：若存在关系使得A被包含于特定的事务T中，则等价于A⊆T；
– 则其关联规则表示为以下蕴含式：
• A → B(s, c)
• 其中s代表该关联规则的支持度；c代表该关联规则的置信度
• 支持度计数(Support count)
– 事务数据库中包含某个项集的事务的个数
– 例如：σ({Milk, Bread,Diaper}) = 2
• 支持度(Support)
– 事务数据库中包含某个项集的事务占事务总数的比例。
支持度 s是指事务集D中包含A ∪ B的百分比
support(A ⇒ B) = P(A ∪ B)
置信度 c是指D中包含A的事务同时也包含B的百分比
confidence (A ⇒ B) = P(B | A) = P(A ∪ B)/ P(A)
• 关联规则挖掘目的
– 在基于事务的数据库TD中进行关联规则挖掘的目的在于寻找满足特定条件的所有规则。
• 规则的支持程度达到或超过预先设定的阈值
• 规则的置信水平不低于预先设定的标准
• 关联规则步骤：
– 1、寻找同一个"同一项集"中的各项"规律"（即各项"模式"），这些"规律"具有相同的支撑值。然后筛选出支撑值大于等于minsup的所有"模式"
– 2、求出该"模式集合中所有各项规律"（即各个子模式）的具体置信值，并从中筛选出置信值大于等于minconf的所有子模式
• 频繁项集(Frequent Itemset)
设P为任意一个项集，则当且仅当P的支持度\geq指定的最小阈值\min\text{sup}\text{threshold}时，P被称为频繁项集
关联规则挖掘分类
– 根据基于挖掘模式完整性的分类：给定最小支持度min_sup，在线能够提取出完整集合、闭频次项目集合以及最大频次项目集合。
– 也可用于提取受约束、近似和接近匹配类型的 freqItemSet（即满足用户指定一组约束条件、仅计算近似支持度计数以及与接近或几乎匹配的支持度计数对应的 freqItemSet）。
– 这些类型包括 top-k 频繁项目组合。
– 不同的应用类型对所提取 freqItemSet 的完整性有着不同的需求；我们主要研究完整 freqItemSet、闭合 freqItemSet 和受约束 freqItemSet
二、Apriori
生成频繁项集
穷举法(Brute-force approach)
– 所有项集都被选为候选频繁项集
– 被系统扫描一次事务数据库后可计算出各候选项集的支持度
• 对每一个交易单元与所有候选项进行评估
计算复杂度－O(NMw)中，N表示事务总数，M=2d代表候选项集合的数量，其中d表示项的数量；而w代表每次比较所需的时间。
• 计算复杂度为O(NMw)
– 表现欠佳，亟需优化
• 优化措施：降低候选集合规模（M）
• 全搜索方案设定候选集合大小为2^d
• 采用剪枝策略减少候选集合规模（M）；同时结合高效数据结构降低比较次数（NM）
• 跳过无需比较的候选组合；并采用优化算法降低每次比较成本（w）
• 缩小候选集
– Apriori性质:
• 如果一个项集被标记为频繁，则该项集中所有的子集都会被标记为频繁。
• 也被称为反单调性
– Apriori性质成立的原因如下
• 任何一个项集的支持度不会超过其任何子集的支持度
缩小候选集思路
Apriori算法
– Apriori算法主要采用布尔型关联规则来获取频繁项集
– 该算法基于先验知识经验信息，并通过逐层递进的方式进行迭代计算
– 它首先从数据集中获取所有满足条件的单个项目 frequent 1-itemsets（即 L₁）
– 然后利用 L₁ 逐步生成候选 2-itemsets，并通过验证这些候选是否存在于数据库中来获得 frequent 2-itemsets（即 L₂）
– 接着再利用 L₂ 来生成候选 3-itemsets 并验证其是否为 frequent 3-itemsets
– 这一过程依次类推直至无法获得新的 frequent k-itemsets
– 在每一步中都需要进行一次完整的数据库扫描以验证候选项集合的有效性
计算候选集支持度
方法：
– 采用哈希树结构来组织候选项集合
– 哈希树的叶子节点则分别存储候选项集合以及对应的计数值
– 中间节点则嵌入哈希表结构
– 基于哈希函数的设计理念，则能够有效识别出事务范围内所有的候选项集合。
构建哈希树
– 假设存在15个长度为3的候选集合：{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8,9}, {3,6,7}, {3,6,8}
– 定义如下参数：
• 哈希函数
• 最大叶节点容量：指每个叶节点中所能存储的最大候选集合数量（当该数值超出阈值时将触发节点分裂）
候选集
– {1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}
– 哈希树
子集操作
查找哈希树
Apriori算法主要的挑战
– 要对数据进行多次扫描；
– 会产生大量的候选项集；
– 对候选项集的支持度计算非常繁琐；
解决思路
– 减少对数据的扫描次数；
– 缩小产生的候选项集；
– 改进对候选项集的支持度计算方法
• 方法1：基于hash表的项集计数
将所有项目集合利用对应的哈希函数分配到不同哈希表的各个桶中，并通过比较各桶内的项目集合与最小支持计数来筛选并去除不符合条件的项目集合。
方法2：Transaction Compression（通过压缩后续迭代中的事务数量实现进一步优化）
- 不包含任何k-项集的事务不可能包含任何(k+1)-项集；因此，在下一步的计算中不会被标记为包含(k+1)-项集。
- 这种事务在下一步的计算中不会被标记为包含(k+1)-项集。
• 方法3：划分
– 获取所有频繁项集仅需两次全局扫描
– 对于D中的每一个频繁项集而言，在至少一个子集中必然是局部频繁项
• 第一阶段操作：在初次扫描过程中将数据分割为若干子块并识别出各子块中的局部高频项目
• 第二阶段操作：在第二次扫描期间计算每个候选项目组的实际支持度，并最终确认全局 frequent 项目
• 方法4：采样（从给定数据集中选取一个子集进行分析）
– 基本思想：从原始数据集中选取一个子集，在该子集上基于Apriori算法挖掘频繁模式
– 为了提高算法效率需以牺牲一定精度为代价选择合适的样本容量应当控制在一个足以放入内存的范围内适当降低最低支持度能够有效减少被遗漏的重要频繁项集
• 通过单次全局遍历即可验证从采样中获得的所有频繁项集
• 通过另一次全局遍历则可补充那些在采样分析中被遗漏的重要项集
方法5：动态项集计数
– 在各个扫描阶段加入候选项集，在此情况下若某个候选项集已达到最低支持度，则可以直接将其加入到频繁项集中，并无需在此处之后继续进行比较计算。
Apriori算法在每次循环中都需要对数据库进行一次完整的扫描以计算候选项目集合的支持度；当项集长度增长时虽然候选项目集合的数量逐渐减少但包含这些候选项目集合的具体事务数量持续下降而数据量并未发生变化；– 优化支持度计算的方法：并在此基础上减少候选生成的数量
AprioriTid
– 核心原理
• 若一个事务中不含频繁k-项目集合，则该事务必定不含任何频繁(k+1)-项目集合。
– 基于上述定理可知，在移除所有不含频繁k-项目集合的事务后，并不会影响对长度超过k的项集支持度的计算。
– 根据这一理论思想形成了Apriori算法的一种优化方案。
• AprioriTid基本思想
– 在产生候选项集之后，构造一个Tid表，用来记录每个事务包含的候选项集。候选k-项集的Tid表记做Ck，其形式为<t.Tid, {C∈Ck| C ⊆t}>，其中，Tid是事务t的标识，C是事务t中包含的候选k-项集。如果一个事务不包含任何候选k-项集，则这个事务就不会出现在Ck中。
– 对于k＝1，C1 ＝TD；
– 对于k >1，Ck由Ck－1生成
• 如果一个事务包含了一个候选k-项集的两个频繁(k－1)-项集，那么其必然包含这个候选k-项集。
• 故构造Ck的方法如下：
– 对每个候选k-项集P，如果P的两个频繁(k－1)-项集都包含在Ck－1里的某个记录中，则添加P到Ck的相应记录中。
示例
AprioriTid算法
优点
• 采用逐步缩减的Tid表替代原有的事务数据库
– 缺点
• 在初始阶段特别是第二次循环（检测频繁2-项集）时，候选项集的数量极大化可能导致生成的Tid表规模超过原有事务数据库规模。此时Apriori算法在效率上仍优于AprioriTid算法
– AprioriHybrid
• 融合Apriori与AprioriTid各自的优点
• 思想
– 首先采用Apriori算法并预估Tid表大小；当Tid表缩减至可内存加载范围时，则切换至使用AprioriTid算法
缩减候选集合规模
– Apriori算法的时间复杂度与其候选对象集合的数量密切相关。候选对象集合元素越多，则构建相应的哈希树所需的空间越大，在运行效率上也会随之降低。因此，在Apriori算法中除了提升算法效率之外的另一个可行方法就是缩减候选对象集合规模。
• Apriori算法在生成k项式候选项时利用频繁出现的(k-1)项式组合进行过滤筛选，在一定程度上减少了候选项的数量
• 但是这种方法对于生成所有可能的2项式候选项并没有产生显著的效果
– 假设频繁出现的1项式共有n个，则生成的所有可能2项式候选项数量为n(n-1)/2
三、频繁图挖掘
频繁子图挖掘
– 若干图中找到最大的频繁子图
标号图
一个标号图被称为由五个元素组成的五元组G={V,E,Γ_E,Γ_V,L}。其中,V表示图中的节点集合；E⊆V×V表示图中的边集；Γ_V和Γ_E各自表示节点和边上的标号集；L则为定义域为节点集和边集上的标签函数，在将标签分配给节点和边上发挥着关键作用。
图的同构
给定两个图G和G'（分别由顶点集、边集以及标签集合等构成），当且仅当它们之间存在同构关系时，则满足以下条件：
- 对于任意顶点u属于顶点集V，在标签映射下有L(f(u)) = L'(u)。
- 对于任意两顶点u和v属于顶点集V，在原始图中存在边（u,v）当且仅当在映射后的新图中存在对应的边（f(u), f(v））。
- 对于每一条边（u,v）属于边集E，在标签映射下有L(f(u), f(v)) = L'(u, v）。
支持度
设GD为所有图的一个集合，则其中某特定图G的支持度定义为SUPG。特别地，计算方法是：找出GD中与该特定子结构G存在同构关系的所有其他子结构G′的数量，并将其与整个数据集中的总结构数量进行比较。这个比值即表示了该特定子结构在整体数据集中的支持度水平。
频繁图/频繁树
设图集GD定义为GD=\{G_i|i=0,1,\dots,n\}，并设定其最小支持度阈值为min\_sup。则称该图为频繁图，其条件为其支持度不低于该阈值，即有SUP(G)\geq min\_sup。相应地，若该图无环路，则称其为频繁树结构。
类Apriori算法
例
变种
– 点与点之间相互连接且各边相等
– 各点间相互连接但各边长度不一定相同（可取小于某个值）
– 各点间相互连接但位置不同
– 各点间相互连接但位置和长度均不同