挖掘频繁项集的三种算法：Apriori，ECLAT，FP-Growth
Apriori
缺陷：需要多次扫描数据库（I/O开销大），且生成的候选项集数量可能极其庞大 。
为了解决 Apriori 的 IO 和候选集问题，PPT 提到了几种优化：
Partitioning (分区):只需要扫描两次数据库。原理是“局部频繁才可能全局频繁” 。
DHP (Direct Hashing and Pruning):利用哈希桶计数来预先过滤无效的 k-itemsets
如果一个 k-项集对应的哈希桶（Bucket）里的总计数小于 minsup，那么该 k-项集一定不频繁
课件例题
挖掘频繁项集（字有点丑哈，凑合看）
ECLAT
这个方法有点类似信息检索中的倒排表
课件例题
FP-Growth
采用分治的思想
深度优先搜索 (Depth-first search)，通过递归挖掘 FP-tree，避免了重复扫描数据库（通常只需扫描两次）
优势：只需要扫描两次数据库；无需生成海量候选集；利用前缀共享压缩存储
例题1
例题2
模式评估
高支持度和高置信度的规则可能是有误导性的。
“打篮球->吃麦片”的置信度是 66%，看起来很高。但如果全校学生吃麦片的比例本来就是 75%，那么打篮球实际上降低了吃麦片的概率（负相关）。
提升度lift,衡量X,Y是否独立
=1独立（无关），>1正相关（有用），<1 负相关
（这里有个符号很坑的点，∪这个符号表示的是XY同时出现，可能是表示包含在一次事务中，不要看成集合里的交集了）
课件例题
lift的问题
Null Transactions (空事务):既不包含 X 也不包含 Y 的事务（例如超市里既没买牛奶也没买咖啡的海量交易）
Kulc
Imbalance Ratio (IR)
空值不变性是指：如果我们在数据集中增加或减少这些“无关的空交易”，某个度量指标的数值保持不变，那么该指标就具有空值不变性。
不具备空值不变性的指标：Lift,
。在处理稀疏大数据（如文本挖掘、推荐系统）时要慎用，因为绝大多数数据都是“空”的（比如两个词在绝大多数文档中都不出现）。
具备空值不变性的指标：Kulczynski, Cosine, Jaccard。它们只关注“有非零值”的部分，因此更适合大规模数据挖掘。
其他简单例题
置信度与支持度
置信度注意哪个是分母！
模式压缩
1.频繁项集支持度为1，也就是这100个都出现，他们组成的子集都符合条件，根据集合非空子集的个数：2^100-1（很有意思，这个情况就像是在求集合的非空子集，也就是把不同事务看作集合，求它的所有非空子集，然后取并集）
2.思路，根据已有的集合，从大集合中删除它的支持度不同的子集
目前最大的集合是{a1,....,a100},它的子集有{a1}{a1,a2}..{a1,.....a50},{a1,...a50,a51}...
对于a1}{a1,a2}..{a1,.....a50}....即不包含a51-a100的集合，他们出现了两次，支持度为2
因为支持度不同，所以{a1,....,a100}不会删去他们，包含a51-a100的集合，count被删去了
再看进一步的特殊情况{a1,.....a50}，它的子集都包含了两次，都删除
所以只剩下{a1,....,a100}：1，{a1,.....a50}：2
3.思路，根据已有的集合，从大集合中删除它的子集，无论支持度是什么情况
目前最大的集合是{a1,....,a100}囊括了所有的子集，所以都删掉了只剩它子集
例题
分别找出所有的：
频繁项集 (Frequent Itemsets)
闭频繁项集 (Closed Patterns)
极大频繁项集 (Max-Patterns)
(1))