Frequent Pairs and A-priori

接着上篇频繁项集和关联规则

频繁对的存储

通常我们最关心的是频繁出现一对对东西,设有N种商品,则共有frac{N^2-N}{2}种不同的对子。若N很大,则记录这些对子出现的频率也会非常占用内存。有两种存储方式:

  1. 三角矩阵
  2. 列表方式

这两种方法都建立在一个从东西到整数的映射之上:

三角矩阵:第j行第i列的元素表示编号ij的两样东西共同出现在多少个篮子中,同时跟新从东西到整数的映射,只保留能能构成超过支持度阈值的项对的东西。

列表方式:

两种方式根据实际情况不同耗费内存各有优劣。

A-priori

A-priori算法是希望利用第k轮运算的结果,来减小第k+1轮的搜索范围,其主要依据如下两点事实:

  • 如果一个项集出现了至少s次,那么其每一个子集都必然出现了至少s
  • 如果东西i出现次数少于s次,那么包含i的项集出现次数必然少于s

因而,如果要找出所有频繁对,可以遍历数据两次:

  1. 遍历所有篮子,计算所有单样东西出现的次数,出现次数超过s的东西称为频繁项
  2. 第二次遍历所有篮子,只考虑1.结果中各项构成的项对是否出现于各个篮子中,并计算出现次数,出现次数超过s的项对称为频繁项对

还可以继续下去,遍历第三次计算频繁3项组,遍历第四次4项组等。

下面是用Apriori算法求频繁项对,并用之前描述的两种存储方式存储结果的代码:

Apriori 算法的改进:

Park Chen Yu 算法是在Apriori算法的第一次遍历时,在"item ~ count"的记录意外额外存储一些哈希信息,用于帮助第二遍遍历的时候减小内存的占用。

MultiStage

Simple

Simple算法是找出各个长度的频繁相集的算法。算法进行一次遍历,对所有的篮子进行若干次随机抽样,针对各个抽样,用修正过的支持度阈值作为频繁项集的判断标准,找出各个抽样中的频繁项集,最后汇总后获得一个频繁项集的候选集作为输出。

也可以遍历第二次,对候选频繁项集进行验证:

Leave a Reply

Your email address will not be published. Required fields are marked *