目录关联分析：基本概念和算法21、基本概念22、频繁项集的产生4（1）格结构4（2）先验原理与反单调性4（3）apriori算法的频繁项
集产生5（4）频繁项集产生与剪枝8（5）支持度计数9（6）计算复杂度11关联分析：基本概念和算法http://archive.ic
s.uci.edu/ml/datasets.htmlUCI机器学习库基本概念支持度：通常用来删去那些无意义的规则。置信度：估计Y
在给定X下的条件概率。支持度计数：支持度是一个概率，而支持度计数则是该概率上的分子。由关联规则作出的推论并不必然蕴涵因果关系，它只
是、表示规则前件和后件中的项明显地同时出现。（因果关系需要关于数据中原因和结果属性的知识。）关联规则：形如X->Yd的蕴涵表达式
，其中X和Y是不相交的项集。从包含d个项的数据集提取的关联规则的总数为：（这个不是频繁项集的个数而是关联规则的个数）例如购物蓝数据
集包含6个项（每一列表示一个项，每一行表示一个事务；0表示在该次事务中没出现，1表示在该次事务中出现了。）则可能的规则有由此看出
若通过这样的方法来计算支持度和置信度，是十分麻烦的，这是由于数据量大，因此我们一般采用“剪植”的方法，通过设定最小置信度和最小支持
度，对不满足这两个指标要求的，先进行剔除，以便计算不必要的数据。一个包含k个项的数据集可能产生个候选项集。一个包含k个项的数据集可
能产生个关联规则。大多数关联规则挖掘算法通常采用的一种策略是将关联规则挖掘任务分解为如下两个主要的子任务：频繁项集产生：其目标是
发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（这个不是之前所说的数据集）规则的产生：其目标是从上一步发现的频繁项集中提取
所有高置信度的规则，这些规则称作强规则。注：频繁项集产生的开销远大于规则的产生。概念区分数据集：项集：｛面包、尿布、啤酒、
鸡蛋｝项：面包、牛奶、尿布、啤酒、鸡蛋、可乐都是项频繁项集：满足最小支持度的项集。｛面包、尿布、啤酒、鸡蛋｝，｛面包、尿布、啤酒｝
，｛面包、鸡蛋｝其中每一个都是项集，由于每一个都满足最小支持度，因此每一个项集都可以称之为频繁项集。产生频繁项集的过程就是获取上
面的每一个频繁项集。关联规则：｛面包、尿布｝=>{啤酒}、{啤酒}=>｛面包、尿布｝是两个不同的关联规则。事务：真正出现过
的项集（为于数据集中）。候选项集：所有可能出现的项集（项的所有组合）。图6-1就是所有的候选项集事务与候选项集进行匹配，若候选项集
包含事务，则该候选项集的支持度增加1。频繁项集的产生下面所描述的都是Apriori算法所涉及的Apriori算法的过程就是拿候选项
集去参考事务集进而得出频繁项集。（1）格结构格结构：常常被用来枚举所有可能的项集（候选项集）一个包含k个项的数据集可能产生个候选项
集。（2）先验原理与反单调性先验原理：如果一个项集是频繁的，则它的所有子集一定也是频繁的。（图6-3）如果一个项集是非频繁的，则
它的所有超集一定也是非频繁的。（图6-4）反单调性：一个项集的支持度，永远小于该项集的子项集的支持度。单调性：一个项集的支持度，永
远小于该项集的超集的支持度。一但发现{a,b}是非频繁项集，则整个包含｛a,b｝的超级可以被立即剪枝。剪枝原理就是基于反单调性
的。（3）apriori算法的频繁项集产生1、核心原理基于支持度的剪枝：这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪
枝。（为什么能够根据支持度进行剪枝，这个就是根据先验原理而来的。我们首先得到候选1-项集，从中删除支持度小于最小支持度的项，这样做
你可能会想，在候选1-项集满足了删除的条件，但在候选2-项集会满足删除条件吗？事实上跟据先验原理，告知我们一个项集的支持度是比它超
集大的，既然子项集都不符合条件，那么其超集就更不符合条件了。因此在子集阶段就可以进行删除。）2、Apriori频繁项集产生的事例一
定要理解Apriori产生频繁项集的过程和几个关键的名词。关键的名词：候选1-项集：表示的是每个候选项集中只有一个项。是格结构的
一个层级候选2-项集：表示的是每个候选项集中只有两个项。是格结构的一个层级候选3-项集：表示的是每个候选项集中只有三个项。是格
结构的一个层级候选项集的产生是根据格结构来的，也就是按层次（项的个数）进行的任意组合。候选项集并不一定在数据集中出现过（支持度为0
）。即使出现过也不一定是频繁项集（支持度比对得出的。数据表中的事务是真实存在的。候选项集只是列出了所有的可能。每产生一个候选项集就会将其与原数据集进行一次比对，即对原数据
集进行一次扫描（由此也可以看出Apriori算法的效率低，产生大量的磁盘IO）候选项集的项候选项集的项是通过上一个候选项集得出的，
上一个候选项集先进行剪枝，然后在根据格结构产生下一个候选项集。（4）候选项集的分类候选项集是按照各结构进行分类，并产生的，也就是按
照集合中项的个数进行分类的，如候选1-项集、候选2-项集、候选3-项集（5）Apriori扫描数据集的次数在每产生一次候选项集时，
就会对原数据集进行一次扫描，其目的是要获取该次候选项集的支持度。apriori产生频繁项集的具体流程（设最小支持度为3）根据数据集
获取项，并根据格结构生成候选1-项集（格结构的第一层）数据集该数据还可以写成：数据集面包牛奶尿布啤酒鸡蛋可乐4
44312候选1-项集由于设置最小支持度为3，因此鸡蛋、可以这两个1-项集属于非频繁项集，即可以省略。根据剪枝后的候选
1-项集以及各结构的第二层，构建候选2-项集如下所示候选2-项集同样我们可以将不满足最小支持度的项集删去。注意｛啤酒、面包｝其支持
度为2，这是因为啤酒和面包一起出现在事务中的情况共有两次，对应在数据中为TID=2、4。我们需要正确的理解数据集中的每行事务。每行
事务可以拆分成很多小的事务。如：TID=2的那行事务，就可以拆成｛面包、尿布｝、｛尿布、鸡蛋｝等事务。当然我们不要弄混，这里说的都
是事务，而不是项集。我们根据剪枝原理可以删除不满足条件的项集，但你不能删除事务啊。这就是因为一个大的事务可以拆成小的事务来对待。根
据剪枝后的候选2-项集以及各结构的第二层，构建候选3-项集如下所示由于在也没有新的候选项集的产生，因此此算法结束。从各个候选项集中
获取频繁项集｛面包｝、｛啤酒｝、｛尿布｝、｛牛奶｝、｛尿布、啤酒｝、｛面包、尿布｝、｛面包、牛奶｝、｛尿布、牛奶｝、｛面包、尿布
、牛奶｝（4）频繁项集产生与剪枝除了Apriori算法产生频繁项集外，还有其他几种方法、这些方法都应该遵循下列3个要求。1、频繁项
集产生的原则：避免产生太多不必要的候选：一个候选项集是不必要的。同时应该排除非频繁项集，以便减少支持度的计算难度。保证频繁项集的完
整性：这就要求候选项集必须完全包含频繁项集。不产生重复的候选项集：如产生｛a,b,c,d｝可以通过多种方式产生，如合并｛a,b,c
｝和｛d｝,合并｛b,d｝和｛a,c｝候选项集的重复产生将会导致计算的浪费。2、几种频繁项集的产生方式蛮力方法：相对于Aprior
i算法来说，该方法并没有将非频繁项集剪枝，而是将全部的候选项集（1-，2-，3-，等）生成完毕以后，才进行剪枝。蛮力方法虽然候选
产生很简单，但后期的剪枝很困难。2）方法用F1频繁项集（不是候选集）来扩充Fk-1频繁项集进而得到Fk候选项集。通过这种方式产生的
候选项集往往存在重复，因此我们可以使用字典的方式进行合并。要求每个频繁（k-1）-项集X只用字典顺序比X中所有的项都大的频繁项进行
扩展。例如：牛奶的字典顺序比面包、尿布都大，因此可以使用｛牛奶｝去扩充｛面包、尿布｝最终等到｛牛奶、面包、尿布｝。事实上虽然候选
3-项集是通过两个频繁项集合并得到的，但候选3-项集仍然存在着非频繁项集，这是因为虽然说子集非频繁，则超级一定非频繁，但并没有说子
集频繁则超级一定频繁。3）要求进行合并的两个频繁项集的前k-2项都是相同的，而k-1项是不相同的，并且k-2项必须是频繁项集。这样
合并后并经过剪枝处理得到的就是频繁k-项。（5）支持度计数支持度的计数有两种方式：方法一：直接拿每个事务与每个候选项集进行一一比对
。进而得出各个候选项集的支持度。缺点是：计算昂贵，尤其当事务和候选项集数目都很大时。方法二：枚举出各个事务所包含的项集，并且利用
他们更新候选项集的支持度。注：方法一与方法二其实与我们之前所说的关于spark中的join算子是否要先进行分区操作的效果是一样的。
对于方法一：相当于没有进行分区而是直接进入shuffle阶段。这样就需要进行挨个匹配。对于方法二：则相当于进行了分区，虽然也是进行
匹配才能得出支持度，但这里的匹配是直接匹配，而不是挨个匹配。这是因为你已经枚举了事务的各个项集，那么当然就可以从字面上直接与候选项
集进行匹配。举各个事务所包含的项集的方法：假定每个项集中的项都以递增的字典序排序，则项集可以这样枚举：先指定最小项，其后跟随较大
的项。如上所示，由于我们要从事务中得到包含3个项的项集，因此在｛1，2，3，4，5，6｝中较小的项为1，2，3；较大的项为5，6。
所以之后我们将分别以较小项开头作为前缀，并让较大项跟随前缀。第一层的前缀结构描述了指定包含在事务t中的3-项集的第一项的方法。（如
1｛2356｝表示这样的3-项集，它以1开始）第二层的前缀结构表示选择第二项的方法。第三层的前缀结构显示了事务t包含的所有的3-项
集。使用Hash树进行支持度的计数在Apriori算法中，候选项集划分为不同的桶，并存放在Hash树中。在支持度计数期间，包含
在事务中的项集也散列到相应的桶中。这种方法不是将事务中的每个项集与所有的候选项集进行比较，而是将它与同一桶内候选项集进行匹配。具体
过程：首先根据所需要的项数，并结合Hash算法，将各个候选项集存储到Hash树中的叶子节点上。再将各个事务所包含的项集根据之前所描
述的事务的层级，以及事务项集各个层级的前缀，将事务项集散列到各个根节点上。每一层级散列一次，直到达到hash树的叶子节点上。存放在
被访问的叶节点中的候选项集与事务进行比较，如果候选项集是该事务的子集，则增加它的支持度计数。补充说明上述hash树中事务的散列过程
：（6）计算复杂度Apriori算法的计算复杂度受如下因素影响：支持度的阈值：阈值越大，复杂度就会越低，频繁项集的最大长度将减小。
项数：随着项数的增加，需要更多的空间来存储项的支持计数。同时项数越大，则候选项集越多。计算复杂度增大。（项数大并不一定事务数就大，
但候选项集肯定是增大的。）事务数：事务数越大，由于Apriori算法反复扫描数据集，因此它的运行时间就会增加。事务的平均宽度：频繁
项集的最大长度随事务平均宽度增加而增加。因而在候选项产生和支持度计数时必须考察更多候选项集。规则的产生关联规则产生于频繁项集，也就
是说频繁项集是关联规则产生的基础。如下：一个频繁项集｛1，2，3｝则由该频繁项集产生的关联规则写成X->Y-X的形式。｛1，2｝-
>{3}{1,3}->{2},{2,3}->{1},{1}->{2,3},{2}->{1,3},{3}->{1,2}；这些关
联规则目前只能称之为候选关联规则，因为最后的关联规则得需要满足最小执行度。这些关联规则都是产生于同一个频繁项集的，因此他们的支持度
与｛1，2，3｝是一样的。由于关联规则是来源于频繁项集的，因此它的阈值一定满足条件，因此在计算其支持度的时候就不用在对数据集进行扫
描了。基于置信度的剪枝对于｛1，2｝->{1,2,3}其置信度为定理：如果规则X->Y-X不满足置信度阈值，则形如X
`->Y-X`的规则一定也不满足置信度阈值，其中X`是X的子集。（其中表示的是概率）证明：X->Y-X的置信度为，X`->Y-X`
的置信度为由于X`是X的子集，因此。因此上述的定理成立。说白了就是若｛1，2｝->{1,2,3}不满足置信度的阈值，那么｛1｝->
{1,2,3}一定不满足置信度的阈值。apriori算法中规则的产生关联规则的产生与频繁项集产生一样，都是根据格结构（构成候选）
，并参照标准进行逐级剪枝。频繁项集的产生是根据最小支持度进行剪枝产生的。而关联规则是根据最小置信度剪枝的。注：（1）事实上候选规则
格结构和候选项集格结构的每个层级的产生都是通过上一级的合并产生的。只是合并的规则不同。候选规则格结构的产生步骤：选取规则后件只有一
项的并且满足置信度的规则最为候选规则格结构的第一层。将候选规则格结构的第一层进行合并，得到格结构的第二层，如上图所示。将候选规则格
结构的第二层进行合并，得到格结构的第三层，直至前件只有一项假设规则｛bcd｝->{a}具有低置信度，则可以丢弃后件包含a的所有规
则，如上图所示。（剪枝）总结：候选项集的剪枝原理：若子项集是非频繁项集，则其超项集也一定是非频繁项集（先验原理）和扫描数据集。（
通过扫描数据集我们才能判定出支持度，进而直到谁的支持度小，进而剪枝）候选规则的剪枝原理：假设规则｛bcd｝->{a}具有低置信度
，则可以丢弃后件包含a的所有规则。候选项集格结构的合并原理：格的每一层的各个项集进行合并得到下一层，合并后的每个项集中所包含项的个
数等于格结构的层数。候选规则格结构的合并原理：格的每一层的各个规则的前件和后件对应合并。得到下一层。合并后的每个规则得后件所包
含的项数等于其所在的格结构的层数。注：在关联规则的产生过程中，我们并不需要通过扫描数据集得出置信度了，这是因为根据置信度的公式，我
们完全可以根据之前在求频繁项集的时候产生各项集的支持度来计算本处得置信度。频繁项集的紧凑表示由于频繁项集数量十分庞大，因此从中找出
据有代表性的、最小的、能够推出其他的频繁项集的频繁项集十分重要。极大频繁项集概念：极大频繁项集的超级都不是频繁的。由定义可知上图中
{a,d},{ace},{bcde}都是极大频繁项集。极大频繁项集的提出使得在格结构中产生了一条分界线，该分界限的上面是频繁项集，
而该分界线下面是非频繁项集。由于有些频繁项集可能是指数倍，因此通过某种算法计算出极大频繁项集，就可以知道该频繁项集的各个子集（根据
反单调性，超集的支持度小于子集的支持度）。进而不用全部枚举出来。极大频繁项集的缺点是没有提供其各个子项的支持度。闭频繁项集定义：闭
频繁项集，提供了频繁项集的一种最小表示。闭频繁项集的支持度与其直接超级的支持度不同，这样频繁项集称为闭频繁项集。结构图中的每个节点
上方所标注的是事务的TID，从所标注的TID的个就可以直接看出该节点所具有的支持度计数。如项集｛a｝其支持度计数为3。有些算法可以
直接从格结构中获取闭频繁项集。功能：1）可以使用闭频繁项集的定义来推出非闭频繁项集的支持度。从闭频繁项集的定义可以反推出，非闭频繁
项集的支持度一定与其某一个直接超项集的支持度相同。因为若都不同的话，则该频繁项集就会是闭频繁项集。同时结合反单调性原理可知子项集的
支持度永远大于其超级的支持度，这说明该子项集的支持度相对于其超项集的支持度一定是最大的。那么我们只需要在其直接超项集中寻找一个支持
度最大的超项集，该超项集的支持度一定与该子项集的支持度相同。2）通过闭频繁项集产生的关联规则是不存在冗余的。注：极大频繁项集是闭频
繁项集的子集。产生频繁项集的其他方法项集格的遍历（遍历的是候选项集）方法一：特殊、一般由一般到特殊（apriori）：适合用于频繁
项集的最大长度不长的情况由特殊到一般：适合用于频繁项集稠密的情况“一般到特殊”与“特殊到一般”相结合：可能会占用大量的存储空间，但
有助于快速确定频繁项集的边界。方法二：等价类该种遍历格结构的方法是先将格划分成多个不相交的结点组（或等价类）。频繁项集产生算法依次
在每个等价类内搜素频繁项集。在划分等价类的时候有两种方式可供选择。前缀树后缀树我们以前缀树为例来说明是如何产生等价类，即如何产生不
相交的节点组的。首先所谓等价类（不相交的节点组）指的是：相比于Apriori即从一般到特殊的格结构，来看等价类的格结构之间是不相交
的。算法首先搜索以前缀a开始的频繁项集，然后是以前缀b等开始的频繁项集，然后是c。方法三：宽度优先和深度优先宽度优先：指的是按照结
构格，一行一行的产生频繁项集，如先产生频繁1-项集，再产生频繁2-项集。深度优先：思想于等价类相同，就是先沿着一个分支走，直到遇见
该分支结点为非频繁项集等情况才结束对该分支的遍历。注：图6-21很好的反映了节点组是否由交叉的情况事务数据集表示事务的数据集一般有
两种表示方法，即水平数据布局（apriori算法使用）、垂直数据布局。不同的方法，所产生的I/O是不同的。其中垂直数据布局种的数字
是TID，其候选项集的支持度需要通过交集来得到。FP增长算法FP树的表示方法Fp树中的各个项都是事务集（1）先对数据集中的事务进行
处理删除：根据先验原理将第一次扫描数据集后不满足最小支持度的1-项集删除。排序：同时将删除后的事务集进行由大到小的排序。（注Apr
iori删除的是候选项集，而FP删除的是事务项集）（2）对数据集进行二次扫描，构建FP树将每个事务映射到FP树中。映射原则如下：
注：1）每一条路径代表一个事务。2）FP树的大小与我们在进行第一次扫描数据集后进行的事务排序（升序、降序）有关。FP树的最优情况是
仅仅只有一条路径，即所有事务都是重合的。Fp树最差的情况是每个事务都有各自单独的路径，即没有重合的部分。这种情况者使得FP树所占
用的存储空间比原数据集的大，这是因为在Fp树中还涉及到指针（图中的箭头）和计数。这里所说的前缀就是当事务进行排序之后，第一项就是前
缀。FP增长算法的频繁项集产生FP增长算法的特点是直接从事务项集中获取频繁项集，而不用枚举所有的候选项集，在扫描比对支持度了。FP
增长（FP-growth）是一种以自底向上方式探索树，并由FP树产生频繁项集的算法。FP增长算法的频繁项集的产生过程关键词：前缀
路径、条件树以构建以e结尾的频繁项集为例：构建事务表的FP树分离出包含e的初始化路径（以e结尾的前缀路径）（首先要看e是否是频繁项
集）根据e的前缀路径获取e的FP条件树（4）跟据e的条件FP树获取以de结尾的前缀路径（首先要看de是否是频繁项即项集）（5）根据
以de结尾的前缀路径获取以de结尾的条件FP树（6）根据de结尾的FP条件树可以获取以de分支结尾的频繁项集｛a,d,e｝跟据e的
条件FP树获取以ce结尾的前缀路径（首先要看ce是否是频繁项即项集）根据以ce结尾的前缀路径获取对应的FP条件树（9）根据ce结尾
的FP条件树可以获取以ce分支结尾的频繁项集{c,e}（10）跟据e的条件FP树获取以ae结尾的前缀路径（首先要看ae是否是频繁
项即项集）（11）根据以ae结尾的前缀路径获取对应的FP条件树（12）根据ae结尾的FP条件树可以获取以ae分支结尾的频繁项集{
a,e}最终我们获得包含e路径分支的全部频繁项集结合上面的过程，同理可以获得包含a,包含b等的路径分支的频繁项集。注：FP算法是通
过事务数据集来获取频繁项集的，而不在使用候选项集。因此就应该想到我们在处理事务数据集的时候，应该像处理候选项集那样，将事务数据集按
照一定的规律进行枚举，比如上面所说的先以e为底，然后又分别以de、ce、be为底。事实上这在一定程度上就是在对事务数据集进行枚举。FP算法采用的是分而治之的思想，这个体现在我们从FP树中获取前缀路径的过程。即将一个大问题划分为多个独立子问题，而划分的依据就是以某个项为结尾的前缀路径。为什么要构建条件FP树，以及如何构建条件FP树通过观察前缀路径和条件FP树我们发现两者是不同的，事实上我们从FP树中分离出来的前缀路径并不是一个独立的关于以某一项结尾的路径，前缀路径上面所标识的支持计数仍然是原FP树的支持计数，它无法对仅仅包含某一项的事务进行描述。因此我们需要再构建一个条件FP树，使之能够完全独立的描述包含该项的事务。如何构建条件FP树呢？条件FP树是利用下面的方法对前缀路劲进行修改而得来的。构建条件FP树的方法：重写前缀路径中的各个项的支持计数根据重写的支持对计数删除不满足最小支持计数的项以哪个项或项的组合结尾，就从前缀路径中删除哪个项或项的组合。说明：1）重写支持计数是因为，当前的支持计数是反映整个候选项集的，而我们现在需要的是仅仅描述以某项结尾的这中独立路径的支持计数2）之所以删除以某项结尾的前缀路基的那个项，是因为在该路径下，都是以这个项结尾，因此该项不回再影响该路径了。 |
|
