Constrained agglomerative hierarchical clustering algorithms with penalties

Semi-supervised clustering with constraints has widely been studied, but there are few studies on constrained agglomerative hierarchical algorithms. We have shown modified kernel algorithms of agglomerative hierarchical clustering, but there is a drawback that the modified kernels are not positive definite in general. In this paper we consider another idea of agglomerative hierarchical algorithms with pairwise constraints. That is, merging of clusters is with penalties. The centroid method and the Ward method with and without a kernel are considered. Typical numerical examples show effectiveness of the proposed algorithms in generating clusters with nonlinear cluster boundaries. We also compare the results with those by COP K-means, showing that the proposed algorithms outperform the COP K-means.