6533b858fe1ef96bd12b6d8b

RESEARCH PRODUCT

Scalable Hierarchical Clustering: Twister Tries with a Posteriori Trie Elimination

Michael CochezFerrante Neri

subject

ta113Theoretical computer scienceBrown clusteringComputer scienceCorrelation clusteringSingle-linkage clusteringHierarchical clusteringCURE data clustering algorithmhierrchial clusteringCanopy clustering algorithmHierarchical clustering of networksCluster analysisclustering

description

Exact methods for Agglomerative Hierarchical Clustering (AHC) with average linkage do not scale well when the number of items to be clustered is large. The best known algorithms are characterized by quadratic complexity. This is a generally accepted fact and cannot be improved without using specifics of certain metric spaces. Twister tries is an algorithm that produces a dendrogram (i.e., Outcome of a hierarchical clustering) which resembles the one produced by AHC, while only needing linear space and time. However, twister tries are sensitive to rare, but still possible, hash evaluations. These might have a disastrous effect on the final outcome. We propose the use of a metaheuristic algorithm to overcome this sensitivity and show how approximate computations of dendrogram quality can help to evaluate the heuristic within reasonable time. The proposed metaheuristic is based on an evolutionary framework and integrates a surrogate model of the fitness within it to enhance the algorithmic performance in terms of computational time. peerReviewed

yearjournalcountryeditionlanguage
2015-12-012015 IEEE Symposium Series on Computational Intelligence
https://doi.org/10.1109/ssci.2015.12