Efficient Mining of Gap-Constrained Subsequences and Its Various Applications
Efficient Mining of Gap-Constrained Subsequences and Its Various Applications
复制标题
间隙约束子序列的高效挖掘及其各种应用
DOI：
10.1145/2133360.2133362
复制
发表时间：
2012-03-01
影响因子：
3.6
通讯作者：
Li, Ming
中科院分区：
文献类型：
--
作者：
Li, Chun;Yang, Qingyan;Li, Ming
频繁子序列模式挖掘是一个典型的数据挖掘问题，人们已经提出了各种有效的序列模式挖掘算法。在许多应用领域（例如，生物学），由预定义的间隙要求限制的频繁连续性比一般的序列模式更有意义。在这篇文章中，我们提出了两个算法，Gap-BIDE从一组输入序列中挖掘封闭的间隙约束连续性，和Gap-Connect从单个输入序列中挖掘重复的间隙约束连续性。Gap-BIDE算法受一些封闭或约束序列模式挖掘算法的启发，采用了一种有效的方法来寻找具有间隙约束的封闭序列模式的完整集合，而Gap-Connect算法通过连接短模式来有效地挖掘长模式的近似集合。我们还提出了几种方法，从一组间隙约束模式的分类和聚类的目的特征选择。我们广泛的性能研究表明，我们的方法是非常有效的挖掘频繁序列与间隙约束，和间隙约束模式为基础的分类/聚类方法可以实现高质量的结果。
Mining frequent subsequence patterns is a typical data-mining problem and various efficient sequential pattern mining algorithms have been proposed. In many application domains (e.g., biology), the frequent subsequences confined by the predefined gap requirements are more meaningful than the general sequential patterns. In this article, we propose two algorithms, Gap-BIDE for mining closed gap-constrained subsequences from a set of input sequences, and Gap-Connect for mining repetitive gap-constrained subsequences from a single input sequence. Inspired by some state-of-the-art closed or constrained sequential pattern mining algorithms, the Gap-BIDE algorithm adopts an efficient approach to finding the complete set of closed sequential patterns with gap constraints, while the Gap-Connect algorithm efficiently mines an approximate set of long patterns by connecting short patterns. We also present several methods for feature selection from the set of gap-constrained patterns for the purpose of classification and clustering. Our extensive performance study shows that our approaches are very efficient in mining frequent subsequences with gap constraints, and the gap-constrained pattern based classification/clustering approaches can achieve high-quality results.