The k-means algorithm based on Finsler geometry

doi:10.3969/j.issn.0253-2778.2014.07.005

Journal of University of Science and Technology of China ›› 2014, Vol. 44 ›› Issue (7): 570-575.DOI: 10.3969/j.issn.0253-2778.2014.07.005

• Original Paper • Previous Articles Next Articles

The k-means algorithm based on Finsler geometry

XU Qing, LI Fanzhang, ZOU Peng

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

Received:2014-03-21 Revised:2014-06-15 Accepted:2014-06-15 Online:2023-05-11 Published:2014-06-15

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.

Key words: Finsler geometry, Finsler metric, k-means algorithm, similarity measure, criterion function

CLC Number:

TP311

XU Qing, LI Fanzhang, ZOU Peng. The k-means algorithm based on Finsler geometry[J]. Journal of University of Science and Technology of China, 2014, 44(7): 570-575.

References

［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.

[1]	LIN Qianhong, WANG Zhihai, YUAN Jidong, ZHANG Wei. Trend information for time series classification [J]. Journal of University of Science and Technology of China, 2019, 49(2): 138-148.
[2]	LIN Yanqing, FU Yanggeng. A rule activation method for extended belief rule base based on improved similarity measures [J]. Journal of University of Science and Technology of China, 2018, 48(1): 20-27.
[3]	HE Chao, LI Ying, SONG Weidong. A class of projectively flat and dually flat Finsler metrics [J]. Journal of University of Science and Technology of China, 2017, 47(6): 459-464.
[4]	LI Ying, SONG Weidong. A new class of projectively flat Finsler metrics [J]. Journal of University of Science and Technology of China, 2015, 45(12): 1015-1022.

The k-means algorithm based on Finsler geometry

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments