Research On Maximum Margin Clustering Based On Indefinite Kernel

Indefinite kernels have attracted more and more attentions in machine learning due to its wider application scope than usual positive definite kernels, such as in gene identification and object recognition. Recently, many indefinite kernel methods have been proposed to solve classification problems and achieved much better performance. However, the research about indefinite kernel clustering is relatively scarce. Furthermore, existing clustering methods are mainly designed based on positive definite kernels which are incapable in indefinite kernel scenarios. In this paper, we will focus on the problem of indefinite kernel clustering. In view of the excellent performance of indefinite kernel classification methods, we aim to utilize these methods to direct indefinite kernel clustering. Consequently, based on the state-of-the-art maximum margin clustering (MMC) model, we propose a novel algorithm termed as indefinite kernel maximum margin clustering (IKMMC). IKMMC tries to find a proxy positive definite kernel to approximate the original indefinite one and thus embeds a new F-norm regularizer in the objective function to measure the diversity of the two kernels, which can be further optimized by an iterative approach. Concretely, at each iteration, given a set of initial class labels, IKMMC firstly transforms the clustering problem into a classification one solved by indefinite kernel support vector machine (IKSVM) with an extra class balance constraint and then the obtained prediction labels will be used as the new input class labels at next iteration until the error rate of prediction is smaller than a pre-specified tolerance. Finally, IKMMC utilizes the prediction labels at the last iteration as the expected indices of clusters. Moreover, we further extend IKMMC from binary clustering problems to more complex multi-class scenarios. Experimental results have shown the superiority of our algorithms.