Simultaneous Clustering and Model Selection: Algorithm, Theory and Applications
| Autor: | Loong-Fah Cheong, Kim-Chuan Toh, Zhuwen Li, Shuoguang Yang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Applied Mathematics Model selection Constrained clustering 02 engineering and technology 01 natural sciences 010104 statistics & probability Computational Theory and Mathematics Artificial Intelligence Robustness (computer science) Outlier 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Stochastic optimization Computer Vision and Pattern Recognition Imperfect 0101 mathematics Mathematical structure Cluster analysis Software Mathematics |
| Zdroj: | IEEE Transactions on Pattern Analysis and Machine Intelligence. 40:1964-1978 |
| ISSN: | 1939-3539 0162-8828 |
| DOI: | 10.1109/tpami.2017.2739147 |
| Popis: | While clustering has been well studied in the past decade, model selection has drawn much less attention due to the difficulty of the problem. In this paper, we address both problems in a joint manner by recovering an ideal affinity tensor from an imperfect input. By taking into account the relationship of the affinities induced by the cluster structures, we are able to significantly improve the affinity input, such as repairing those entries corrupted by gross outliers. More importantly, the recovered ideal affinity tensor also directly indicates the number of clusters and their membership, thus solving the model selection and clustering jointly. To enforce the requisite global consistency in the affinities demanded by the cluster structure, we impose a number of constraints, specifically, among others, the tensor should be low rank and sparse, and it should obey what we call the rank-1 sum constraint. To solve this highly non-smooth and non-convex problem, we exploit the mathematical structures, and express the original problem in an equivalent form amenable for numerical optimization and convergence analysis. To scale to large problem sizes, we also propose an alternative formulation, so that those problems can be efficiently solved via stochastic optimization in an online fashion. We evaluate our algorithm with different applications to demonstrate its superiority, and show it can adapt to a large variety of settings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|