nips nips2010 nips2010-166 nips2010-166-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Kiyohito Nagano, Yoshinobu Kawahara, Satoru Iwata
Abstract: A number of objective functions in clustering problems can be described with submodular functions. In this paper, we introduce the minimum average cost criterion, and show that the theory of intersecting submodular functions can be used for clustering with submodular objective functions. The proposed algorithm does not require the number of clusters in advance, and it will be determined by the property of a given set of data points. The minimum average cost clustering problem is parameterized with a real variable, and surprisingly, we show that all information about optimal clusterings for all parameters can be computed in polynomial time in total. Additionally, we evaluate the performance of the proposed algorithm through computational experiments. 1
[1] W. H. Cunningham: Optimal attack and reinforcement of a network. Journal of the ACM 32 (1985), pp. 549–561.
[2] R. P. Dilworth: Dependence relations in a semimodular lattice. Duke Mathematical Journal, 11 (1944), pp. 575–587.
[3] J. Edmonds: Submodular functions, matroids, and certain polyhedra. Combinatorial Structures o and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Sch¨ nheim, eds., Gordon and Breach, 1970, pp. 69–87.
[4] S. Fujishige: Submodular Functions and Optimization (Second Edition). Elsevier, Amsterdam, 2005.
[5] O. Goldschmidt and D. S. Hochbaum: A polynomial algorithm for the k-cut problem for fixed k, Mathematics of Operations Research, 19 (1994), pp. 24–37.
[6] S. Iwata: Submodular function minimization. Mathematical Programming, 112 (2008), pp. 45–64.
[7] V. Kolmogorov: A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica 56, pp. 394-412.
[8] Y. Kawahara, K. Nagano, and Y. Okamoto: Submodular fractional programming for balanced clustering. Pattern Recognition Letters, to appear.
[9] M. Narasimhan and J. Bilmes: Local search for balanced submodular clusterings. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 981–986.
[10] M. Narasimhan, N. Jojic, and J. Bilmes: Q-clustering. In Advances in Neural Information Processing Systems, 18 (2006), pp. 979–986. Cambridge, MA: MIT Press.
[11] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2:849–856, 2002.
[12] K. Okumoto, T. Fukunaga, and H. Nagamochi: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878, 2009, pp. 55–64.
[13] M. Queyranne: Minimizing symmetric submodular functions, Mathematical Programming, 82 (1998), pp. 3–12.
[14] A. Schrijver: Combinatorial Optimization — Polyhedra and Efficiency. Springer-Verlag, 2003.
[15] U. von Luxburg: Tutorial on spectral clustering. Statistics and Computing 17 (2007), pp. 395– 416.
[16] L. Xu, J. Neufeld, B. Larson, and D. Schuurmans. Maximum margin clustering. Advances in neural information processing systems, 17:1537–1544, 2005.
[17] L. Zhao, H. Nagamochi, and T. Ibaraki: Approximating the minimum k-way cut in a graph via minimum 3-way cuts. Journal of Combinatorial Optimization, 5 (2001), pp. 397–410.
[18] L. Zhao, H. Nagamochi, and T. Ibaraki: A unified framework for approximating multiway partition problems. In Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC 2001), LNCS 2223, 2001, pp. 682–694. 9