Open AccessK-Linkage: A New Agglomerative Approach for Hierarchical Clustering
Author(s) -
Pelin Yıldırım,
Derya Birant
Publication year - 2017
Publication title -
advances in electrical and computer engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 23
eISSN - 1844-7600
pISSN - 1582-7445
DOI - 10.4316/aece.2017.04010
Subject(s) - hierarchical clustering , hierarchical clustering of networks , cluster analysis , single linkage clustering , linkage (software) , computer science , complete linkage , data mining , brown clustering , complete linkage clustering , artificial intelligence , cure data clustering algorithm , correlation clustering , biology , genetics , genotype , single nucleotide polymorphism , gene
In agglomerative hierarchical clustering, the traditional approaches of computing cluster distances are single, complete, average and centroid linkages. However, single-link and complete-link approaches cannot always reflect the true underlying relationship between clusters, because they only consider just a single pair between two clusters. This situation may promote the formation of spurious clusters. To overcome the problem, this paper proposes a novel approach, named k-Linkage, which calculates the distance by considering k observations from two clusters separately. This article also introduces two novel concepts: k-min linkage (the average of k closest pairs) and k-max linkage (the average of k farthest pairs). In the experimental studies, the improved hierarchical clustering algorithm based on k-Linkage was executed on five well-known benchmark datasets with varying k values to demonstrate its efficiency. The results show that the proposed k-Linkage method can often produce clusters with better accuracy, compared to the single, complete, average and centroid linkages