Adaptive sampling methods for scaling up knowledge discovery algorithms
Adaptive sampling methods for scaling up knowledge discovery algorithms
复制标题
DOI：
10.1023/a:1014091514039
复制
发表时间：
2002-04-01
影响因子：
4.8
通讯作者：
Watanabe, O
中科院分区：
文献类型：
--
作者：
Domingo, C;Gavaldà, R;Watanabe, O
可伸缩性是任何KDD和数据挖掘算法的关键要求，而最大的研究挑战之一是开发允许使用大量数据的方法。处理大量数据的一种可能方法是取一个随机样本并对其进行数据挖掘，因为对于许多数据挖掘应用程序来说，近似答案是可以接受的。然而，正如一些研究人员所争论的那样，由于难以确定适当的样本量，随机抽样很难使用。在本文中，我们采用顺序采样方法来解决这一困难，并提出了一种自适应采样方法，该方法解决了发现科学应用中出现的许多实际问题。采用该方法的算法以在线方式顺序获取样例，并从得到的样例中判断是否已经看到了足够多的样例。因此，样本量不是先验固定的；相反，它会根据情况做出适应性调整。由于这种适应性，如果我们没有像许多实际应用中幸运地发生的那样处于最坏的情况，那么我们可以用比最坏情况所需的小得多的示例来解决问题。从理论上证明了该方法的正确性和有效性。为了说明它的有效性，我们考虑了一个需要采样的具体任务，提供了一个基于我们的方法的算法，并通过实验证明了它的有效性。
Scalability is a key requirement for any KDD and data mining algorithm, and one of the biggest research challenges is to develop methods that allow to use large amounts of data. One possible approach for dealing with huge amounts of data is to take a random sample and do data mining on it, since for many data mining applications approximate answers are acceptable. However, as argued by several researchers, random sampling is difficult to use due to the difficulty of determining an appropriate sample size. In this paper, we take a sequential sampling approach for solving this difficulty, and propose an adaptive sampling method that solves a general problem covering many actual problems arising in applications of discovery science. An algorithm following this method obtains examples sequentially in an on-line fashion, and it determines from the obtained examples whether it has already seen a large enough number of examples. Thus, sample size is not fixed a priori; instead, it adaptively depends on the situation. Due to this adaptiveness, if we are not in a worst case situation as fortunately happens in many practical applications, then we can solve the problem with a number of examples much smaller than required in the worst case. We prove the correctness of our method and estimates its efficiency theoretically. For illustrating its usefulness, we consider one concrete task requiring sampling, provide an algorithm based on our method, and show its efficiency experimentally.