Direct mining of discriminative and essential frequent patterns via model-based search tree-猫眼课题宝

DOI：

10.1145/1401890.1401922

发表时间：

2008-08

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

W. Fan;Kun Zhang;Hong Cheng;Jing Gao;Xifeng Yan;Jiawei Han;Philip S. Yu;O. Verscheure

频繁模式为没有结构良好的特征向量的数据集提供了解决方案。然而，频繁模式挖掘是不平凡的，因为唯一模式的数量是指数级的，但许多是非歧视性的和相关的。目前，频繁模式挖掘分为两个连续的步骤：枚举一组频繁模式，然后进行特征选择。尽管在过去的几年中已经提出了许多方法来有效地执行每个单独的步骤，但在最终找到高度紧凑和有区别的模式方面仍然取得了有限的成功。罪魁祸首是由于这种广泛采用的两步方法的固有性质。本文讨论了这些问题，并提出了一种新的和不同的方法。它构建了一个决策树，将数据划分到不同的节点上。然后在每个节点上，它直接发现一个判别模式，进一步将其样本划分为更纯的子集。由于对叶级的例子的数量相对较少，新的方法是能够检查模式与极低的全球支持，不能列举整个数据集的两步方法。发现的特征向量是更准确的一些最困难的图，以及频繁的项集问题比最近提出的算法，但总的大小通常是50%或更小。重要的是，一些判别模式的最小支持度可能非常低（例如0.03%）。为了枚举这些低支持度的模式，最先进的频繁模式算法要么由于巨大的内存消耗而无法完成，要么必须枚举101到103倍的模式才能找到它们。软件和数据集可通过联系作者获得。

Frequent patterns provide solutions to datasets that do not have well-structured feature vectors. However, frequent pattern mining is non-trivial since the number of unique patterns is exponential but many are non-discriminative and correlated. Currently, frequent pattern mining is performed in two sequential steps: enumerating a set of frequent patterns, followed by feature selection. Although many methods have been proposed in the past few years on how to perform each separate step efficiently, there is still limited success in eventually finding highly compact and discriminative patterns. The culprit is due to the inherent nature of this widely adopted two-step approach. This paper discusses these problems and proposes a new and different method. It builds a decision tree that partitions the data onto different nodes. Then at each node, it directly discovers a discriminative pattern to further divide its examples into purer subsets. Since the number of examples towards leaf level is relatively small, the new approach is able to examine patterns with extremely low global support that could not be enumerated on the whole dataset by the two-step method. The discovered feature vectors are more accurate on some of the most difficult graph as well as frequent itemset problems than most recently proposed algorithms but the total size is typically 50% or more smaller. Importantly, the minimum support of some discriminative patterns can be extremely low (e.g. 0.03%). In order to enumerate these low support patterns, state-of-the-art frequent pattern algorithm either cannot finish due to huge memory consumption or have to enumerate 101 to 103 times more patterns before they can even be found. Software and datasets are available by contacting the author.

Direct mining of discriminative and essential frequent patterns via model-based search tree

文献摘要

被引文献

相似文献