Fast evolutionary maximum margin clustering

ABSTRACT

The maximum margin clustering approach is a recently proposed extension of the concept of support vector machines to the clustering problem. Briefly stated, it aims at finding an optimal partition of the data into two classes such that the margin induced by a subsequent application of a support vector machine is maximal. We propose a method based on stochastic search to address this hard optimization problem. While a direct implementation would be infeasible for large data sets, we present an efficient computational shortcut for assessing the "quality" of intermediate solutions. Experimental results show that our approach outperforms existing methods in terms of clustering accuracy.

REFERENCES

• 1: Adankon, M. M., & Cheriet, M. (2007). Learning semi-supervised svm with genetic algorithm. Proc. International Joint Conference on Neural Networks (pp. 1825--1830).
• 2: Bach, F., & Harchaoui, Z. (2008). Diffrac: a discriminative and flexible framework for clustering. Adv. in Neural Information Proc. Systems 20 (pp. 49--56).
• 3: Hans-Georg Beyer , Hans-Paul Schwefel, Evolution strategies –A comprehensive introduction, Natural Computing: an international journal, v.1 n.1, p.3-52, May 2002 [doi>10.1023/A:1015059928466]
• 4: Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 5: Golub, G. H., & Van Loan, C. (1989). Matrix computations. Baltimore and London: Johns Hopkins University Press. Second edition.
• 6: Hartigan, J. A., & Wong, M. A. (1979). A K-means clustering algorithm. Applied Statistics, 28, 100--108.
• 7: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 8: Rifkin, R., Yeo, G., & Poggio, T. (2003). Regularized least-squares classification. In Adv. in learning theory: Methods, models and applications. IOS Press.
• 9: Ryan Michael Rifkin , Tomaso Poggio, Everything old is new again: a fresh look at historical approaches in machine learning, Massachusetts Institute of Technology, 2002
• 10: Bernhard Schölkopf , Ralf Herbrich , Alex J. Smola, A Generalized Representer Theorem, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.416-426, July 16-19, 2001
• 11: Marcelo M. Silva , Thiago T. Maia , Antonio P. Braga, An evolutionary approach to Transduction in Support Vector Machines, Proceedings of the Fifth International Conference on Hybrid Intelligent Systems, p.329-334, December 06-09, 2005 [doi>10.1109/ICHIS.2005.21]
• 12: Ingo Steinwart , Andreas Christmann, Support Vector Machines, Springer Publishing Company, Incorporated, 2008
• 13: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 14: Valizadegan, H., & Jin, R. (2007). Generalized maximum margin clustering and unsupervised kernel learning. Adv. in Neural Information Proc. Systems 19 (pp. 1417--1424).
• 15: Vapnik, V. (1998). Statistical learning theory. New York: Wiley.
• 16: Xu, L., Neufeld, J., Larson, B., & Schuurmans, D. (2005). Maximum margin clustering. Adv. in Neural Information Proc. Systems 17 (pp. 1537--1544).
• 17: Xu, L., & Schuurmans, D. (2005). Unsupervised and semi-supervised multi-class support vector machines. Proc. National Conference on Artificial Intelligence (pp. 904--910).
• 18: Kai Zhang , Ivor W. Tsang , James T. Kwok, Maximum margin clustering made practical, Proceedings of the 24th international conference on Machine learning, p.1119-1126, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273637]
• 19: Zhao, B., Wang, F., & Zhang, C. (2008a). Efficient maximum margin clustering via cutting plane algorithm. Proc. SIAM International Conference on Data Mining (pp. 751--762).
• 20: Bin Zhao , Fei Wang , Changshui Zhang, Efficient multiclass maximum margin clustering, Proceedings of the 25th international conference on Machine learning, p.1248-1255, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390313]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  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

General Terms:
Algorithms, Design, Performance, Theory