OWSP-Miner: Self-adaptive One-off Weak-gap Strong Pattern Mining
Youxi Wu, Xiaohui Wang, Yan Li, Lei Guo, Zhao Li, Ji Zhang, Xindong Wu
Abstract
Gap constraint sequential pattern mining (SPM), as a kind of repetitive SPM, can avoid mining too many useless patterns. However, this method is difficult for users to set a suitable gap without prior knowledge and each character is considered to have the same effects. To tackle these issues, this article addresses a self-adaptive One-off Weak-gap Strong Pattern (OWSP) mining, which has three characteristics. First, it determines the gap constraint adaptively according to the sequence. Second, all characters are divided into two groups: strong and weak characters, and the pattern is composed of strong characters, while weak characters are allowed in the gaps. Third, each character can be used at most once in the process of support (the frequency of pattern) calculation. To handle this problem, this article presents OWSP-Miner, which equips with two key steps: support calculation and candidate pattern generation. A reverse-order filling strategy is employed to calculate the support of a candidate pattern, which reduces the time complexity. OWSP-Miner generates candidate patterns using pattern join strategy, which effectively reduces the candidate patterns. For clarification, time series is employed in the experiments and the results show that OWSP-Miner is not only more efficient but also is easier to mine valuable patterns. In the experiment of stock application, we also employ OWSP-Miner to mine OWSPs and the results show that OWSPs mining is more meaningful in real life. The algorithms and data can be downloaded at https://github.com/wuc567/Pattern-Mining/tree/master/OWSP-Miner.