A clustering framework based on subjective and objective validity criteria

ABSTRACT

Clustering, as an unsupervised learning process is a challenging problem, especially in cases of high-dimensional datasets. Clustering result quality can benefit from user constraints and objective validity assessment. In this article, we propose a semisupervised framework for learning the weighted Euclidean subspace, where the best clustering can be achieved. Our approach capitalizes on: (i) user constraints; and (ii) the quality of intermediate clustering results in terms of their structural properties. The proposed framework uses the clustering algorithm and the validity measure as its parameters. We develop and discuss algorithms for learning and tuning the weights of contributing dimensions and defining the “best” clustering obtained by satisfying user constraints. Experimental results on benchmark datasets demonstrate the superiority of the proposed approach in terms of improved clustering accuracy.

REFERENCES

• 1: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 3: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 4: Brigham S. Anderson , Andrew W. More , David Cohn, A Nonparametric Approach to Noisy and Costly Optimization, Proceedings of the Seventeenth International Conference on Machine Learning, p.17-24, June 29-July 02, 2000
• 5: Bar-Hillel, A., Hertz, T., Shental, N., and Weinshall, D. 2003. Learning distance function using equivalence relations. In Proceedings of the International Conference on Machine Learning (ICML).
• 6: 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]
• 7: Michael J. Berry , Gordon Linoff, Data Mining Techniques: For Marketing, Sales, and Customer Support, John Wiley & Sons, Inc., New York, NY, 1997
• 8: Mikhail Bilenko , Sugato Basu , Raymond J. Mooney, Integrating constraints and metric learning in semi-supervised clustering, Proceedings of the twenty-first international conference on Machine learning, p.11, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015360]
• 9: A. Blansché , P. Gançarski , J. J. Korczak, MACLAW: A modular approach for clustering with local attribute weighting, Pattern Recognition Letters, v.27 n.11, p.1299-1306, August 2006 [doi>10.1016/j.patrec.2005.07.027]
• 10: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 11: Cohn, D., Caruana, R., and McCallum, A. 2003. Semi-Supervised clustering with user feedback. Tech. Rep. TR2003-1892, Cornell University, Ithaca, NY.
• 12: Ester, M., Kriegel, H.-P., Sender, J., and Xu, X. 1997. Sensity-Connected sets and their application for trend detection in spatial databases. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 10--15.
• 13: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 14: Douglas H. Fisher, Knowledge Acquisition Via Incremental Conceptual Clustering, Machine Learning, v.2 n.2, p.139-172, September 1987 [doi>10.1023/A:1022852608280]
• 15: Frigui, H. and Nasraoui, O. 2004. Unsupervised learning of prototypes and attribute weights. Pattern Recogn. 37, 3, 943--952.
• 16: Gao, J., Tan, P.-N., and Cheng, H. 2005. Semi-Supervised fuzzy clustering with pairwise-constrained competitive agglomeration. In IEEE Conference on Fuzzy Systems.
• 17: M. Halkidi , D. Gunopulos , N. Kumar , M. Vazirgiannis , C. Domeniconi, A Framework for Semi-Supervised Learning Based on Subjective and Objective Clustering Criteria, Proceedings of the Fifth IEEE International Conference on Data Mining, p.637-640, November 27-30, 2005 [doi>10.1109/ICDM.2005.4]
• 18: Maria Halkidi , Michalis Vazirgiannis, Clustering Validity Assessment: Finding the Optimal Partitioning of a Data Set, Proceedings of the 2001 IEEE International Conference on Data Mining, p.187-194, November 29-December 02, 2001
• 19: Hinneburg, A. and Keim, D. 1998. An efficient approach toclustering in large multimedia databases with noise. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 58--65.
• 20: Hogg, R. and Craig, A. 1978. Introduction to Mathematical Statistics. Macmillan, New York.
• 21: Hubert, L. and Arabie, P. 1985. Comparing partitions. J. Classif.
• 22: 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]
• 23: Jing, L., Ng, M., and Huang, J. X. 2005. Subspace clustering of text documents with feature weighting k-means algorithm. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD). Advances in Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, vol. 3518. Springer, Berlin.
• 24: Brian Kulis , Sugato Basu , Inderjit Dhillon , Raymond Mooney, Semi-supervised graph clustering: a kernel approach, Proceedings of the 22nd international conference on Machine learning, p.457-464, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102409]
• 25: MacQueen, J. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the Symposium on Math, Statistics and Probability, University of California Press, Berkeley, CA, 281--297.
• 26: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 27: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 28: Segal, E., Wang, H., and Koller, D. 2003. Discovering molecular pathways from protein interaction and gene expression data. Bioinformatics 19, 264--272.
• 29: Stein, B., zu Eissen, S. M., and Wibrock, F. 2003. On cluster validity and the information need of users. In Proceedings of the Artificial Intelligenece and Applications Conference.
• 30: 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
• 31: 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
• 32: Xing, E. P., Ng, A. Y., Jordan, M. I., and Russell, S. 2002. Distance metric learning, with application to clustering with side-information. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).
• 33: Kevin Y. Yip , David W. Cheung , Michael K. Ng, On Discovery of Extremely Low-Dimensional Clusters Using Semi-Supervised Projected Clustering, Proceedings of the 21st International Conference on Data Engineering, p.329-340, April 05-08, 2005 [doi>10.1109/ICDE.2005.96]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation, Reliability, Theory

Keywords:
Semisupervised learning, cluster validity, data mining, similarity measure learning, space learning