A Data Partitioning Approach for Hierarchical Clustering

In this paper, we propose a parameter-insensitive data partitioning approach for Chameleon, a hierarchical clustering algorithm. The proposed method splits a given dataset into every possible number of clusters by using existing algorithms that do allow arbitrary-sized sub-clusters in partitioning. After that, it evaluates the quality of every set of initial sub-clusters by using our measurement function, and decides the optimal set of initial sub-clusters such that they show the highest value of measurement. Finally, it merges these optimal initial sub-clusters repeatedly and produces the final clustering result. We perform extensive experiments, and the results show that the proposed approach is insensitive to parameters and also produces a set of final clusters whose quality is better than the previous one.This research was supported by MKE (The Ministry of Knowledge Economy), Korea and Microsoft Research, under IT/SW Creative research program (NIPA-2012-H0503-12-1018) and under the Convergence-ITRC (Convergence Information Technology Research Center) support program(NIPA-2012-H0401-12-1001) supervised by the NIPA (National IT Industry Promotion Agency)