Linear time maximum margin clustering.

Area of Science:

• Machine Learning
• Data Mining
• Computational Statistics

Background:

• Maximum Margin Clustering (MMC) extends Support Vector Machine (SVM) principles to unsupervised learning.
• Traditional MMC formulations as nonconvex integer programming are computationally intensive and difficult to solve.
• Existing methods like semidefinite programming (SDP) and alternating optimization are time-consuming for large datasets.

Purpose of the Study:

• To propose an efficient and accurate algorithm for Maximum Margin Clustering (MMC) applicable to large-scale datasets.
• To address the computational limitations of existing MMC methods.

Main Methods:

• Introduced a Cutting Plane Maximum Margin Clustering (CPMMC) algorithm.
• Decomposed the nonconvex MMC problem into a series of convex subproblems using the constrained concave-convex procedure (CCCP).
• Employed the cutting plane algorithm to solve each convex subproblem.

Main Results:

• The CPMMC algorithm achieves convergence in O(sn) time, where n is the number of samples and s is the data sparsity.
• Guaranteed accuracy is demonstrated for the CPMMC algorithm.
• A multiclass version of the CPMMC algorithm was successfully derived.

Conclusions:

• The proposed CPMMC algorithm significantly outperforms existing MMC methods in both efficiency and accuracy on real-world datasets.
• CPMMC offers a practical solution for applying maximum margin clustering to large-scale machine learning problems.