Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm

Maciej Bartoszuk , Anna Cena , Marek Gągolewski


The time needed to apply a hierarchical clustering algorithm is most often dominated by the number of computations of a pairwise dissimilarity measure. Such a constraint, for larger data sets, puts at a disadvantage the use of all the classical linkage criteria but the single linkage one. However, it is known that the single linkage clustering algorithm is very sensitive to outliers, produces highly skewed dendrograms, and therefore usually does not reflect the true underlying data structure – unless the clusters are well-separated. To overcome its limitations, we propose a new hierarchical clustering linkage criterion called Genie. Namely, our algorithm links two clusters in such a way that a chosen economic inequity measure (e.g., the Gini- or Bonferroni-index) of the cluster sizes does not increase drastically above a given threshold. The presented benchmarks indicate a high practical usefulness of the introduced method: it most often outperforms the Ward or average linkage in terms of the clustering quality while retaining the single linkage speed. The Genie algorithm is easily parallelizable and thus may be run on multiple threads to speed up its execution further on. Its memory overhead is small: there is no need to precompute the complete distance matrix to perform the computations in order to obtain a desired clustering. It can be applied on arbitrary spaces equipped with a dissimilarity measure, e.g., on real vectors, DNA or protein sequences, images, rankings, informetric data, etc. A reference implementation of the algorithm has been included in the open source genie package for R.
Author Maciej Bartoszuk (FMIS / DAICM)
Maciej Bartoszuk,,
- Department of Artificial Intelligence and Computational Methods
, Anna Cena (FMIS / DIE) - [Instytut Badań Systemowych Polskiej Akademii Nauk]
Anna Cena,,
- Department of Integral Equations
- Instytut Badań Systemowych Polskiej Akademii Nauk
, Marek Gągolewski (FMIS / DIE)
Marek Gągolewski,,
- Department of Integral Equations
Journal seriesInformation Sciences, ISSN 0020-0255
Issue year2016
Publication size in sheets0.75
Keywords in EnglishHierarchical clustering, Single linkage, Inequity measures, Gini-index
ASJC Classification1702 Artificial Intelligence; 1802 Information Systems and Management; 1706 Computer Science Applications; 2614 Theoretical Computer Science; 2207 Control and Systems Engineering; 1712 Software
Abstract in PolishCzas działania algorytmów hierarchicznej analizy skupień jest często zdominowany liczbą odwołań do funkcji grającej rolę miary odległości. Z tego powodu dla dużych zbiorów danych praktycznie jedyną sensowną w praktyce odmiennością jest odmienność najbliższego sąsiada (ang. single linkage). Niestety jest ona bardzo wrażliwa na obserwacje odstające i prowadzi do bardzo nierównomiernych (skośnych) dendrogramów. Zaproponowaliśmy więc nowy algorytm, który opiera się na indeksach nierówności ekonomicznej (np. Giniego), a który pozbawiony jest wad odmienności najbliższego sąsiada. Wyniki benchmarkowe pokazały, że generowane skupienia cechują się wysoką jakością, a sam algorytm jest bardzo szybki, także dla dużych zbiorów danych.
Languageen angielski
Score (nominal)45
Score sourcejournalList
ScoreMinisterial score = 45.0, 26-01-2020, ArticleFromJournal
Ministerial score (2013-2016) = 45.0, 26-01-2020, ArticleFromJournal
Publication indicators Scopus Citations = 23; WoS Citations = 13; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 2.487; WoS Impact Factor: 2016 = 4.832 (2) - 2016=4.732 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?