RandomLink - Avoiding Linkage-Effects by employing Random Effects for Clustering

Author(s)
Benjamin Schelling, Gert Sluiter, Claudia Plant
Abstract

We present here a new parameter-free clustering algorithm that does not impose any assumptions on the data. Based solely on the premise that close data points are more likely to be in the same cluster, it can autonomously create clusters. Neither the number of clusters nor their shape has to be known. The algorithm is similar to SingleLink in that it connects clusters depending on the distances between data points, but while SingleLink is deterministic, RandomLink makes use of random effects. They help RandomLink overcome the SingleLink-effect (or chain-effect) from which SingleLink suffers as it always connects the closest data points. RandomLink is likely to connect close data points but is not forced to, thus, it can sever chains between clusters. We explain in more detail how this negates the SingleLink-effect and how the use of random effects helps overcome the stiffness of parameters for different distance-based algorithms. We show that the algorithm principle is sound by testing it on different data sets and comparing it with standard clustering algorithms, focusing especially on hierarchical clustering methods.

Organisation(s)
Research Group Data Mining and Machine Learning, Research Network Data Science
External organisation(s)
Munich Center for Machine Learning (MCML), Ludwig-Maximilians-Universität München
Volume
12391
Pages
217-232
DOI
https://doi.org/10.1007/978-3-030-59003-1_15
Publication date
09-2020
Peer reviewed
Yes
Austrian Fields of Science 2012
102033 Data mining
Portal url
https://ucris.univie.ac.at/portal/en/publications/randomlink--avoiding-linkageeffects-by-employing-random-effects-for-clustering(80e6c4e5-a077-4e48-8e3d-44c034e31e2c).html