1.   引言

模糊C均值(FCM)聚类由Bezdek^[1]在1981年提出，经过多年的研究，目前已经大量应用于机器学习、图像处理和数据挖掘等领域，是无监督类模式识别研究的重要内容之一。

随着各类应用领域的深入研究，出现大量改进算法。从算法参数结构和输入特征的角度看，FCM算法的改进基本上可以分为两类。第1类是FCM算法参数优化选取。为了自动确定聚类簇数，文献[2]将鲁棒竞争凝聚理论引入FCM中，所提出的RCA算法可以有效解决在聚类簇数个数未知情况下FCM算法聚类问题。文献[3]在此基础上提出一种基于鲁棒学习的RL-FCM算法，聚类效果得到大幅提高。为了生成最优初始聚类中心，文献[4]分别基于网格估计和密度估计生成最优初始聚类中心，继而提出两种改进算法GB-FCM和DG-FCM，相较于FCM更适合大数据聚类。为了选择最优模糊加权指数，文献[5]提出一种熵指数约束竞争凝聚聚类算法EICCA，不仅可以自动确定聚类个数，还可以自动选择最佳模糊加权指数。为了选择最适合的距离函数，除了现在广泛采用的欧式距离和马氏距离，文献[6]通过分析磁共振图像的特点，用局部和非局部区域的加权欧式距离替代传统的欧氏距离作为FCM距离函数，图像聚类准确度较传统算法更高。文献[7]用样本数据的几何散度值作为距离函数，改进的FCM算法不仅聚类准确度有所提高，还具有更强的抗躁性能。文献[8]基于样本影响值改进簇类中心计算方法和距离函数，所提出的SCMS-FCM算法对含有大噪声样本具有较好的处理效果。第2类是对算法输入数据进行分析处理。基于样本数据特征的一类改进方法，充分挖掘和利用样本点、各个簇类和样本总体三者间在样本空间的相对分布特征信息。实际上，由于样本特征差异的程度不同，此类改进方法的难点仍然是如何提取最显著的样本特征，然后对不同特征赋权^[9]。另外，在所提取的数据特征冗杂的情况下，选取尽量少的特征聚类也是当前关注的热点^[10]。在这两类改进思路的实现过程中，常将FCM算法与其他方法的混合或集成，如粒子群^[11]、遗传算法^[12,13]、神经网络^[14]、核函数^[15]等。

虽然上述改进算法在不同程度上提高了聚类性能，但是最后一步仍然采用传统的定类准则—最大模糊隶属度准则，简单地处理迭代后模糊隶属度矩阵以确定簇类标签，未对最大隶属度准则进行分析和改进。传统模糊理论认为，最大模糊隶属度准则可以保证最终所确定的样本隶属关系相对而言是最显著的。所以，在样本的各个模糊隶属度取值相差较大的情况下，此原则是简单且有效的。然而，在采用FCM算法进行实际聚类时会出现以下情况：在各个模糊隶属度取值差异较小的情况下，当设置不同的模糊加权指数、目标函数最小误差和迭代次数等基本参数时，继续使用最大模糊隶属度准则进行定类可能造成这些样本被错误分类，继而影响聚类准确度。

近年来，为了解决大数据背景下复杂多属性数据分析问题，除了传统的样本点间数据分析研究，研究人员也从属性降维技术^[16,17]、属性约简^[18,19]和属性空间的构建与表述^[20,21]等方面开展了大量样本属性空间研究。主成分分析(Principal Components Analysis, PCA)是应用最为广泛的属性空间降维技术之一，文献[17]基于PCA和极限学习机提出一种堆叠隐空间FCM改进算法，具有更高效的非线性数据处理能力，克服了传统FCM算法对模糊指数的敏感性问题。文献[19]将张量正则分解用于属性约简并与传统FCM结合，提出一种适用于物联网大数据的FCM改进算法，虽然聚类准确率略有降低，但是聚类效率得到了大幅提升，在物联网数据智能信息挖掘方面具有较大应用前景。但是，属性降维技术和属性约简将样本高维属性空间投影到低维属性空间，不同程度地造成原样本信息的丢失。因此，在降维或维数约简之前需要充分分析样本属性间的数据关联性影响。文献[21]分析成对属性间的关联性影响，构建可以体现属性间相互影响程度的成对关联属性空间，并应用于凝聚层次聚类算法的改进，结果比传统属性空间的结果更好。但是，文献[21]只给出了基于成对属性间余弦夹角的簇类间距离计算方法，证明过程和属性空间中的物理意义并未详细说明。

受到文献[21,22]启发，针对传统FCM中定类准则可能产生误判的问题，本文提出一种FCM算法新的改进思路：改进FCM算法的输出定类方法，即最大模糊隶属度原则。可以构建存疑样本与簇类中心在属性空间中的相似度计算模型，度量模糊隶属度取值无明显差异的样本与各个簇类中心的相似度，将相似度最大的簇类中心所在类作为此存疑样本所隶属的簇类。该思路可以充分利用迭代后簇类中心内涵丰富的不同簇类间的属性特征信息，实现对最大隶属度原则的有效改进。

因此，本文首先在分析FCM算法和最大模糊隶属度原则定类缺点的基础上，给出样本与簇类中心属性相似度的定义，详细说明样本属性相似度计算的空间几何模型的建立和推导过程，然后，提出一种基于属性空间相似性的改进FCM算法(FCM based on Similarity of Attribute Space, FCM-SAS)，可以在不增加算法复杂度的情况下，明显提高聚类准确度。最后，通过UCI数据实验验证改进算法的有效性，聚类指标较FCM算法和其他改进算法更优。

2.   FCM算法

假设具有$s$个属性的样本${\text{x}}$组成的样本集${\text{X}} =$$\left\{ {{{\text{x}}_1}, {\text{x}}_2,·\!·\!· , {{\text{x}}_n}} \right\}$，则FCM算法的目标函数$J$如式(1)所示

其中，${\text{V}} = \left\{ {{{\text{v}}_1},{\text{v}}_2, ·\!·\!· , {{\text{v}}_c}} \right\}$是$c$个可能的簇类中心；${\text{U}} = \left[ {{u_{ij}}} \right] \in \left[ {0, 1} \right]$是样本的模糊隶属矩阵，${u_{ij}}$表示样本点${x_j}$属于第$i$个簇类的模糊隶属度，数值越大隶属程度越强；$m$是模糊加权指数，一般取为2。

在满足式(2)所示约束条件的情况下，根据Lagrange乘子法，按照式(3)和式(4)经过多次迭代更新模糊隶属矩阵${\text{U}}$和簇类中心${\text{V}}$后，便可得到理论上的最优解。

3.   最大模糊隶属度原则分析与改进思路

传统FCM算法及其一些改进型算法基于最大模糊隶属度原则进行定类，在处理上述样本集的聚类问题时存在以下两个共性问题。

(1)只对模糊隶属矩阵$\text{U}$进行取极大值运算，存在误判的可能性。例如，在处理样本类别特征不鲜明的样本点${{\text{x}}_1}$和${{\text{x}}_2}$时，${{\text{x}}_1}{{\text{v}}_1} \approx {{\text{x}}_1}{{\text{v}}_2} \approx {{\text{x}}_1}{{\text{v}}_3}$和${{\text{x}}_2}{{\text{v}}_3} \gg {{\text{x}}_2}{{\text{v}}_1} \approx {{\text{x}}_2}{{\text{v}}_2}$，样本点${{\text{x}}_1}$和${{\text{x}}_2}$的隶属关系就取决于其模糊隶属度微小的数值大小差别。当算法设置不同的初始参数或者选择不同度量距离时，会使这些差别发生改变，可能影响最终的定类结果。

(2)在确定簇类标签时，忽略了迭代后的簇类中心。簇类中心的迭代变化可以看做是一种由大数据量样本集映射到小数据量样本集的压缩变换，蕴含了样本集全部簇类簇内和簇间的特征信息。忽略迭代后的簇类中心会降低这部分特征信息的有效利用，不利于聚类准确度的提高。

为了解决这两个问题，本文提出一种基于最大属性相似度原则定类的改进方法，其改进思路是初步筛选模糊隶属度分布不明显的样本作为存疑样本，再结合聚类中心的属性特征信息，对存疑样本进行2次定类。例如，对于${{\text{x}}_3}$, ${{\text{x}}_4}$和${{\text{x}}_5}$等模糊隶属度分布差异明显的样本点，可以根据最大模糊隶属度原则直接定类；然后，筛选出最大模糊隶属度低于已给定数值的样本作为存疑样本，此给定数值可以称为聚类置信度$\eta$，像样本点${{\text{x}}_1}$和${{\text{x}}_2}$这样的存疑样本便需要2次定类；最后，再分别计算存疑样本点与各个簇类中心的相似度，选取相似度最大的相似关系更新类别标签。

4.   最大属性相似度

首先定义样本的2元属性拓扑空间，然后在此空间中先后定义拓扑相似度集合和属性相似度。

定义1　设待聚类的样本点${\text{x}}$具有$s$个属性${\text{x}} = \left\{ {{x_1},{x_2}, ·\!·\!· , {x_s}} \right\}$, $\cal{T}\;$是由这些属性的某些子集所组成的集类，取$\cal{T} = {\cal{T}_2} \cup\varnothing \cup {\text{x}}$，其中${\cal{T}_2}$如式(5)所定义

则称$\left( {{\text{x}}, \cal{T}}\; \right)$为${\text{x}}$的属性拓扑空间，$\cal{T}\;$为${\text{x}}$的属性拓扑，$\left( {{\text{x}}, {\cal{T}_2}} \right)$为${\text{x}}$的2元属性拓扑子空间，${\cal{T}_2}$为${\text{x}}$的2元属性拓扑。

定义2　样本集${\text{X}} = \left\{{{\text{x}}_1}, {{{\text{x}}_2}, ·\!·\!· , {{\text{x}}_n}} \right\}$中任意两个样本点${{\text{x}}_1} = \left\{ {{a_1}, {a_2}, ·\!·\!· , {a_s}} \right\}$和${{\text{x}}_2} = \left\{ {{b_1}, {b_2}, ·\!·\!· , {b_s}} \right\}$，对其2元属性拓扑先后取$\rho$运算和$\gamma$运算，得到式(6)—式(8)

称$\gamma \left( {\rho \left( {{{\text{x}}_1}} \right), \rho \left( {{{\text{x}}_2}} \right)} \right)$是样本点${{\text{x}}_1}$和${{\text{x}}_2}$在2元属性拓扑子空间中的拓扑相似度集合，简记为$\gamma \left( {{{\text{x}}_1}, {{\text{x}}_2}} \right)$；此集合中元素个数称为拓扑相似度集合长度，简记为${\gamma _{\rm dis}} = C_s^2$。

例如，对于存疑样本点${{\text{x}}_3} = \left\{ {{d_1}, {d_2}, {d_3}, {d_4}} \right\}$和簇类中心${{\text{v}}_1} = \left\{ {{e_1}, \;{e_2}, \;{e_3}, \;{e_4}} \right\}$，其拓扑相似度集合$\gamma \left( {{{\text{x}}_3}, {{\text{v}}_{1}}} \right)$如式(9)所示

如果两者属于同一种簇类，那么在2元属性拓扑子空间中体现为$\gamma \left( {{{\text{x}}_3}, {{\text{v}}_1}} \right)$中所有或者大部分元素逼近1。

定义3　如果两个样本点${{\text{x}}_1}$和${{\text{x}}_2}$的拓扑相似度集合为$\gamma \left( {{{\text{x}}_1}, {{\text{x}}_2}} \right)$，记$\gamma \left( {{{\text{x}}_1}, {{\text{x}}_2}} \right)$中落在以1为中心，以$\delta$为半径的邻域${U^o}\left( {1, \delta } \right)$的元素个数为$\lambda$，则称

是样本点${{\text{x}}_1}$和${{\text{x}}_2}$在二元属性拓扑子空间中的属性相似度。显然，$\psi \in \left[ {0, 1} \right]$。两个样本越相似，则$\psi$越接近1；反之，则$\psi$越接近0。

5.   FCM-SAS算法

在上述分析和定义的基础上，提出一种基于属性空间相似性的模糊聚类算法(FCM-SAS)，具体步骤如表1所示。

表 1  FCM-SAS算法具体步骤

输入：	样本集${\text{X}}$、样本数$n$，聚类个数$c$、加权指数$m$、迭代阈 值$\varepsilon$、最大迭代次数T、聚类存疑率$\xi$、属性占比率$\kappa$；
输出：	样本标签集${{\text{X}}_l}'$；
1	按表1的传统FCM算法步骤得到迭代后模糊隶属度矩阵${\text{U}}$、簇类中心${\text{V}}$和样本标签集${{\text{X}}_l}$，令$j = 0$；
2	计算所有样本点${\text{x}}$的模糊隶属度最大值，按递增顺序排序并组成数组，选出此数组中第$\left[ {\xi \times n} \right]$个元素的数值作为聚类置信度$\eta$；
3	令$j = j + 1$，判断第$j$个样本的模糊隶属度$\max \left( {\left\{ {{u_{ij}}\left| {i = 1, 2, ·\!·\!· , c} \right.} \right\}} \right)$是否不大于聚类置信度$\eta$，若是则此样本为存疑样本，转步骤4；否则转步骤8；
4	按式(8)计算第$j$个样本与各个簇类中心在2元属性拓扑子空间中的拓扑相似度集合$\gamma \left( {{{\text{x}}_j}, {{\text{v}}_i}} \right)$，将所有集合中的元素取绝对值后按递增的顺序排序并组成数组，计算此数组中第$\left[ {n \times {\gamma _{dis}} \times \kappa } \right]$个元素与数值1之间差的绝对值作为邻域半径$\delta$；
5	以$\delta$为邻域半径，按式(10)计算第$j$个样本与各个簇类中心的属性相似度$\psi \left( {{{\text{x}}_j}, {{\text{v}}_i}} \right)$；
6	若最大属性相似度$\max \left( {\psi \left( {{{\text{x}}_j}, {{\text{v}}_i}} \right)} \right)$只有一个，则选出最大属性相似度时的簇类中心所在的类别作为此样本更新后的标签$x_{lj}'$，转步骤8；否则，转步骤7；
7	若最大属性相似度不止一个，则选择这些簇类中最大拓扑相似度集合之和$\widehat S = \max \left( {\Sigma \gamma \left( {{{\text{x}}_j}, {{\text{v}}_i}} \right)} \right)$时的簇类中心所在的类别作为$x_{lj}'$；
8	判断$j < n$，若是则转步骤3，否则输出更新后的样本标签集${{\text{X}}_l}'$。

下载: 导出CSV 

| 显示表格

在此算法中，如果聚类置信度$\eta$取值过大，则会筛选出包含大量无需再次定类的样本作为存疑样本，使得算法计算量增加；如果聚类置信度$\eta$取值过小，则初步筛选的存疑样本较少，对最终的聚类准确度无显著影响。对于不同簇类的样本，邻域半径$\delta$的取值是不同的，需要根据每个存疑样本与簇类中心的拓扑相似度集合中的元素分布确定。在此情况下，步骤2中的聚类存疑率$\xi \in \left( {0, 1} \right)$的应用不仅可以自动确定聚类置信度$\eta$，还可以保证筛选出的存疑样本占总体样本的比重适中。步骤4中属性占比率$\kappa \in \left( {0, 1} \right)$的应用可以生成合适的邻域半径$\delta$，保证在充分考虑整体属性相似性的基础上，计算存疑样本与簇类中心的属性相似度。

6.   仿真实验

6.1   实验说明

实验平台为一台配置Intel i7 3.6 GHz 中央处理器、8 G内存、安装Windows 7操作系统的计算机，在MATLAB R2017a中编写和运行。实验数据为专门用于测试机器学习和数据挖掘算法的UCI数据集：Iris, Wine, Seeds, Breast, Glass^[23]。采用普遍应用于聚类性能测试的聚类准确率(Accuracy Rate, AR)、兰德指数^[24](Rand Index, RI)和标准化互信息^[25](Normalized Mutual Information, NMI)作为聚类评价指标，指标数值越大，聚类性能越好，其定义分别为

其中，$z$为正确分类样本个数，$n$为样本数，${\rm{TP}}$为实际标签和聚类后标签都相同的样本对的个数，${\rm{TN}}$为实际标签和聚类后标签都不相同的样本对的个数，$C_n^2$为所有样本对的总个数，$P\left( i \right)$和$P'\left( j \right)$分别为实际样本标签组和聚类后标签组中各簇类标签出现的次数与总样本数的比值，${s_1}$和${s_2}$分别为实际样本标签组和聚类后标签组中簇类的个数。

FCM-SAS算法的输入参数如表2所示。

表 2  算法输入参数设置

参数	数值
加权指数$m$	2
迭代阈值$\varepsilon$	${10^{ - 3}}$
最大迭代次数$T\;$	$100$
聚类存疑率$\xi$	$0.3$
属性占比率$\kappa$	$0.5$

下载: 导出CSV 

| 显示表格

6.2   UCI数据集聚类分析

选择UCI中Iris, Wine, Seeds, Breast, Glass等数据集，进一步测试FCM-SAS算法对真实数据集的聚类效果，其统计描述如表3所示，其中Breast数据集存在有缺省属性的样本16个，本文已删除。

表 3  UCI数据集的统计描述

数据集	样本数	维数	簇类	各类占比
Iris	150	4	3	50:50:50
Wine	178	13	3	59:71:48
Seeds	210	7	3	70:70:70
Breast	683	9	2	444:239
Glass	214	9	6	70:17:76:13:9:29

下载: 导出CSV 

| 显示表格

从表3可以看出，Iris和Seeds为低维、簇类少、各类占比均匀的数据集，Wine为高维、簇类少、各类占比略微不均匀的数据集，Breast为高维、簇类少、各类占比不均匀的数据集，Glass为高维、簇类多、各类占比不均匀的数据集。这些数据集可以较好地测试聚类算法对不同数据分布特征数据集的聚类效果。数据集经FCM-SAS算法聚类处理后结果的评价指标与FCM算法、第1类相关改进算法(RCA算法^[2]、RL-FCM算法^[3]、KFCM算法^[26])、第2类相关改进算法(WFCM算法^[9]、FRCM算法^[10])和混合算法(PSO-FCM算法^[11]、GA-FCM算法^[11]、ABC-FCM算法^[11]、WGFCM算法^[12])对比。聚类结果对比如表4和表5所示，这些用来对比的算法都是以最大隶属度原则确定聚类标签的，评价指标数值为算法多次运行后的平均值，在相同数据集和同一指标的情况下加粗更优的指标数值。

表 4  UCI数据集聚类结果评价指标对比(1)

		FCM	RL-FCM	RCA	WFCM	FRCM	FCM-SAS(标准化样本)	FCM-SAS(未标准化样本)
Iris	AR	0.893	0.907	0.967	0.957	0.960	0.987	0.953
	RI	0.880	0.892	0.958	0.934	0.952	0.983	0.942
	NMI	0.750	–	–	0.831	0.873	0.949	0.8498
Seeds	AR	0.895	0.895	0.903	0.895	0.895	0.919	0.900
	RI	0.874	0.874	0.884	0.873	0.876	0.899	0.877
	NMI	0.695	–	–	0.677	0.697	0.717	0.671
Breast	AR	0.937	0.953	0.655	0.938	0.947	0.965	0.946
	RI	0.876	0.910	0.548	0.884	0.911	0.932	0.897
	NMI	0.730	–	–	0.736	0.755	0.782	0.688

下载: 导出CSV 

| 显示表格

表 5  UCI数据集聚类结果评价指标对比(2)

		FCM	PSO-IFCM	GA-IFCM	ABC-IFCM	KFCM	WGFCM	FCM-SAS(标准化样本)	FCM-SAS(未标准化样本)
Iris	AR	0.893	0.807	0.849	0.787	0.895	0.973	0.987	0.953
Wine	AR	0.949	0.655	0.652	0.642	0.942	0.966	0.955	0.781
Glass	AR	0.421	0.419	0.393	0.467	0.460	0.733	0.533	0.472

下载: 导出CSV 

| 显示表格

分析表4和表5，可以发现FCM-SAS算法对这5种不同类型实际数据集的聚类指标都比FCM算法更优，尤其是在对高维、簇类多、各类占比不均匀数据集Glass的聚类准确度提高了0.112，说明基于属性最大相似度原则的改进方法是有效的。是否对样本进行标准化处理对FCM-SAS算法的聚类性能会有影响，样本经过标准化处理的聚类评价指标整体上比未经过标准化处理的更优，这也与前文属性相似度原理分析相符。对于在聚类过程中量纲影响程度较大的数据集，比如Wine数据集，如果未经过标准化处理，FCM-SAS算法的聚类效果甚至远低于传统FCM算法。同时，相比于其他类型的改进算法，除了在处理Wine和Glass数据集时聚类指标比WGFCM算法低之外，FCM-SAS的聚类指标整体上是最优的，这说明FCM-SAS算法比多数现有改进算法更优。

表6是FCM-SAS算法聚类过程中的统计数据，其中，1次定类错误的样本数实际上就是传统FCM聚类错误的样本数，存疑样本数是需要进行2次定类的样本数。

表 6  FCM-SAS算法聚类过程统计数据

样本集	1次定类错误样本数	1次定类正确的存疑样本数	1次定类错误的存疑样本数	存疑样本数	2次定类正确样本数	2次定类错误样本数
Iris	16	29	16	45	43	2
Seeds	21	44	19	63	48	15
Breast	43	173	27	200	191	9
Wine	9	45	8	53	47	6
Glass	126	21	42	63	45	18

下载: 导出CSV 

| 显示表格

从表6可以看出，在聚类存疑率$\xi {{ = }}0.3$的情况下，大部分传统FCM算法定类错误的样本(1次定类错误的样本数)被FCM-SAS算法筛选为存疑样本数，经过属性相似度计算与比较，这些样本被2次定类。相较于1次定类错误的存疑样本数，2次定类错误的样本数明显减小；相较于1次定类正确的存疑样本数，2次定类正确的样本数明显增加，说明基于最大属性相似度原则的2次定类是聚类评价指标得到改善的主要原因。

综上：(1)对算法输出定类原则进行改进的新思路是有效的；(2)在处理实际数据时，基于属性最大相似度原则的改进方法显著提高了传统FCM算法的聚类性能；(3)FCM-SAS算法比上述改进算法整体上更优。

7.   结束语

本文建立样本属性相似度计算的空间拓扑模型，继而提出一种基于最大属性相似性原则定类的FCM-SAS算法，可以充分利用迭代后的模糊隶属矩阵和簇类中心的属性特征信息，在不显著增加算法复杂度的情况下，各项聚类性能评价指标都有得到提高。UCI数据集的聚类实验证明FCM-SAS算法的有效性，具有更优的聚类性能。在后续的研究中需要进一步考虑如何选取最优算法初始参数的问题。