读书笔记 -- 012_数据挖掘_频繁模式_关联性_相关性_2

**FP增长(Frequent Pattern Growth, FP-growth)算法：该算法能够识别频繁项集而无需生成候选项集。

正如在Apriori算法中看到的，Apriori算法的候选产生-检查方法显著压缩了候选项集的规模，并产生了很好的性能。然而，它可能仍然需要产生大量的候选项集。同时，Apriori算法可能需要重复地扫描整个数据库。

下面介绍一种称作FP-growth的算法。该算法采用完全不同的方法来发现频繁项集。该算法不同于Apriori算法的“产生-测试”泛型，而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。

1、FP树数据结构
FP树是一种对数据进行紧凑存储的技术手段，在处理事务记录时会按照预设规则将事务记录按照项属性进行分类排列，并将其映射至特定路径位置。由于不同事务可能存在共享项的情况，在构建过程中这些项的处理会产生一定的路径共用特性。具体而言，在构建过程中若该数据结构占用内存空间较小，则无需反复扫描位于磁盘存储的数据集即可完成频繁项集的提取任务；而当共享项的比例越高，则潜在压缩效率也会相应提升。

如上图所示显示了一个数据集，它包含10个事务和5个项。图中还绘出了读入前3个事务之后FP树的结构。树中每一个结点都包括一个项的标记和一个计数，计数显示映射到给定路径的事务的个数。初始，FP树仅包含一个根结点，用符号null标记。随后，用如下的方法扩种FP树：
(1.)扫描一次数据集，确定每个项 的支持度计数。丢弃非频繁项，将频繁项按照支持度的递减排序。对于上图中的数据集，a是最频繁的项，接下来依次是b, c, d和 e。
(2.)算法第二次扫描数据集，构建FP树。读入第一个事务{a, b}之后，创建标记为a 和b 的结点。然后形成null\toab路径，对该事务编码。该路径上的所有结点的频度计数为1。
(3.)读入第二个事务{b, c, d}之后，为项b, c和d创建新的结点集。然后连接结点nullbcd，形成一条代表该事务的路径。该路径上的所有结点的频度计数也等于1。尽管前两个事物具有一个共同项b，但是它们的路径不相交，因为这两个事务没有共同的前缀。
(4.)第三个事务{a, c, d, e}与第一个事务共享一个共同前缀项a，所以第三个事务的路径nullacde与第一个事务的路径nullab部分重叠。因为它们的路径重叠，所以结点a的频度计数增加为2，而新创建的结点a, c和e的频度计数等于1。
(5.)继续该过程，直到每个事务都映射到FP树的一条路径。读入所有的事务后形成的FP树如上图。

FP树还包含连接具有相同项的结点的一个指针列表。这些指针在图中被用作虚线表示，并且能够便于迅速获取树中的各项信息。

2、FP增长算法的频繁项集产生
FP增长采用自顶向下的方法构建树状数据结构，并基于此生成目标数据集合中的频繁项集序列。通过分析下图所示的数据结构，在初始阶段该过程会识别出所有候选节点中末尾节点的部分信息，并逐步扩展至其他相关分支节点直至完成整个数据序列的关键特征提取工作；这种操作模式与关注特定节点后续路径的方法具有相同的逻辑基础，并且能够有效地发现任意指定子序列所对应的高频事件集合；在这一过程中, 通过利用每个关键节点相关的指针连接关系, 可以快速定位到与其相关的数据链路; 在完成对所有关键节点及其后续分支链路的相关信息提取后, 系统将能够完整地还原出整个数据序列的基本组成特征并完成最终的目标识别任务

将由频繁项集产生的问题拆分为若干个子问题，并对每个子问题分别设计用于发现以e、d、c、b和a结尾的具体频繁项集。例如，在关注所有以e结尾的频繁项集时（或：当关注所有以e结尾的频繁项时），必须首先验证项集{e}本身是否为频繁项集（或：确定集合{e}是否属于高频集合）。为了实现这一目标（或：这一目标），必须首先检查集合{e}本身是否属于高频集合（或：判断集合{E}是否为高频集合）。如果确认该集合确实属于高频集合（或：确认数据集中包含 frequent 集合 {E}），则需进一步探索其延伸情况：即寻找包含de、ce以及ae结尾的新 frequent 项目组合（或：寻找在项目序列中延伸后仍能保持高频性的可能性）。依次地（或：逐一地），每一个可能扩展的方向都需要被考虑进去。通过整合这些子问题的结果（或：通过汇总各个相关子路径的结果），即可获得完整的关于所有以e结尾 frequent 项目组合的信息（或：即可汇总出完整的一系列具备 e 结尾的所有 frequent 项目组合）。这种分而治之的方法正是 FP 增长算法所采用的核心策略之一

如上图所示，在详细阐述如何解决各个子问题的过程中，请考虑收集所有以e结尾且具有较高频度的任务。
(1)第一步是收集包含e结点的所有路径；这些初始路径被称为前缀路径（prefix path），如图a所示；
(2)基于图a中的前缀路径，请将与结点e相关的计数总和计算出来得到e的支持度计数；假设最小支持度计数为2，则由于{e}的支持度为3因此它被视为一个频繁项集；
(3)由于{e}已经被确认为频繁项集，则必须解决其后续子问题：即发现以de、ce、be和ae结尾的所有频繁项集；为此必须先将前缀路径转换为条件FP树（conditional FP-tree） ；该结构与原始FP树类似但具有不同的构建方法：
(3.1)首先需要更新前缀路径上的计数值；因为某些计数值包含了那些不包含e的数据实例；例如图a中最右端的一条路径nullb:2c:2e:1包含了不包含e的数据实例{b,c}因此需要将该路径上的计数值调整为1以便准确反映包含{b,c,e}这一数据实例的数量变化；
(3.2)删除结点e以及相关的前缀路径信息这是因为已经更新过的计数值已经能够反映包含有结点e的数据实例特性；而后续针对de、ce、be和ae等后缀的问题则不再需要依赖于结点e的信息内容；
(3.3)在完成计数值更新之后某些节点可能不再满足高频条件因而被移除例如节点b只出现了一次其支持度仅等于1这表明只存在一个同时包含b和e的数据实例由于所有以be结尾的任务一定不是高频任务因此在后续分析中完全忽略节点b的影响；此时节点e所对应的条件FP树仅显示在节点b处该树结构发生了变化是因为支持度计数值已经被重新计算并且删除了不再满足高频要求的相关节点；
(4)接下来采用FP增长算法结合上述构造好的条件FP树来解决各个后续子问题：为了找到de结尾的所有高频任务需从节点e对应的条件FP树中收集d的所有前缀路径（如图c所示）然后将与结点d相关的计数值求和得到任务集合{d,e}的支持度值因为该值等于2所以该集合被视为高频集合接下来按照第三步所述的方法构建出de对应的条件FP树并进行相应支持度更新之后移除非高频项c之后得到如图d所示的新结构在此基础上提取出新的高频任务集合{a,d,e}并继续推进下一个子问题直到最终确定所有的目标任务集合。

该实例详细阐述了FP增长算法所采用的分治策略。在每一次递归过程中，在更新前缀路径中的支持度计数并剔除非频繁项之后会构建相应的条件FP树。由于子问题之间没有重叠，在此过程中不会出现重复的项集情况出现。此外，在与特定节点相关的支持度计数值下使得算法能够在生成相同的后续模式时计算其具体的支持度值。

3、模式评估方法

3.1强规则不一定是有趣的

3.2、从关联分析到相关分析
在第3.1节中我们了解到，在数据挖掘领域仅依赖支撑强度和可靠性作为衡量标准是无法有效消除那些没有实际意义的关联规则。针对这一问题可以通过引入相关程度指标来扩展原有的支撑强度-可靠性模型。这导致如下形式的相关性规则

具体而言，在计算相关规则时不仅会考虑基于支持度和支持率的评估标准（即SBC值），而且还会基于两个项集A与B间的关联程度进行分析（如计算Jaccard系数）。实际上，在数据挖掘领域中存在多种不同的关联性指标可供选择。

提升度(lift)： 它是一种衡量关联程度的简单指标。具体定义如下：当且仅当P(A\cup B)=P(A)P(B)时，我们称项集A与B是相互独立的；反之，则这两件事之间存在依存关系且相互关联。这一概念易于扩展到涉及更多项目集的情况。A和B之间的提升度可通过以下公式计算得到：

当上式的计算结果低于阈值时（替代了"小于1"），变量A与变量B之间的关系被定义为负关联（替代了"负相关"）。这预示着变量A的存在可能会阻止变量B的发生（替代了"可能导致"）。当计算结果超过阈值时（替代了"大于1"），变量A与变量B被判定为正相关（替代了"正相关"）。每个变量A的存在都会预示着另一个变量B也会存在（替代了"意味着一个出现可能导致另一个不出现"）。该指标用于衡量单个事件发生对另一事件发生程度的影响（增加了具体性）。

采用\chi^2检验法：]数据集成–检验中有详细的描述。用于计算该统计量，则需考虑相关表格中的(A,B)位置，并将观测与期望之差平方后加总起来。

注：这里就相依表做一个解释

每个f_{ij}都是一个频度计数。举个例子来说，在某个事务中同时出现A和B的情况有f_{11}次，在另一个事务中包含B但不包含A的情况有f_{01}次。对于行来说，f_{+j}是衡量A支持程度的一个指标；同样地，在列上统计得到的是B的支持度数值。