jmlr jmlr2013 jmlr2013-100 jmlr2013-100-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raman Arora, Maya R. Gupta, Amol Kapila, Maryam Fazel
Abstract: For similarity-based clustering, we propose modeling the entries of a given similarity matrix as the inner products of the unknown cluster probabilities. To estimate the cluster probabilities from the given similarity matrix, we introduce a left-stochastic non-negative matrix factorization problem. A rotation-based algorithm is proposed for the matrix factorization. Conditions for unique matrix factorizations and clusterings are given, and an error bound is provided. The algorithm is particularly efficient for the case of two clusters, which motivates a hierarchical variant for cases where the number of desired clusters is large. Experiments show that the proposed left-stochastic decomposition clustering model produces relatively high within-cluster similarity on most data sets and can match given class labels, and that the efficient hierarchical variant performs surprisingly well. Keywords: clustering, non-negative matrix factorization, rotation, indefinite kernel, similarity, completely positive
R. Arora. Group Theoretical Methods in Signal Processing: Learning Similarities, Transformations and Invariants. PhD thesis, Univ. of Wisconsin-Madison, 2009a. R. Arora. On learning rotations. Advances in Neural Information Processing Systems (NIPS), 2009b. R. Arora and K. Livescu. Kernel CCA for multi-view learning of acoustic features using articulatory measurements. In Symp. on Machine Learning in Speech and Language Processing, 2012. R. Arora and K. Livescu. Multi-view CCA-based acoustic features for phonetic recognition across speakers and domains. In Int. Conf. on Acoustics, Speech, and Signal Processing, 2013. R. Arora and W. A. Sethares. An efficient and stable algorithm for learning rotations. In Proc. Intl. Conf. Pattern Recognition, 2010. 1743 A RORA , G UPTA , K APILA AND FAZEL R. Arora, M. R. Gupta, A. Kapila, and M. Fazel. Clustering by left-stochastic matrix factorization. Proc. Intl. Conf. Machine Learning (ICML), 2011. R. Arora, A. Cotter, K. Livescu, and N. Srebro. Stochastic optimization for PCA and PLS. In 50th Annual Allerton Conference on Communication, Control, and Computing, 2012. A. Berman and N. Shaked-Monderer. Completely Positive Matrices. World Scientific, 2003. M. W. Berry, M. Browne, A. N. Langville, V. P. Pauca, and R. J. Plemmons. Algorithms and applications for approximate nonnegative matrix factorization. Computational Statistics and Data Analysis, 52(1):155 – 173, 2007. M. Biggs, A. Ghodsi, and S. Vavasis. Nonnegative matrix factorization via rank-one downdate. Proc. Intl. Conf. Machine Learning (ICML), 2008. M. Brown and S. Susstrunk. Multispectral SIFT for scene category recognition. Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), 2011. J. Bruna and S. Mallat. Classification with scattering operators. Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), 2011. L. Cazzanti, M. R. Gupta, and S. Srivastava. Fusing similarities and Euclidean features with generative classifiers. In Proc. IEEE Conf. on Information Fusion (FUSION), 2009. Y. Chen, E. K. Garcia, M. R. Gupta, L. Cazzanti, and A. Rahimi. Similarity-based classification: Concepts and algorithms. JMLR, 2009a. Y. Chen, M. R. Gupta, and B. Recht. Learning kernels from indefinite similarities. In Proc. Intl. Conf. Machine Learning (ICML), 2009b. N. Cristianini, J. Shawe-Taylor, A. Elisseeff, and J. Kandola. On kernel target alignment. Advances in Neural Information Processing Systems (NIPS), 2001. P. Deuflhard and M. Weber. Robust Perron cluster analysis in conformation dynamics. Linear Algebra and Its Applications, 398:161–184, 2005. C. Ding, X. He, and H. D. Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. SIAM Conf. Data Mining, 2005. C. Ding, T. Li, and M. I. Jordan. Convex and semi-nonnegative matrix factorizations. IEEE Trans. PAMI, 32, 2010. J. E. Driskell and T. McDonald. Identification of incomplete networks. Technical Report of Florida Maxima Corporation, 2008. C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936. I. F¨ rber, S. G¨ nnemann, H.-P. Kriegel, P. Kr¨ ger, E. M¨ ller, E. Schubert, T. Seidl, and A. Zimek. a u o u On using class-labels in evaluation of clusterings. Proc. ACM SIGKDD, 2010. 1744 S IMILARITY- BASED C LUSTERING S. Feng, H. Krim, and I. A. Kogan. 3D face recognition using Euclidean integral invariants signature. Proc. IEEE Workshop Statistical Signal Processing, 2007. E. Hanusa, D. Krout, and M. R. Gupta. Clutter rejection by clustering likelihood-based similarities. In Proc. IEEE Conf. on Information Fusion (FUSION), 2011. T. Hastie, R. Tibshirani, and J.Friedman. The Elements of Statistical Learning. Springer-Verlag, New York, 2nd edition, 2009. N.-D. Ho. Nonnegative Matrix Factorizations Algorithms and Applications. PhD thesis, Universite Catholique de Louvain, 2008. P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. JMLR, 5:1457–1469, 2004. L. Kaufman and P. J. Rousseeuw. Finding Groups in Data. Wiley Series in Applied Probability and Statistics. Wiley, 1990. H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83–97, 1955. G. R. G. Lanckriet, M. Deng, N. Cristianini, M. I. Jordan, and W. S. Noble. Kernel-based data fusion and its application to protein function prediction in yeast. In Proc. of the Pacific Symposium on Biocomputing, 2004. D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788–791, 1999. D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. Advances in Neural Information Processing Systems (NIPS), 2000. Y. Li and A. Ngom. NMF Toolbox Ver. 1.0. cs.uwindsor.ca/˜li11112c/nmf.html, 2011. P. MacNaughton-Smith, W.T. Williams, M. B. Dale, and L. G. Mockett. Dissimilarity analysis: A new technique of hierarchical sub-division. Nature, 202:1034–5, 1964. C. Michelot. A finite algorithm for finding the projection of a point onto the canonical simplex of Rn . J. Opt. Theory Appl., 50:195–200, 1986. J. K. Nelson and M. R. Gupta. An EM technique for multiple transmitter localization. 41st Conference on Information Science and Systems, pages 610–615, 2007. A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems (NIPS), 2002. D. Niu, J. G. Dy, and M. I. Jordan. Multiple non-redundant spectral clustering views. Proc. Intl. Conf. Machine Learning (ICML), 2010. P. Paatero. Least-squares formulation of robust non-negative factor analysis. Chemometrics and Intell. Lab. Sys., 37:23 – 35, 1997. 1745 A RORA , G UPTA , K APILA AND FAZEL P. Paatero. The multilinear engine: A table-driven, least squares program for solving multilinear problems, including the n-way parallel factor analysis model. J. Comp. Graph. Stat., 8(4):854– 888, 1999. P. Paatero and U. Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5:111–126, 1994. S. Philips, J. Pitton, and L. Atlas. Perceptual feature identification for active sonar echoes. Proc. IEEE OCEANS, 2006. S. Selim and M. A. Ismail. K-means type algorithms: a generalized convergence theorem and characterization of local optimality. IEEE Trans. PAMI, 6(1):81–87, 1984. G. W. Stewart. Matrix Algorithms, Volume I: Basic Decompositions. SIAM, 1998. U. von Luxburg. A tutorial on spectral clustering. Technical Report TR-149, Max Planck Institute for Biological Cybernetics, August 2006. M. Weber and S. Kube. Robust Perron cluster analysis for various applications in computational life science. Lecture Notes in Computer Science, 3695:55–66, 2005. M. Weber, W. Rungsarityotin, and A. Schliep. Perron cluster analysis and its connection to graph partitioning for noisy data. Zentrum Informationstechnik Berlin Report, 04-39, 2004. H. Zha, C. Ding, M. Gu, X. He, and H. Simon. Spectral relaxation for k-means clustering. Advances in Neural Information Processing Systems (NIPS), 2001. 1746