Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
复制标题
使用 VC 维度和 Rademacher 复杂度挖掘序列模式
作者：
Diego Santoro;Andrea Tonon;Fabio Vandin
序列模式挖掘是数据挖掘中的一项基本任务，在许多领域都有应用。我们研究了两个变种，这个任务的第一个是频繁序列模式的提取，其在连续事务的数据集中的频率高于用户提供的阈值;第二个是真正的频繁序列模式的挖掘，这出现的概率高于用户定义的阈值从生成过程中提取的数据。我们提出了第一个基于采样的算法来挖掘，具有高置信度，严格近似的频繁序列模式从海量数据集。我们还提出了第一个算法来挖掘近似的真实频繁的序列模式，严格保证输出的质量。我们的算法是基于新的应用Vapnik-Chervonenkis维和Rademacher复杂性，先进的工具，从统计学习理论，序列模式挖掘。我们广泛的实验评估表明，我们的算法提供了高质量的近似，我们考虑的两个问题。
Sequential pattern mining is a fundamental data mining task with application in several domains. We study two variants of this task—the first is the extraction of frequent sequential patterns, whose frequency in a dataset of sequential transactions is higher than a user-provided threshold; the second is the mining of true frequent sequential patterns, which appear with probability above a user-defined threshold in transactions drawn from the generative process underlying the data. We present the first sampling-based algorithm to mine, with high confidence, a rigorous approximation of the frequent sequential patterns from massive datasets. We also present the first algorithms to mine approximations of the true frequent sequential patterns with rigorous guarantees on the quality of the output. Our algorithms are based on novel applications of Vapnik-Chervonenkis dimension and Rademacher complexity, advanced tools from statistical learning theory, to sequential pattern mining. Our extensive experimental evaluation shows that our algorithms provide high-quality approximations for both problems we consider.