Low-rank doubly stochastic matrix decomposition for cluster analysis
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2016-10-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
25
Series
Journal of Machine Learning Research, Volume 17
Abstract
Cluster analysis by nonnegative low-rank approximations has experienced a remarkable progress in the past decade. However, the majority of such approximation approaches are still restricted to nonnegative matrix factorization (NMF) and su er from the following two drawbacks: 1) they are unable to produce balanced partitions for large-scale manifold data which are common in real-world clustering tasks; 2) most existing NMF-type clustering methods cannot automatically determine the number of clusters. We propose a new low-rank learning method to address these two problems, which is beyond matrix factorization. Our method approximately decomposes a sparse input similarity in a normalized way and its objective can be used to learn both cluster assignments and the number of clusters. For efficient optimization, we use a relaxed formulation based on Data-Cluster-Data random walk, which is also shown to be equivalent to low-rank factorization of the doublystochastically normalized cluster incidence matrix. The probabilistic cluster assignments can thus be learned with a multiplicative majorization-minimization algorithm. Experimental results show that the new method is more accurate both in terms of clustering large-scale manifold data sets and of selecting the number of clusters.Description
Keywords
Cluster analysis, Doubly stochastic matrix, Manifold, Multiplicative updates, Probabilistic relaxation
Other note
Citation
Yang , Z , Corander , J & Oja , E 2016 , ' Low-rank doubly stochastic matrix decomposition for cluster analysis ' , Journal of Machine Learning Research , vol. 17 . < http://www.jmlr.org/papers/volume17/15-549/15-549.pdf >
