Nonnegative spectral clustering with discriminative regularization

Publication Type:
Conference Proceeding
Proceedings of the National Conference on Artificial Intelligence, 2011, 1 pp. 555 - 560
Issue Date:
Filename Description Size
3681-16339-1-PB.pdfPublished version541.94 kB
Adobe PDF
Full metadata record
Clustering is a fundamental research topic in the field of data mining. Optimizing the objective functions of clustering algorithms, e.g. normalized cut and k-means, is an NP-hard optimization problem. Existing algorithms usually relax the elements of cluster indicator matrix from discrete values to continuous ones. Eigenvalue decomposition is then performed to obtain a relaxed continuous solution, which must be discretized. The main problem is that the signs of the relaxed continuous solution are mixed. Such results may deviate severely from the true solution, making it a nontrivial task to get the cluster labels. To address the problem, we impose an explicit nonnegative constraint for a more accurate solution during the relaxation. Besides, we additionally introduce a discriminative regularization into the objective to avoid overfitting. A new iterative approach is proposed to optimize the objective. We show that the algorithm is a general one which naturally leads to other extensions. Experiments demonstrate the effectiveness of our algorithm. Copyright © 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.
Please use this identifier to cite or link to this item: