FCIVI算法的改进及仿真实验研究

黄胜　曹宇

摘要：模糊C均值（FCM）聚类算法可以用来建立样本对类别的不确定性描述。文章提出一种基于拉普拉斯系数优化目标函数的FCM聚类算法。在目标函数中引入拉普拉斯系数，给对象之间的结构信息赋予权重，从而提高算法的质量和效率。通过紧凑性来优化聚类的有效性，并利用最大有效性的方法来提高改进算法的抗噪性能。仿真实验表明，改进的FCM算法与标准算法相比具有更准确的聚类效果，且受噪声影响小，鲁棒性强。

关键词：模糊C均值聚类算法;拉普拉斯系数;紧凑性;鲁棒性

中图分类号：TP391.9 文献标识码：A 文章编号：1006-8228（2020）08-75-04

0 引言

聚类技术是一种对有限类型的集合或聚类集合进行搜索、识别、描述的数据挖掘技术。聚类分析是数据挖掘的一个重要功能，它可以获得数据的分布情况，从而观察到每个簇的特征，并对某些特定的簇进行集中分析。此外，聚类分析可以作为其他算法的预处理步骤（特征提取和分类等），大大提高了这些算法的精确度和挖掘效率。因此，聚类分析已经成为数据挖掘中一个非常活跃的研究领域。许多有效的聚类算法已经被开发出来，新的算法也在不断涌现。

为了提高聚类算法的性能和效果，有学者提出将其他领域的方法与聚类算法相结合，弥补聚类算法在数据挖掘领域的一些缺陷，充分发挥聚类算法的最优性能。常用的方法有：遗传算法、免疫算法、蚁群算法等。戴文华使用一种新型的可变长度染色体编码方案，通过选择随机采样点作为初始簇中心形成染色体，有效的避免了局部最优解，通过种群内遗传变异和并行化得到最优聚类数和聚类结果，种群间的“联姻”结合了k-means算法的高效率和并行遗传算法的全局寻优能力[1]。近年来兴起的人工免疫系统研究是一个新的应用领域。随着免疫算法的发展，为聚类分析领域带来了新的活力。陈曦等成功地将免疫算法应用于聚类分析[2]。在模糊聚类算法的研究中，Ruspini首先提出了基于目标函数的模糊聚类算法[3]，而真正有效的模糊聚类算法FCM（fuzzy C-Means）是Dunn提出的[4]。FCM算法简单、高效，在应用领域得到了广泛应用。FCM算法的缺点也很明显，针对FCM算法对初始化敏感、容易陷入局部极值点等缺点，李莉莉提出了一种基于模拟退火粒子群的模糊聚类优化算法[5]。该算法利用粒子群强大的全局寻优能力和模拟退火算法跳出局部极值的能力，克服了模糊c均值聚类算法的缺点。针对FCM算法容易陷入局部最优的问题，人们将进化计算的思想引入到FCM中，以达到全局优化的目的。现有算法主要有粒子群优化算法、基于模拟退火算法、遗传算法、进化策略算法等[6].

1 FCM聚类算法的缺陷分析

FCM算法（模糊C均值聚类算法）的基本思想是：在HCM算法的基础上引入不同类别样本的隶属函数矩阵和模糊系数m。与HCM算法相比，该算法在数据分类、聚类点计算、目标函数等方面进行了调整。

（6）输出聚类结果（V，U）。

FCM类型的聚类算法是一种基于划分的方法，正如划分方法本身存在缺点，它是依靠聚类簇个数c来对数据集进行劃分，而不考虑数据的自然结构和特征空间。因此，该算法有一个不合理的假设：待分析的数据是可以被聚类的。这种不合理的假设导致了现有的FCM类型的聚类算法没有分析数据集的聚类可能性，而是难以应用一定的数据隶属度。这将导致一些数据在特征空间中均匀分布，没有任何聚类结构，对这类不适合应用于FCM类型算法的数据集进行了模糊划分，从而得到难以解释的聚类分析的结果。

如图1所示，这是一个均匀分布的数据集，没有自然的结构，但是当设置聚类簇个数c=3时，FCM算法将产生图2中的划分，不同的数据分区是由不同的初始化产生的。因此，很难对聚类结果做出合理的解释，也不可能揭示数据中包含的结构信息，帮助用户产生新的想法或形成新的假设。

2 基于拉普拉斯系数优化目标函数的FCM聚类算法

2.1 基于拉普拉斯系数的优化目标函数

本文利用拉普拉斯系数对标准FCM算法的目标函数进行优化。拉普拉斯系数S=（S ij）用来表示样本j属于聚类中心i的加权系数。S ij的定义如下：

当我们把噪声点作为一个单独的类型时，它的重量是比其他类别更大，它也会影响整个有效性度量的值，因此更能抵抗噪音。只用来做一些小的调整以达到更好的分割结果。

3 算法仿真实验

为了验证本文提出的改进算法的性能，进行了仿真实验。首先，选取了UCI标准数据集Iris和Wine的数据集，设置模糊加权参数m=2和停止迭代条件8=0.01，经过20次迭代，结果表明该数据集被分为3类。同时将改进的FCM算法与标准FCM算法进行比较，如果聚类簇个数不同，得到的结果也不同。结果见表1。

从表1可以看出，与标准FCM算法相比，改进后的FCM算法更加精确。

然后利用Bupa肝损伤数据集检验有效性函数的降噪能力。数据集如图3所示。

数据集都用有效性函数进行了检验，我们使用不同的初始值进行了几次实验，都得到了相同的结果。因此，只需列出一个实验结果，不同数据集的有效性函数的变化如图4所示。

为了验证功能的鲁棒性，在图5所示的肝损伤数据集中随机加入100个噪声点，变化示意图如图6所示。

从图6可以看出，所提出的有效性函数能够给出两个数据集正确的聚类数，实验结果表明，该函数不受噪声的影响，具有较强的鲁棒性。

4 总结与展望

本文针对FCM聚类算法存在的缺陷，提出了一种基于拉普拉斯系数的目标函数FCM聚类优化算法。

仿真结果表明，改进的FCM算法的聚类效果比标准算法更准确，值得推广。但是在对目标函数进行优化的同时必定以损失时间为代价，合理的平衡二者之间的关系是未来需要研究的。此外如何在保证算法优化性的同时减少时间的损耗，是未来一段时间可以做的工作。

参考文献（References）：

[1]Dai Wenhua， Jiao Cuizhen， He Tingting. Research on K-means Cluster Based on Parallel Genetic Algorithm[J].Computer Science，2012.35（6）：171-174

[2]Chen Xi， Xu Jianing， Yang Jianxiong. Research on K-

means File Clustering Algorithm Based on ImmuneNehAiork[J].Computer Engineering and Design，2011.10：2629-2631

[3]Dunn J C.Well-separated Clusters and the Optimal FuzzyPartitions[J].J. Cybernet，1974.4（1）：95-104

[4]Ruspini E H.A New Approach to Clustering[J]， Information& Contr01，2009.15：22-32

[5]Li lili， Liu Xiyu， Liu Tao， Sun Xiujuan.A FCM clusteringalgorithm based on particle swarm optimization[J].Information technology and informationization， 2012.1：89-92

[6| Huang，S. Optimization of Big Data Fusion Scheduling inMaritime Communication Based on Fuzzy C-meansClustering Algorithm. CCAMLR SCIENCE， 2018.25（3）：229-236

★基金項目：湖南省教育厅科研项目“基于大数据分析的改进模糊C均值聚类算法研究”（No.18C1104）;校级科研项目“基于大数据的改进模糊C均值聚类算法研究”（No.2018809）;湖南涉外经济学院大学生创新训练项目“基于学生借阅行为分析的图书推荐系统”

作者简介：黄胜（1980-），男，湖南长沙人，硕士，高级工程师，主要研究方向：大数据，算法研究。