数据挖掘算法（二）

数据频繁模式分析

其最典型的一种应用在于超市的销售，通过频繁模式分析可以知道哪些商品经常被一起购买，便于摆放及促销。

从这部分开始，才真正算得上是对数据本身进行信息挖掘。首先给出两个定义，支持度S（support）以及信心度C（confidence）。我给他们通俗的解释是：在事物a对b时S代表（事物a和事物b一起出现的频率）C代表（有a和b的时候有b的频率）。对于一组数据，我们在这一部分感兴趣的是哪些属性经常一起出现（即频繁模式）。首先是先验准则算法，它的原理很简单，当一个母集频繁时，其子集一定频繁，反之，即当一个数据子集不频繁时，其母集必定不频繁。根据反推出的这点，有先验准则算法：

1、以1个事物为单位遍历数据集，去掉不频繁（S低于自己设定的阈值即可）的事物

2、接下来以2个事物一起（这时的2个事物不包括上面去掉的事物）为单位遍历数据集，去掉不频繁的事物

3、重复此操作至需要的频繁模式

然而，这个算法的代价是巨大的，因为它每次迭代都需要遍历一次数据集。为此，FP-Tree（频繁模式树）应运而生。仍记得老师在课堂上对这个算法的作者评价甚高。步骤：

1、将数据集中事物按单个频率排序，并去掉低于阈值的事物（遍历一次数据集）

2、构建FP树（遍历一次数据集）

3、构建FP条件树

4、分析频繁模式

FP树

下一步的所谓FP条件树则是从选定事物如g出发，由下往上统计其到达根部经历的所有事物，若出现次数高于阈值，则其与g可构成FP条件树

g的FP条件树

下一步根据FP条件树很容易找到各个频繁事物集了。