Advances in frequent itemset mining implementations: report on FIMI'03
Advances in frequent itemset mining implementations: report on FIMI'03
复制标题
DOI：
10.1145/1007730.1007744
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
Bart Goethals;Mohammed J. Zaki
中科院分区：
文献类型：
--
作者：
Bart Goethals;Mohammed J. Zaki
1.为什么组织FIMI？自1993年Agrawal Imielinski和Swami提出关联规则挖掘以来，频繁项集挖掘（Frequent itemset mining，简称频繁项集挖掘）任务受到了广泛的关注。在过去的十年中，已经开发了大量的算法来挖掘所有[3; 5; 20; 4; 27; 24; 29; 34; 10; 22; 19; 32]，封闭[25; 6; 12; 26; 30; 23; 31; 28; 33]和最大频繁项集[18; 21; 7; 2; 1; 11; 36; 38; 39]。十六个; 17]。每一篇新的论文都声称比以前现有的算法运行得更快，这是基于他们的实验测试，这通常在范围上是相当有限的，因为许多原始算法由于知识产权和版权问题而不可用。Zheng，Kohavi和Mason [35]观察到，当在一些不同的数据集上进行测试时，其中几种算法的性能并不总是如其作者所声称的那样。此外，从个人经验来看，我们注意到即使是同一算法的不同实现，对于不同的数据集和参数也会有很大的不同。考虑到并行计算算法的激增，以及有时相互矛盾的说法，迫切需要对算法性能空间进行基准测试，表征和理解。我们想知道为什么以及在什么条件下一个算法优于另一个算法。这意味着要在各种各样的参数下，在不同的数据集上测试这些方法，这些数据集包括密集和稀疏、真实的和合成的、小的和大的等等。考虑到实验的、算法的性质，数据挖掘（以及大多数数据挖掘），其他研究人员能够独立地验证一篇新论文中的主张是至关重要的。不幸的是，在这方面，社区（除了少数例外）的记录非常差。许多新算法甚至不能作为可执行文件使用，更不用说源代码了。有多少次我们听到“这是专有软件，不可用。”这不是其他科学工作的方式。独立可验证性是物理学、化学、生物学等科学的标志。有人可能会说，研究的性质是不同的，他们有详细的实验程序，可以复制，而我们有算法，并且有不止一种方法来编码算法。然而，生物信息学界是一个值得效仿的好例子。他们比我们更热衷于支持开源模式。生物信息学的期刊和会议要求软件可用是很常见的。例如，以下是《生物信息学》杂志的直接引用（http：//bioinformatics.oupjournals.org/）：
1. WHY ORGANIZE FIMI? Since the introduction of association rule mining in 1993 by Agrawal Imielinski and Swami [3], the frequent itemset mining (FIM) tasks have received a great deal of attention. Within the last decade, a phenomenal number of algorithms have been developed for mining all [3; 5; 20; 4; 27; 24; 29; 34; 10; 22; 19; 32], closed [25; 6; 12; 26; 30; 23; 31; 28; 33] and maximal frequent itemsets [18; 21; 7; 2; 1; 11; 36; 16; 17]. Every new paper claims to run faster than previously existing algorithms, based on their experimental testing, which is oftentimes quite limited in scope, since many of the original algorithms are not available due to intellectual property and copyright issues. Zheng, Kohavi and Mason [35] observed that the performance of several of these algorithms is not always as claimed by its authors, when tested on some different datasets. Also, from personal experience, we noticed that even different implementations of the same algorithm could behave quite differently for various datasets and parameters. Given this proliferation of FIM algorithms, and sometimes contradictory claims, there is a pressing need to benchmark, characterize and understand the algorithmic performance space. We would like to understand why and under what conditions one algorithm outperforms another. This means testing the methods for a wide variety of parameters, and on different datasets spanning dense and sparse, real and synthetic, small and large, and so on. Given the experimental, algorithmic nature of FIM (and most of data mining in general), it is crucial that other researchers be able to independently verify the claims made in a new paper. Unfortunately, the FIM community (with few exceptions) has a very poor track record in this regard. Many new algorithms are not available even as an executable, let alone the source code. How many times have we heard “this is proprietary software, and not available.” This is not the way other sciences work. Independent verifiability is the hallmark of sciences like physics, chemistry, biology, and so on. One may argue, that the nature of research is different, they have detailed experimental procedure that can be replicated, while we have algorithms, and there is more than one way to code an algorithm. However, a good example to emulate is the bioinformatics community. They have espoused the open-source paradigm with more alacrity than we have. It is quite common for journals and conferences in bioinformatics to require that software be available. For example, here is a direct quote from the journal Bioinformatics (http://bioinformatics.oupjournals.org/):