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: Rie Kubota Ando , Tong Zhang, Two-view feature generation model for semi-supervised learning, Proceedings of the 24th international conference on Machine learning, p.25-32, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273500]
• 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: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 6: Spencer Charles Brubaker , Santosh Vempala, Isotropic PCA and Affine-Invariant Clustering, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.551-560, October 25-28, 2008 [doi>10.1109/FOCS.2008.48]
• 7: Chaudhuri, K., & Rao, S. (2008). Learning mixtures of distributions using correlations and independence. Conf. On Learning Thy. (pp. 9--20).
• 8: Sanjoy Dasgupta, Learning Mixtures of Gaussians, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.634, October 17-18, 1999
• 9: Sanjoy Dasgupta , Leonard J. Schulman, A Two-Round Variant of EM for Gaussian Mixtures, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.152-159, June 30-July 03, 2000
• 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: Mark Rudelson , Roman Vershynin, Sampling from large matrices: An approach through geometric functional analysis, Journal of the ACM (JACM), v.54 n.4, p.21-es, July 2007 [doi>10.1145/1255443.1255449]
• 15: Sanderson, C. (2008). Biometric person recognition: Face, speech and fusion. VDM-Verlag.
• 16: Santosh Vempala , Grant Wang, A Spectral Algorithm for Learning Mixtures of Distributions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.113, November 16-19, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory