距离修正的模糊C均值聚类算法

时间:2024-01-10 点赞:47928 浏览:95103 作者原创标记本站原创

关于算法及计算机工程及数据方面的免费优秀学术论文范文,算法有关经典论文范例,关于距离修正的模糊C均值聚类算法相关论文范文集,对写作算法论文范文课题研究的大学硕士、本科毕业论文开题报告范文和文献综述及职称论文参考文献资料下载有帮助。

摘 要 :经典的模糊C均值算法基于欧氏距离,存在等划分趋势的缺陷,分错率较高,只适用于球形结构的聚类.针对这一问题,利用数据的点密度信息,在数据点与聚类中心的距离度量中引入了调节因子,提出了一种基于密度的距离修正矩阵,并用其代替经典模糊C均值算法中的距离度量矩阵.通过人造数据集和UCI数据集的两组聚类实验,证实了改进算法对非球形结构的数据同样适用,且相比经典的模糊C均值算法具有更高的聚类准确率.

关 键 词 :聚类,模糊C均值,距离度量,点密度,调节因子

中图分类号: TP18,TP391.4,TP301.6文献标志码:A

Improved fuzzy C-means clustering algorithm based on distance correction

英文作者名LOU Xiao-jun1*, LI Jun-ying1, LIU Hai-tao1,2

英文地址(1.Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China,

2.Wuxi SensingNet Industrialization Research Institute, Wuxi Jiangsu 214135,China)

Abstract: Based on Euclidean distance, the classic Fuzzy C-Means (FCM) clustering algorithm has the limitation of equal partition trend for data sets. And the clustering accuracy is lower when the distribution of data points is not spherical. To solve these problems, a distance correction factor based on dot density was introduced. Then a distance matrix with this factor was built for measuring the differences between data points. Finally, the new matrix was applied to modify the classic FCM algorithm. Two sets of experiments using artificial data and UCI data were operated, and the results show that the proposed algorithm is suitable for non-spherical data sets and outperforms the classic FCM algorithm in clustering accuracy.

Key words: clustering, Fuzzy C-Means (FCM), distance measurement, dot density, regulatory factor

0引言

模糊聚类技术基于模糊集合论,被广泛应用于数据挖掘、模式识别、控制决策等领域,具有重要的理论和实际应用价值.模糊C均值(Fuzzy C-Means, FCM)算法是模糊聚类中最基本也是应用最广泛的方法之一,它是一种基于划分的聚类算法,依据最小二乘原理,采用迭代方法优化目标函数,最终得到每个样本点的归属[1-4].然而经典的FCM算法基于欧氏距离,只能适用于球形结构的聚类,最小化目标函数的方法具有对数据集进行等划分的趋势,对于其他结构的聚类分错率较高[5-6].因此出现了许多FCM的改进算法,有学者考虑了样本点不同维度对聚类效果的不同贡献,通过特征加权的方式来优化算法[7-9],有学者引入了不同的距离度量方法,如马氏距离[10-11]、组合距离[12]、权重距离[13],还有学者通过修正隶属度函数和目标函数来优化算法[14-15].本文基于数据的点密度信息,提出了一种基于距离修正的FCM(FCM based on Distance Correction, FCM-DC)改进算法,引入了距离度量的调节因子,弥补了欧氏距离等划分趋势的影响,通过人造数据和UCI数据的两组聚类实验,证实了该算法相比经典的FCM具有更广的适用范围和更高的聚类准确率.

模式识别中通常利用样本点之间的距离来度量其差异性,然后作为判别其归属的依据.经典的模糊C均值算法采用欧氏距离来度量样本间的差异性,虽然运算简单,但是对于非球形结构或者非对称结构的聚类存在缺陷.样本点密度能够反映其合群程度,同时也能一定程度上说明其对聚类的影响能力,因此利用样本点密度信息,构造了距离的调节因子,形成样本与聚类中心的距离矩阵,用于修正经典FCM.

2.1基于点密度的距离调节因子

在样本集X等于{x1,x2,等,xn}中,对于每个样本点xi,通常点密度函数的表达式定义为:

zi等于∑nj等于1j≠i1di j,di j≤σ,1≤i≤n(5)

其中:di j表示样本xi与xj之间的欧氏距离,σ是点密度的有效半径,可根据实际情况设置,σ越大得到的点密度相对值也越大.为了简化算法,提出了一种新的点密度定义方式:

zi等于1/min({di j}),1≤i≤n(6)

即将样本xi到其最近邻样本之间的距离的倒数作为其点密度.


利用式(6)定义的点密度信息,提出了用于FCM距离修正的调节因子,定义为:

3实验与分析

为了验证算法的有效性,对FCM-DC进行人造数据集和UCI数据集两组实验,并与经典FCM算法进行了比较与分析.实验采用Matlab程序仿真,参数都选择默认的常规配置,即m等于2,ε等于10-5,T等于100.

3.1人造数据集实验

为了能够直观地分析与对比聚类算法的性能,在二维坐标轴上随机生成两组样本点,分别代表两个类别子集.随机样本点满足以下规则:第一组样本点均匀分布在圆心(0,0),半径为1的圆形区域内,第二组样本点均匀分布在圆心(5.5,0),半径为5的圆形区域内,两组样本各100个点,因此第二组样本的密度小于第一组样本.对产生的样本点分别进行经典FCM聚类与FCM-DC聚类,实验重复进行20次,图1是某次实验的聚类结果对比图.

图片图1人造数据集上的单次聚类性能对比

表1给出了重复20次实验后,两种聚类算法的平均分错率及聚类中心的平均偏差.聚类中心的偏差定义为实际运算得到的聚类中心与真实聚类中心的绝对空间距离.从表1可看出:FCM-DC算法的聚类效果与真实情况更为接近,具有更高的聚类准确率.这是因为经典FCM算法具有等划分趋势的限制,样本点被自然划分到离聚类中心近的类别中,因此当样本点的分布密度不同时,FCM就会出现较高的分错率.而FCM-DC算法正是基于点密度信息,引入了距离修正的调节因子,因此在此类情况下,能够大大提升聚类的准确率.


表格(有表名)表1人造数据集20次实验平均聚类性能对比

聚类算法聚类平均

分错率/%聚类中心

平均偏差FCM聚类10.50.97FCM-DC聚类1.80.263.2UCI数据集实验

为了进一步验证FCM-DC算法的有效性,采用UCI数据集中的IRIS和WINE数据进行实验,因为这两组数据是国际公认的比较无监督聚类方法效果好坏的典型数据.其中IRIS数据包含150个4维的样本点,类别数为3,每类50个样本点.第一类数据与其他两类数据离得较远,第二类数据与第三类数据离得较近,且部分重叠,WINE数据包含178个13维数据,类别数也为3,三类样本数目各为59,71和48.

表2~3是FCM算法与FCM-DC算法对UCI数据集的聚类效果对比.在IRIS数据实验中,对于相隔较远的第一类数据,两种算法都能够完全做到没有错误,但对于有交叉重合的第二类和第三类数据,FCM-DC算法表现出了更高的准确率,总体准确率比FCM提升了12.6%,在WINE数据实验中,由于数据本身的高维稀疏特性,两种算法的聚类分错率都比较高,但FCM-DC算法仍然比FCM提升了9.1%的聚类准确率.实验说明,调节因子wi起到了距离度量的修正优化效果,提升了聚类的准确率.同时,由于这两组数据集是典型的非球形结构数据,因此实验也说明FCM-DC算法适用面更广.

表格(有表名)表2IRIS数据的聚类效果对比

聚类算法数据类别分错个数聚类分错率/%FCM聚类FCM-DC

聚类第一类0第二类13第三类3第一类0第二类9第三类510.679.33表格(有表名)表3WINE数据的聚类效果对比

聚类算法数据类别分错个数聚类分错率/%FCM聚类FCM-DC

聚类第一类40第二类25第三类23第一类33第二类22第三类2549.4444.944结语

针对经典模糊C均值算法存在的等划分趋势的缺陷,本文提出了一种距离修正的改进算法――FCM-DC.基于样本点密度信息,引入了距离修正的调节因子,对FCM算法样本差异性度量进行了修正.通过人造数据集与UCI数据集两组实验,对比分析FCM-DC与FCM算法的性能,结果表明,FCM-DC算法对于非球形结构的数据同样适用,且具有更高的聚类准确率.

相关论文

基于Matlab环境下的K均值聚类算法

这篇比较好论文范文属于参考文献免费优秀学术论文范文,关于比较好硕士学位论文,与基于Matlab环境下的K均值聚类算法相关论文文献综述范文。。

基于均值聚类的背景估计算法

这篇计算机工程论文范文属于参考文献免费优秀学术论文范文,计算机工程方面有关硕士论文开题报告,与基于均值聚类的背景估计算法相关论文参考。

聚类在话务量预测中的应用

本论文是一篇话务量类论文文献综述范文,关于聚类在话务量预测中的应用相关在职研究生毕业论文范文。免费优秀的关于话务量及样本及社会学方。