Leveraging user query log: toward improving image data clustering

ABSTRACT

Image clustering is useful in many retrieval and classification applications. The main goal of image clustering is to partition a given dataset into salient clusters such that the images in each cluster appear visually similar to each other compared with those in other clusters. In this paper, we propose a semi-supervised clustering algorithm, which leverages the accumulated user query log to guide the clustering process. Guided by the log file, our method arranges images into small groups and constructs a graph that captures the dissimilar relations between the groups. Each group is assigned to a feasible cluster. Our analysis reveals that the probability of image points being assigned to the correct clusters is much higher by our new proposal, compared to conventional methods. Our algorithm can produce image clusters close to the ground truth and satisfying the semantic relations between the images inferred from the query log. Experimental results further confirm the superiority of our design.

REFERENCES

• 1: http://www.cse.msu.edu/~yangliu1/dca.zip.
• 2: http://www.cs.huji.ac.il/~tomboy/code/constrainedem_lusbnt.zip.
• 3: http://www.cs.huji.ac.il/~tomboy/code/rca.zip.
• 4: http://www.cs.utexas.edu/users/ml/risc/code/.
• 5: S. Aksoy and R. M. Haralick. Graph-theoretic clustering for image grouping and retrieval. In Conference on Computer Vision and Pattern Recognition, CVPR '99, pages 1063--, 1999.
• 6: Aharon Bar-Hillel , Tomer Hertz , Noam Shental , Daphna Weinshall, Learning a Mahalanobis Metric from Equivalence Constraints, The Journal of Machine Learning Research, 6, p.937-965, 12/1/2005
• 7: 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
• 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: Y. Chen, J. Z. Wang, and R. Krovetz. Clue: cluster-based retrieval of images by unsupervised learning. IEEE Transactions on Image Processing, 14(8):1187--1201, 2005.
• 10: Hao Cheng , Kien A. Hua , Khanh Vu, Local and Global Structures Preserving Projection, Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007), p.362-365, October 29-31, 2007 [doi>10.1109/ICTAI.2007.195]
• 11: I. Davidson and S. S. Ravi. Clustering with constraints: Feasibility issues and the k-means algorithm. In SDM '05: SIAM International Conference on Data Mining, 2005.
• 12: I. Davidson and S. S. Ravi. Identifying and generating easy sets of constraints for clustering. In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, 2006.
• 13: Ian Davidson , S. S. Ravi, Intractability and clustering with constraints, Proceedings of the 24th international conference on Machine learning, p.201-208, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273522]
• 14: Chris Ding , Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the twenty-first international conference on Machine learning, p.29, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015408]
• 15: C. Elkan. Using the triangle inequality to accelerate K-Means. In Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), pages 147--153, 2003.
• 16: J. Goldberger, S. Gordon, and H. Greenspan. Unsupervised image-set clustering using an information theoretic framework. IEEE Transactions on Image Processing, 15(2):449--458, 2006.
• 17: Greg Hamerly , Charles Elkan, Alternatives to the k-means algorithm that find better clusterings, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584890]
• 18: Steven C. H. Hoi , Wei Liu , Michael R. Lyu , Wei-Ying Ma, Learning Distance Metrics with Contextual Constraints for Image Retrieval, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2072-2078, June 17-22, 2006 [doi>10.1109/CVPR.2006.167]
• 19: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 20: 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]
• 21: E. T. Jaynes. Probability Theory: The Logic of Science. Cambridge University Press, 2003.
• 22: Sepandar D. Kamvar , Dan Klein , Christopher D. Manning, Interpreting and Extending Classical Agglomerative Clustering Algorithms using a Model-Based approach, Proceedings of the Nineteenth International Conference on Machine Learning, p.283-290, July 08-12, 2002
• 23: 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
• 24: R. M. Neal and G. E. Hinton. A view of the EM algorithm that justifies incremental, sparse, and other variants. pages 355--368, 1999.
• 25: W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66:622--626, 1971.
• 26: S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, December 2000.
• 27: Y. Rui, T. Huang, M. Ortega, and S. Mehrotra. Relevance feedback: a power tool for interactive content-based image retrieval. Circuits and Systems for Video Technology, IEEE Transactions on, 8(5):644--655, Sep 1998.
• 28: N. Shental, A. Bar-Hillel, and D. W. Tomer Hertz. Computing gaussian mixture models with EM using equivalence constraints. In NIPS '03: Advances in Neural Information Processing Systems, 2003.
• 29: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
• 30: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, December 2000.
• 31: K. Vu, H. Cheng, and K. Hua. Image retrieval in multipoint queries. International Journal of Imaging Systems and Technology, Special Issue on Multimedia Information Retrieval, To appear.
• 32: K. Wagstaff, S. Basu, and I. Davidson. When is constrained clustering beneficial, and why?. In AAAI'06: Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, 2006.
• 33: 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
• 34: 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
• 35: Y. Wu, Q. Tian, and T. S. Huang. Discriminant-EM algorithm with application to image retrieval. In 2000 Conference on Computer Vision and Pattern Recognition (CVPR 2000), pages 1222--1227, 2000.
• 36: M.-C. Yeh, I.-H. Lee, G. Wu, Y. Wu, and E. Y. Chang. Manifold learning, a promised land or work in progress? In Proceedings of the 2005 IEEE International Conference on Multimedia and Expo, ICME 2005, pages 1154--1157, 2005.
• 37: Jie Yu , Qi Tian , Jaume Amores , Nicu Sebe, Toward Robust Distance Metric Analysis for Similarity Estimation, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.316-322, June 17-22, 2006 [doi>10.1109/CVPR.2006.310]
• 38: Ying Zhao , George Karypis, Evaluation of hierarchical clustering algorithms for document datasets, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584877]
• 39: Xin Zheng , Deng Cai , Xiaofei He , Wei-Ying Ma , Xueyin Lin, Locality preserving clustering for image database, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027731]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.m Miscellaneous

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
chunklet assignment, constrained clustering, image clustering, semi-supervised clustering, user query log