ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

The k-means algorithm based on Finsler geometry

  • School of Computer Science and Technology, Soochow University, Suzhou 215006, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.07.005
  • Received Date: 21 March 2014
  • Accepted Date: 15 June 2014
  • Rev Recd Date: 15 June 2014
  • Publish Date: 30 July 2014
    Abstract

  • Abstract

    The problems with the k-means algorithm that the optimization effect of similarity measure and criterion function is not ideal and the analysis performance of multi-dimensional manifold data is ineffective, a modified version based on Finsler geometry was proposed, which introduces Finsler metric. Experimental results in comparison with traditional k-means algorithm and SBKM algorithm on UCI data sets and ORL face image sets show the feasibility and effectiveness of the algorithm.

    Abstract

    The problems with the k-means algorithm that the optimization effect of similarity measure and criterion function is not ideal and the analysis performance of multi-dimensional manifold data is ineffective, a modified version based on Finsler geometry was proposed, which introduces Finsler metric. Experimental results in comparison with traditional k-means algorithm and SBKM algorithm on UCI data sets and ORL face image sets show the feasibility and effectiveness of the algorithm.
    • FullText(HTML)
  • loading
    • References(19)
  • [1]
    MacQueen J B. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. London, UK: Cambridge University Press, 1967: 281-297.
    [2]
    Jain A K. Data clustering: 50 years beyond k-means [J]. Pattern Recognition Letters, 2010, 31(8): 651-666.
    [3]
    Kashima H, Hu J Y, Ray B, et al. k-means clustering of proportional data using L1 distance[C]//Proceedings of the 19th International Conference on Pattern Recognition. Tampa, USA: IEEE Press, 2008: 1-4.
    [4]
    Banerjee A, Merugu S, Dhillon I S, et al. Clustering with Bregman divergences [J]. The Journal of Machine Learning Research, 2005, 6: 1 705-1 749.
    [5]
    Su M C, Chou C H. A modified version of the k-means algorithm with a distance based on cluster symmetry [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(6):674-680.
    [6]
    Wang L, Bo L F, Jiao L C. A modified k-means clustering with a density-sensitive distance metric[C]// Proceedings of the First International Conference on Rough Sets and Knowledge Technology. Berlin Heidelberg: Springer, 2006: 544-551.
    [7]
    Liu C R, Hu T M, Ge Y, et al. Which distance metric is right: An evolutionary k-Means view[C]// Proceedings of the SIAM International Conference on Data Mining. Anaheim, USA: SIAM Press, 2012: 907-918.
    [8]
    Linde Y, Buzo A, Gray R M. An algorithm for vector quantizer design [J]. IEEE Transactions on Communications, 1980, 28(1): 84-95.
    [9]
    Mao J C, Jain A K. A self-organizing network for hyperellipsoidal clustering (HEC)[J]. IEEE Transactions on Neural Networks, 1996, 7(1): 16-29.
    [10]
    Yang F Z, Zhu Y Y. An efficient method for similarity search on quantitative transactions data [J]. Journal of Computer Research and Development, 2004, 41(2): 361-368.
    杨风召，朱扬勇.一种有效的量化交易数据相似性搜索方法[J].计算机研究与发展，2004, 41(2): 361-368.
    [11]
    Chen G Z, Cheng X Y, Yuan M G. On a class of projectively flat Finsler metrics with weakly isotropic flag curvature [J]. Periodica Mathematica Hungarica, 2013, 67(2): 155-166.
    [12]
    Matsumoto M. On Finsler spaces with Randers metric and special forms of important tensors [J].Journal of Mathematics of Kyoto University, 1974, 14(3): 477-498.
    [13]
    Cui N W, Shen Y B. Projective change between two classes of (α, β)-metrics [J]. Differential Geometry and its Applications, 2009, 27(4): 566-573.
    [14]
    Chern S S, Shen Z M. Riemann-Finsler Geometry [M]. Singapore: World Scientific, 2005.
    [15]
    沈一兵, 沈忠民. 现代芬斯勒几何初步[M]. 北京: 高等教育出版社, 2013.
    [16]
    陈省身, 陈维桓. 微分几何讲义 [M]. 二版, 北京: 北京大学出版社, 2001.
    [17]
    李凡长, 张莉, 杨季文, 等. 李群机器学习[M]. 合肥: 中国科学技术大学出版社, 2013.
    [18]
    Machine Learning Repository[EB/OL]. http://archive.ics.uci.edu/ml/datasets.html.
    [19]
    http://cs.nyu.edu/~roweis/data/olivettifaces.mat.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    MacQueen J B. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. London, UK: Cambridge University Press, 1967: 281-297.
    [2]
    Jain A K. Data clustering: 50 years beyond k-means [J]. Pattern Recognition Letters, 2010, 31(8): 651-666.
    [3]
    Kashima H, Hu J Y, Ray B, et al. k-means clustering of proportional data using L1 distance[C]//Proceedings of the 19th International Conference on Pattern Recognition. Tampa, USA: IEEE Press, 2008: 1-4.
    [4]
    Banerjee A, Merugu S, Dhillon I S, et al. Clustering with Bregman divergences [J]. The Journal of Machine Learning Research, 2005, 6: 1 705-1 749.
    [5]
    Su M C, Chou C H. A modified version of the k-means algorithm with a distance based on cluster symmetry [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(6):674-680.
    [6]
    Wang L, Bo L F, Jiao L C. A modified k-means clustering with a density-sensitive distance metric[C]// Proceedings of the First International Conference on Rough Sets and Knowledge Technology. Berlin Heidelberg: Springer, 2006: 544-551.
    [7]
    Liu C R, Hu T M, Ge Y, et al. Which distance metric is right: An evolutionary k-Means view[C]// Proceedings of the SIAM International Conference on Data Mining. Anaheim, USA: SIAM Press, 2012: 907-918.
    [8]
    Linde Y, Buzo A, Gray R M. An algorithm for vector quantizer design [J]. IEEE Transactions on Communications, 1980, 28(1): 84-95.
    [9]
    Mao J C, Jain A K. A self-organizing network for hyperellipsoidal clustering (HEC)[J]. IEEE Transactions on Neural Networks, 1996, 7(1): 16-29.
    [10]
    Yang F Z, Zhu Y Y. An efficient method for similarity search on quantitative transactions data [J]. Journal of Computer Research and Development, 2004, 41(2): 361-368.
    杨风召，朱扬勇.一种有效的量化交易数据相似性搜索方法[J].计算机研究与发展，2004, 41(2): 361-368.
    [11]
    Chen G Z, Cheng X Y, Yuan M G. On a class of projectively flat Finsler metrics with weakly isotropic flag curvature [J]. Periodica Mathematica Hungarica, 2013, 67(2): 155-166.
    [12]
    Matsumoto M. On Finsler spaces with Randers metric and special forms of important tensors [J].Journal of Mathematics of Kyoto University, 1974, 14(3): 477-498.
    [13]
    Cui N W, Shen Y B. Projective change between two classes of (α, β)-metrics [J]. Differential Geometry and its Applications, 2009, 27(4): 566-573.
    [14]
    Chern S S, Shen Z M. Riemann-Finsler Geometry [M]. Singapore: World Scientific, 2005.
    [15]
    沈一兵, 沈忠民. 现代芬斯勒几何初步[M]. 北京: 高等教育出版社, 2013.
    [16]
    陈省身, 陈维桓. 微分几何讲义 [M]. 二版, 北京: 北京大学出版社, 2001.
    [17]
    李凡长, 张莉, 杨季文, 等. 李群机器学习[M]. 合肥: 中国科学技术大学出版社, 2013.
    [18]
    Machine Learning Repository[EB/OL]. http://archive.ics.uci.edu/ml/datasets.html.
    [19]
    http://cs.nyu.edu/~roweis/data/olivettifaces.mat.
    Recommended articles
    TrendMD
    Volume 44 Issue 7 page: 570-575
    Cover

    Article Metrics

    Article views (37) PDF downloads(63)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return