本文共 2274 字，大约阅读时间需要 7 分钟。

1. 关联分析：发现隐藏在大型数据集中的有意义的联系；所发现的联系可以用关联规则和频繁项集来表示
2. 两个问题：
   1. 从大型事务数据集中发现联系的开销大
   2. 所发现的联系需要验证
3. 问题定义：
   1. 二元表示：购物篮事务每行对应一个事务，每列对应一个项，项在事务中的值为0或1，出现很重要，所以是非对称二元变量
   2. 项集和支持度计数：事务的宽度是事务中出现项的个数；项集的支持度计数即包含该项集的事务个数
   3. 关联规则：关联规则的强度用支持度和置信度度量
      1. 支持度：确定规则可以用于给定数据集的频繁程度
      2. 置信度：确定Y在包含X的事务中出现的频繁程度
      3. 支持度代表规则出现程度，置信度通过规则进行推理具有可靠性
      4. 关联分析做出的推论并不必然蕴含因果关系，这只表示规则前后件中的项明显的同时出现；因果关系需要关于数据中原因和结果属性的知识
   4. 关联规则的发现：对给定事务集合T，关联规则发现是指找出支持度和置信度>=阈值的规则
   5. 从包含多个项的数据集中提取规则的直接办法开销很大，提高效率的方法是拆分支持度和置信度要求，一种策略：
      1. 频繁项集的产生：从项集中找到满足最小支持度阈值的项集，即频繁项集
      2. 规则的产生：从频繁项集中提取满足最小置信度阈值的规则，即强规则
4. 频繁项集的产生：
   1. 两种降低频繁项集的计算复杂度的策略：
      1. 减少候选项集的数目：先验原理Apriori
      2. 减少比较次数：替代每个候选项集和每个事务相匹配，使用更高级的数据结构、存储候选项集、压缩数据集
   2. 先验原理：如果一个项集是频繁的，则它的所有子集是频繁的；相反，子集如果是非频繁的，其超集也是非频繁的；基于支持度的剪枝，依赖于支持度的反单调性：一个项集的支持度不会超过其子集的支持度
   3. Apriori算法的频繁项集的产生：两个特点
      1. 逐层算法，找出频繁k-项集
      2. 使用产生-测试策略来发现频繁项集（产生候选项集->识别属于事务的所有候选、支持度计数->提取频繁k-项集）
   4. 候选集的产生和剪枝：Apriori-gen函数：
      1. 候选项集的产生：由前一次迭代发现的频繁（k-1）-项集产生新的候选k-项集
      2. 候选项集的剪枝：基于支持度，删除一些候选k-项集
      3. 候选项集产生过程的要求：
         1. 避免产生过多不必要的候选：子集非频繁
         2. 确保候选项集是完全的：没有遗漏
         3. 避免产生重复的候选项集
      4. 候选项集产生过程的几种方法：
         1. 蛮力方法：对指定k，把所有k-项集作为候选，去除不要的候选
         2. F(k-1)*F(1)方法：用其他频繁1-项集来扩展频繁(k-1)-项集；完备的方法，但会出现重复的候选项集，避免产生重复的方法是将每个项以字典序存储，每个频繁(k-1)-项集X只用字典序比X中所有的项都大的频繁项进行扩展
         3. F(k-1)*F(k-1)方法：即Apriori-gen函数，合并一对频繁(k-1)-项集，仅当它们的前(k-2)项相同且最后一项不同
   5. 支持度计数：枚举每个事务包含的项集，利用它们更新对应的候选项集的支持度（项集中的项以字典序排序）
      1. Hash树的支持度计数：在Apriori算法中，将候选项集划分为不同的桶，包含在事务中的项集也散列在相应的桶中
   6. 计算复杂度：
      1. Apriori算法的计算复杂度由以下因素影响：
         1. 支持度阈值：支持度阈值降低，频繁项集的最大长度会增加
         2. 项数（维度）
         3. 事务数
         4. 事务的平均宽度：频繁项集的最大长度随事务的平均宽度的增加而增加；事务宽度增加，Hash树遍历次数增加
      2. 时间复杂度：
         1. 频繁1-项集的产生：O(N*w)
         2. 候选的产生
         3. 支持度计数
5. 规则产生：每个频繁k-项集产生多达2^k-2个关联规则，满足置信度阈值则被留下；计算关联规则的置信度不需要再次扫描事务数据集
   1. 基于置信度的剪枝：不具有任何单调性
   2. 定理：如果规则X->(Y-X)不满足置信度阈值，则X'->(Y-X')也不满足，X'是X的子集
   3. Apriori算法的规则的产生：使用一种逐层方法产生关联规则，其中每层对应于规则后件的项数；开始，提取规则后件只有一个项的所有高置信度规则，然后合并两个规则后件产生新的候选规则；在规则产生时，不必再扫描数据集，而是使用在频繁项集中产生时计算的支持度计数来确定置信度
6. 频繁项集的紧凑表示：频繁项集的数量可能很大，从中找出重点的、其他所有频繁项集的、较小的、具有代表性的项集是有用的；两种：
   1. 极大频繁项集：直接超集都是不频繁的；极大频繁项集形成了可以导出所有频繁项集的最小的项集的集合；但是极大频繁项集却不包含其子集的支持度信息
   2. 闭频繁项集：提供了频繁项集的一种最小表示，不丢失支持度信息；
      1. 闭项集：项集的直接超集都不具有和它相同的支持度计数
      2. 可以用闭频繁项集的支持度来确定非闭频繁项集的支持度，非闭频繁项集的支持度一定与其某个直接超集相同，而子集的支持度>=超集的支持度，所以非闭频繁项集的支持度一定等于其超集的最大支持度
      3. 所以从闭频繁项集找出子集中的非闭频繁项集，可以确定其支持度
      4. 对于分析，仅提供闭频繁项集就足够了，而不是所有的频繁项集
      5. 冗余规则：如果存在X的子集X'和Y的子集Y'，X->Y和X‘->Y'的支持度和置信度是相同的，则X’->Y'是冗余的；如果使用闭频繁项集产生规则，则不会出现这样的冗余规则
      6. 极大频繁项集都是闭的，因为任何极大频繁项集都不可能和其直接超集有相同的支持度计数
7. 产生频繁项集的其他方法：Apriori算法多次扫描事务数据集，开销大
   1. 项集格遍历：3种策略
      1. 双向
      2. 等价类
      3. 宽度优先和深度优先：深度优先策略用来寻找极大频繁项集的算法，找到后再其子集上进行剪枝
   2. 事务数据集的表示：表示方法的选择可能影响计算候选集支持度的开销

转载地址：https://blog.csdn.net/u013103305/article/details/83307724 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！