The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Exposing and fixing causes of inconsistency and nondeterminism in clustering implementations
Author:	Yin, Xin
View Online:	njit-etd2020-070 (xvi, 95 pages ~ 2.3 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Neamtiu, Iulian (Committee chair) Mili, Ali (Committee member) Roshan, Usman W. (Committee member) Koutis, Ioannis (Committee member) Loh, Ji Meng (Committee member)
Date:	2020-12
Keywords:	Clustering implementation Differential approach Dynamic analysis Programming language Software engineering Statistical approach
Availability:	Unrestricted
Abstract:	Cluster analysis aka Clustering is used in myriad applications, including high-stakes domains, by millions of users. Clustering users should be able to assume that clustering implementations are correct, reliable, and for a given algorithm, interchangeable. Based on observations in a wide-range of real-world clustering implementations, this dissertation challenges the aforementioned assumptions. This dissertation introduces an approach named SmokeOut that uses differential clustering to show that clustering implementations suffer from nondeterminism and inconsistency: on a given input dataset and using a given clustering algorithm, clustering outcomes and accuracy vary widely between (1) successive runs of the same toolkit, i.e., nondeterminism, and (2) different toolkits, i.e, inconsistency. Using a statistical approach, this dissertation quantifies and exposes statistically significant differences across runs and toolkits. This dissertation exposes the diverse root causes of nondeterminism or inconsistency, such as default parameter settings, noise insertion, distance metrics, termination criteria. Based on these findings, this dissertation introduces an automatic approach for locating the root causes of nondeterminism and inconsistency. This dissertation makes several contributions: (1) quantifying clustering outcomes across different algorithms, toolkits, and multiple runs; (2) using a statistical rigorous approach for testing clustering implementations; (3) exposing root causes of nondeterminism and inconsistency; and (4) automatically finding nondeterminism and inconsistency's root causes.