Gaussian model-based partitioning using iterated local search.

Area of Science:

• Computational statistics
• Data mining
• Machine learning

Background:

• Gaussian model-based partitioning offers an alternative to K-means clustering.
• Existing methods struggle with computationally demanding criteria for complex cluster conditions (elliptical shapes, varying orientations, unequal sizes).
• Traditional multiple-restart (multistart) heuristics are less effective for these demanding criteria.

Purpose of the Study:

• To introduce and evaluate an Iterated Local Search (ILS) approach for discrete optimization in model-based partitioning.
• To compare the performance of ILS, multistart, and hybrid multistart-ILS procedures.
• To assess these methods using a general model-based criterion without cluster size or covariance structure restrictions.

Main Methods:

• Implementation of Iterated Local Search (ILS) for combinatorial data analysis.
• Comparison of multistart, ILS, and hybrid multistart-ILS algorithms.
• Minimization of a general model-based criterion across 23 diverse classification datasets.
• Constrained time limit of 10 minutes for all tested methods.

Main Results:

• ILS and hybrid multistart-ILS heuristics generally achieved superior criterion function values compared to the multistart approach.
• The performance difference was observed within a strict 10-minute time constraint.
• Significant differences in obtained data partitions were frequently linked to improvements in criterion function values.

Conclusions:

• Iterated Local Search (ILS) provides a more effective heuristic strategy for model-based partitioning than traditional multistart methods.
• Hybrid ILS approaches further enhance partitioning performance.
• These findings are crucial for efficient and accurate clustering of complex, real-world datasets.