Title: Enhanced algorithms for hierarchical clustering
Authors: Ana Maria Puiu - Alexandru Ioan Cuza University of Iasi (Romania)
Cristian Gatu - Alexandru Ioan Cuza University of Iasi (Romania) [presenting]
Abstract: Two hierarchical clustering approaches are investigated. The first is based on a previously proposed iterative clustering algorithm. It follows a deterministic approach that tries to improve a current clustering, represented as a binary tree. At each step two local moves are performed: reordering and graft, and the best alternative is chosen. A randomized version is proposed such that a non-improving move is accepted with a specified probability. The second approach considers a combinatorial and two randomized clustering procedures that are based on the Ward method. The Combinatorial Hierarchical Clustering differs from the original Ward method by the fact that at each merging step the execution is divided into two new execution threads, one in which the best cluster pair is merged, and a second one in which the second best cluster pair is merged. The execution plan can be visualized as a binary tree in which each node has two edges representing the current choice (best or second best) and the child nodes represent the partial solutions generated so far. A Restricted Randomized Hierarchical Clustering differs from the original Ward method by the fact that at each merging step the second best clustering pair is merged instead of the optimal one with a specified probability. A generalization of this method that randomly chooses from all merging possibilities is also introduced. Experimental results are performed and analyzed.