多尺度取样：一种近似关联规则挖掘的自适应取样算法
Multi-Scaling Sampling: An Adaptive Sampling Method for Discovering Approximate Association Rules
-
摘要: 随着网络技术、存贮器技术和处理器技术的提高，整个世界的信息总量正以惊人的速度急剧膨胀，从事数据分析和处理的数据挖掘专家们所面对和处理的数据库或数据仓库的规模也随之不断增长。现有的数据挖掘算法在性能上难以满足处理海量数据库或数据仓库的要求。关联规则挖掘作为数据挖掘的核心任务之一，由于其任务本身的复杂性（通常需要多次整个扫描数据库才能完成挖掘任务且频繁模式可能产生组合爆炸），使得从原始的大规模数据集上抽取一部分样本，在其上寻找用户感兴趣的近似规则成为目前提高算法效率和可扩展性的一种简单、有效的现实可行方法之一。但是，取样策略必须在算法的效率和结果的精确性之间进行很好的折中，“如何确定合适的样本大小使得运行于其上的关联规则挖掘满足精确性的要求（取样复杂性）”成为这一方法的关键、难解问题。已有的研究表明：根据数据库的特性，动态的选取样本大小、进而获取可接受的近似关联规则的自适应取样方法是解决上述问题的一种好方法。但与之相关的一个关键问题：取样误差的量化模型和快速估计方法的研究被人们所忽视，同时已有结果的效率和真实适用性还需要人们进一步的改进以适应日益增长大规模数据库处理的需求。因此，本文首先在现实的实验观察和PAC理论的指导下给出了一种有效的取样误差量化方法和快速估计算法。它主要依赖于如下事实和结论：1）关联规则挖掘取样所产生的误差主要由错误和遗漏频繁项集决定；2）错误和遗漏频繁项集常出现在支撑度阈值的附近。基于以上结果，本文将由错误和遗漏频繁项集所产生的误差定义为主误差，并只在支撑度阈值附近探测错误和遗漏频繁项集以实现主误差的快速估计。实验结果表明，该方法可以精确地估计出主误差、并成倍地加快取样误差估计的速度，为设计行之有效的自适应取样算法奠定了基础。接着，我们在多分辨分析和Shannon取样定理的启发下，设计出了一种高效的、自适应、在线获取近似关联规则的取样算法：多尺度取样算法（Multi-scaling Sampling, MS）。实验结果表明，我们的取样算法可以快速地得到想要的样本大小和可接受的近似关联规则。同时，它可以克服已有的渐近取样算法（Progressives Sampling，PS）的诸多不足。并且，在相同的条件下MS要比已有的PS快数倍。可以说，MS在一定程度上较好地解决了基于取样策略的关联规则挖掘近似算法“取样复杂性”难于确定的问题。Abstract: One of the obstacles of the efficient association rule mining is theexplosive expansion of data sets since it is costly or impossible toscan large databases, esp., for multiple times. A popular solution toimprove the speed and scalability of the association rule mining is todo the algorithm on a random sample instead of the entire database. Buthow to effectively define and efficiently estimate the degree of errorwith respect to the outcome of the algorithm, and how to determine the samplesize needed are entangling researches until now. In this paper,an effective and efficient algorithm is given based on the PAC(Probably Approximate Correct) learning theory to measure and estimatesample error. Then, a new adaptive, on-line, fast samplingstrategy --- multi-scaling sampling --- is presented inspired by MRA(Multi-Resolution Analysis) and Shannon sampling theorem, for quicklyobtaining acceptably approximate association rules at appropriate samplesize. Both theoretical analysis and empirical study have showed that thesampling strategy can achieve a very good speed-accuracy trade-off.
下载: