频繁模式挖掘总结

概念:

对于频繁模式挖掘，有两个基本的概念:

support: support = P(A,B)

confidence: confidence = P(A|B) = support/P(B)

存储 ：

在频繁模式挖掘的过程中，在每一次迭代中计算所有k项集的时候，原本需要使用多维数组结构（如k×n），优化策略则是采用单一的一维数组来存储原本的多维数组内容。具体来说，在这种优化方法中使用a[k] 来存储原始二维数组中的元素a[i][j] ，其中k的计算公式为(i-1)*(n - i/2) + j - i。常用的一种高效实现方式是通过哈希表将键值对<i,j>映射到计数值上；同时也可以通过三元组<x,y,count>的形式来进行数据表示。

算法 :

Apriori 算法：

在所有transaction数据中,每一个交易中的各项都按照字母顺序排列

1. 先扫描transaction，找出所有count>support的单个item，作为1项集

2. 对于所有1项集，拼成2项集

3. 扫描transaction，将不满足count>support的2项集剪枝掉

4. 对于已剪枝的k-1项集，如果两个k-1项的前k-2项相同，则合并为k项集

5. 对k项集再进行剪枝，再合并。。。再剪枝。。。

问题：

对于每一次剪枝操作来说，在具体实施过程中需要依次对每一个k-项集进行剪枝处理。具体而言，在每一轮处理中都需要遍历所有的 transaction 数据库来进行计数操作。然而在实际应用中发现，在 transaction 数据库往往较大规模的情况下，并非所有 k-项集都能被有效加载到内存中存储和处理。这导致该过程运行效率低下。尤其是当 k-项集的数量较多时

优化策略：

1. Hash 策略：（PCY algorithm）

在统计k-1项集的频率时（即统计其出现次数），将所有的k项集合进哈希表中的N个桶里（即对应到相应的哈希位置），并不一定实际存在对应的桶（因为可能没有足够多的数据支持），只是对相应桶的计数值进行递增操作。

如果桶n的计数值小于支持阈值，在下一轮选择k项集时，这些被映射到桶n的所有k-itemsets都会被丢弃。这一操作降低了对整个transaction集合进行扫描的次数。

问题：桶的个数很难确定，太小的话，没有效果，太多的话比较占内存

Multistage：

接着，在步骤2完成后继续进行工作。首先依据k-1项集的计数结果判断所有k-1项集是否属于频繁项集，并随后进行一次哈希操作将满足特定条件的k-1项集合映射至新的桶中。

a.此k-1项集为频繁项集

b. 此k-1项集在频繁的桶中（count>support)

然后将在原频繁桶却不在新频繁桶中的k-1项集裁减掉

2.Transaction Reduction

所有没有满足条件的k-1项集的transaction都不会有对应的满足条件的k项集，并将这些k-1项集进行标记之后不再进行扫描。

当事务位于磁盘上时，在标记某行未被读取的情况下

**** 3. SON Algorithm

为了设置支持参数 s 将所有交易划分为 N 个分区，并分别对每个分区执行内存版本的 Apriori 算法（亦可采用多阶段方法），收集各分区产生的局部频繁项集作为候选全球高频项目集合。依次遍历所有候选集合，并统计其出现次数并判断是否达到全球支持阈值。

SONAlgorithm可以写成MapReduce版本分布式计算。

在某些情况下，在数据分析中可以通过将数据按照时间和地点划分为partitions，并对每个partition计算其内部的频繁项集来进行后续分析。实际上无需在全局层面上进行所有的关联规则合并操作；因为这些关联规则仅限于特定的时间和空间范围内的分析需求，在时间和空间维度下分析即可

FP-Tree ：

算法：

首先依次遍历所有的交易记录，并统计每个商品或项目的出现次数。随后，在重构整个交易数据库时按照出现频率降序排列各项内容，并对那些出现频率低于支持阈值的商品或项目进行移除

基于新的 transaction 数据集构建 FP-tree 结构，在构建过程中以一个空（null）根节点开始。对于每一个 transaction 记录，在 FP-tree 中按照项计数从高到低排列的方式组织父子节点关系。每个节点初始化为计数 1。当父节点已存在时，则继承父节点并将其计数加一。

对于每一个item，请按照count从低到高的顺序进行挖掘，并找到其所有的路径。针对每一个路径，请分析出以该item结尾的所有频繁项集。

FP-tree算法不需要在磁盘上多次扫描交易数据（transaction data），相比Apriori算法而言运行效率更高。然而，在面对大量数据时会导致内存占用问题。具体而言，FP-tree的规模显著超过物品集（item）的数量，并且其规模必须控制在交易项（transaction data）数量之下。

实际上，在设置支持参数较高的情况下，Apriori算法的运行轮数显著减少。若能够通过数据分割或采样将其加载到内存进行计算，则其速度与FP-Tree算法相当。

Vertical Format Mining

算法：

遍历所有的transaction数据，并对每个transactionnumber对应的item number list进行转换以生成item number -> transaction number list的关系

转换后的item编号与交易号列表之间存在对应关系，在此基础上将其被视为一个集合体，并对其进行剪枝操作

3. 对于多个 item-number -> transaction-number list 执行交操作，结果为 item-number 二元组集合 -> transaction-number list.

4. 再交得到 三项集，四项集等等

算法总结：采用分布式计算策略，在内存中完成数据运算才是行之有效的方案！在众多挖掘算法中，Apriori算法因其易于实现分布式的特性脱颖而出，并且各个节点之间的交互非常有限，在网络传输方面也展现出显著优势。对于FP-Tree结构而言，则存在相应的分布式处理方案，请待后续深入研究。然而Vertical Format Mining由于其与每个Transaction间的紧密关联性，在实现高效的分布式挖掘方面仍面临诸多挑战

频繁模式挖掘的作用 ： 由频繁模式推断出关联规则

假设J为一频繁的n-项集合。j为其任一元素，则每一个由这n个（J−j）组成的子集合也都满足作为（n−1）-项集的条件。

所以共有n个候选的关联规则：

(J-j) ->j

support = P(j, J-j) = P(J)

confidence = P(j|J-j) = P(j, J-j)/P(J-j) = support/P(J-j)

可见对于每个关联规则来说support是相同的，confidence各不相同。

所以将这n个候选按confidence进行筛选

通常情况下关联规则不宜过多，因此为了提高效率应将支持阈值设置得较高一些，并将其设定在交易总数的1%左右。