A Validation and Quality Assessment Method with Metamorphic Relations for Unsupervised Machine Learning Software

Zhiyi Zhang, Xiaoyuan Xie, Tsong Yueh Chen, Yang Liu, Baowen XuarXiv 2018 · arXiv

Abstract

Unsupervised machine learning, particularly clustering, faces a significant "oracle problem" where the lack of ground truth labels makes software validation difficult. This paper proposes a metamorphic testing framework using 11 Metamorphic Relations (MRs) to assess the quality and reliability of clustering software. By analyzing the relationship between outputs of transformed inputs, the study identifies critical gaps between theoretical expectations and actual software implementations across various algorithms in the Weka framework.

Introduction

In supervised learning, model performance is easily verified against labeled ground truth. However, unsupervised learning—specifically clustering—lacks such labels, leading to the Oracle Problem. Traditional validation methods are often "static," evaluating a single output in isolation. These methods fail to capture "dynamic" user expectations, such as the requirement that shuffling data order or rotating coordinates should not fundamentally alter the resulting clusters. This research introduces a systematic, lightweight framework to validate clustering programs and assist users in selecting algorithms appropriate for their specific data scenarios.

Methodology: Metamorphic Testing

The proposed method utilizes Metamorphic Testing (MT). Instead of verifying a single output against a known result, MT examines the relationship between the outputs of related inputs. The authors defined 11 Metamorphic Relations (MRs) categorized into six groups:

  1. Object Order: Shuffling data point sequences.
  2. Distinctness: Shrinking clusters or mirroring datasets.
  3. Density: Adding points near cluster centers or boundaries.
  4. Attributes: Adding informative or removing redundant features.
  5. Coordinate Systems: Rotating or scaling axes.
  6. Outliers: Inserting global outliers.

To quantify violations, the Reclustering Percentage (RP) was introduced, measuring the proportion of data points reassigned to different clusters following a transformation.

Experimental Setup

The study employed synthetic datasets generated via Scikit-learn's make_blobs, creating well-separated isotropic Gaussian blobs in 2D space for clear visualization. Algorithms from the Weka 3.6.6 framework were tested, including prototype-based (K-Means, X-Means, EM), hierarchy-based (AGNES, FarthestFirst), and density-based (DBSCAN) methods.

Key Insights and Results

The Theory-Practice Gap

A significant finding involved coordinate rotation (MR 5.1). Theoretically, rotation should not alter cluster assignments. However, initial tests showed high violation rates across nearly all programs. Investigation revealed that Weka implementations included a hidden Min-Max Normalization step. This nonlinear preprocessing changed relative distances post-rotation, leading to divergent clustering results. Removing this normalization reduced the violation rate to zero.

Algorithm Robustness

  • AGNES proved most robust, violating only 3 of 11 MRs.
  • K-Means was the most sensitive, violating 9 of 11 MRs, often due to transformations causing convergence to different local optima.
  • FarthestFirst exhibited extreme sensitivity to input order (90% violation rate) due to its dependency on the initial point selection.
  • DBSCAN showed a 100% violation rate in "Data Mirroring" (MR 2.2) because of its handling of "noise" points in expanded data spaces.

Conclusion

Metamorphic Relations provide a valuable "profile" for software selection. For instance, applications with evolving datasets should prioritize an algorithm robust to "Adding objects" (MR 3.1). While this study focused on 2D synthetic data, future work will explore high-dimensional real-world datasets and automated MR selection to further bridge the gap between clustering theory and software implementation.

Summary updated

Abstract

Unsupervised machine learning is the training of an artificial intelligence system using information that is neither classified nor labeled, with a view to modeling the underlying structure or distribution in a dataset. Since unsupervised machine learning systems are widely used in many real-world applications, assessing the appropriateness of these systems and validating their implementations with respect to individual users' requirements and specific application scenarios$\,/\,$contexts are indisputably two important tasks. Such assessment and validation tasks, however, are fairly challenging due to the absence of a priori knowledge of the data. In view of this challenge, we develop a $\textbf{MET}$amorphic $\textbf{T}$esting approach to assessing and validating unsupervised machine $\textbf{LE}$arning systems, abbreviated as METTLE. Our approach provides a new way to unveil the (possibly latent) characteristics of various machine learning systems, by explicitly considering the specific expectations and requirements of these systems from individual users' perspectives. To support METTLE, we have further formulated 11 generic metamorphic relations (MRs), covering users' generally expected characteristics that should be possessed by machine learning systems. To demonstrate the viability and effectiveness of METTLE we have performed an experiment involving six commonly used clustering systems. Our experiment has shown that, guided by user-defined MR-based adequacy criteria, end users are able to assess, validate, and select appropriate clustering systems in accordance with their own specific needs. Our investigation has also yielded insightful understanding and interpretation of the behavior of the machine learning systems from an end-user software engineering's perspective, rather than a designer's or implementor's perspective, who normally adopts a theoretical approach.
BibTeX
@misc{zhang2018validation,
  author = {Zhiyi Zhang and Xiaoyuan Xie and Tsong Yueh Chen and Yang Liu and Baowen Xu},
  title = {{A Validation and Quality Assessment Method with Metamorphic Relations for Unsupervised Machine Learning Software}},
  year = {2018},
  eprint = {1807.10453},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.10453},
}
Figure