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:
- Object Order: Shuffling data point sequences.
- Distinctness: Shrinking clusters or mirroring datasets.
- Density: Adding points near cluster centers or boundaries.
- Attributes: Adding informative or removing redundant features.
- Coordinate Systems: Rotating or scaling axes.
- 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