A rate-distortion one-class model and its applications to clustering

ABSTRACT

In one-class classification we seek a rule to find a coherent subset of instances similar to a few positive examples in a large pool of instances. The problem can be formulated and analyzed naturally in a rate-distortion framework, leading to an efficient algorithm that compares well with two previous one-class methods. The model can be also be extended to remove background clutter in clustering to improve cluster purity.

REFERENCES

• 1: Ron Bekkerman , Andrew McCallum, Disambiguating Web appearances of people in a social network, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060813]
• 2: Asa Ben-Hur , David Horn , Hava T. Siegelmann , Vladimir Vapnik, Support vector clustering, The Journal of Machine Learning Research, 2, 3/1/2002
• 3: Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: Koby Crammer , Gal Chechik, A needle in a haystack: local one-class optimization, Proceedings of the twenty-first international conference on Machine learning, p.26, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015399]
• 6: Crammer, K., & Singer, Y. (2003). Learning algorithms for enclosing points in bregmanian spheres. COLT 16.
• 7: Gunjan Gupta , Joydeep Ghosh, Bregman Bubble Clustering: A Robust, Scalable Framework for Locating Multiple, Dense Regions in Data, Proceedings of the Sixth International Conference on Data Mining, p.232-243, December 18-22, 2006 [doi>10.1109/ICDM.2006.32]
• 8: Lashkari, D., & Golland, P. (2008). Convex clustering with exemplar-based models. NIPS.
• 9: Schölkopf, B., Burges, C., & Vapnik, V. (1995). Extracting support data for a given task. KDD 1.
• 10: Bernhard Schölkopf , John C. Platt , John C. Shawe-Taylor , Alex J. Smola , Robert C. Williamson, Estimating the Support of a High-Dimensional Distribution, Neural Computation, v.13 n.7, p.1443-1471, July 2001 [doi>10.1162/089976601750264965]
• 11: Slonim, N. (2003). The information bottleneck: Theory and applications. Doctoral dissertation, Hebrew University.
• 12: Noam Slonim , Nir Friedman , Naftali Tishby, Unsupervised document classification using sequential information maximization, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564401]
• 13: Slonim, N., & Weiss, Y. (2002). Maximum likelihood and the information bottleneck. NIPS.
• 14: Tax, D., & Duin, R. (1999). Data domain description using support vectors. ESANN (pp. 251--256).
• 15: Tishby, N., Pereira, F., & Bialek, W. (1999). The information bottleneck method. 37th Allerton Conference on Communication, Control, and Computing. Allerton House, Illinois.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
  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