A-Priori算法 目的 寻找频繁项集 概念 假设有集合 I 和 j，有关联规则 R =>( I -> j ) 频繁项集 一个子集，在多个集合中出现，并且出现次数大于支持度，就是一个频繁项集合 如果项集 I 是频繁的，那么其所有的子集都是频繁的 支持度 区分是否频繁的值，一般会定义得很大，使得频繁集合（二元，三元）只占有原来集合的1% 可信度 对于关联规则 R，集合 I U { j } 的支持度与 I 的支持度的比值 就是说规则是否能成立，有点像新词发现，只要 I 出现，j 就出现 兴趣度 对于关联规则 R, 可信度及包含 j 的集合比率之间的差值 就是说规则有没有能引起人的兴趣，接近0就没趣了，正数表示吸引，负数表示互斥 算法过程 遍历一遍编号1~n 找出频繁的单项物品1~m(m<n) 两两组合成二元集合，组合的两个项必须都是频繁的（单调性） 根据计数器，找出二元集合中的频繁项对 n元上的A-Priori算法 L(k): 有k个元素的集合，这个集合是频繁的，当C(k)的频繁度>s(支持度)，C(k) => L(k) C(k): 有k个元素的集合，其中任意k-1个元素的集合都是L(k-1) 优化 hash 频繁桶 利用hash的性质，hash到一个桶中的集合有自己的频繁度计数器pc，对于同一个桶 sum(pc) < s,那么桶内的集合都不是频繁的 可以多进行一次hash频繁桶来降低扫描数量，当一个集合同时出现在第一次和第二次的hash频繁桶中，这个集合才有可能频繁 son算法 这个算法属于抽样算法中的优化，可以派出所有伪反例和伪正例 mapreduce计算 第一次： map: in_key => 购物篮集合中的一个子集, in_value => no out_key => 频繁度 > ps 的候选项目对 p为这个map分到的集合的比例, 可以证明，如果是频繁项，至少有一个map会传递它给reduce reduce： 输出候选值 第二次： map: in => 候选集合+部分原来购物车数据(或购物车数据) out_...