Sampling算法

1996 年，Toivonen 在文章《Sampling Large Databases for Association Rules》中提出了基于抽样的频繁项集挖掘算法——Sampling算法。他希望利用抽样方式，从原数据集中抽取适量的样本，以便将样本直接放入内存中，接着再对样本进行频繁项集挖掘，以此减少挖掘时间。因为挖掘样本变小了，所以能够比较快速地得到频繁项集。

定义频繁项集的挖掘工作需要花费大量的时间，主要是因为数据库中的数据量非常庞大，加上需要多次扫描数据库（尤其是 Apriori 及其改进算法），所以挖掘工作需要花费大量的时间。如果能有效地减少数据量，这样就能提高挖掘的效率，基于这样的考虑。Toivonen提出Sampling算法。Sampling算法属于一种单机挖掘算法，对机器性能要求较低，采用抽样方式从数据集中抽取一定数据的样本，由于样本数据较小，能较快得到频繁项集。但是，由于采用抽样技术，这必然会产生抽样误差，Toivonen也因此建议适量降低最小支持度以避免遗漏频繁项集。Toivonen 提出的 Sampling 算法利用随机抽样进行样本抽取，由于样本数据量较小，所以挖掘所需的时间也就较短，提高了效率，因此它具有简单高效的优点。但是，也是因为采用了随机抽样技术，这必然会结果带来误差，如果数据扭曲严重的话，会使得样本不具有代表性，从而使挖掘结果与实际结果相差很大1。

频繁项集挖掘频繁项集挖掘是数据挖掘研究课题中一个很重要的研究基础，它可以告诉我们在数据集中经常一起出现的变量，为可能的决策提供一些支持。频繁项集挖掘是关联规则、相关性分析、因果关系、序列项集、局部周期性、情节片段等许多重要数据挖掘任务的基础。因此，频繁项集有着很广泛的应用，例如：购物蓝数据分析、网页预取、交叉购物、个性化网站、网络入侵检测等。，对频繁项集挖掘算法进行研究的方向大概可归纳为以下四个方面：一、在遍历方向上采取自底向上、自顶向下以及混合遍历的方式；二、在搜索策略上采取深度优和先宽度优先策略；三、在项集的产生上着眼于是否会产生候选项集；四、在数据库的布局上，从垂直和水平两个方向上考虑数据库的布局。对于不同的遍历方式，数据库的搜索策略和布局方式将会产生不同的方法，研究表明，没有什么挖掘算法能同时对所有的定义域和数据类型都优于其他的挖掘算法，也就是说，对于每一种相对较为优秀的算法，它都有它具体的适用场景和环境。

抽样抽样就是从研究总体中选取一部分代表性样本的方法。例如我们要研究某城市居民的生活方式问题，那么整个城市居民都是我们的研究对象。但限于研究条件等原因，我们难以对每一个居民进行调查研究，而只能采用一定的方法选取其中的部分居民作为调查研究的对象，这种选择调查研究对象的过程就是抽样。采用抽样法进行的调查就称为抽样调查。抽样调查是最常用的调查研究方法之一，它已被广泛应用到社会调查、市场调查和舆论调查等多个领域。

抽样对调查研究来说至关重要。社会科学研究的对象通常是非常复杂的，涉及到社会生活的方方面面，既包括个体行动者，也包括群体甚至整个社区或社会。但在大多数情况下，我们难以对全部的对象做研究，而只能研究其中的一部分。对这部分研究对象的选择就要依靠抽样来完成，如此可以节省研究的成本和时间。但我们的研究又不是停留在所选取的样本本身，而是通过对有代表性的样本的分析来研究总体。故抽样的目的，就是从研究对象总体中抽选一部分作为代表进行调查分析，并根据这一部分样本去推论总体情况。

根据概率论原理常用的抽样形式主要分为随机抽样和非随机抽样两大类。二者的区别在于：前者按照随机原则来抽取样本，而后者不按随机原则抽取样本。

随机抽样

随机抽样又称概率抽样，是指严格按照随机原则来抽取样本，要求总体中每个单位都有被抽取的同等机会。由随机抽样所抽取的样本称为随机样本，这类样本具有较高的代表性。随机抽样法又分为下列五种不同的抽样方法：

简单随机抽样，也称纯随机抽样，是指按照随机原则从总体单位中直接抽取若干单位组成样本。它是最基本的概率抽样形式，也是其他几种随机抽样方法的基础。

等距随机抽样也称机械随机抽样或系统随机抽样，是指按照一定的间隔，从根据一定的顺序排列起来的总体单位中抽取样本的一种方法。具体做法是：首先将总体各单位按照一定的顺序排列起来，编上序号；然后用总体单位数除以样本单位数得出抽样间隔；最后采取简单随机抽样的方式在第一个抽样间隔内随机抽取一个单位作为第一个样本，再依次按抽样间隔做等距抽样，直到抽取最后一个样本为止。

分层随机抽样，也称类型随机抽样，是指首先将调查对象的总体单位按照一定的标准分成各种不同的类别(或组)，然后根据各类别(或组)的单位数与总体单位数的比例确定从各类别(或组)中抽取样本的数量，最后按照随机原则从各类(或组)中抽取样本。

整群随机抽样，又称聚类抽样，是先把总体分为若干个子群，然后一群一群地抽取作为样本单位。它通常比简单随机抽样和分层随机抽样更实用，像后者那样，它也需要将总体分成类群，所不同的是，这些分类标准往往是特殊的。具体做法是：先将各子群体编码，随机抽取分群数码，然后对所抽样本群或组实施调查。因此，整群抽样的单位不是单个的分子，而是成群成组的。凡是被抽到的群或组，其中所有的成员都是被调查的对象。这些群或组可以是一个家庭、一个班级，也可以是一个街道、一个村庄。

分段随机抽样，也称多段随机抽样或阶段随机抽样，是一种分阶段从调查对象的总体中抽取样本进行调查的方法。它首先要将总体单位按照一定的标准划分为若干群体，作为抽样的第一级单位；再将第一级单位分为若干小的群体，作为抽样的第二级单位；以此类推，可根据需要分为第三级或第四级单位。然后，按照随机原则从第一级单位中随机抽取若干单位作为第一级单位样本，再从第一级单位样本中随机抽取若干单位作为第二级单位样本，以此类推，直至获得所需要的样本。

非随机抽样

在实际的调查过程中，还有一类抽样方法，称之为非随机抽样，即它不是严格按照随机原则抽取样本，而是根据调查者的主观经验和主观判断选择样本的。

与随机抽样相比，虽然这类非随机动抽样的代表性差，提供的资料信息较零散，难以从样本调查的结论中对总体做出准确的推断。但是，由于它非常简便易行，并能通过对样本的调查而大致了解总体的某些情况，对调查研究工作很有启发性。因此，它适用于那种调查对象的总体难以具体界定，以及不需要准确推断总体情况的调查。常用非随机抽样的方法主要有以下几种：

偶遇抽样，也称方便抽样，是指调查者将自己在特定场合下偶然遇到的对象作为样本的一种方法。如在商店门口、街头路口、车站码头、公园广场等公共场所，随便选取某些顾客、行人、旅客、观众等作为样本进行调查研究.这种方法比较简单方便，适用于探索性研究，但样本的代表性较差，具有很大的偶然性。

立意抽样，也称主观抽样，它是调查者根据自己的主观印象、以往的经验和对调查对象的了解来选取样本的一种方法；这种抽样适用于那些总体范围较小、总体单位之间的差异较大的调查。

这种主观抽样所抽取的样本是否具有代表性、所得出的结论是否准确，完全取决于调查者本人的判断能力，以及对调查对象的了解程度。因此这种方法具有很大的主观随意性。但是当对总体状况较为熟悉时，用这一抽样法所选择的样本也有较高的代表性。例如当在们对某一群体作调查时，就可以根据我们所了解的群体情况选取某些样本做研究。

配额抽样，也称定额抽样，即调查者首先确定所要抽取样本的数量，再按照一定的标准和比例分配样本，然后从符合标准的对象中任意地抽取样本。其方法类似于分层随机抽样，但它不是按照随机原则抽取样本。例如，我们可以根据研究目的，把总体按性别、民族等变量进行分组，然后分配相应的样本数选取样本。

这种配额抽样比前两种方法所抽取的样本更有代表性，而且简便易行，在民意调查中经常使用。但这种方法也具有很大的主观随意性和局限性，如盖洛普采用此抽样法曾几次成功地预测了美国的总统大选，但在1948年总统选举的民意调查中却失败了。人们有时把这一方法与随机抽样法结合起来使用，其效果会更好些。

滚雪球抽样，即以少量样本为基础，逐渐扩大样本的规模，直至找出足够的样本。此法适用于对调查总体不甚清楚的情况，常用于探索性的实地研究，特别适用于对小群体关系的研究。例如我们要了解某个人经常交往的社会圈子，就可以通过这个人提供的线索找到更多与他有关联的人。其具体做法是，先找到一个或几个符合研究目的的对象，然后再根据这些对象所提供的线索找另外相关的对象，依次进行，直至达到研究目的。但滚雪球抽样法所选择的样本有时会有很大的随意性和特殊性，因而代表性不高。

单机挖掘算法关联规则挖掘的整个过程主要分两步来完成：第一步是找出数据库中所有满足最小支持度阈值的频繁项集；第二步是由频繁项集产生所有满足最小置信度阈值的关联规则。由于关联规则挖掘的整体性能主要是由第一步的性能所决定，因此，关联规则挖掘的关键和难点都集中在了频繁项集的挖掘上。随着关联分析技术的不断发展，众多的研究学者提出了许多优秀的频繁项集挖掘算法，包括单机（single-machine）挖掘算法、基于 MPI（Message Passing Interface）的挖掘算法、基于 Map Reduce 的挖掘算法和基于 Spark 的挖掘算法。

单机（single-machine）挖掘算法指的是运行在一台机器上的频繁项集挖掘算法，它们的特点是数据量小，对机器的内存大小和计算性能要求不高，在一台机器上即可完成挖掘任务。一些经典的算法，如 Apriori 和 FP-growth 等经典的频繁项集挖掘算法，都是单机频繁项集挖掘算法。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所