Genetic-guided semi-supervised clustering algorithm with instance-level constraints

ABSTRACT

Semi-supervised clustering with instance-level constraints is one of the most active research topics in the areas of pattern recognition, machine learning and data mining. Several recent studies have shown that instance-level constraints can significantly increase accuracies of a variety of clustering algorithms. However, instance-level constraints may split the search space of the optimal clustering solution into pieces, thus significantly compound the difficulty of the search task. This paper explores a genetic approach to solve the problem of semi-supervised clustering with instance-level constraints. In particular, a novel semi-supervised clustering algorithm with instance-level constraints, termed as the hybrid genetic-guided semi-supervised clustering algorithm with instance-level constraints (Cop-HGA), is proposed. Cop-HGA uses a hybrid genetic algorithm to perform the search task of a high quality clustering solution that is able to draw a good balance between predefined clustering criterion and available instance-level background knowledge. The effectiveness of Cop-HGA is confirmed by experimental results on several real data sets with artificial instance-level constraints.

REFERENCES

• 1: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 2: K. Wagstaff. Intelligent Clustering with Instance-Level Constraints. Department of Computer Science and Engineering, Cornell University, 2002.
• 3: M. Law. Clustering, Dimensionality Reduction, and Side Information. Department of Computer Science and Engineering, Michigan State University, 2006.
• 4: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 5: 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
• 6: Dan Klein , Sepandar D. Kamvar , Christopher D. Manning, From Instance-level Constraints to Space-Level Constraints: Making the Most of Prior Knowledge in Data Clustering, Proceedings of the Nineteenth International Conference on Machine Learning, p.307-314, July 08-12, 2002
• 7: Z. Lu and T.K. Leen. Semi-supervised learning with penalized probabilistic clustering. In Advances in Neural Information Processing Systems, 2005.
• 8: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 9: E.P. Xing, A. Y. Ng, M.I. Jordan, and S. Russell. Distance metrix learning with application to clustering with side-information. In Advances in Neural Information Processing Systems, pages 505--512, 2002.
• 10: S. Basu and I. Davidson. Clustering with constraints: Theory and practice. In ACM KDD2006 Tutorials, 2006.
• 11: Y. Hong and S. Kwong. Learning assignment order of instances for constrained k-means clustering algorithm. IEEE Transactions on System, Man and Cybernetics, Part B, Under Review.
• 12: Yi Hong , Sam Kwong , Hui Xiong , Qingsheng Ren, Data clustering using virtual population based incremental learning algorithm with similarity matrix encoding strategy, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389183]
• 13: C. Blake and C. Merz. UCI Machine Learning Repository. http://www.ics.uci.edu/mlearn/MLRepository.html, 1998.
• 14: W.M. Rand. Objective criterion for the evaluation of clustering methods. Journal of Americal Statistical Association, 66:846--850, 1970.
• 15: K. Krishna and M. Murty. Genetic k-means algorithm. IEEE Transactions on System, Man, and Cybernetics-Part B, 29:433--439, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms

Keywords:
genetic algorithms, semi-supervised clustering