Advertisement

Active Constrained Clustering by Examining Spectral Eigenvectors

  • Qianjun Xu
  • Marie desJardins
  • Kiri L. Wagstaff
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3735)

Abstract

This work focuses on the active selection of pairwise constraints for spectral clustering. We develop and analyze a technique for Active Constrained Clustering by Examining Spectral eigenvectorS (ACCESS) derived from a similarity matrix. The ACCESS method uses an analysis based on the theoretical properties of spectral decomposition to identify data items that are likely to be located on the boundaries of clusters, and for which providing constraints can resolve ambiguity in the cluster descriptions. Empirical results on three synthetic and five real data sets show that ACCESS significantly outperforms constrained spectral clustering using randomly selected constraints.

Keywords

Similarity Matrix Spectral Cluster Laplacian Matrix Rand Index Adjusted Rand Index 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Wagstaff, K., Cardie, C., Rogers, S., Schroedl, S.: Constrained k-means clustering with background knowledge. In: Proceedings of the 18th International Conference of Machine Learning, pp. 577–584 (2001)Google Scholar
  2. 2.
    Klein, D., Kamvar, S.D., Manning, C.D.: From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering. In: Proceedings of the Nineteenth International Conference on Machine Learning, pp. 307–314 (2002)Google Scholar
  3. 3.
    Bar-Hillel, A., Hertz, T., Shental, N., Weinshall, D.: Learning distance functions using equivalence relations. In: Proceedings of the Twentieth International Conference on Machine Learning, pp. 11–18 (2003)Google Scholar
  4. 4.
    Bilenko, M., Basu, S., Mooney, R.J.: Integrating constraints and metric learning in semi-supervised clustering. In: Proceedings of the Twenty-First International Conference on Machine Learning, pp. 81–88 (2004)Google Scholar
  5. 5.
    Basu, S., Banerjee, A., Mooney, R.J.: Active semi-supervision for pairwise constrained clustering. In: Proceedings of the SIAM International Conference on Data Mining, pp. 333–344 (2004)Google Scholar
  6. 6.
    Hagen, L., Kahng, A.B.: New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11, 1074–1085 (1992)CrossRefGoogle Scholar
  7. 7.
    Shi, J., Malik, J.: Normalized cuts and image segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 731–737 (1997)Google Scholar
  8. 8.
    Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems 14, 849–856 (2002)Google Scholar
  9. 9.
    Meilă, M., Shi, J.: A random walks view of spectral segmentation. In: Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (2001)Google Scholar
  10. 10.
    Kamvar, S.D., Klein, D., Manning, C.D.: Spectral learning. In: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pp. 561–566 (2003)Google Scholar
  11. 11.
    Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal 25, 619–627 (1975)MathSciNetGoogle Scholar
  12. 12.
    Dhillon, I.S.: Co-clustering documents and words using bipartite spectral graph partitioning. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 269–274 (2001)Google Scholar
  13. 13.
    Ding, C.H., He, X., Zha, H.: A spectral method to separate disconnected and nearly-disconnected web graph components. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2001)Google Scholar
  14. 14.
    Blake, C., Merz, C.: UCI repository of machine learning databases (1998)Google Scholar
  15. 15.
    Rand, W.: Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association 66, 846–850 (1971)CrossRefGoogle Scholar
  16. 16.
    Hubert, A.: Comparing partitions. Journal of Classification 2, 193–218 (1985)CrossRefGoogle Scholar
  17. 17.
    Xu, Q., desJardins, M., Wagstaff, K.L.: Constrained spectral clustering under a local proximity structure assumption. In: Proceedings of the 18th International FLAIRS Conference (2005)Google Scholar
  18. 18.
    Xu, Q.: desJardins, M., Wagstaff, K.L.: Active constraint selection for clustering (Submitted to ICDM 2005)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Qianjun Xu
    • 1
  • Marie desJardins
    • 1
  • Kiri L. Wagstaff
    • 2
  1. 1.Dept. of CS&EEUniversity of Maryland Baltimore CountyBaltimore
  2. 2.Jet Propulsion LaboratoryCalifornia Institute of TechnologyPasadena

Personalised recommendations