Spectral clustering with inconsistent advice

ABSTRACT

Clustering with advice (often known as constrained clustering) has been a recent focus of the data mining community. Success has been achieved incorporating advice into the k-means and spectral clustering frameworks. Although the theory community has explored inconsistent advice, it has not yet been incorporated into spectral clustering. Extending work of De Bie and Cristianini, we set out a framework for finding minimum normalised cuts, subject to inconsistent advice.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: Asuncion, A., & Newman, D. (2007). UCI machine learning repository.
• 3: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 4: Tom Coleman , James Saunderson , Anthony Wirth, A Local-Search 2-Approximation for 2-Correlation-Clustering, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_26]
• 5: Tijl De Bie , Nello Cristianini, Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems, The Journal of Machine Learning Research, 7, p.1409-1436, 12/1/2006
• 6: De Bie, T., Suykens, J., & De Moor, B. (2004). Learning from general label constraints. Joint IAPR International Workshops on Structural, Syntactic, and Statistical Pattern Recognition, 671--679.
• 7: Michel X. Goemans, Semidefinite programming in combinatorial optimization, Mathematical Programming: Series A and B, v.79 n.1-3, p.143-161, Oct. 1, 1997 [doi>10.1007/BF02614315]
• 8: Kamvar, S., Klein, D., & Manning, C. (2003). Spectral learning. Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-2003), 561--566.
• 9: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 10: Kiri Wagstaff , Claire Cardie, Clustering with Instance-level Constraints, Proceedings of the Seventeenth International Conference on Machine Learning, p.1103-1110, June 29-July 02, 2000
• 11: Xing, E., & Jordan, M. (2003). On Semidefinite Relaxation for Normalized K-cut and Connections to Spectral Clustering. Computer Science Division, University of California.
• 12: Xing, E., Ng, A., Jordan, M., & Russell, S. (2003). Distance metric learning, with application to clustering with side-information. Advances in Neural Information Processing Systems, 15, 505--512.
• 13: Yu, S., & Shi, J. (2001). Grouping with Bias. Carnegie Mellon University, the Robotics Institute.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  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