Fast K-means algorithm based on influence factors

• Database Technology • Previous Articles Next Articles

Fast K-means algorithm based on influence factors

Received:2007-03-02 Revised:2007-05-07 Online:2007-12-01 Published:2007-12-01
Contact: MingWei Leng

一种基于影响因子的快速K-均值算法

冷明伟陈晓云颜清

上饶师范学院兰州大学上饶师范学院数学与计算机系

通讯作者: 冷明伟

Abstract

Abstract: The running time of K-means overly depends on the initial points but the right value of k is unknown and selecting the initial points effectively is also difficult. To solve this problem, depending on the research about initialization deeply, a high effective approach used to select the initial points was presented, which ensured at least one point to be selected in each cluster. Influence factor between clusters was presented to measure the similarity of two clusters, and a new merging algorithm based on it was put forward. This algorithm and the initial points' selection algorithm can automatically and fast give the actual value of k and select the right initial points based on the dataset characters. Finally, Gaussian datasets were used to test the algorithm and a satisfying result was obtained.

Key words: clustering, k-means, initial point, influence factor

摘要： K-均值聚类算法的执行时间过度依赖于初始点的选取，但是在实际问题中并不知道k的取值和怎样才能有效地选取初始点。在对K-均值算法中初始点的选取进行深入研究的基础上，提出了一种有效的初始点选取算法。现存的类间相似度并不能很好地度量两个类的相似性，为此提出了一种新颖的度量方法：类间影响因子，使用类间影响因子对类进行合并。该方法和上面提出的初始点选取算法能够根据数据集本身的特性快速地自动选取初始中心并给出初始点的个数。最后用高斯数据集对算法进行测试，得到了一个令人满意的结果。

关键词: 聚类, k-均值, 初始点, 影响因子

CLC Number:

TP301

MingWei Leng Xiaoyun Chen . Fast K-means algorithm based on influence factors[J]. Journal of Computer Applications.

冷明伟陈晓云颜清. 一种基于影响因子的快速K-均值算法[J]. 计算机应用.

[1]	CHEN Hengheng, NI Zhiwei, ZHU Xuhui, JIN Yuanyuan, CHEN Qian. Differential privacy high-dimensional data publishing method via clustering analysis [J]. Journal of Computer Applications, 2021, 41(9): 2578-2585.
[2]	ZHU Cheng, ZHAO Xiaoqi, ZHAO Liping, JIAO Yuhong, ZHU Yafei, CHENG Jianying, ZHOU Wei, TAN Ying. Classification of functional magnetic resonance imaging data based on semi-supervised feature selection by spectral clustering [J]. Journal of Computer Applications, 2021, 41(8): 2288-2293.
[3]	ZENG Xiangyin, ZHENG Bochuan, LIU Dan. Detection of left and right railway tracks based on deep convolutional neural network and clustering [J]. Journal of Computer Applications, 2021, 41(8): 2324-2329.
[4]	DAI Yanran, DAI Guoqing, YUAN Yubo. Multi-face foreground extraction method based on skin color learning [J]. Journal of Computer Applications, 2021, 41(6): 1659-1666.
[5]	WANG Jiarui, TAN Guoping, ZHOU Siyuan. Clustered wireless federated learning algorithm in high-speed internet of vehicles scenes [J]. Journal of Computer Applications, 2021, 41(6): 1546-1550.
[6]	MA Jianhong, CAO Wenbin, LIU Yuangang, XIA Shuang. Patent clustering method based on functional effect [J]. Journal of Computer Applications, 2021, 41(5): 1361-1366.
[7]	WANG Zhihe, CHANG Xiaoqing, DU Hui. Adaptive affinity propagation clustering algorithm based on universal gravitation [J]. Journal of Computer Applications, 2021, 41(5): 1337-1342.
[8]	LI Guorong, YE Jimin, ZHEN Yuanting. Time series clustering based on new robust similarity measure [J]. Journal of Computer Applications, 2021, 41(5): 1343-1347.
[9]	LONG Chaoqi, JIANG Yu, XIE Yu. Improved wavelet clustering algorithm based on peak grid [J]. Journal of Computer Applications, 2021, 41(4): 1122-1127.
[10]	LI Xingfeng, HUANG Yuqing, REN Zhenwen, LI Yihong. Robust multi-view clustering algorithm based on adaptive neighborhood [J]. Journal of Computer Applications, 2021, 41(4): 1093-1099.
[11]	ZOU Zhiwen, QIN Cheng. Method of dynamically constructing spatial topic R-tree based on k-means++ [J]. Journal of Computer Applications, 2021, 41(3): 733-737.
[12]	LYU Jia, XIAN Yan. Co-training algorithm combining improved density peak clustering and shared subspace [J]. Journal of Computer Applications, 2021, 41(3): 686-693.
[13]	GUO Jia, HAN Litao, SUN Xianlong, ZHOU Lijuan. Comparative density peaks clustering algorithm with automatic determination of clustering center [J]. Journal of Computer Applications, 2021, 41(3): 738-744.
[14]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[15]	YUAN Qianqian, DENG Hongmin, WANG Xiaohang. Citrus disease and insect pest area segmentation based on superpixel fast fuzzy C-means clustering and support vector machine [J]. Journal of Computer Applications, 2021, 41(2): 563-570.