Efficient Single-Linkage hierarchical clustering based on partitioning
Mohamed A. Mahfouz · 2016
Ease of interpretation of results makes hierarchical clustering algorithms suitable for many applications. However they suffer high computational complexity. Single Linkage hierarchical clustering with its related graph theoretical terms is the most famous among hierarchical algorithms. Several existing techniques reduce its complexity by formulating it as a minimum spanning tree (MST) problem. The main contribution of this research study is minimizing the number of edges given as input to the MST algorithm by first partitioning the dataset using any scalable clustering technique then building k-nearest neighbors table for each partition. After that, outliers and border objects are identified in each partition and moved to a separate partition. Objects in the outliers' partition are used in updating the k-nearest neighbors table of itself and the other partitions. The final edges in the k-nearest neighbors' tables of all partitions are sorted in descending order then merged. The final sorted edges are given as input to a MST algorithm. Several experiments are carried in order to validate the idea, fine tune the input parameters and to get insights of its performance. The proposed algorithm can be completely implemented in parallel which can improve the performance by significant factor.