On mining maximal pattern-based clusters

Pattern-based clustering is important in many applications, such as DNA micro-array data analysis in bio-informatics, as well as automatic recommendation systems and target marketing systems in e-business. However, pattern-based clustering in large databases is still challenging. On the one hand, there can be a huge number of clusters and many of them can be redundant and thus make the pattern-based clustering ineffective. On the other hand, the previous proposed methods may not be efficient or scalable in mining large databases. In this paper, we study the problem of maximal pattern-based clustering. The major idea is that the redundant clusters are avoided completely by mining only the maximal pattern-based clusters. We show that maximal pattern-based clusters are skylines of all pattern-based clusters. Two efficient algorithms, MaPle and MaPle+ (MaPle is for Maximal Pattern-based Clustering) are developed. The algorithms conduct a depth-first, progressively refining search and prune unpromising branches smartly. MaPle+ integrates several interesting heuristics further. Our extensive performance study on both synthetic data sets and real data sets shows that maximal pattern-based clustering is effective - it reduces the number of clusters substantially. Moreover, MaPle and MaPle+ are more efficient and scalable than the previously proposed pattern-based clustering methods in mining large databases, and MaPle,+ often performs better than MaPle. © 2009 Springer US.

Duke Scholars

Author Jian Pei Computer Science