[科普中国]-有限扫描算法

在频繁项集发现算法中，经常需要对每个不同规模的项集采用一遍扫描过程。如果内存太小以致无法容纳数据和提供对某规模频繁项集进行计数所需的空间，要计算所有频繁项集似乎没有办法可以避免k遍扫描。有限扫描算法是指能够在两遍之内发现全部或大部分频繁项集的算法。

简介在数据挖掘中，有限扫描算法简单来说对大规模项集最多进行两次扫描就可以发现大部分频繁项集的算法。常见的有限扫描算法有抽样方法，即只利用数据样本而不是全部数据集进行计算，以及SON算法和Toivonen算法，这两种算法对项集只需扫描两遍，可以得到一个精确解。

算法类型SON算法SON算法是Savasere等于1995 年提出的一种基于Apriori 算法的分区算法 ( partition algorithm) 。SON 算法的思想源于对于给定的项集只需要对整个事务数据集扫描一次即可得到其支持度，进而判断其是否为频繁项集。所以只需要找出一个项集的集合，使得这个集合包含事务数据集上所有的频繁项集。SON 算法将事务数据集划分为多个互不重叠的分区，然后分别在每个分区上计算出本分区的频繁项集，最后将各个分区计算得到的结果汇总成一个项集的集合，该集合将包含事务数据集上所有的频繁项集。SON 算法的正确性基于如果一个项集是全局频繁的，那么该项集至少在一个分区中是局部频繁的。

从以上分析容易看出，SON 算法对事务数据集进行了两次扫描。第一次扫描，将生成一个项集的集合，该集合包含所有的频繁项集； 第二次扫描，将对上一次扫描得到的每个项集进行计数，得到其支持度，根据最小支持度获得最终的频繁项集。算法的执行分为两个阶段。在阶段一中，该算法将整个事务数据集逻辑上划分为互不重叠的分区，每个分区互相独立，分别为每个分区单独的计算出本分区上的局部频繁项集。最后，把所有分区上计算得到的局部频繁项集汇总起来得到一个全局的候选项集。在阶段二中，根据上一阶段得到的候选项集，计算每个候选项集在整个事务数据集上的支持度，并以此判断是否满足最小支持度，从而得到最终的结果1。

Toivonen算法Toivonen算法首先在抽样数据集上发现频繁项集，但是采用的支持度阈值较低以保证在整个数据及上的频繁项集的丢失几率较低。下一步是检查购物篮整个文件，此时不仅要对所有样本数据集上的频繁项集计数，而且要对反例边界（那些自己还没发现频繁但是其所有直接子集都频繁的项集）上的项集计数。如果反例边界上的人以及和都在整个数据集上不频繁，那么结果是确切的。但是如果反例边界上的一个集合被发现是频繁的，那么需要在一个新的样本数据集上重复整个处理过程。

接下来的问题是发现流中的频繁项集，流和数据文件的区别在于，流元素只有到达后才可用，并且通常情况下到达速率很高以至于无法存储整个流来支持简单查询，另外，一个流会随着时间推移而不断变化，当前的频繁项也许过段时间就不再频繁。

而且流不会结束，只要某个项集反复在流中出现，它最终都会超过支持度阈值。为了解决这个问题，我们将支持度阈值看成是项集出现的购物篮所占的比例。

发现流的频繁项集需要对流进行抽样，我们可以先收集一定量的购物篮并将它存为一个文件，在该文件上执行频繁项集算法，然后这同时可以收集另外一个文件，当第一次迭代完成且收集到的新购物篮流数据数目足够时开始运行第二次迭代。定期从流中收集新的数据进行迭代，新的迭代进行，如果任一项集的购物篮出现的比例显著低于比例阈值，则该项集可以从所有的频繁项集集合中去掉，频繁项集集合包含没有被删除的项集和新文件中发现的频繁项集。

抽样方法在统计学中，抽样（Sampling）是一种推论统计方法，它是指从目标总体（Population，或称为母体）中抽取一部分个体作为样本（Sample），通过观察样本的某一或某些属性，依据所获得的数据对总体的数量特征得出具有一定可靠性的估计判断，从而达到对总体的认识。抽样过程主要包括以下几个阶段：定义总体（母体）、确定抽样框、确定抽样方法、决定样本量、实施抽样计划、抽样与数据收集以及回顾抽样过程。

目标是所要研究的对象的全体。例如，制造商检查某个批次的产品质量是否合格，目标总体就是这一批次的产品。抽样总体是用于从中抽取样本的总体。按理，抽样总体应该与目标总体一致，但实践中时常发生不一致的情况。例如，科学家通过小白鼠试验来检测药物用于人类总体的效果。

抽样框，在抽样之前，总体应划分成抽样单位，抽样单位互不重叠且能合成总体，总体中的每个个体只属于一个单位。抽样框是一份包含所有抽样单元的名单。

简单随机抽样（simple random sampling），也叫纯随机抽样。从总体N个单位中随机地抽取n个单位作为样本，使得每一个容量为样本都有相同的概率被抽中。特点是：每个样本单位被抽中的概率相等，样本的每个单位完全独立，彼此间无一定的关联性和排斥性。简单随机抽样是其它各种抽样形式的基础。通常只是在总体单位之间差异程度较小和数目较少时，才采用这种方法。

系统抽样（systematic sampling），也称等距抽样。将总体中的所有单位按一定顺序排列，在规定的范围内随机地抽取一个单位作为初始单位，然后按事先规定好的规则确定其他样本单位。先从数字1到k之间随机抽取一个数字r作为初始单位，以后依次取r+k、r+2k……等单位。这种方法操作简便，可提高估计的精度。

分层抽样（stratified sampling）。将抽样单位按某种特征或某种规则划分为不同的层，然后从不同的层中独立、随机地抽取样本。从而保证样本的结构与总体的结构比较相近，从而提高估计的精度。

整群抽样（cluster sampling）。将总体中若干个单位合并为组，抽样时直接抽取群，然后对中选群中的所有单位全部实施调查。抽样时只需群的抽样框，可简化工作量，缺点是估计的精度较差。

频繁项集项集：最基本的模式是项集，它是指若干个项的集合。频繁模式是指数据集中频繁出现的项集、序列或子结构。频繁项集是指支持度大于等于最小支持度(min_sup)的集合。其中支持度是指某个集合在所有事务中出现的频率。频繁项集的经典应用是购物篮模型。

频繁项集挖掘是数据挖掘研究课题中一个很重要的研究基础，它可以告诉我们在数据集中经常一起出现的变量，为可能的决策提供一些支持。频繁项集挖掘是关联规则、相关性分析、因果关系、序列项集、局部周期性、情节片段等许多重要数据挖掘任务的基础。因此，频繁项集有着很广泛的应用，例如：购物蓝数据分析、网页预取、交叉购物、个性化网站、网络入侵检测等。

对频繁项集挖掘算法进行研究的方向大概可归纳为以下四个方面：一、在遍历方向上采取自底向上、自顶向下以及混合遍历的方式；二、在搜索策略上采取深度优和先宽度优先策略；三、在项集的产生上着眼于是否会产生候选项集；四、在数据库的布局上，从垂直和水平两个方向上考虑数据库的布局。对于不同的遍历方式，数据库的搜索策略和布局方式将会产生不同的方法，研究表明，没有什么挖掘算法能同时对所有的定义域和数据类型都优于其他的挖掘算法，也就是说，对于每一种相对较为优秀的算法，它都有它具体的适用场景和环境。所以，应该了解不同挖掘算法的不同特性和适用场景，掌握不同算法的适用环境和条件，这样才可以使研究者清楚算法的改进点，明白自己的研究方向，从而使用户更加方便地把算法应用到实际的生产活动中。

随着大数据时代的到来，传统的算法，比如 Apriori 算法、FP-growth 算法等，都无法处理这些处理大量的数据，主要原因有：一、时间消耗太大。面对大量数据，即使是比 Apriori快一个数量级的 FP-growth 算法，也无法在较短的时间内完成挖掘任务；二、内存无法满足要求。由于 Apriori 算法（包括类 Apriori算法）需要产生大量的候选项集，所以在处理大量数据的时候，就会由于内存消耗殆尽而无法使算法继续进行下去，即使是不需要生成候选项集的 FP-growth 算法，也会因为 FP-tree 太大无法放入内存，而使得算法无法运行。面对这样的问题，众多的研究学者开始着眼研究基于多处理器系统的并行频繁项集挖掘算法，以及基于 Hadoop 等分布式集群的分布式频繁项集挖掘算法。比如 Agrawal 等人 CD算法、DD 算法和 Ca D 算法，以及 Zaiane 等人的 MLFPT算法和 Li 等人的 PFP 算法等等，都是一些很优秀的并行或分布式频繁项集挖掘算法。频繁项集挖掘是数据挖掘研究领域中的一个重要课题，它是关联规则、因果关系、相关性分析、情节片段、序列项集、局部周期性等许多数据挖掘任务的基础。所以，频繁项集有着广泛的实际应用，例如：购物蓝数据分析、网页预取、交叉购物、个性化网站以及网络入侵检测等。

本词条内容贡献者为:

方正 - 副教授 - 江南大学