挖掘频繁模式、相关和关联（1）
Frequent patterns（Frequent Pattern）是指在数据集中频繁出现的项集、子序列和子结构。这些模式通常用关联规则分析来判断其频繁程度。关联规则分析涉及两个关键指标：支持度和置信度。
支撑度（support）：在所考察的所有对象中所占的比例反映了该模式（规则）的应用价值；
信心度（cofidence）：衡量了从前提到结论推导过程中的可靠性程度，并且反映了其可靠性和稳定性。
设规则为A->B，则支持度和置信度可以表示如下：
support(A->B) = P(AUB)
confidence(A->B) = P(A|B)
基于上述定义, 我们能够推导出, 挖掘关联规则(A→B)的问题实际上等价于挖掘频繁项集（此处的概率计算基于满足条件A项目的出现次数与总样本数量的比例）。
1. 找出所有的频繁项集；
2. 有频繁项集产生强关联规则；
将可以看到，第一步的开销远大于第二步，所以性能将由第一步决定。
挖掘海量数据的主要困难在于这种数据挖掘过程往往会产生大量满足最小支持度阈值条件下的项目集合（term sets），因为在一个项目集合被确定为高频项目集合的前提下，则其所有可能存在的子项目集合也必然成为高频项目集合（frequent item sets）。例如，在现有计算机系统中处理包含100个项目的子集合时会遇到严重的存储问题。因此为了解决这一问题，研究人员提出了比传统的高频项目集合和极大高频项目集合更为复杂的概念。
闭频率项目集：若不存在一个严格的真超项目集Y与当前项目集X具有相同的支撑计数，则称该项目集X在其数据集中为闭合频率项目集；当且仅当前提下（即当一个项目集合满足既是封闭又是频繁时），我们称其为该数据中的一个闭合频繁项目集合；
最大频率项目集合：当且仅当前提下（即对于所有包含当前项目的集合Z，在数据集中Z的支持度都不低于当前项目的支撑度），我们称这样的频率项目集合为最大频率项目集合；
闭包频繁项集的集合包含了一个完整的关于所有频繁项集的信息集合；然而，在极大频繁项集中仅能确定某个特定的候选项集是否属于 frequent itemset，并缺乏具体的支持度数值。
下面是从事务或关系数据集中挖掘频繁项集的方法。
Apriori算法---使用候选产生发现频繁项集
基于Apriori算法采用逐层迭代的方法逐步生成候选项集。在生成每个层次时需遍历整个数据集一次以获得下一个层次的所有候选集合。为了优化逐层扫描效率利用Apriori规则来缩减搜索范围。
Apriori性质：频繁项集的所有非空子集也必须是频繁的
该性质意味着"大"频繁项集可以有"小"频繁项集来产生。
定义L(k)为每个项包含k个元素的数量，并且表示需要进行k次扫描。Apriori算法主要包含两个步骤，具体来说...
\text{Step 1: 生成所有1-长度的频繁项集}
\text{Step 2: 通过合并候选项集生成更大的频繁项集}
连接阶段：假定我们已经获得了 L^{(K-1)} 这一序列，则通过将 L^{(K-1)} 自连接的方式生成 L^{(K)} 的所有候选序列。这一操作主要涉及集合合并运算，并遵循特定规则以确保所生成的结果仅包含恰好 K 个元素；
剪枝阶段：获取了所有候选序列之后，在下一步骤中我们应用Apriori性质进行过滤处理。具体来说，在每一个候选序列中都需要检查其所有可能存在的 (K-1) 长度子序列是否已经被包含在 L^{(K)} 中；若发现有某一个子序列未被包含，则需要从候选项集中剔除该特定序列。完成上述过滤后会获得一个新的缩减候选项集 L'^{(K)} ；随后我们需遍历整个原始数据集并对 L'^{(K)} 中的每一个具体序列计算其支持度计数；最后根据支持度阈值筛选出满足条件的支持度较高的序列即可确定最终结果为 L^{(K)} ；
连续执行这两步，就可以得到所有的频繁项集：L(1),L(2),…,L(n)。
现在有很多提高Apriori算法效率的方法可用。例如基于散列技术、事务压缩、划分、抽样以及动态项集技术等方法。其中，“划分”的方法类似于分治法：将数据集划分为若干个部分，在第一个阶段生成各个子区域的局部频繁项集；在第二个阶段将这些局部频繁项集合并后生成全局候选；最后在整个数据集中扫描一遍以剔除不符合最小支持度条件的候选项。在第一个阶段中通过使用特定的数据结构来实现一次遍历获取所有局部频繁项集。每个子区域的划分均以能够放入内存为标准进行操作。
**不候选产生挖掘频繁项集 **
Apriori算法中的候选生成机制通过大幅缩减候选项集规模从而带来了良好的性能特点；然而该方法也存在一些明显问题例如当处理大数据量时候选项集可能会变得极为庞大（此时采用划分策略可以有效缓解这一问题）；此外还需要对数据库进行多次访问（这使得划分策略成为一个非常高效的解决方案）。为此 FP增长算法（Frequent Pattern Growth 简称 FP-Growth）应运而生其基本工作原理如下：通过分治策略将频繁项的相关信息压缩存储在一个频繁模式树中；随后将此树划分为多个条件数据库每个数据库对应一个频繁项或模式段；最后分别对各个条件数据库进行挖掘以获取完整的频繁模式集合
1.构造FP树和项头表 FP树包含了原始数据的关联关系和计数信息。
- 1.1 首先遍历一遍数据库，得到1项集的计数信息，并按减序排列成L 。
- 1.2 初始化一颗树T，根节点为NULL；
- 1.3 第二次遍历数据库，对其中的每一项，先按照L的顺序重新组织项里面的元素，得到E'。然后查找T，检查T是否已经有一条路径为项E'，若没有，则根据情况增加T的节点。并且将路径上各元素的计数加1；
- 1.4 对于每一项得到的叶节点，更新项头表：如果叶节点为新加入的，则添加指针到该节点对应元素的桶的末尾。
2.从FP树中提取后缀模式并构建其FP树 由FP树生成条件模式基并构造相应的前缀路径集合。
1.从L中的最后一个元素e出发将其视为后缀开始构建FP树。具体操作是：通过项头表指向找到T中的叶子节点位置然后向上回溯即可获得所有包含e的前缀路径及其计数信息这些路径共同构成了e所对应的条件模式基；
2.按照上述方法对每个条件模式分别进行处理从而生成多个条件FP树；
3.将所有条件FP树中的路径元素组合与其对应的后缀元素集合汇总即可得到完整的频繁模式集。
我对这个算法的理解有几点是：
- 数据库中的项目应当按照单目集合中各项目的计数从高到低进行排序，并以此为基础构建后续生成的具体路径（即FP树），从而确保整个构建过程具有极强的操作简便性；
- 基于第一步构建得到的FP树结构可以看出，在单目集合中每个项目e所对应的子集S（其中S中的所有项目均具有大于e的单目计数值）仅可能存在于其前缀路径集中；
- 依据第2点可知，在实际应用过程中选择从小到大遍历各个项目的原因主要有两个方面：其一是在计算包含较大计数值项目的频繁模式时，并无需考虑那些较小计数值的小于当前项目e的情况；其二是通过这种方式能够更加高效地定位出所有潜在的重要关联规则。
FP增长方法的不同形式能够有效地应用于大型数据库。
该递归方法能够实现这一目标。
如果有机会的话，打算尝试开发一个基于C++语言的版本，并认为这非常有趣。