On the Consistency and Large-Scale Extension of Multiple Kernel Clustering

Area of Science:

• Machine Learning
• Data Mining
• Computational Statistics

Background:

• Multiple Kernel Clustering (MKC) algorithms face challenges with theoretical analysis of kernel weight consistency and computational complexity for large datasets.
• Existing MKC methods often lack rigorous theoretical guarantees, particularly regarding the convergence and stability of learned kernel weights.
• High computational complexity limits the applicability of current MKC algorithms to large-scale datasets, hindering practical adoption.

Purpose of the Study:

• To provide theoretical analysis for the consistency of kernel weights in Multiple Kernel k-Means (SimpleMKKM).
• To develop a computationally efficient extension of MKC algorithms for handling large-scale datasets.
• To validate the theoretical findings and practical performance of the proposed methods through empirical evaluation.

Main Methods:

• Consistency analysis of SimpleMKKM kernel weights, establishing an upper bound for the difference between learned and expected weights (~O(1/√n)).
• Derivation of the excess clustering risk based on the consistency analysis.
• Modification of SimpleMKKM by replacing eigen decomposition with Singular Value Decomposition (SVD) to reduce computational complexity to O(n).

Main Results:

• Established theoretical bounds on kernel weight consistency for SimpleMKKM, providing a foundation for understanding its behavior.
• Demonstrated that the SVD-based extension significantly reduces computational complexity, enabling scalability to large datasets.
• Experimental results confirm the superiority of the proposed SVD-based MKC method over existing approaches in terms of both theoretical properties and practical performance.

Conclusions:

• The proposed theoretical analysis offers new insights into the consistency of kernel weights in MKC algorithms.
• The SVD-based MKC method effectively addresses the scalability issue, making advanced clustering techniques applicable to larger datasets.
• The combined theoretical and practical advancements position the new method as a promising solution for complex clustering tasks.