Implementation-induced Inconsistency and Nondeterminism in Deterministic Clustering Algorithms

Xin Yin, Iulian Neamtiu, Saketan Patil, Sean T. Andrews

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

A deterministic clustering algorithm is designed to always produce the same clustering solution on a given input. Therefore, users of clustering implementations (toolkits) naturally assume that implementations of a deterministic clustering algorithm A have deterministic behavior, that is: (1) two different implementations I1 and I2 of A are interchangeable, producing the same clustering on a given input D, and (2) an implementation produces the same clustering solution when run repeatedly on D. We challenge these assumptions. Specifically, we analyze clustering behavior on 528 datasets, three deterministic algorithms (Affinity Propagation, DBSCAN, Hierarchical Agglomerative Clustering) and the deterministic portion of a fourth (K-means), as implemented in various toolkits; in total, we examined 13 algorithm-toolkit combinations. We found that different implementations of deterministic clustering algorithms make different choices, e.g., default parameter settings, noise insertion, input dataset characteristics. As a result, clustering solutions for a fixed algorithm-dataset combination can differ across runs (nondeterminism) and across toolkits (inconsistency). We expose several root causes of such behavior. We show that remedying these root causes improves determinism, increases consistency, and can even improve efficiency. Our approach and findings can benefit developers, testers, and users of clustering algorithms.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 13th International Conference on Software Testing, Verification and Validation, ICST 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages231-242
Number of pages12
ISBN (Electronic)9781728157771
DOIs
StatePublished - Oct 2020
Event13th IEEE International Conference on Software Testing, Verification and Validation, ICST 2020 - Porto, Portugal
Duration: Mar 23 2020Mar 27 2020

Publication series

NameProceedings - 2020 IEEE 13th International Conference on Software Testing, Verification and Validation, ICST 2020

Conference

Conference13th IEEE International Conference on Software Testing, Verification and Validation, ICST 2020
Country/TerritoryPortugal
CityPorto
Period3/23/203/27/20

All Science Journal Classification (ASJC) codes

  • Software
  • Safety, Risk, Reliability and Quality

Keywords

  • ML reliability
  • ML testing
  • cluster analysis

Fingerprint

Dive into the research topics of 'Implementation-induced Inconsistency and Nondeterminism in Deterministic Clustering Algorithms'. Together they form a unique fingerprint.

Cite this