Neural tangent kernel K‑Means clustering

doi:10.11772/j.issn.1001-9081.2021111961

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (11): 3330-3336.DOI: 10.11772/j.issn.1001-9081.2021111961

Special Issue: 第九届CCF大数据学术会议(CCF Bigdata 2021)

• CCF Bigdata 2021 • Previous Articles Next Articles

Neural tangent kernel K‑Means clustering

Mei WANG¹^,², Xiaohui SONG¹, Yong LIU³^,⁴(), Chuanhai XU¹

^1.School of Computer and Information Technology，Northeast Petroleum University，Daqing Heilongjiang 163318，China
^2.Heilongjiang Key Laboratory of Petroleum Big Data and Intelligent Analysis （Northeast Petroleum University），Daqing Heilongjiang 163318，China
^3.Gaoling School of Artificial Intelligence，Renmin University of China，Beijing 100872，China
^4.Beijing Key Laboratory of Big Data Management and Analysis Method （Renmin University of China），Beijing 100872，China

Received:2021-11-17 Revised:2021-12-13 Accepted:2021-12-23 Online:2022-01-04 Published:2022-11-10
Contact: Yong LIU
About author:WANG Mei， born in 1976， Ph. D.， professor. Her research interests include machine learning， kernel methods， model selection.
SONG Xiaohui， born in 1998， M. S. candidate. Her research interests include deep kernel learning.
XU Chuanhai， born in 1998， M. S. candidate. His research interests include deep kernel learning.
First author contact:LIU Yong， born in 1986， Ph. D.， research associate. His research interests include large‑scale machine learning， automatic machine learning， statistical machine learning theory.
Supported by:
National Natural Science Foundation of China(51774090);Postdoctoral Research Startup Fund of Heilongjiang Province(LBH?Q20080);Natural Science Foundation of Heilongjiang Province(LH2020F003);Higher Education Teaching Reform Key Entrusted Project of Heilongjiang Province(SJGZ20190011)

神经正切核K‑Means聚类

王梅¹^,², 宋晓晖¹, 刘勇³^,⁴(), 许传海¹

^1.东北石油大学计算机与信息技术学院, 黑龙江大庆 163318
^2.黑龙江省石油大数据与智能分析重点实验室(东北石油大学), 黑龙江大庆 163318
^3.中国人民大学高瓴人工智能学院, 北京 100872
^4.大数据管理与分析方法研究北京市重点实验室(中国人民大学), 北京 100872

通讯作者: 刘勇
作者简介:王梅（1976—），女，河北保定人，教授，博士，CCF会员，主要研究方向：机器学习、核方法、模型选择
宋晓晖（1998—），女，山东济南人，硕士研究生，CCF会员，主要研究方向：深度核学习
刘勇（1986—），男，湖南益阳人，副研究员，博士，CCF会员，主要研究方向：大规模机器学习、自动机器学习、统计机器学习理论 liuyonggsai@ruc.edu.cn
许传海（1998—），男，黑龙江鸡西人，硕士研究生，CCF会员，主要研究方向：深度核学习。
基金资助:
国家自然科学基金资助项目(51774090);黑龙江省博士后科研启动金资助项目(LBH?Q20080);黑龙江省自然科学基金资助项目(LH2020F003);黑龙江省高等教育教学改革重点委托项目(SJGZ20190011)

Abstract

Abstract:

Aiming at the problem that the clustering results of K-Means clustering algorithm are affected by the sample distribution because of using the mean to update the cluster centers， a Neural Tangent Kernel K-Means （NTKKM） clustering algorithm was proposed. Firstly， the data of the input space were mapped to the high-dimensional feature space through the Neural Tangent Kernel （NTK）， then the K-Means clustering was performed in the high-dimensional feature space， and the cluster centers were updated by taking into account the distance between clusters and within clusters at the same time. Finally， the clustering results were obtained. On the car and breast-tissue datasets， three evaluation indexes including accuracy， Adjusted Rand Index （ARI） and FM index of NTKKM clustering algorithm and comparison algorithms were counted. Experimental results show that the effect of clustering and the stability of NTKKM clustering algorithm are better than those of K-Means clustering algorithm and Gaussian kernel K?Means clustering algorithm. Compared with the traditional K?Means clustering algorithm， NTKKM clustering algorithm has the accuracy increased by 14.9% and 9.4% respectively， the ARI increased by 9.7% and 18.0% respectively， and the FM index increased by 12.0% and 12.0% respectively， indicating the excellent clustering performance of NTKKM clustering algorithm.

Key words: Neural Tangent Kernel (NTK), K?Means, kernel clustering, feature space, kernel function

摘要：

针对K-Means聚类算法利用均值更新聚类中心，导致聚类结果受样本分布影响的问题，提出了神经正切核K-Means聚类算法（NTKKM）。首先通过神经正切核（NTK）将输入空间的数据映射到高维特征空间，然后在高维特征空间中进行K-Means聚类，并采用兼顾簇间与簇内距离的方法更新聚类中心，最后得到聚类结果。在car和breast-tissue数据集上，对NTKKM聚类算法的准确率、调整兰德系数（ARI）及FM指数这3个评价指标进行统计。实验结果表明，NTKKM聚类算法的聚类效果以及稳定性均优于K?Means聚类算法和高斯核K-Means聚类算法。NTKKM聚类算法与传统的K-Means聚类算法相比，准确率分别提升了14.9%和9.4%，ARI分别提升了9.7%和18.0%，FM指数分别提升了12.0%和12.0%，验证了NTKKM聚类算法良好的聚类性能。

关键词: 神经正切核, K?Means, 核聚类, 特征空间, 核函数

CLC Number:

TP181

Mei WANG, Xiaohui SONG, Yong LIU, Chuanhai XU. Neural tangent kernel K‑Means clustering[J]. Journal of Computer Applications, 2022, 42(11): 3330-3336.

王梅, 宋晓晖, 刘勇, 许传海. 神经正切核K‑Means聚类[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3330-3336.

Figures/Tables 9

Tab. 1 Experimental dataset information

数据集名称	维度	类别个数	样本数量
car	6	4	1 728
breast‑tissue	9	6	106
winequality‑red	12	6	1 599
iris	4	3	150

Tab. 2 Accuracies of three algorithms

数据集	K‑Means	GKKM	NTKKM
car	0.706 $±$ 0.110	0.731 $±$ 0.008	0.811 $±$ 0.005
breast tissue	0.854 $±$ 0.019	0.884 $±$ 0.007	0.934 $±$ 0.004
winequality‑red	0.731 $±$ 0.120	0.637 $±$ 0.009	0.800 $±$ 0.004
iris	0.889 $±$ 0.005	0.904 $±$ 0.006	0.924 $±$ 0.009

Tab. 2 Accuracies of three algorithms

数据集	K‑Means	GKKM	NTKKM
car	0.706 $±$ 0.110	0.731 $±$ 0.008	0.811 $±$ 0.005
breast tissue	0.854 $±$ 0.019	0.884 $±$ 0.007	0.934 $±$ 0.004
winequality‑red	0.731 $±$ 0.120	0.637 $±$ 0.009	0.800 $±$ 0.004
iris	0.889 $±$ 0.005	0.904 $±$ 0.006	0.924 $±$ 0.009

Tab. 3 Adjusted Rand indexes of three algorithms

数据集	K‑Means	GKKM	NTKKM
car	0.729 $±$ 0.150	0.745 $±$ 0.011	0.800 $±$ 0.007
breast tissue	0.712 $±$ 0.120	0.761 $±$ 0.009	0.840 $±$ 0.006
winequality‑red	0.758 $±$ 0.200	0.501 $±$ 0.150	0.801 $±$ 0.008
iris	0.867 $±$ 0.008	0.710 $±$ 0.007	0.822 $±$ 0.008

Tab. 3 Adjusted Rand indexes of three algorithms

数据集	K‑Means	GKKM	NTKKM
car	0.729 $±$ 0.150	0.745 $±$ 0.011	0.800 $±$ 0.007
breast tissue	0.712 $±$ 0.120	0.761 $±$ 0.009	0.840 $±$ 0.006
winequality‑red	0.758 $±$ 0.200	0.501 $±$ 0.150	0.801 $±$ 0.008
iris	0.867 $±$ 0.008	0.710 $±$ 0.007	0.822 $±$ 0.008

Tab. 4 Fowlkes and Mallows Indexes of three algorithms

数据集	K‑Means	GKKM	NTKKM
car	0.581 $±$ 0.020	0.561 $±$ 0.160	0.651 $±$ 0.007
breast tissue	0.750 $±$ 0.011	0.753 $±$ 0.009	0.840 $±$ 0.004
winequality‑red	0.509 $±$ 0.020	0.453 $±$ 0.023	0.611 $±$ 0.009
iris	0.751 $±$ 0.018	0.753 $±$ 0.002	0.768 $±$ 0.008

Tab. 4 Fowlkes and Mallows Indexes of three algorithms

数据集	K‑Means	GKKM	NTKKM
car	0.581 $±$ 0.020	0.561 $±$ 0.160	0.651 $±$ 0.007
breast tissue	0.750 $±$ 0.011	0.753 $±$ 0.009	0.840 $±$ 0.004
winequality‑red	0.509 $±$ 0.020	0.453 $±$ 0.023	0.611 $±$ 0.009
iris	0.751 $±$ 0.018	0.753 $±$ 0.002	0.768 $±$ 0.008

Fig. 1 Accuracies of three algorithms in different dimensions

Fig. 2 Accuracies of three algorithms under different numbers of clusters

Fig. 3 Accuracies of three algorithms under different numbers of samples

Fig. 4 Clustering effect diagrams of three algorithms on iris dataset

Fig. 5 Clustering effect diagrams of three algorithms on breast?tissue dataset

References 33

1	FAHIM A M， SALEM A M， TORKEY F A， et al. An efficient enhanced k‑means clustering algorithm［J］. Journal of Zhejiang University — SCIENCE A （Applied Physics and Engineering）， 2006， 7（10）： 1626-1633. 10.1631/jzus.2006.a1626
2	汪敏，武禹伯，闵帆. 基于多种聚类算法和多元线性回归的多分类主动学习算法［J］. 计算机应用， 2020， 40（12）：3437-3444. 10.11772/j.issn.1001-9081.2020060921
	WANG M， WU Y B， MIN F. Multi‑category active learning algorithm based on multiple clustering algorithms and multiple linear regression［J］. Journal of Computer applications， 2020， 40（12）：3437-3444. 10.11772/j.issn.1001-9081.2020060921
3	LAWRENCE L O. A Primer on Cluster Analysis by James C. Bezdck［J］. IEEE Systems， Man， and Cybernetics Magazine， 2018， 4（1）：48-50. 10.1109/msmc.2017.2769202
4	于佐军，秦欢. 基于改进蜂群算法的K‑means算法［J］. 控制与决策， 2018， 33（1）：181-185.
	YU Z J， QIN H. K‑means algorithm based on improved artificial bee swarm algorithm［J］. Control and Decision， 2018， 33（1）：181-185.
5	覃华，詹娟娟，苏一丹. 基于概率无向图模型的近邻传播聚类算法［J］. 控制与决策， 2017， 32（10）：1796-1802. 10.13195/j.kzyjc.2016.0861
	QIN H， ZHAN J J， SU Y D. Affinity propagation clustering algorithm based on probabilistic undirected graphical model［J］. Control and Decision， 2017， 32（10）： 1796-1802. 10.13195/j.kzyjc.2016.0861
6	周涛，陆惠玲. 数据挖掘中聚类算法研究进展［J］. 计算机工程与应用， 2012， 48（12）：100-111. 10.3778/j.issn.1002-8331.2012.12.021
	ZHOU T， LU H L. Clustering algorithm research advances on data mining［J］. Computer Engineering and Applications， 2012， 48（12）：100-111. 10.3778/j.issn.1002-8331.2012.12.021
7	GIROLAMI M. Mercer kernel‑based clustering in feature space［J］. IEEE Transactions on Neural Networks， 2002， 13（3）：780-784. 10.1109/tnn.2002.1000150
8	张莉，周伟达，焦李成. 核聚类算法［J］. 计算机学报， 2002， 25（6）： 587-590. 10.3321/j.issn:0254-4164.2002.06.005
	ZHANG L， ZHOU W D， JIAO L C. Kernel clustering algorithm［J］. Chinese Journal of Computers， 2002， 25（6）： 587-590. 10.3321/j.issn:0254-4164.2002.06.005
9	BEN‑HUR A， HORN D， SIEGELMANN H T， et al. Support vector clustering［J］. Journal of Machine Learning Research， 2001， 2：125-137.
10	徐小来，房晓丽. 基于改进的直觉模糊核聚类的图像分割方法［J］. 计算机工程与应用， 2019， 55（17）：227-231. 10.3778/j.issn.1002-8331.1904-0307
	XU X L， FANG X L. Image segmentation method based on improved intuitive fuzzy kernel c‑means clustering algorithms［J］. Computer Engineering and Applications， 2019， 55（17）：227-231. 10.3778/j.issn.1002-8331.1904-0307
11	杨飞，朱志祥. 基于特征和空间信息的核模糊C-均值聚类算法［J］. 电子科技， 2016， 29（2）：16-19.
	YANG F， ZHU Z X. Kernelized fuzzy C‑means clustering algorithm based on feature and spatial information［J］. Electronic Science and Technology， 2016， 29（2）：16-19.
12	XIANG L Y， ZHAO G H， LI Q， et al. A fast and effective multiple kernel clustering method on incomplete data［J］. Computers， Materials & Continua， 2021， 67（1）：267-284. 10.32604/cmc.2021.013488
13	LIU X W， ZHU E， LIU J Y， et al. SimpleMKKM： simple multiple kernel k‑means［EB/OL］. （2020-05-12）［2021-07-20］. . 10.1109/tpami.2022.3198638
14	LIU Y， DING L. Nearly optimal risk bounds for kernel K‑means［EB/OL］. （2020-03-09）［2021-07-01］..
15	孔锐，张国宣，施泽生，等. 基于核的K-均值聚类［J］. 计算机工程， 2004， 30（11）：12-13， 80. 10.3969/j.issn.1000-3428.2004.11.005
	KONG R， ZHANG G X， SHI Z S， et al. Kernel‑based K‑means clustering［J］. Computer Engineering， 2004， 30（11）：12-13， 80. 10.3969/j.issn.1000-3428.2004.11.005
16	NEAL R M. Bayesian Learning for Neural Networks［M］. New York： Springer， 1996： 29-53. 10.1007/978-1-4612-0745-0
17	LEE J， BAHRI Y， NOVAK R， et al. Deep neural networks as Gaussian processes［EB/OL］. （2018-03-03）［2020-05-19］..
18	MATTHEWS A G D G， ROWLAND M， HRON J， et al. Gaussian process behaviour in wide deep neural networks［EB/OL］. （2018-08-16）［2020-05-19］..
19	JACOT A， GABRIEL F， HONGLER C. Neural tangent kernel： convergence and generalization in neural networks［C］// Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2018：8580-8589.
20	ARORA S， DU S S， HU W， et al. On exact computation with an infinitely wide neural net［C/OL］// Proceedings of the 33rd Conference on Neural Information Processing Systems. ［2020-12-24］..
21	王梅，许传海，刘勇. 基于神经正切核的多核学习方法［J］. 计算机应用， 2021， 41（12）：3462-3467. 10.11772/j.issn.1001-9081.2021060998
	WANG M， XU C H， LIU Y. Multi‑kernel learning methods based on neural positive tangent kernel［J］. Journal of Computer Applications， 2021， 41（12）：3462-3467. 10.11772/j.issn.1001-9081.2021060998
22	ARORA S， DU S S， LI Z Y， et al. Harnessing the power of infinitely wide deep nets on small‑data tasks［EB/OL］. （2019-10-27）［2021-01-08］..
23	SCHÖLKOPF B， SEBASTIAN MIKA S， BURGES C J C， et al. Input space versus feature space in kernel‑based methods［J］. IEEE Transactions on Neural Networks， 1999， 10（5）： 1000-1017. 10.1109/72.788641
24	王守志，何东健，李文，等. 基于核K-均值聚类算法的植物叶部病害识别［J］. 农业机械学报， 2009， 40（3）：152-155.
	WANG S Z， HE D J， LI W， et al. Plant leaf disease identification based on the nuclear K‑means clustering algorithm［J］. Transactions of the Chinese Society for Agricultural Machinery， 2009， 40（3）： 152-155.
25	王宇，李晓利. 核k-凝聚聚类算法［J］. 大连理工大学学报， 2007， 47（5）：763-766.
	WANG Y， LI X L. Kernel k‑aggregate clustering algorithm［J］. Journal of Dalian University of Technology， 2007， 47（5）： 763-766.
26	HUO J， BI Y H， LÜ D R， et al. Cloud classification and distribution of cloud types in Beijing using Ka‑band radar data［J］. Advances in Atmospheric Sciences， 2019， 36（8）：793-803. 10.1007/s00376-019-8272-1
27	TZORTZIS G， LIKAS A. The MinMax k‑Means clustering algorithm［J］. Pattern Recognition， 2014， 47（7）：2505-2516. 10.1016/j.patcog.2014.01.015
28	翟东海，鱼江，高飞，等. 最大距离法选取初始簇中心的K‑means文本聚类算法的研究［J］. 计算机应用研究， 2014， 31（3）：713-715， 719.
	ZHAI D H， YU J， GAO F， et al. K‑means text clustering algorithm based on initial cluster centers selection according to maximum distance［J］. Application Research of Computers， 2014， 31（3）：713-715， 719.
29	DENG Z H， CHOI K S， CHUNG F L， et al. Enhanced soft subspace clustering integrating within‑cluster and between‑cluster information［J］. Pattern Recognition， 2010， 43（3）：767-781. 10.1016/j.patcog.2009.09.010
30	HUANG X H， YE Y M， ZHANG H J. Extensions of kmeans‑type algorithms： a new clustering framework by integrating intra‑cluster compactness and inter‑cluster separation［J］. IEEE Transactions on Neural Networks and Learning Systems， 2014， 25（8）： 1433-1446. 10.1109/tnnls.2013.2293795
31	PANG N， ZHAO X， WANG W， et al. Few‑shot text classification by leveraging bi‑directional attention and cross‑class knowledge［J］. Science China Information Sciences， 2021， 64（3）： No.130103. 10.1007/s11432-020-3055-1
32	黄学雨，程世超. KNN优化的密度峰值聚类算法［J］. 通信技术， 2021， 54（7）：1608-1618. 10.3969/j.issn.1002-0802.2021.07.010
	HUANG X Y， CHENG S C. KNN optimized density peak clustering algorithm［J］. Communication Technology， 2021， 54（7）： 1608-1618. 10.3969/j.issn.1002-0802.2021.07.010
33	王芙银，张德生，张晓. 结合鲸鱼优化算法的自适应密度峰值聚类算法［J］. 计算机工程与应用， 2021， 57（3）：94-102. 10.3778/j.issn.1002-8331.2007-0205
	WANG F Y， ZHANG D S， ZHANG X. Adaptive density peak clustering algorithm combining with whale optimization algorithm［J］. Computer Engineering and Applications， 2021， 57（3）： 94-102. 10.3778/j.issn.1002-8331.2007-0205

[1]	Yunzhi QIU, Tinghua WANG, Xiaolu DAI. Doubly feature-weighted fuzzy support vector machine [J]. Journal of Computer Applications, 2022, 42(3): 683-687.
[2]	Xiangzhou QI, Hongjie XING. Centered kernel alignment based multiple kernel one-class support vector machine [J]. Journal of Computer Applications, 2022, 42(2): 349-356.
[3]	Mei WANG, Chuanhai XU, Yong LIU. Multi-kernel learning method based on neural tangent kernel [J]. Journal of Computer Applications, 2021, 41(12): 3462-3467.
[4]	XIAO Qi, YIN Zengshan, GAO Shuang. Extremely dim target search algorithm based on detection and tracking mutual iteration [J]. Journal of Computer Applications, 2021, 41(10): 3017-3024.
[5]	CHEN Hao, QIN Zhiguang, DING Yi. Multi-modal brain tumor segmentation method under same feature space [J]. Journal of Computer Applications, 2020, 40(7): 2104-2109.
[6]	LI Fei, DU Liang, REN Chaohong. Multiple kernel concept factorization algorithm based on global fusion [J]. Journal of Computer Applications, 2019, 39(4): 1021-1026.
[7]	SUN Shilei, WANG Chao, ZHAO Yuandi. Parameter independent clustering of air traffic trajectory based on silhouette coefficient [J]. Journal of Computer Applications, 2019, 39(11): 3293-3297.
[8]	FAN Jun, WANG Xin, XU Hui. Prediction method of tectonic coal thickness based on particle swarm optimized hybrid kernel extreme learning machine [J]. Journal of Computer Applications, 2018, 38(6): 1820-1825.
[9]	HU Lisha, WANG Suzhen, CHEN Yiqiang, HU Chunyu, JIANG Xinlong, CHEN Zhenyu, GAO Xingyu. Objective equilibrium measurement based kernelized incremental learning method for fall detection [J]. Journal of Computer Applications, 2018, 38(4): 928-934.
[10]	ZHANG Leyuan, LI Jiaye, LI Pengqing. Low rank non-linear feature selection algorithm [J]. Journal of Computer Applications, 2018, 38(12): 3444-3449.
[11]	NAN Jingchang, CUI Hongyan. Modeling of power amplifier based on dynamic X-parameter of new two-dimensional kernel function [J]. Journal of Computer Applications, 2017, 37(8): 2421-2426.
[12]	GUO Qian, YANG Hongju, LIANG Xinyan. Image retrieval method based on new space relationship feature [J]. Journal of Computer Applications, 2016, 36(7): 1918-1922.
[13]	LI Bin, DI Lan, WANG Shaohua, YU Xiaotong. Clustering algorithm with maximum distance between clusters based on improved kernel fuzzy C-means [J]. Journal of Computer Applications, 2016, 36(7): 1981-1987.
[14]	LI Hua, LI Deyu, WANG Suge, ZHANG Jing. Kernel improvement of multi-label feature extraction method [J]. Journal of Computer Applications, 2015, 35(7): 1939-1944.
[15]	WANG Weidong, LIU Bing, GUAN Hongjie, ZHOU Yong, XIA Shixiong. Spectral embedded clustering algorithm based on kernel function [J]. Journal of Computer Applications, 2015, 35(3): 761-765.

Neural tangent kernel K‑Means clustering

神经正切核K‑Means聚类

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 33

Related Articles 15

Recommended Articles

Metrics