Active semi-supervised fuzzy clustering for image database categorization

ABSTRACT

We consider data clustering problems where a limited amount of high-level semantic information, in the form of pairwise must-link and cannot-link constraints, can be acquired from the user. This form of supervision will guide the categorization of image databases in order to provide overviews that fit better user expectations. We propose here an effective semi-supervised clustering algorithm, Active Fuzzy Constrained Clustering (AFCC), that minimizes a competitive agglomeration-based cost function with fuzzy terms corresponding to pairwise constraints provided by the user. In order to minimize the amount of constraints required, we define an active mechanism for the selection of candidates for constraints. The comparisons performed on a simple benchmark and on a ground truth image database show that with AFCC the results of clustering can be significantly improved with few constraints, making this semi-supervised approach an attractive alternative in the categorization of image databases.

REFERENCES

• 1: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 2: Sugato Basu , Arindam Banerjee , Raymond J. Mooney, Semi-supervised Clustering by Seeding, Proceedings of the Nineteenth International Conference on Machine Learning, p.27-34, July 08-12, 2002
• 3: S. Basu, M. Bilenko, and R. J. Mooney. Comparing and unifying search-based and similarity-based approaches to semi-supervised clustering. In Proceedings of the ICML-2003 Workshop on the Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining, pages 42--49, Washington, DC, August 2004.
• 4: N. Boujemaa, J. Fauqueur, M. Ferecatu, F. Fleuret, V. Gouet, B. L. Saux, and H. Sahbi. Ikona: Interactive generic and specific image retrieval. In Proceedings of the International workshop on Multimedia Content-Based Indexing and Retrieval (MMCBIR'2001), pages 25--28, 2001.
• 5: D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 4:129--145, 1996.
• 6: A. Demiriz, K. Bennett, and M. Embrechts. Semi-supervised clustering using genetic algorithms. In C. H. D. et al., editor, Intelligent Engineering Systems Through Artificial Neural Networks 9, pages 809--814. ASME Press, 1999.
• 7: Marin Ferecatu , Michel Crucianu , Nozha Boujemaa, Retrieval of difficult image classes using svd-based relevance feedback, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA [doi>10.1145/1026711.1026716]
• 8: H. Frigui and R. Krishnapuram. Clustering by competitive agglomeration. Pattern Recognition, 30(7):1109--1119, 1997.
• 9: I. Gath , A. B. Gev, Unsupervised Optimal Fuzzy Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.7, p.773-780, July 1989 [doi>10.1109/34.192473 ]
• 10: N. Grira, M. Crucianu, and N. Boujemaa. Unsupervised and semi-supervised clustering: a brief survey. In A Review of Machine Learning Techniques for Processing Multimedia Content. Report of the MUSCLE European Network of Excellence, July 2004.
• 11: N. Grira, M. Crucianu, and N. Boujemaa. Semi-supervised fuzzy clustering with pairwise-constrained competitive agglomeration. In The IEEE International Conference on Fuzzy Systems, Fuzz'IEEE 2005, pages 80--86, May 2005.
• 12: Thomas Hofmann , Joachim M. Buhmann, Active data clustering, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.528-534, July 1998, Denver, Colorado, United States
• 13: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 14: 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

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
image database categorization, pairwise constraints, semi-supervised clustering