Mining Compressing Sequential Patterns

Statistical Analysis and Data Mining

Hoang Thanh Lam¹  Toon Calders¹  Dmitriy Fradkin²  Fabian Mrchen³ 

[1] Siemens Corporation, Corporate Research and Technology, Princeton, NJ, USA;Technische Universiteit Eindhoven, Department of Maths and Computer Science, Eindhoven, Netherlands;Terry Avenue North, Seattle WA 98109, USA

关键词: sequence data;    compressing patterns mining;    complexity;    minimum description length;    compression‐;    based pattern mining;   

DOI  :  10.1002/sam.11192

学科分类：社会科学、人文和艺术（综合）

来源: John Wiley & Sons, Inc.

【 摘 要 】

Pattern mining based on data compression has been successfully applied in many data mining tasks. For itemset data, the Krimp algorithm based on the minimum description length (MDL) principle was shown to be very effective in solving the redundancy issue in descriptive pattern mining. However, for sequence data, the redundancy issue of the set of frequent sequential patterns is not fully addressed in the literature. In this article, we study MDL‐based algorithms for mining non‐redundant sets of sequential patterns from a sequence database. First, we propose an encoding scheme for compressing sequence data with sequential patterns. Second, we formulate the problem of mining the most compressing sequential patterns from a sequence database. We show that this problem is intractable and belongs to the class of inapproximable problems. Therefore, we propose two heuristic algorithms. The first of these uses a two‐phase approach similar to Krimp for itemset data. To overcome performance issues in candidate generation, we also propose GoKrimp, an algorithm that directly mines compressing patterns by greedily extending a pattern until no additional compression benefit of adding the extension into the dictionary. Since checks for additional compression benefit of an extension are computationally expensive we propose a dependency test which only chooses related events for extending a given pattern. This technique improves the efficiency of the GoKrimp algorithm significantly while it still preserves the quality of the set of patterns. We conduct an empirical study on eight datasets to show the effectiveness of our approach in comparison to the state‐of‐the‐art algorithms in terms of interpretability of the extracted patterns, run time, compression ratio, and classification accuracy using the discovered patterns as features for different classifiers..

【 授权许可】

Unknown