Maximum normalized spacing for efficient visual clustering

ABSTRACT

In this paper, for efficient clustering of visual image data that have arbitrary mixture distributions, we propose a simple distance metric learning method called Maximum Normalized Spacing (MNS) which is a generalized principle based on Maximum Spacing [12] and Minimum Spanning Tree (MST). The proposed Normalized Spacing (NS) can be viewed as a kind of adaptive distance metric for contextual dissimilarity measure which takes into account the local distribution of the data vectors. Image clustering is a difficult task because there are multiple nonlinear manifolds embedded in the data space. Many of the existing clustering methods often fail to learn the whole structure of the multiple manifolds and they are usually not very effective. Combining both the internal and external statistics of clusters to capture the density structure of manifolds, MNS is capable of efficient and effective solving the clustering problem for the complex multi-manifold datasets in arbitrary metric spaces. We apply this MNS method into the practical problem of multi-view image clustering and obtain good results which are helpful for image browsing systems. Using the COIL-20 [19] and COIL-100 [18] multi-view image databases, our experimental results demonstrate the effectiveness of the proposed MNS clustering method and this clustering method is more efficient than the traditional clustering methods.

References

1. D. Cai, X. He, Z. Li, W. Y. Ma, and J. R. Wen. Hierarchical clustering of www image search results using visual, textual and link information. ACM Multimedia 2004, pages 952--959, 2004.
2. B. Chazelle. A minimum spanning tree algorithm with inverse-ackermann type complexity. Journal of the ACM, 47:1028--1047, 2000.
3. Y. Chen, J. Z. Wang, and R. Krovetz. Clue: cluster-based retrieval of images by unsupervised learning. IEEE Transactions on Image Processing, 14:1187--1201, 2005.
4. J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. OSDI 2004, pages 137--150, 2004.
5. C. Ding, X. He, H. Zha, M. Gu, and H. D. Simon. A min-max cut algorithm for graph partitioning and data clustering. ICDM 2001, pages 107--114, 2001.
6. R. O. Duda, P. E. Hart, and D. G. Stork. Pattern classification. John Wiley & Sons Inc., 2nd edition, 2001.
7. Z. G. Fan, J. Li, B. Wu, and Y. Wu. Local patterns constrained image histograms for image retrieval. ICIP 2008, pages 941--944, 2008.
8. P. F. Felzenszwalb and D. P. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision, 59:167--181, 2004.
9. M. Filippone, F. Camastra, F. Masulli, and S. Rovetta. A survey of kernel and spectral methods for clustering. Pattern Recognition, 41:176--190, 2008.
10. B. J. Frey and D. Dueck. Clustering by passing messages between data points. Science, 315:972--976, 2007.
11. A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: a review. ACM Comput. Surv., 31:264--323, 1999.
12. J. Kleinberg and E. Tardos. Algorithm design. Addison Wesley, 1st edition, 2005.
13. A. Levin, D. Lischinski, and Y. Weiss. A closed form solution to natural image matting. CVPR 2006, 1:61--68, 2006.
14. J. Li and J. Z. Wang. Automatic linguistic indexing of pictures by a statistical modeling approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25:1075--1088, 2003.
15. J. Lim, J. Ho, M. Yang, K. Lee, and D. Kriegman. Image clustering with metric, local linear structure and affine symmetry. ECCV 2004, 1:456--468, 2004.
16. Y. Ma, H. Derksen, W. Hong, and J. Wright. Segmentation of multivariate mixed data via lossy data coding and compression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29:1546--1562, 2007.
17. A. McCallum, K. Nigam, and L. Ungar. Efficient clustering of high-dimensional data sets with application to reference matching. KDD 2000, pages 169--178, 2000.
18. S. A. Nene, S. K. Nayar, and H. Murase. Columbia object image library (coil-100). Technical Report CUCS-006-96, 1996.
19. S. A. Nene, S. K. Nayar, and H. Murase. Columbia object image library (coil-20). Technical Report CUCS-005-96, 1996.
20. A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. NIPS 2001, pages 849--856, 2001.
21. P. Pudil, J. Novovicova, and J. Kittler. Floating search methods in feature selection. Pattern Recognition Letters, 15:1119--1125, 1994.
22. S. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323--2326, 2000.
23. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22:888--905, 2000.
24. R. Souvenir and R. Pless. Manifold clustering. ICCV 2005,1:648--653, 2005.
25. J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319--2323, 2000.
26. K. Q. Weinberger and L. K. Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision, 70:77--90, 2006.
27. Y. Weiss. Segmentation using eigenvectors: a unifying view. ICCV 1999, 1:975--982, 1999.
28. R. Xu and D. Wunsch. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16:645--678, 2005.
29. Y. Xu, V. Olman, and D. Xu. Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees. Bioinformatics, 18:536--545, 2002.
30. D. Yankov and E. Keogh. Manifold clustering of shapes. ICDM 2006, 1:1167--1171, 2006.
31. C. T. Zahn. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Transactions on Computers, 20:68--86, 1971.
32. L. Zelnik-Manor and P. Perona. Self-tuning spectral clustering. NIPS 2004, pages 1601--1608, 2004.
33. S. Zhang, C. Shi, Z. Zhang, and Z. Shi. A global geometric approach for image clustering. ICPR 2006, 4:960--963, 2006.
34. Y. Zhao and G. Karypis. Evaluation of hierarchical clustering algorithms for document datasets. CIKM 2002, pages 515--524, 2002.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis

• Mathematics of computing

  • Discrete mathematics

    • Graph theory