Soft large margin clustering

Motivated by the successes of large margin principle in classification learning, the maximum margin clustering method (MMC) received intensive attention recently. It seeks a decision function and cluster labels for data simultaneously such that a supervised SVM trained on the label-assigned data could achieve the maximum margin. MMC assigns a unique cluster label for each instance. However, in real applications, the data distributions from different clusters are usually overlapped, and thus an instance might belong to multiple clusters with certain probabilities. Several soft clustering methods, which make use of soft membership assignment, have been developed in literature and lead to better data partition than their label-assignment counterparts. It motivates us to develop a novel Soft Large Margin Clustering (SLMC for short hereafter) method. SLMC enjoys the advantages of both MMC and the soft clustering methods, i.e., on one hand, it possesses a decision function with the maximal margin between clusters, and on the other hand, it accomplishes soft assignments for each instance to individual clusters to capture the nature of data structure. Its algorithmic implementation follows an alternating iterative strategy, in which each step in the iteration generates a closed-form solution, and the convergence of the whole iteration process can be theoretically guaranteed. Experiments on both synthetic and real datasets verify the effectiveness of SLMC.