Title: An apriori-based algorithm for mining semi-order-preserving submatrix

Authors: Yun Xue; Tiechen Li; Haolan Zhang; Xiaosheng Wu; Meihang Li; Xiaohui Hu

Addresses: Guangzhou Higher Education Mega Centre, South China Normal University, Guangzhou, China ' Guangzhou Higher Education Mega Centre, South China Normal University, Guangzhou, China ' Zhejiang University, Center for SCDM, NIT, China ' Guangzhou Higher Education Mega Centre, South China Normal University, Guangzhou, China ' Guangzhou Higher Education Mega Centre, South China Normal University, Guangzhou, China ' Guangzhou Higher Education Mega Centre, South China Normal University, Guangzhou, China

Abstract: Order-preserving submatrices (OPSMs) find objects that exhibit a coherent pattern with the same linear ordering in subspace. In general, this problem can be reducible to a special case of the sequential pattern mining problem, where a pattern and its supporting sequences uniquely specify an OPSM. In this paper, we extend the idea of order-preserving submatrix and define a new model semi-order-preserving submatrix (or SOPSM) that can be generalised to cover most existing bicluster models, and then propose a novel exact algorithm for mining all significant SOPSMs. To reduce the computational costs, we further propose a pruning technique and design an improved data structure for prefix tree to speed up the running time of the algorithm. A set of extensive experiments have been performed which demonstrate the effectiveness and efficiency of our method in mining SOPSMs.

Keywords: data mining; biclustering; order-preserving submatrix; OPSM; sequential pattern mining; pruning; data structure; prefix tree.

DOI: 10.1504/IJCSE.2016.077734

International Journal of Computational Science and Engineering, 2016 Vol.13 No.1, pp.66 - 79

Received: 02 Jan 2014
Accepted: 09 Apr 2014
Published online: 14 Jul 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article