A method of two-stage clustering with constraints using agglomerative hierarchical algorithm and one-pass k-means

摘要

The aim of this paper is to propose a new method of two-stage clustering with constraints using agglomerative hierarchical algorithm and one-pass k-means. An agglomerative hierarchical algorithm has a larger computational complexity than non-hierarchical algorithm. It takes much time to execute agglomerative hierarchical algorithm, and sometimes, agglomerative hierarchical algorithm cannot be executed. In order to handle a large-scale data by an agglomerative hierarchical algorithm, the present method is proposed. The method is divided into two stages. In the first stage, a method of one-pass k-means is carried out. The difference between k-means and one-pass k-means is that the former uses iterations, while the latter not. Small clusters obtained from this stage are merged using agglomerative hierarchical algorithm in the second stage. In order to improve correctness of clustering, pairwise constraints are included. To show effectiveness of the proposed method, numerical examples are given.