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

Maciej Bartoszuk , Anna Cena , Marek Gągolewski

Abstract

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 ZSIMO
Maciej Bartoszuk,,
- Department of Artificial Intelligence and Computational Methods
, Anna Cena
Anna Cena,,
-
, Marek Gągolewski ZRC
Marek Gągolewski,,
- Department of Integral Equations
Journal seriesInformation Sciences, ISSN 0020-0255
Issue year2016
Vol363
Pages8-23
Publication size in sheets0.75
Keywords in EnglishHierarchical clustering, Single linkage, Inequity measures, Gini-index
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.
DOIDOI:10.1016/j.ins.2016.05.003
URL http://www.sciencedirect.com/science/article/pii/S002002551630319X
Languageen angielski
Score (nominal)45
ScoreMinisterial score = 45.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 45.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 4.832 (2) - 2016=4.732 (5)
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


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