Submit Manuscript

Information Technology Journal

Year: 2011 | Volume: 10 | Issue: 12 | Page No.: 2420-2426
Research Article

Information-theoretic Agglomerative K-means

Yanfeng Zhang
Department of Computer Science, Harbin Institute of Technology, China
Xutao Li
Department of Computer Science, Harbin Institute of Technology, China
Yunming Ye
Department of Computer Science, Harbin Institute of Technology, China
Xiaofei Xu
Department of Computer Science, Harbin Institute of Technology, China
Shengchun Deng
Department of Computer Science, Harbin Institute of Technology, China
Agglomerative K-means is a clustering algorithm of K-means type. The algorithm has good properties because of its insensitiveness to the locations of initial centers and its effectiveness in determining the number of clusters. In present study, we extend the agglomerative K-means from information theoretic view and develop a new clustering algorithm, Information-Theoretic Agglomerative K-means. Different from the agglomerative K-means, we propose a new objective function employing the Kullback-Leibler divergence to measure the dispersion of clusters. Based on this objective function, we derive the updating formulas of centers and membership for objects associated to different centers and then develop an efficient algorithm. Experimental results on both well-separated and overlapped data suggested that the proposed clustering algorithm is not only promising in obtaining good clustering performance but also effective in identifying the number of clusters.
PDF Fulltext XML References Citation

Leave a Comment

Your email address will not be published. Required fields are marked *

Article Trend

Total views 1600

References

  1. Arthur, D. and S. Vassilvitskii, 2007. K-means++: The advantages of careful seeding. Proceedings of the 18th Annual ACM-SIAM Symposium of Discrete Analysis, January 7-9, 2007, New Orleans, LA., USA., pp: 1027-1035.
    Direct Link
  2. Feng, Y. and G. Hamerly, 2007. PG-means: Learning the number of clusters in data. Adv. Neural Inform. Proc. Syst., 19: 393-400.
    Direct Link
  3. Hamerly, G. and C. Elkan, 2003. Learning the k in k-means. http://u.math.biu.ac.il/~louzouy/courses/seminar/kmeans1.pdf
  4. Krishna, K. and M.N. Murty, 1999. Genetic K-means algorithm. IEEE Trans. Syst. Man Cybern. Part B. Cyber., 29: 433-439.
    CrossRefDirect Link
  5. Li, M.J., M.K. Ng, Y.M. Cheung and J.Z. Huang, 2008. Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters. IEEE Trans. Knowledge Data Eng., 20: 1519-1534.
    CrossRefDirect Link
  6. Li, X., Y. Ye, M.J. Li and M.K. Ng, 2010. On cluster tree for nested and multi-density data clustering. Pattern Recognit., 43: 3130-3143.
    CrossRef
  7. Likas, A., N. Vlassis and J.J. Verbeek, 2003. The global k-means clustering algorithm. Pattern Recognit., 36: 451-461.
    CrossRef
  8. Lu, Y., S. Lu, F. Fotouhi, Y. Deng and S.J. Brown, 2004. FGKA: A fast genetic k-means clustering algorithm. Proceedings of the 19th ACM Symposium on Applied Computing, Nicosia, Cyprus, March 14-17, ACM, pp: 622-623.
  9. Pelleg, D. and A. Moore, 2000. X-means: Extending K-means with efficient estimation of the number of clusters. Proceedings of the 17th International Conference on Machine Learning, June 29-July 2, 2000, Standord, CA., USA., pp: 727-734.

Keywords