0 概述

聚类分析是将样本对象划分成子集的过程，即把每个子集作为一个簇，簇中的对象相似程度高，不同簇中的对象相异程度高。目前，聚类分析已被广泛应用于数据挖掘、模式识别和图像处理等领域，很多经典算法被提出用于样本对象的聚类，主要有基于划分、层次、密度、网格和模型五大类^[1]。模糊C均值(Fuzzy C-means，FCM)聚类算法是一种基于划分的聚类算法，其因简洁、高效而得到了广泛的应用^[2]，但在建立相似度矩阵、随机初始化聚类中心和预先确定聚类数目等方面还存在不足。在建立相似度矩阵的过程中，FCM算法采用欧氏距离的相似性度量只对凸数据具有良好的处理性能，在复杂形状和非凸数据中往往会失败，因此，确定合适的相似度矩阵是提高FCM算法聚类性能的关键因素。

相似度矩阵依赖于距离度量这一特点，吸引了很多学者的研究与关注。文献[3]提出一种基于加权欧氏距离的改进FCM算法，其中加权欧氏距离是将特征权值合并到常用的欧氏距离中，结果表明，适当的特征权值分配可以提高FCM算法的聚类性能。文献[4]引入一种鲁棒的非欧氏距离度量方法来提高传统FCM算法的效率，从而减少噪声和异常值对聚类性能的影响。文献[5]提出使用马氏距离和闵可夫斯基距离来代替欧氏距离，提高了FCM算法对于高维数据的识别能力。文献[6]提出一种基于散度相似性度量的FCM算法，其对噪声特征的扰动具有更强的鲁棒性。以上文献虽然提高了FCM算法识别高维数据和噪声等方面的聚类性能，但这些距离度量仍然无法对非凸数据聚类。文献[7]提出一种模糊核C均值聚类算法，该算法采用基于核的距离度量代替欧氏距离作为相似性度量，可以识别任意形状的聚类，但其中核宽度$ \sigma $都是通过反复实验得出的，增加了算法的计算复杂度和时间复杂度。文献[8]提出一种基于传递闭包和谱聚类的多中心FCM算法，解决了FCM算法无法处理非凸数据的问题，但算法中对于子簇初始数目和子簇数目的设置都缺乏理论支持。

本文借鉴文献[9]提出的密度敏感距离度量方法，提出一种基于密度敏感距离的改进FCM算法AMMF-DSD。在建立相似度矩阵时采用密度敏感距离代替欧氏距离，以解决FCM算法无法对非凸数据聚类的问题。同时为进一步提高算法的聚类性能，利用近邻传播(Affinity Propagation，AP)聚类算法^[10]获取粗类数，快速确定最佳聚类数的搜索范围上限，基于此改进最大最小距离算法获得具有代表性的采样点作为FCM算法的初始聚类中心，最后结合轮廓系数^[11]在聚类数搜索范围内自动确定最佳聚类数。

1 相关工作 1.1 FCM聚类算法

给定数据集：$ X=({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $。其中，每个数据对象$ {x}_{i} $包含$ d $个特征值，$ n $是样本数据集的个数。FCM算法将$ X $划分为$ k $个类，[$ {v}_{1}, {v}_{2}, \cdots , {v}_{k} $]为$ k $个聚类中心。FCM聚类算法的目标函数如式(1)所示：

$ J=\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{k}{u}_{ij}^{m}{‖{x}_{i}-{v}_{j}‖}^{2} $

(1)

其中，$ m $是模糊指标，$ m>1 $，$ {u}_{ij} $是样本点$ {x}_{i} $在第$ j $分组中的隶属度，$ ‖{x}_{i}-{v}_{j}‖ $是样本点$ {x}_{i} $和聚类中心$ {v}_{j} $之间的欧式距离。在满足约束条件$ \sum \limits_{j=1}^{k}{u}_{ij}=1 $的情况下对目标函数使用拉格朗日(Lagrange)乘数法，得到隶属度矩阵和聚类中心，分别如式(2)和式(3)所示：

$ {u}_{ij}=\frac{1}{\sum \limits_{c=1}^{k}{\left(\frac{‖{x}_{i}-{v}_{j}‖}{‖{x}_{i}-{v}_{c}‖}\right)}^{\frac{2}{m-1}}} $

(2)

$ {V}_{j}=\frac{\sum \limits_{i=1}^{n}{u}_{ij}^{m}{x}_{i}}{\sum \limits_{i=1}^{n}{u}_{ij}^{m}} $

(3)

FCM聚类算法具体步骤如下：

算法1   FCM聚类算法

输入  聚类数$ k $，初始聚类中心，模糊指标$ m $，终止误差$ \epsilon $

输出  聚类中心，隶属度矩阵

步骤1   按式(2)更新隶属度矩阵。

步骤2   按式(3)更新聚类中心。

步骤3   如果$ ‖{J}^{\left(k\right)}-{J}^{\left(k-1\right)}‖ <\epsilon $，则算法终止；否则回到步骤1，继续进行迭代。

1.2 密度敏感距离

根据上述FCM算法的过程可以明显看出，所获得相似度矩阵的准确性直接影响聚类性能。此外，相似度矩阵主要取决于距离度量的确定。因此，选择合适的距离度量方法对于提高FCM算法聚类性能至关重要。基于该距离获得的数据点之间的相似性度量必须满足以下两个一致性关系^[9]：1)局部一致性，即空间上相邻的数据点之间应具有较高的相似性；2)全局一致性，即位于同一流形上的数据点之间应具有较高的相似性。

传统的FCM算法通常采用欧氏距离来确定数据点之间的相似性，然而欧氏距离只考虑数据点之间的局部一致性特征，忽略了全局一致性特征。因此，对于复杂数据和非凸数据，基于欧氏距离的相似性矩阵往往无法准确地捕获实际的数据结构，从而导致聚类性能较差。如图 1所示，根据相似测度的全局一致性要求，同一流形上的数据点应具有较高的相似性，即点1与点3之间的相似性应高于点1与点2之间的相似性，但是在按照欧氏距离进行相似性度量时，点1与点3的相似性要明显小于点1与点2，这与期望不一致，即将欧氏距离作为相似性度量不能满足全局一致性。

为满足聚类结果的全局一致性，使相同流形结构中数据对的相似度高于不同的流形结构，必须使得穿过高密度区域以较短边相连的路径长度低于穿过低密度区域直接相连的两点间距离，即$ \overline{\mathrm{a}\mathrm{f}}+\overline{\mathrm{f}\mathrm{e}}+\overline{\mathrm{e}\mathrm{d}}+\overline{\mathrm{d}\mathrm{c}}+\overline{\mathrm{c}\mathrm{b}} <\overline{\mathrm{a}\mathrm{b}} $，如图 2所示。

本文提出一种基于密度敏感距离度量创建相似度矩阵的算法，通过引入密度敏感距离能够同时考虑全局一致性和数据分布的局部一致性，使获得的相似性矩阵可以更准确地捕获真实数据结构，从而解决FCM算法无法识别复杂非凸数据的问题。具体如下：

定义1   密度调整长度如式(4)所示：

$ L(x, y)={\mathrm{e}}^{\rho d\left(x, y\right)}-1 $

(4)

其中，$ d(x, y) $表示点$ x $与点$ y $间的欧氏距离，$ \rho $为伸缩因子，通过调节伸缩因子$ \rho $来放大或缩短两点间线段长度，可以同时满足全局一致性和局部一致性。基于密度调整长度进一步定义密度敏感距离，通过在图中寻找最短路径来测量一对点之间的距离。

定义2   将数据点看作一个加权无向图$ G=\left\{V, E\right\} $，$ V $表示顶点集合，$ E $表示边集合。令$ P\in {V}^{l} $为图上长度为$ l=\left|p\right|-1 $的连接点$ {p}_{1} $、$ {p}_{\left|p\right|} $之间的路径，其中，边($ {p}_{k}, {p}_{k+1} $)$ \in E, 1\le k <l $，$ {p}_{ij} $为连接数据点对$ \{{x}_{i}, {x}_{j}\} $的所有路径的集合，$ 1\le i, j <n $，$ {x}_{i} $与$ {x}_{j} $之间的密度敏感距离如式(5)所示：

$ {D}_{i, j}^{\rho }=\frac{1}{{\rho }^{2}}\mathrm{l}\mathrm{n}\mathrm{ }(1+{d}_{\mathrm{s}\mathrm{p}}({x}_{i}, {x}_{j}{\left)\right)}^{2} $

(5)

$ {d}_{\mathrm{s}\mathrm{p}}({x}_{i}, {x}_{j})=\underset{p\subset {P}_{\mathrm{i}\mathrm{j}}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum \limits_{k=1}^{\left|p\right|-1}\left({\mathrm{e}}^{\rho d\left({p}_{k}, {p}_{k+1}\right)}-1\right) $

(6)

其中，$ {d}_{\mathrm{s}\mathrm{p}}({x}_{i}, {x}_{j}) $表示图$ G $上节点$ {x}_{i} $和$ {x}_{j} $之间的最短路径距离，$ d({p}_{k}, {p}_{k+1}) $是节点$ {x}_{i} $到$ {x}_{j} $最短路径上任意相邻两点的欧氏距离。不难看出，本文提出的距离度量方法可同时满足距离度量的以下4种特性：

1) 自反性：$ {D}_{i, j}^{\rho }=0 $，当且仅当$ {x}_{i}={x}_{j} $。

2) 对称性：$ {D}_{i, j}^{\rho }={D}_{j, i}^{\rho } $。

3) 非负性：$ {D}_{i, j}^{\rho }\ge 0 $。

4) 三角不等式：$ {D}_{i, j}^{\rho }\le {D}_{i, k}^{\rho }+{D}_{k, j}^{\rho } $。

1.3 轮廓系数

轮廓系数是由KAUFMAN等人提出的一种用于评价算法聚类质量的有效性指标。该指标结合了凝聚度和分离度，不仅能够评价聚类质量，而且还可用于获取最佳聚类数。假设数据集的样本对象$ {x}_{i} $属于类A。数据集的聚类轮廓系数$ {S}_{k} $(平均轮廓系数)定义如式(7)所示：

$ \begin{array}{c}{S}_{k}=\frac{1}{n}\sum \limits_{i=1}^{n}\frac{b\left(i\right)-a\left(i\right)}{\mathrm{m}\mathrm{a}\mathrm{x}\left\{a\left(i\right), b\left(i\right)\right\}} \end{array} $

(7)

其中，$ n $为数据集中的样本个数，$ a\left(i\right) $表示样本点$ i $与同簇剩余样本对象的平均距离，$ b\left(i\right) $表示样本点$ i $与剩余每个簇的样本对象平均距离的最小值。轮廓系数的取值范围在$ \left[-\mathrm{1, 1}\right] $之间，其值越大，表明聚类的质量越好。对于现有的分类数，求取轮廓系数的最大值，与之对应的$ k $值就是最佳聚类数^[12]。结合相关资料和实验情况可知，本文采用轮廓系数来评价聚类效果从而获得最佳聚类数的方法是有效的。

2 基于密度敏感距离的改进FCM算法 2.1 基于密度敏感距离的FCM距离度量

改进后的FCM算法距离度量采用密度敏感距离，目标函数如式(8)所示：

$ J=\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{k}{u}_{ij}^{m}{D}_{ij}^{\rho } $

(8)

其中，$ {D}_{ij}^{\rho } $为样本$ {x}_{i} $与聚类中心$ {v}_{j} $之间的密度敏感距离，采用式(5)计算，$ {u}_{ij} $是样本点$ {x}_{i} $在第$ j $分组中的隶属度。在满足约束条件$ \sum \limits_{j=1}^{k}{u}_{ij}=1 $的情况下对目标函数使用拉格朗日乘数法求得隶属度矩阵，如式(9)所示：

$ {u}_{ij}=\frac{1}{\sum \limits_{c=1}^{k}{\left(\frac{{D}_{ij}^{\rho }}{{D}_{ic}^{\rho }}\right)}^{\frac{2}{m-1}}} $

(9)

基于密度敏感距离度量的FCM算法具体步骤如下：

算法2   基于密度敏感距离度量的FCM算法

输入  聚类数$ k $，模糊指标$ m $，初始聚类中心，终止误差$ \epsilon $

输出  聚类中心，隶属度矩阵

步骤1   第$ c $次迭代，根据式(9)更新隶属度矩阵。

步骤2   根据式(11)更新聚类中心。

步骤3   根据新得的聚类中心从密度敏感距离矩阵中获得新的$ {D}_{ij} $，重新计算隶属度函数$ {u}_{ij} $，迭代循环，直到聚类中心不发生变化，算法结束。

算法2中的聚类中心更新方式如下：将数据集中的样本点作为聚类中心，在确定初始聚类中心后，由上述密度敏感距离得到$ {D}_{ij}^{\rho } $。目标函数如式(10)所示：

$ J=\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{k}{u}_{ij}^{m}{D}_{ij}^{\rho }={u}_{j1}^{m}{D}_{j1}^{\rho }+{u}_{j2}^{m}{D}_{j2}^{\rho }+\cdots +{u}_{jn}^{m}{D}_{jn}^{\rho } $

(10)

已知$ {u}_{ij}^{m} $和任意两样本间的密度敏感距离矩阵$ {\boldsymbol{D}}^{M} $，即：

$ \left[\begin{array}{c}{D}_{11}^{\rho }{D}_{12}^{\rho }\cdots {D}_{1n}^{\rho }\\ {D}_{21}^{\rho }{D}_{22}^{\rho }\cdots {D}_{2n}^{\rho }\\ ⋮\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }⋮\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }⋮\\ {D}_{n1}^{\rho }{D}_{n2}^{\rho }\cdots {D}_{nn}^{\rho }\end{array}\right]\left[\begin{array}{c}{u}_{11}^{m}{u}_{21}^{m}\cdots {u}_{k1}^{m}\\ {u}_{12}^{m}{u}_{22}^{m}\cdots {u}_{k2}^{m}\\ ⋮\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }⋮\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }⋮\\ {u}_{1n}^{m}{u}_{2n}^{m}\cdots {u}_{kn}^{m}\end{array}\right]=\left[\begin{array}{c}{a}_{11}{a}_{12}\cdots {a}_{1k}\\ {a}_{21}{a}_{22}\cdots {a}_{2k}\\ ⋮\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }⋮\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }⋮\\ {a}_{n1}{a}_{n2}\cdots {a}_{nk}\end{array}\right]= $

$ {\boldsymbol{A}}_{n\times k} $

则第$ j $类的聚类中心$ {v}_{j} $如式(11)所示：

$ {v}_{j}=\left\{{x}_{i}|i=\underset{c}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}{A}_{cj}\right\}，j=\mathrm{1, 2}, \cdots , k $

(11)

2.2 最佳聚类数的确定

传统的FCM算法采用多种方法获取最佳聚类数$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $。文献[13]提出一些检验聚类有效性的函数来评估聚类结果并确定$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $，但是这些有效性函数自身存在一定的问题，一般很难直接确定。文献[14-15]提出使用一种新的紧密度和分离度的指标，文献[16-17]使用轮廓系数来确定$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $，这些算法在每次迭代中，通过有效性函数衡量聚类结果，最后利用指标值来估计$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $，但是对于大型数据集，需要较高的计算量资源。以上研究虽然确定了最佳聚类数，但仍存在$ k $值最优搜索不稳定、计算复杂度高等问题，因此，需要事先确定$ k $的搜索范围，即确定$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $的上下限$ \left[{k}_{\mathrm{m}\mathrm{i}\mathrm{n}}, {k}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right] $。由于$ {k}_{\mathrm{m}\mathrm{i}\mathrm{n}}=1 $表示样本均匀分布，无法区分样本基本特征，因此一般情况下设置$ {k}_{\mathrm{m}\mathrm{i}\mathrm{n}} $最小为2。关于如何确定$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，目前尚无明确的理论指导，很多学者根据经验规则$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}}\le \mathrm{i}\mathrm{n}\mathrm{t}\left(\sqrt[]{n}\right) $来获取，其中$ n $为样本点的个数^[18]，而文献[19]中所有数据集的样本数和实际类数并不具有这样的性质。由此可见，仅仅利用有效性指标或者经验规则确定FCM算法的最佳聚类数不具有普遍性，且FCM算法聚类中心的随机初始化更是对聚类质量造成了极大的影响。本文在引入密度敏感距离的基础上，利用AP算法获取粗类数作为$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，并结合轮廓系数自动确定最佳聚类数。AP算法的基本原理是经过样本对象彼此的消息传递以获取高质量的聚类中心，对于类内紧密、类间远离的聚类结构，AP算法能获得比较准确的聚类结果，但对于比较松散的聚类结构，算法倾向于产生较多的局部聚类，这使得算法产生的聚类数往往偏多，从而不能给出准确的聚类结果^[20]。AP算法中的偏向参数$ p\left(i\right) $表示样本点$ {x}_{i} $被选作聚类中心的倾向性，它对聚类数的大小有重要影响，$ p\left(i\right) $越大，倾向于产生的聚类数越多。本文将$ p\left(i\right) $统一设置为相似度矩阵的最小值$ {s}_{\mathrm{m}\mathrm{i}\mathrm{n}} $^[10]。经实验可证明，当$ p={s}_{\mathrm{m}\mathrm{i}\mathrm{n}} $时，算法结束时得到的聚类数和经验规则$ \mathrm{i}\mathrm{n}\mathrm{t}\left(\sqrt[]{n}\right) $相比，AP算法获得的聚类数$ {k}_{\mathrm{A}\mathrm{P}} $更接近正确类数。

2.3 初始聚类中心的确定

在上述聚类数搜索范围确定的前提下，基于密度敏感距离度量的FCM算法搜索聚类空间逐步增加聚类数。当聚类数为$ {k}_{\mathrm{m}\mathrm{i}\mathrm{n}} $时，基于最大最小距离算法原则^[21]选取$ {k}_{\mathrm{m}\mathrm{i}\mathrm{n}} $个样本点初始化FCM算法的聚类中心，之后每增加一个聚类数，在保持上一次初始聚类中心不变的基础上，再按照最大最小距离算法原则增加一个初始聚类中心，从而保持聚类结果的稳定性和延续性。基于最大最小距离算法选出的聚类中心倾向于属于不同类别的可能性比较大，这样可以得到较好的聚类结果。传统的最大最小距离算法利用比例系数$ \theta $作为限制条件来确定聚类数对聚类结果影响很大，而本文是在聚类数已知的前提下进行的，因此无需设定比例系数$ \theta $。此外，最大最小距离算法随机选择初始聚类中心，会使聚类结果不稳定。根据数据的实际分布情况，选取密度最大点作为最大最小距离算法的第一个聚类中心，这样所有的初始聚类中心都是确定的，其最终聚类结果也就保证了唯一且稳定，同时此方法有效地避免了噪声点的选取。

改进的最大最小距离算法具体步骤如下：

算法3   改进的最大最小距离算法

输入  聚类数搜索范围$ {k}_{\mathrm{m}\mathrm{i}\mathrm{n}}=2 $，$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}}={k}_{\mathrm{A}\mathrm{P}} $

输出    $ k $个聚类中心。

步骤1   求出各样本点之间的距离$ {d}_{ij} $，将密度最大的一个样本点作为第1个聚类中心$ {Z}_{1} $ ^[22]。根据$ {\rho }_{i}=\sum \limits_{j}x({d}_{ij}-{d}_{\mathrm{c}}) $确定$ i $点的密度大小，以$ i $点为圆心，包含在以截断距离$ {d}_{\mathrm{c}} $为半径的圆内点的个数，即为$ i $点的密度大小。

步骤2   当聚类数为2时，计算剩余样本对象到$ {Z}_{1} $的距离，找到距离$ {Z}_{1} $最大的样本点作为第2个聚类中心$ {Z}_{2} $。

步骤3   当聚类数为3时，计算剩余样本对象与$ {Z}_{1} $、$ {Z}_{2} $之间的距离，并求出它们之中的最小值$ {D}_{Zi} $，将第$ r $个样本作为第3个聚类中心。

步骤4   当聚类数为$ k $且$ k\le {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $时，对于已有的($ k-1 $)个聚类中心，计算剩余不属于聚类中心的样本对象分别到每个聚类中心的距离$ {D}_{ij} $，并计算$ {D}_{t}=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{i}\mathrm{n}\left({Z}_{i1}, {Z}_{i2}, \cdots , {Z}_{i\left(k-1\right)}\right)\right\} $，将第$ t $个样本作为第$ k $个聚类中心。当算法满足结束条件时，算法结束。

2.4 AMMF-DSD算法

为提高传统FCM算法对复杂数据和非凸数据的聚类性能，提高算法聚类结果的稳定性，本文在原有FCM算法思想的基础上，提出基于密度敏感距离度量创建相似度矩阵的改进FCM算法AMMF-DSD。首先利用密度敏感距离代替欧式距离创建相似度矩阵；然后通过设定AP算法的偏向参数$ p={s}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，获取粗类数作为$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，基于此改进最大最小距离算法获取一些有代表性的样本点初始化FCM算法的聚类中心；最后结合轮廓系数自动确定最佳聚类数。AMMF-DSD算法流程如图 3所示。

对AMMF-DSD算法的时间复杂度进行分析，主要包含以下3个部分：

1) 利用AP算法遍历整个数据集，以获取粗类数作为$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，其时间复杂度为$ O\left({n}^{2}\right) $，其中$ n $是数据点的个数。

2) 利用改进最大最小距离算法获取具有代表性的样本点作为FCM算法的初始聚类中心，其时间复杂度为$ O\left({n}^{2}\right) $。

3) 改进的FCM算法中主要涉及欧氏距离的计算，其计算复杂度为$ O\left({n}^{2}\right) $，引入的密度敏感距离度量由于采用Dijkstra的最短路径算法^[23]来实现最小路径距离的计算，其时间复杂度也为$ O\left({n}^{2}\right) $。

综上所述，AMMF-DSD算法的时间复杂度为3个部分时间复杂度之和$ O\left({n}^{2}\right) $，即AMMF-DSD算法的时间复杂度相比原FCM算法没有改变。但AMMF-DSD算法具有明显的优势：按照本文方法获取的$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $由$ n $降低为粗类数$ {k}_{\mathrm{A}\mathrm{P}} $，同时改进最大最小距离算法确定的聚类中心避免了FCM算法聚类中心初始化时可能出现的初始聚类中心过于邻近以及多个初始聚类中心都选自同一个类中而小类中没有初始聚类中心的情况。因此，AMMF-DSD算法收敛速度较快，可有效减少迭代次数。

3 实验与结果分析

通过在人工数据集和UCI数据集上进行实验评估和分析本文算法性能。实验环境为Intel^®Core^TMi5-1035G1CPU@ 1.00 GHz，内存为8 GB。编程环境为Eclipse，MATLAB R2016b显示实验结果。在Windws10操作系统的计算机上运行通过。实验数据集包括UCI数据集(Iris、Wine、TAE、Seeds、CMC、Blood、Heart-stat-log、Thyroid、Haber-man、Bu-pa)和人工数据集(Three-circles、Spiral、Line-blobs、Aggregation、Square1)。对比算法包括FCM、K-means和CFSFDP算法，其中，CFSFDP算法是一种快速搜索查询的利用决策图确定中心的算法^[22]，K-means算法采用欧氏距离建立相似度矩阵，是一种只适用于凸数据的聚类算法^[24]。本文采用聚类准确率(ACC)^[25]和调整兰德系数(ARI)^[26]对算法的聚类性能进行评估。

聚类准确率(ACC)用于评估算法的准确性，如式(12)所示，其中，$ {C}_{i} $是所提算法的类标签，$ \overset\frown{{{C}_{i}}} $是数据真实的类标签，$ \delta (x, y) $表示函数，$ \mathrm{m}\mathrm{a}\mathrm{p}\left(x\right) $作为最好的映射函数使用了匈牙利算法进行映射，对获得的中心和真实的中心进行映射。

$ {A}_{\mathrm{A}\mathrm{C}\mathrm{C}}=\frac{\sum \limits_{i=0}^{n}\delta \left(\overset\frown{{{C}_{i}}}, map({C}_{i})\right)}{n} $

(12)

调整兰德系数(ARI)如式(13)所示，其中，$ a $是属于$ U $的同类且属于$ V $的同类的数据对数目，$ b $是属于$ U $的同类但属于$ V $的不同类的数据对数目，$ c $是属于$ U $的不同类而属于$ V $的同类的数据对数目，$ d $是属于$ U $的不同类且属于$ V $的不同类的数据对数目。ARI数值越接近1代表聚类结果越好，越接近0代表聚类结果越差。

$ {A}_{\mathrm{A}\mathrm{R}\mathrm{I}}=\frac{2(ad-bc)}{(a+b)(b+d)+(a+c)(c+d)} $

(13)

3.1 聚类数搜索范围

本节运用AP算法确定聚类数的搜索范围上限，$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}}={k}_{\mathrm{A}\mathrm{P}} $，其中设定AP算法中的参考度为相似度矩阵$ \boldsymbol{S} $的最小值，即$ p={s}_{\mathrm{m}\mathrm{i}\mathrm{n}} $(忽略参数对聚类结果的影响)。与经验规则$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{i}\mathrm{n}\mathrm{t}\left(\sqrt[]{n}\right) $进行对比实验，实验结果如表 1所示。

从表 1可以看出，当运用AP算法确定$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $时，UCI数据集Iris、Wine、Heart-stat-log、Bu-pa和人工数据集Aggregation获取的聚类数目等于正确类数，而UCI数据集TAE、Seeds、CMC、Blood、Thyroid、Haber-man和人工数据集Three-circles、Spiral、Line-blobs、Square1获取的聚类数均大于正确类数，但是与经验规则$ \mathrm{i}\mathrm{n}\mathrm{t}\left(\sqrt[]{n}\right) $确定的$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $相比，显然AP算法获取的聚类数更接近正确类数，大幅缩小了$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $的搜索范围，由此验证了将AP算法获取的聚类数作为$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $是合理的。

3.2 算法对比与分析

在聚类数搜索范围确定的基础上，分别对UCI数据集Iris、Wine、TAE、Seeds、CMC、Blood、Heart-stat-log、Thyroid、Haber-man、Bu-pa和人工数据集Three-circles、Spiral、Line-blobs、Aggregation、Squarel进行的实验。其中，Line-blobs、Three-circles的伸缩因子$ \rho $设置为$ {\mathrm{e}}^{3} $，Iris、Wine、TAE、Seeds、CMC、Thyroid的伸缩因子$ \rho $设置为$ {\mathrm{e}}^{2} $，Spiral、Aggregation、Squarel、Blood、Heart-stat-log、Haber-man、Bu-pa的伸缩因子$ \rho $设置为$ \mathrm{e} $。

3.2.1 最佳聚类数

本节将AMMF-DSD算法和随机选取初始聚类中心的FCM算法进行实验对比，比较这两种算法关于聚类中心的不同初始化方法对轮廓系数Silhouette的影响，进而比较对最佳聚类数$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $的确定造成的影响。为减少误差，对每个数据集实验重复运行10次，所确定的最佳聚类数$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $如表 2所示。

从表 2可以看出，在聚类数搜索范围确定时，AMMF-DSD算法对于各种数据集获得的最佳聚类数都等于正确类数，而FCM算法只有Aggregation、Heart-stat-log、Bu-pa数据集的$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $等于正确类数，且AMMF-DSD算法得到的$ {k}_{\mathrm{o}\mathrm{p}\mathrm{t}} $对应的轮廓系数均大于FCM算法，这进一步验证了改进后的算法AMMF-DSD是有效的且获得的最佳类数是合理的。

由于传统的FCM算法随机选取初始聚类中心，使聚类结果存在不稳定的现象，因此随机选取4个数据集(Spiral、Line-blobs、Iris和Wine)对AMMF-DSD和FCM算法进行算法稳定性对比，实验结果如图 4所示。从图 4可以看出，FCM算法的轮廓系数会随着实验次数的不同而呈现出不同的聚类结果，其原因是FCM算法的初始聚类中心是随机选取的，因此聚类结果也表现出不稳定的状态，而AMMF-DSD算法是对传统FCM算法的改进，避免了初始聚类中心随机选取的问题，且聚类数的搜索范围又是确定的，其聚类结果就表现出较强的稳定性。AMMF-DSD算法和FCM算法聚类时得到的迭代次数如图 5所示。从图 5可以看出，AMMF-DSD算法的迭代次数明显小于FCM算法，即AMMF-DSD算法加快了算法的收敛速度，而FCM算法的迭代次数仍在不断变化。

3.2.2 人工数据集上的实验

分别在Three-circles、Spiral、Line-blobs、Aggregation和Square1这5个人工数据集上使用4种聚类算法进行实验，实验数据集见表 1，聚类结果如图 6~图 10所示。从图 6可以看出，FCM、K-means和CFSFDP算法在Three-circles数据集上的聚类效果都不理想，而AMMF-DSD算法能够正确划分数据类别。从图 7可以看出，FCM、K-means和CFSFDP算法在Spiral数据集上依然聚类效果不佳，不能正确聚类，而AMMF-DSD算法将正确地划分了数据类别。从图 8可以看出，FCM和K-means算法在Line-blobs数据集上的聚类效果不理想，CFSFDP和AMMF-DSD算法则得到了正确的聚类结果。从图 9可以看出，AMMF-DSD算法的聚类效果最好，CFSFDP算法次之，FCM和K-means算法在Aggregation数据集上的的聚类效果都不好。从图 10可以看出，在Square1数据集上，AMMF-DSD算法聚类效果最优，FCM和CFSFDP算法仅次之，而K-means算法的聚类效果最差。

通过对图 6~图 10实验的可视化对比实验分析可知，AMMF-DSD算法比K-means、FCM和CFSFDP算法更擅长对非凸数据和复杂形状的数据进行聚类。以上4种聚类算法在人工数据集上的性能对比如表 3所示。从表 3可以看出，AMMF-DSD算法在Three-circles、Spiral、Line-blobs和Squarel数据集上的聚类指标值都是1，在Aggregation数据集上的聚类指标值均大于对比算法，聚类性能最好，CFSFDP算法仅在Line-blobs数据集上的聚类指标值是1。从聚类指标值来看，AMMF-DSD算法聚类性能最优，CFSFDP算法次之，而FCM和K-means算法最差。可见，用密度敏感距离代替欧氏距离创建相似度矩阵大幅提高了原始FCM算法的聚类性能，聚类数搜索范围的确定和初始聚类中心的确定也提高了AMMF-DSD算法的稳定性，聚类效果较好。

3.2.3 UCI数据集上的实验

本组实验选取10个UCI数据集将AMMF-DSD算法的聚类结果同CFSFDP、FCM和K-means算法的聚类结果进行比较，实验数据集见表 1，各算法得到的ACC和ARI指标值见表 4。为了减少实验误差，每个数据集独立运行10次。从表 4可以看出：AMMF-DSD算法在这10个UCI数据集上的聚类指标值均高于K-means、FCM和CFSFDP算法，聚类性能最好；本文算法的聚类结果是相对稳定的，因此聚类效果较好；CFSFDP算法次之；K-means、FCM算法的指标值随着实验次数的不同而呈现出不同的聚类结果，聚类效果欠佳。通过上述分析可以看出，AMMF-DSD算法具有较好的聚类性能，并且聚类结果也更稳定。

4 结束语

针对传统FCM算法无法识别非凸数据，同时对复杂形状的数据聚类性能不佳的问题，本文提出使用密度敏感距离代替欧氏距离创建相似度矩阵的AMMF-DSD算法。该距离度量通过调整伸缩因子$ \rho $，可以同时满足全局一致性和局部一致性，使得到的相似度矩阵能够更准确地捕获真实的数据结构，从而实现对非凸数据的聚类。同时，使用AP算法确定最佳聚类数的搜索范围上限$ {k}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，基于此改进最大最小距离算法获取代表点初始化FCM算法的聚类中心，并结合轮廓系数确定最佳聚类数。实验结果表明，AMMF-DSD算法能够对非凸数据和复杂形状的数据进行聚类并提高算法的聚类性能和稳定性，同时加快算法的收敛速度。但是该算法在处理大规模数据时需要较大的存储空间和计算时间，并且算法结果受参数取值的影响大，下一步将结合Spark框架和抽样技术实现算法的并行化，改善算法的大数据聚类性能并减小对参数的敏感度。