Abstract
We consider the problem of clustering data into k ≥ 2 clusters given complex relations — going beyond pairwise — between the data points. The complex n-wise relations are modeled by an n-way array where each entry corresponds to an affinity measure over an n-tuple of data points. We show that a probabilistic assignment of data points to clusters is equivalent, under mild conditional independence assumptions, to a super-symmetric non-negative factorization of the closest hyper-stochastic version of the input n-way affinity array. We derive an algorithm for finding a local minimum solution to the factorization problem whose computational complexity is proportional to the number of n-tuple samples drawn from the data. We apply the algorithm to a number of visual interpretation problems including 3D multi-body segmentation and illumination-based clustering of human faces.
Chapter PDF
Similar content being viewed by others
References
Agrawal, S., Lim, J., Zelnik-Manor, L., Perona, P., Kriegman, D., Belongie, S.: Beyond pairwise clustering. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2005)
Alpert, C.J., Kahng, A.B.: Recent directions in netlist partitioning. The VLSI Journal 19(1-2), 1–81 (1995)
Fiduccia, C.M., Mattheyses, R.M.: A linear time heuristic for improving network partitions. In: Proc. of the 19th IEEE Design Automation Conference, pp. 175–181 (1982)
Gelfand, I.M., Karpanov, M.M., Zelevinsky, A.V.: Discriminants, Resultants and multidimensional determinants. Birkhauser, Boston (1994)
Govindu, V.M.: A tensor decomposition for geometric grouping and segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2005)
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal 49(2) (1970)
Lee, D., Seung, H.: Learning the parts of objects by non-negative matrix factorization. Nature 401, 788–791 (1999)
Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximate algorithms. In: Proceedings Symposium on Foundations of Comp. Sci (1988)
Longuet-Higgins, H.C.: A computer algorithm for reconstructing a scene from two projections. Nature 293, 133–135 (1981)
Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Proceedings of the conference on Neural Information Processing Systems, NIPS (2001)
Perona, P., Freeman, W.T.: A factorization approach to grouping. In: Burkhardt, H.-J., Neumann, B. (eds.) ECCV 1998. LNCS, vol. 1406, pp. 655–670. Springer, Heidelberg (1998)
Rodriguez, J.A.: On the Laplacian eigenvalues and metric parameters of hypergraphs. Linear and Multilinear Algebra 50(1), 1–14 (2002)
Shashua, A.: Illumination and view position in 3D visual recognition. In: Proceedings of the conference on Neural Information Processing Systems (NIPS), Denver, CO (December 1991)
Shashua, A., Hazan, T.: Non-negative tensor factorization with applications to statistics and computer vision. In: Proceedings of the International Conference on Machine Learning, ICML (2005)
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8) (2000)
Sinkhorn, R.: A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35, 876–879 (1964)
Ullman, S., Basri, R.: Recognition by linear combination of models. IEEE Transactions on Pattern Analysis and Machine Intelligence 13, 992–1006 (1991)
Vidal, R., Ma, Y., Soatto, S., Sastry, S.: Two-view multibody structure from motion. International Journal of Computer Vision (2004)
Wolf, L., Shashua, A.: Two-body segmentation from two perspective views. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Hawaii (December 2001)
Zass, R., Shashua, A.: A unifying approach to hard and probabilistic clustering. In: Proceedings of the International Conference on Computer Vision, Beijing, China (October 2005)
Zhou, D., Huang, J., Scholkopf, B.: Beyond pairwise classification and clustering using hypergraphs. Technical report, Max Planck Institute for Biol. Cybernetics, TR-143 (August 2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shashua, A., Zass, R., Hazan, T. (2006). Multi-way Clustering Using Super-Symmetric Non-negative Tensor Factorization. In: Leonardis, A., Bischof, H., Pinz, A. (eds) Computer Vision – ECCV 2006. ECCV 2006. Lecture Notes in Computer Science, vol 3954. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11744085_46
Download citation
DOI: https://doi.org/10.1007/11744085_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33838-3
Online ISBN: 978-3-540-33839-0
eBook Packages: Computer ScienceComputer Science (R0)