Extraction of sequential patterns with least minimum generalization based on ambiguous retrieval
Kotaro Araki, Keiichi Tamura, Tomoyuki Kato, Susumu Kuroki · 2007
We propose a method for extracting frequent sequence patterns including the expression of ambiguous characters from sequence databases. The proposed method is composed of two stages that are ambiguous retrieval allowing mismatch characters and least minimum generalization for the results of the retrieval. At the stage of the ambiguous retrieval, the set of positive k−length subsequences for a retrieval key given by user are selected from the disk based-suffix tree on the condition that the each subsequence satisfies a minimum support, M ini sup, and permissible error margin radius, r. At the stage of the least minimum generalization, the least minimum patterns are acquired by refining a most general pattern using the set of negative k−length patterns. The set of negative k−length patterns are computed by refining a most general pattern using the set of positive k−length patterns. We experiment by using some data sets to confirm the usefulness of the proposed method. As a result, we confirmed that a large amount of k−length character strings selected by the first stage is represented by few generalization patterns. Moreover, we succeeded in extracting the generalization pattern that represented a part of the motif included in the dataset by this method.