Multi-view clustering via canonical correlation analysis

ABSTRACT

Clustering data in high dimensions is believed to be a hard problem in general. A number of efficient clustering algorithms developed in recent years address this problem by projecting the data into a lower-dimensional subspace, e.g. via Principal Components Analysis (PCA) or random projections, before clustering. Here, we consider constructing such projections using multiple views of the data, via Canonical Correlation Analysis (CCA).

Under the assumption that the views are un-correlated given the cluster label, we show that the separation conditions required for the algorithm to be successful are significantly weaker than prior results in the literature. We provide results for mixtures of Gaussians and mixtures of log concave distributions. We also provide empirical support from audio-visual speaker clustering (where we desire the clusters to correspond to speaker ID) and from hierarchical Wikipedia document clustering (where one view is the words in the document and the other is the link structure).

References

1. Achlioptas, D., & McSherry, F. (2005). On spectral learning of mixtures of distributions. Conf. on Learning Thy (pp. 458--469).
2. Ando, R. K., & Zhang, T. (2007). Two-view feature generation model for semi-supervised learning. Int. Conf. on Machine Learning (pp. 25--32).
3. Arora, S., & Kannan, R. (2005). Learning mixtures of separated nonspherical Gaussians. Ann. Applied Prob., 15, 69--92.
4. Blaschko, M. B., & Lampert, C. H. (2008). Correlational spectral clustering. Conf. on Comp. Vision and Pattern Recognition.
5. Blum, A., & Mitchell, T. (1998). Combining labeled and unlabeled data with co-training. Conf. on Learning Thy. (pp. 92--100).
6. Brubaker, S. C., & Vempala, S. (2008). Isotropic PCA and affine-invariant clustering. Found. of Comp. Sci. (pp. 551--560).
7. Chaudhuri, K., & Rao, S. (2008). Learning mixtures of distributions using correlations and independence. Conf. On Learning Thy. (pp. 9--20).
8. Dasgupta, S. (1999). Learning mixtures of Gaussians. Found. of Comp. Sci. (pp. 634--644).
9. Dasgupta, S., & Schulman, L. (2000). A two-round variant of EM for Gaussian mixtures. Uncertainty in Art. Int. (pp. 152--159).
10. Davis, S. B., & Mermelstein, P. (1980). Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences. IEEE Trans. Acoustics, Speech, and Signal Proc., 28, 357--366.
11. Dunn, G., & Everitt, B. (2004). An introduction to math. taxonomy. Dover Books.
12. Kakade, S. M., & Foster, D. P. (2007). Multi-view regression via canonical correlation analysis. Conf. Learning Thy (pp. 82--96).
13. Kannan, R., Salmasian, H., & Vempala, S. (2005). The spectral method for general mixture models. Conf. on Learning Thy (pp. 444--457).
14. Rudelson, M., & Vershynin, R. (2007). Sampling from large matrices: An approach through geometric functional analysis. Jour. of ACM.
15. Sanderson, C. (2008). Biometric person recognition: Face, speech and fusion. VDM-Verlag.
16. Vempala, V., & Wang, G. (2002). A spectral algorithm for learning mixtures of distributions. Found. of Comp. Sci. (pp. 113--123).

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Supervised learning by classification

      • Unsupervised learning

        • Cluster analysis

    • Machine learning approaches

      • Classification and regression trees

      • Factorization methods

        • Canonical correlation analysis

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

      • Modeling methodologies

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Regression analysis