挖掘模式(上)

*** 频繁项集 闭项集 关联规则

1. 概念 [100%]
2. 支持度 support(A=>B) = P(A ∩ B)
3. 置信度 confidence(A=>B) = P(B | A)
4. 项集 项的集合
   ** 挖掘频繁模式方法
   *** Aprioir FP-growth
5. 概念与技术 [3/3]
6. Aprioir
   浪费空间与时间的做法
7. FP-growth
   构建类似字典树来整合空间与时间关系
8. 垂直数据格式挖掘频繁项集
   ** 挖掘闭模式和极大模式
9. 概念与技术 [2/2]
10. 闭模式 [2/2]
11. 朴素方法
    频繁项集 的 完全集 , 删除是其他项集 的 真子集 , 并且 具有 相同 的 支持度
    这种 方法 开销 很大 .
12. 改进方法 [3/3]
    在 挖掘 过程 直接搜索 闭 频繁项集, 也就是 识别出 闭项集 然后 尽快对 搜索空间 减枝 .
    减枝 包括
13. 项合并
    X 的 每个 事物 包含 Y , 但是 不包含 Y 的 任何 真超集 . X U Y 成为 一个 闭频繁 项集 , 不必 搜索 包含 X 不 包含 Y 的 项集 .
14. 子项集 减枝
    X 是 Y 的 真子集 and support(X) == support(Y) 那么 X 与 X 在 集合 枚举树 中的所有后代 都不是 闭频繁项集 .
15. 项跳过
    深度有限的挖掘中, 每一层 都有 一个 与 头表和投影数据库相关连的前缀 X, 如果一个局部频繁项 p 不同的头表都有相同的 支持度 那么就可以从 高层的头表中裁剪掉.
16. 极大模式
    可以将 闭模式 的 挖掘技术 相应的 嵌套在 极大模式上
    ** 模式评估方法
17. 从关联分析到相关分析 [5/5]
18. 提升度
    lift(A, B) = P(A ∪ B) / (P(A) * P(B))
    小于 1 负相关 大于1 正相关 1 是独立的
19. X^2 检验
    X^2 = sum((observe_value - expection_value)^2 / expection_value)
    然后根据自由度使用相依表
20. 全置信度
    all_conf(A, B) = sup(A union B) / max(support(A), support(B)) = min(P(A | B), P(B | A))
21. Kulczynski(Kulc) 度量
    Kulc(A, B) = (P(A | B) + P(B | A))/ 2
    可以看做两个置信度的平均值
22. 余弦度量
    cosine(A, B) = P(A ∪ B) / (P(A) * P(B)) ^ (1/2) = (P(A | B) * P(B | A)) ^ (1/2)
    可以看做 调和 提升度量
23. 小结 [4/4]
24. 提升度 和 X^2 模式关联 分析 能力 有欠缺
25. 零事物 (null transaction)
    不包含 任何考察项集的事物
26. 不平衡比 IR(Imbalance Ratio)
    IR(A, B) = abs(sup(A) - sup(B)) / (sup(A) + sup(B) - sup(A ∪ B))
    如果 A, B 方向的蕴含 相同, 则IR(A, B) = 0
    IR 的值 越大越不平衡
27. 推荐
    Kluc 与 不平衡比 配合使用