Global data-driven fuzzy cluster validity index
-
摘要:
现有模糊聚类有效性指标(cluster validity index, CVI)在处理具有噪声干扰以及簇规模差异较大的数据集时，往往难以保持准确的评估性能。为此，本文提出了一个全局数据驱动指标(global data driven index, GDD)，该指标针对聚类结果中各簇规模的差异，设计了一套针对簇内紧致度与簇间分离度的基于簇规模的加权机制，以此来应对该差异对指标结果的影响。GDD指标设计时采用簇内紧致度与簇间分离度比值的形式，对于可能会出现的CVI结果根据聚类结果数目单调递增的情况进行遏制；在考虑模糊隶属度的簇内点的平均距离的基础上，基于不同规模的簇占数据集中的比重不同，对于较大的簇给予其更高的权重，在计算单个簇内紧致度的基础上引入了该簇样本数占总样本的比值，该加权机制将直接影响该簇紧致度结果对于加和过后的总紧致度的贡献，从而构建了更客观的簇内紧致度的表达；综合考虑了所有类中心之间的均值与不同规模的簇占数据集的比重，对于较大的簇给予更高的权重，在计算每个聚类中心到聚类中心均值的距离的基础上加入了该簇样本数占总样本的比值，从而锚定了上述距离结果占所有簇加和的距离结果的比重，这种加权机制构建了更合理的簇间分离度的表达。实验结果显示，GDD能够很好地适应各种模糊聚类算法，而且在面对复杂结构和噪声时表现出较强的鲁棒性。本文提出的GDD指标可以在复杂结构与噪声环境下较好地完成对各类模糊聚类算法的评价。
Abstract:Existing cluster validity index(CVI) for fuzzy clustering often struggle to maintain accurate evaluation performance when handling datasets containing noise interference or exhibiting significant differences in cluster sizes. To address these limitations, this study proposes a global data-driven(GDD) index. The GDD index incorporates a scale-aware weighting mechanism for intra-cluster compactness and inter-cluster separation to mitigate the adverse impact of imbalanced cluster sizes on validity assessment. First, the GDD index adopts a ratio-based formulation of intra-cluster compactness to inter-cluster separation. This design prevents the undesirable monotonic increase of the index value as the number of clusters grows. Second, to obtain a more objective measure of intra-cluster compactness, the index computes the average distance among data points within each cluster, incorporating fuzzy membership degrees. Crucially, recognizing that clusters of different scales contribute unequally to the overall dataset structure, larger clusters are assigned higher weights. Specifically, the ratio of the number of samples in each cluster to the total number of samples is introduced into the compactness calculation. This weighting scheme directly influences each cluster’s contribution to the overall compactness, thereby enhancing representational fairness and accuracy. Third, for inter-cluster separation, the index comprehensively considers both the centroid distribution and the relative sizes of different clusters. Rather than treating all centroids equally, the index assigns higher weights to centroids of larger clusters. When computing the distance from each cluster centroid to the mean of all centroids, the sample-size ratio of the corresponding cluster is incorporated. This adjustment anchors the contribution of each centroid’s distance to the total separation measure, resulting in a more reasonable and balanced expression of inter-cluster separation. To evaluate the effectiveness and robustness of the GDD index, extensive experiments were conducted using three representative fuzzy clustering algorithms. Experimental results demonstrate that the GDD index consistently identifies the optimal number of clusters with high accuracy, adapts well across various fuzzy clustering frameworks, and demonstrates strong robustness in challenging scenarios with noise and highly imbalanced cluster sizes. The proposed index provides a more comprehensive and reliable evaluation of fuzzy clustering algorithms in complex, noisy environments.
-
聚类作为一种无监督的机器学习方法[1-2]，其在数据处理和数据分析方向的能力适用于处理不同领域和类型的复杂数据[3]，尤其在数据挖掘、模式识别和图像处理等领域得到了广泛的研究和应用。聚类是将一个未标识的数据集划分成不同类簇的过程，尽可能使相似的数据被划分到同一个簇中，不相似的数据划分到不同的簇中[4]。聚类在研究和应用过程中有两个重要问题需要考虑：一是聚类算法，通过聚类算法来划分数据集，得到聚类结果；二是聚类验证[5]，通过评估聚类结果进而评估聚类算法的效果。
随着计算机科学的发展，尤其是大数据和人工智能的兴起，聚类算法得到了长足的发展和广泛的应用。经典的K均值聚类算法(K-Means)[6]和层次聚类方法[7]最早被提出，随后催生了基于密度[8-9]、网格和模型等的聚类方法[10-12]。以上这些通常都是硬聚类算法，在划分过程中要求每个数据点只能划分到一个唯一的簇中。这种非此即彼的划分方式难以适用某些不确定的数据集，在这种特殊的情况下，数据点可以同时归属于多个簇，具有一定的模糊性。这种需求催生了模糊聚类算法。Dunn[13]于1973年提出了模糊C均值聚类算法(fuzzy C-means，FCM)，后续Bezdek等[14]在此基础上发展并推广了FCM算法。FCM 是模糊聚类的代表算法，通过优化隶属度函数来计算每个数据点对于簇的隶属度。此算法成为模糊聚类的重要基础，在处理不确定性数据方面有了显著进展。但FCM也存在缺点，如对噪声数据敏感。针对这一问题，Krishnapuram等[15]提出了可能性C均值聚类算法(possibilistic C-means，PCM)，PCM引入了可能性隶属度，而非单一的隶属度，放宽了对隶属度的限制，赋予噪声点更低的隶属度，从而增强了聚类的鲁棒性。后续随着模糊聚类应用需求的增加，研究人员提出了更多种类的模糊聚类算法。例如，Pal等[16]提出的模糊可能性C均值聚类算法(fuzzy possibilistic C-means，FPCM)、Antoine等[17]提出的可能性模糊C均值聚类算法(possibilistic fuzzy C-means，PFCM)、Zhang等[18]提出的基于核的模糊聚类算法(kernel-based fuzzy C-means，KFCM)，KFCM将核空间的概念引入到模糊聚类算法中，增强了算法的鲁棒性。
聚类验证是对聚类的结果进行评估，以验证聚类算法的划分是否正确。聚类验证常用的方法是通过聚类有效性指标(cluster validity index, CVI)[19]来对聚类算法划分的结果进行计算，对比不同划分状态下的计算结果，选取最优的划分结果。CVI大体上可以划分为3种[20]，即外部有效性[21]、内部有效性[22]和相对有效性[23]，文中涉及的指标主要是内部有效性指标。内部有效性指标通过聚类结果的内部结构来评估聚类质量，不依赖于外部标签。常见的内部有效性指标有Calinski等[24]提出的CH(Calinski-Harabasz)指标、Davies等[25]提出的DB(Davies-Bouldin)指标，还有Dunn[13]提出的Dunn指标，但Dunn指标对于环状或者线性数据集的适应效果较差。此外还有，Xie等[26]的XBI(Xie-Beni)指标、Fukuyama等[27]提出的FSI(Fukuyama-Sugeno)指标、Wu等[28]等提出的WLI(Wu-and-Li)指标、Liu等[29]提出的不平衡指数( imbalanced index，IMI)、 Mittal等[30]提出的SMI(Saraswat-and-Mittal)指标、Zhu等[31]提出的基于方差的聚类有效性(the variance based clustering validity，VCVI)指标、Maulikh等[32]提出的MB(Maulik-Bandyopadhyay)指标和Tang等[33]提出的三重中心关系(triple center relation，TCR)指标等，这些指标都在CVI发展进程中起到一定作用。
上文提到的这些CVI在聚类质量的评估上起到重要作用，是聚类分析过程中不可或缺的一部分，但是它们也存在一些缺点和局限性：1)部分CVI对于簇的形状较为敏感，且对于现实数据中常出现的多噪声情况难以有合适的应对方法；2)基于FCM算法提出的CVI会因为FCM的错误分类导致出现错误的结果。如FCM算法的均匀效应会导致FCM算法在处理不平衡数据集时会出现错误结果[34-35]。
考虑以上问题，本文提出了一种新的CVI，称之为全局数据驱动指标(global data driven index，GDD)。该CVI共有2个部分组成。GDD全面考虑了簇内外的数据特征，同时2个部分的组合，将簇内紧致性和簇间分离性结合起来分析，从而更好地度量聚类结果的合理性。
针对提出的CVI，本文采用UCI数据集[36]、人工数据集和Olivetti Face数据集共19个数据集以及11个CVI进行了对比实验。为了增加实验的可信度，分别选取了一些含有噪声的数据集和一些数据分布不均匀的数据集进行对比实验。与此同时，为了验证GDD能否同时适应多种模糊聚类算法，本文采用了FCM、PFCM和KFCM这3种不同的模糊聚类算法。通过不同的模糊聚类算法进行实验验证，证明GDD有更强的适应力和更广泛的实用价值。此外，本文论证了GDD的收敛性，以证明新CVI在理论上的正确性。
1. 部分内部有效性评价指标分析
内部有效性评价指标通过分析聚类结果中簇的结构来衡量聚类划分的质量，无需使用外部的分类标签来对比判断。具体指标主要关注簇内紧致性（foc）和簇间分离性（fos）两个方面。这里介绍较为经典的5种有效性指标。
1) Dunn指标
Dunn指标是一种经典且有广泛应用的内部评价指标，其对非球形数据分布有较好的适应性。但是其对噪声敏感且计算较复杂。计算公式为
$$ \text{Dun}{\mathrm{n}}^{(+)}=\frac{\min\limits_{1\leq i< j\leq K} \{\mathrm{dis}({C}_{i},{C}_{j})\}}{\max \limits_{1\leq k\leq K} \{\mathrm{diam}({C}_{k})\}} $$ 式中：$ \mathrm{dis}({C}_{i},{C}_{j})=\min\limits_{{{{x}}_{{i}}}\in {{{C}}_{{i}}},{{{x}}_{{j}}}\in {{{C}}_{{j}}}} \{||{x}_{i}-{x}_{j}||\} $，$ \mathrm{diam}({C}_{k})= \max\limits_{{{x}_{i}},{{x}_{j}}\in {{{C}}_{{k}}}} \{||{x}_{i}- {x}_{j}||\} $。$ {C}_{i} $为第i个簇。
2) XBI指标
XBI指标通过计算簇内部数据点到聚类中心的距离来度量簇内紧致性，计算所有聚类中心之间的距离最小值来度量簇间分离性，考虑因素比较全面。但是其单独选用聚类中心之间的距离最小值来度量簇间分离性，会导致对不规则数据集处理的效果不佳。同时，指标容易随着聚类簇数增加而单调变化。其计算公式为
$$ \text{XB}{\mathrm{I}}^{(-)}=\frac{\displaystyle\sum \limits_{k=1}^{K}\displaystyle\sum \limits_{i=1}^{N}\mu _{ik}^{m}||{x}_{i}-{v}_{k}||}{N\times \min\limits_{{i}\neq {j}} \{||{v}_{i}-{v}_{j}||\}} $$ 式中：N为样本总数，K为聚类数。这里的距离通常采用欧氏距离。
3) WLI指标
WLI指标在度量簇内紧致性的公式中加入了模糊隶属度的和，更好地度量簇内数据的紧致性，同时采用聚类中心之间距离的最小值和中值来度量簇间分离性，对分离性的度量更加全面。其计算公式为
$$ \text{WL}{\mathrm{I}}^{(-)}=\frac{\displaystyle\sum \limits_{k=1}^{K}\left(\frac{\displaystyle\sum \limits_{i=1}^{N}\mu _{ik}^{2}||{x}_{i}-{v}_{k}|{|}^{2}}{\displaystyle\sum \limits_{i=1}^{N}{\mu }_{ik}}\right)}{\min\limits_{i\neq j} \{||{v}_{i}-{v}_{j}|{|}^{2}\}+\mathop {\mathrm{median}}\limits_{i\neq j} \{||{v}_{i}-{v}_{j}|{|}^{2}\}} $$ 式中min与median为簇中心之间的距离的最小值与中位数值。通常采用欧氏距离进行计算。
4) IMI指标
IMI指标在簇间分离性的度量上加入了不同簇之间的数据点数量比值，考虑了不同簇之间的不平衡比，对分离性的刻画更加准确。其公式为
$$ \text{IM}{\mathrm{I}}^{(-)}=\frac{\displaystyle\sum \limits_{k=1}^{K}\frac{\displaystyle\sum \limits_{i=1}^{N}u_{ik}^{q}||{x}_{i}-{v}_{k}||}{\displaystyle\sum \limits_{i=1}^{N}{u}_{ik}}}{\min\limits_{i\neq j} \{{\delta }_{ij}||{v}_{i}-{v}_{j}|{|}^{2}\}+\mathop{\text{median}}\limits_{i\neq j} \{{\delta }_{ij}||{v}_{i}-{v}_{j}|{|}^{2}\}} $$ 式中：$ {\delta }_{ij}={f}_{i}/{f}_{j},{f}_{i}> {f}_{j} $，$ {f}_{i}=\displaystyle\sum \limits_{n=1}^{N}{u}_{ni} $，可以看出$ {\delta }_{lj} $是簇$ {C}_{i} $和簇$ {C}_{j} $的不平衡比。
5) TCR指标
TCR指标通过计算聚类中心之间距离最小值和均值，以及聚类中心方差来度量簇间分离性，三重因素相互作用，互相平衡，更好地刻画了分离性。其计算公式为
$$ \begin{gathered} \text{TC}{\mathrm{R}}^{(-)}= \dfrac{\displaystyle\sum \limits_{k=1}^{K}\dfrac{\displaystyle\sum \limits_{i=1}^{N}u_{ik}^{2}||{x}_{i}-{v}_{k}|{|}^{2}}{\displaystyle\sum \limits_{i=1}^{N} \max\limits_{1\leq k\leq K} {u}_{ik}}}{\dfrac{N}{K-1}\left(\min \limits_{i\neq j} \{||{v}_{i}-{v}_{j}|{|}^{2}\}\times \mathop {\text{mean}}\limits_{i\neq j} \{||{v}_{i}-{v}_{j}|{|}^{2}\}\times \displaystyle\sum \limits_{k=1}^{K}||{v}_{k}-\overline{v}|{|}^{2}\right)} \end{gathered}$$ 式中：N为样本数，K为聚类数，min和mean分别为簇中心之间距离的最小值与均值。通常采用欧氏距离进行计算。
2. 全局数据驱动指标
GDD指标主要由簇内紧致性和簇间分离性两个部分组成。在参考XBI指标的整体结构基础上，GDD指标对簇内紧致性和簇间分离性的表达进行一些改进。
2.1 簇内紧致性表达
GDD指标的簇内紧致性的表达分为两个部分。第一部分foc为簇内所有数据点之间的平均距离，在此基础上，考虑到模糊聚类中的模糊隶属度，在计算数据点之间的欧氏距离时加上两点对当前簇的模糊隶属度，定义的公式为
$$ f_{\mathrm{oc}1}=\dfrac{\displaystyle\sum_{1 \leqslant i \lt j \leqslant n_k}^{ }u_{ik}u_{jk}||x_i-x_j||}{\dfrac{n_k(n_k-1)}{2}} $$ 式中：nk为第k个簇的数据点数目，uik为在第k个簇中第i个样本的模糊隶属度，xi，xj分别为该簇中两个互不相同的样本。距离计算采用欧氏距离。
第二部分foc为单个簇内部数据点的标准差，$ \overline{x} $表示簇内样本的样本均值，表达式为
$$ {f}_{\mathrm{oc}{2}}=\sqrt{\frac{1}{{n}_{k}}{{\sum \limits_{i=1}^{{n}_{k}}}||{x}_{i}-\overline{x}||^{2}}} $$ 将两个部分相加得到对单个簇内部紧致性的表达式，同时考虑到不同的簇所含数据点数目的不同，其在整个数据集中所占的比重不同。所以每个簇对整体数据紧凑程度的贡献不应相同，所占比重高的簇应当在整个数据集紧凑程度表达上有更高的权重。因此整体紧致性表达式由每个簇内部紧致性表达式加权相加得来，权重为当前簇的数据点数目占总体数据点数目的比值。最终表达式为
$$ \begin{gathered} f_{\mathrm{oc}}=\displaystyle\sum \limits_{k=1}^{K}\dfrac{{n}_{k}}{N}\left(\dfrac{\displaystyle\sum _{1\leq i< j\leq {{n}_{k}}}{u}_{ik}{u}_{jk}||{x}_{i}-{x}_{j}||}{\dfrac{{n}_{k}({n}_{k}-1)}{2}}+\right. \\ \left. \sqrt{\dfrac{1}{{n}_{k}}{{\displaystyle\sum \limits_{i=1}^{{n}_{k}}}||{x}_{i}-\overline{x}||^{2}}}\right) \end{gathered}$$ 使用加权距离和来衡量数据紧凑程度能更好地反映簇内的数据几何结构，也能更好应对形状各异的数据集。此外标准差的加入能增强GDD指标对簇内数据点紧致性和离散程度的评估能力。两个部分的结合使得GDD指标对簇内紧致性的评估更加全面。
2.2 簇间分离性表达
GDD指标的簇间分离性的表达分为两个部分。第一部分fos以所有聚类中心到聚类中心均值距离之和为基底，同时考虑到不同聚类中心所在簇所含数据点数目的不同，其在整个数据集中所占的比重不同。所以每个聚类中心所在簇对整体数据的贡献不应相同，所占比重高的簇应当在整个数据集上有更高的权重。因此，在每个聚类中心到聚类中心均值的距离上加上对应的权重。权重为当前聚类中心所在簇的数据点数目占总体数据点数目的比值。最终表达式为
$$ {f}_{\text{os}{1}}=\sum \limits_{k=1}^{K}\left(\frac{{n}_{k}}{N}||{v}_{k}-\overline{v}||\right) $$ 式中：$ \overline{v} $为所有簇中心的均值；N为样本总数。同样采用欧氏距离进行计算。
第二部分fos为所有聚类中心之间距离的均值，表达式为
$$ {f}_{{\mathrm{os}}{2}}=\mathop{\text{mean}}\limits_{i\neq j} \{||{v}_{i}-{v}_{j}||\} $$ 将两个部分相加即得到GDD指标对于簇间分离性的刻画，表达式为
$$ {f_{\mathrm{os}}}=\sum \limits_{k=1}^{K}\left(\frac{{n}_{k}}{N}||{v}_{k}-\overline{v}||\right)+\mathop{\text{mean}}\limits_{i\neq j} \{||{v}_{i}-{v}_{j}||\} $$ 关于簇间分离性刻画的第一部分，加权距离和在整体上对所有聚类中心与中心点的离散程度和分离性做评估，权重的引入进一步考虑了不同大小的簇对整体数据分离程度的影响。关于第二部分，聚类中心之间距离均值从另一个方面对所有聚类中心之间的分离程度做全面的评估。两者的互相结合使得GDD指标对簇间分离性的刻画更加全面深刻。
综上所述，GDD指标由两个部分组成：第一部分foc用来刻画簇内数据点之间的紧致性；第二部分fos用于刻画聚类中心之间分离性，也就是簇间分离性。
$$ \begin{gathered} \mathrm{GDD}({K}{)}^{(-)}=\dfrac{{f_{\mathrm{oc}}}}{{f_{\mathrm{os}}}}=\\ \dfrac{\displaystyle\sum \limits_{k=1}^{K}\dfrac{{n}_{k}}{N}\left(\dfrac{\displaystyle\sum_{1\leq i< j\leq {{n}_{k}}}{u}_{ik}{u}_{jk}||{x}_{i}-{x}_{j}||}{\dfrac{{n}_{k}({n}_{k}-1)}{2}}+\sqrt{\dfrac{1}{{n}_{k}}{{\displaystyle\sum \limits_{i=1}^{{n}_{k}}}||{x}_{i}-\overline{x}||^{2}}}\right)}{\displaystyle\sum \limits_{k=1}^{K}\left(\dfrac{{n}_{k}}{N}||{v}_{k}-\overline{v}||\right)+\mathop {\text{mean}}\limits_{i\neq j} \{||{v}_{i}-{v}_{j}||\}} \end{gathered}$$ (1) 2.3 CVI有效性证明
下面将对GDD指标的有效性做出证明，其中用到了Dunn指标作为参照。其公式为
$$ \text{Dun}{\mathrm{n}}^{(+)}=\frac{\min \limits_{1\leq i< j\leq K} \{\mathrm{dis}({C}_{i},{C}_{j})\}}{\max \limits_{1\leq k\leq K} \{\mathrm{diam}({C}_{k})\}} $$ 其中$ \mathrm{dis}({C}_{i},{C}_{j}) $和$ \mathrm{diam}({C}_{k}) $定义分别为
$$ \mathrm{dis}({C}_{i},{C}_{j})=\min\limits _{{{x}_{i}}\in {{C}_{i}},{{x}_{j}}\in {{C}_{j}}} \{||{x}_{i}-{x}_{j}||\} $$ $$ \mathrm{diam}({C}_{k})=\max \limits_{{{x}_{i}},{{x}_{j}}\in {{C}_{k}}} \{||{x}_{i}-{x}_{j}||\} $$ Dunn指标的论文中证明当Dunn>1时，Dunn指标会指出正确的聚类数目并且Dunn指标的数值越大标识当前的聚类效果越好。分析GDD指标的构成，猜测当在正确的聚类划分结构下，Dunn指标变得足够大，GDD指标会变得足够小。接下来将对这一猜测进行证明。
假设在聚类数目为K时，对数据集进行划分得到划分结果。分别使用GDD指标和Dunn指标对结果进行评估，得到评价数值GDD(K)和Dunn(K)。
定理1 设$ k \in \{2{,}3,\cdots ,N-1\} $，且$ \max \limits_{1\leq k\leq K} \{\text{di}{\mathrm{a}}^{2}({C}_{k})\} \geq 1 $成立。同时，$ {\mu }_{ik}\,(1\leq i\leq N, 1\leq k\leq K) $是模糊隶属度，而$ {\omega }_{ik}\,(1\leq i\leq N,1\leq k\leq K) $是相应硬划分的隶属度，其公式为
$$ {\omega }_{ik}=\begin{cases} 1,\quad k=\mathop{\text{argmax}}\limits_{1\leq {{k}^{*}}\leq K} \{{\mu }_{i{{k}^{*}}}\}\\ 0, \quad \mathrm{其他}\\ \end{cases} $$ 则可得
$$ \mathrm{GDD}(K)\leq \frac{2}{\mathrm{Dunn}(K)} $$ (2) 证明 设K类划分为数据集X的优化划分，其中$ X=\{{x}_{i}|1\leq i\leq N\} $，聚类中心为$ {v}_{k} (1\leq k\leq K) $，隶属度为$ {\mu }_{ik} (1\leq i\leq N,1\leq k\leq K) $。$ {n}_{k} $为第k个簇内部数据点的数目。推导foc和$ \text{diam}({C}_{k}) $的大小关系可得公式为
$$ \mathrm{diam}({C}_{k})= \max\limits_{{{x}_{i}},{{x}_{j}}\in {{C}_{k}}} \{||{x}_{i}-{x}_{j}||\}\geq \frac{\displaystyle\sum _{1\leq i< j\leq {{n}_{k}}}||{x}_{i}-{x}_{j}||}{\dfrac{{n}_{k}({n}_{k}-1)}{2}}={f}_{{\mathrm{oc}}{1}} $$ (3) $$ \mathrm{diam}({C}_{k})=\max\limits_{{{x}_{i}},{{x}_{j}}\in {{C}_{k}}} \{||{x}_{i}-{x}_{j}||\}\geq \sqrt{\frac{1}{{n}_{k}}{\sum \limits_{i=1}^{{n}_{k}}}||{x}_{i}-\overline{x}||^{2}}={f}_{{\mathrm{oc}}{2}} $$ (4) 结合式(3)和式(4)，且聚类结果中所有的簇都满足式(3)和式(4)，所以对式(3)和式(4)的加权和也满足。推出下式：
$$ \begin{gathered} f_\mathrm{oc} = \sum \limits_{k=1}^{K}\frac{{n}_{k}}{N}\left( \frac{\displaystyle\sum _{1\leq i< j\leq {{n}_{k}}}{u}_{ik}{u}_{jk}||{x}_{i}-{x}_{j}||}{\dfrac{{n}_{k}({n}_{k}-1)}{2}}+\sqrt{\frac{1}{{n}_{k}}{{\sum \limits_{i=1}^{{n}_{k}}}||{x}_{i}-\overline{x}||}^{2}} \right) \\ \leq 2{\max }_{1\leq k\leq K} \{\mathrm{diam}({C}_{k})\} \end{gathered}$$ (5) 同时，由于
$$ {f}_\text{os}\geq \underset{1\leq i< j\leq K}{\text{mean}} \left\{{\left|\left|{v}_{i}-{v}_{j}\right|\right|}^{2}\right\}\geq \mathrm{dis}({C}_{i},{C}_{j})\geq \underset{1\leq i< j\leq K}{\min } \mathrm{dis}({C}_{i},{C}_{j})\} $$ (6) 结合式(5)、(6)以及$ \max\limits_{1\leq k\leq K} \{\text{di}{\mathrm{a}}^{2}({C}_{k})\}\geq 1 $，可推出：
$$ \mathrm{GDD}({K})=\frac{f_\text{oc}}{f_\text{os}}\leq \frac{2 \max\limits_{1\leq k\leq K} \{\mathrm{diam}({C}_{k})\}}{ \min\limits_{1\leq i< j\leq K} \{\mathrm{dis}({C}_{i},{C}_{j})\}}\leq \frac{2}{\mathrm{Dunn}(K)} $$ 至此证明完毕。
从定理1的式(2)可知，在正确的聚类划分结构下，Dunn指标变得足够大，GDD指标会变得足够小，说明对应的聚类划分效果是非常理想的。
2.4 CVI时间复杂度分析
时间复杂度是衡量一个CVI面对由聚类算法划分后的数据集的处理效率的重要参照。一个优秀的CVI往往在拥有优秀识别正确率的基础上尽可能的达到更小的时间复杂度。时间复杂度因为有对CVI的实用性评估的功效，需要对其进行分析。
分析式(1)，将GDD分成以下部分进行时间复杂度的讨论。
1）计算全局质心。对于全局质心，有
$$ \overline{x}=\frac{1}{n}\sum \limits_{i=1}^{n}{x}_{i} $$ 对此，需要遍历数据集中所有共n个点，每个点d维，所以该部分的时间复杂度为$ O(nd) $。
2）计算模糊加权平均距离。对于每个簇j分别进行处理。每个簇的簇大小$ \left| {C}_{j}\right| ={n}_{j}\leq \tau $，其中$ \tau $为所有簇中最大的样本数量，所需计算的所有数据点对共$ O({\tau }^{2}) $对，每对计算距离$ \left|\left|{x}_{i}-{x}_{j}\right|\right| $的复杂度为$ O(d) $。每对需乘其隶属度$ O(1) $。因此该部分的总计算量为$ \displaystyle\sum \limits_{j=1}^{k}O({\tau }^{2}d) $，考虑其最坏时间复杂度为$ O(K{\tau }^{2}d) $，其中K为簇的数量。
3）计算簇内标准差之和。计算每个簇的质心$ \overline{{x}_{j}} $所需的时间复杂度为$ O(\tau d) $，接着计算$ \displaystyle\sum \limits_{{x}_{i}\in {C}_{j}}{\left|\left|{x}_{i}-\overline{{x}_{j}}\right|\right|}^{2} $，其时间复杂度为$ O(\tau d) $，这只是单个簇的复杂度，该部分总的时间复杂度为$ \displaystyle\sum_j^{ }O\left(\tau d\right)=O(nd) $。
4）计算加权类间距离。由于在以上部分已经计算了全局质心$ \overline{x} $和每个簇的质心$ \overline{{x}_{j}} $，因此该部分计算$ {\left|\left|\overline{{x}_{j}}-\overline{x}\right|\right|}^{2} $的时间复杂度为$ O(d) $，这同样是单个簇的复杂度，一共有K个簇，从而类间距离部分总共$ O(Kd) $，又因为需要遍历数据集内所有共n个点，这部分需要$ O(nd) $因此该部分的总复杂度为$ O(Kd+nd) $。
5）计算簇中心间的平均距离。单个簇中心对的距离$ \left|\left|\overline{{x}_{i}}-\overline{{x}_{j}}\right|\right| $的时间复杂度为$ O(d) $，而该簇中心对一共有K2对，因此该部分的总复杂度为$ O({K}^{2}d) $。
至此，可以得到GDD指标的时间复杂度为$ O(K{\tau }^{2}d+nd+Kd+nd+{K}^{2}d) $，而当聚类正确的情况下聚类数K应当远小于样本数n，因此GDD的时间复杂度最终记为$ O(K{\tau }^{2}d+nd) $。
表1中给出了文中参与实验的12个指标的时间复杂度。
表 1 12个指标的时间复杂度Table 1 Time complexity of 12 indicators序号 CVI 时间复杂度 1 CH $ O(K\tau d) $ 2 Dunn $ O({K}^{2}{\tau }^{2}d) $ 3 DB $ O(K{\tau }^{2}d) $ 4 MB $ O(Knd) $ 5 IMI $ O(Kn(d+K)) $ 6 XBI $ O(Knd) $ 7 VCVI $ O(K\tau d) $ 8 FSI $ O(Knd) $ 9 WLI $ O(Knd) $ 10 SMI $ O({K}^{2}{\tau }^{2}d+Knd) $ 11 TCR $ O(Kn(d+K)) $ 12 GDD $ O(K{\tau }^{2}d+nd) $ 从表1中可以看出，GDD的时间复杂度为 $ O(K{\tau }^{2}d+nd) $，属于高开销指标，同为高开销指标的还有Dunn指标与SMI指标，而其余指标在时间复杂度上均优于上述三者，这意味着GDD指标在实际使用时可能需要更多的时间来处理数据并得出结果。
3. GDD指标的仿真与对比实验
本文选取3个模糊聚类算法、11个对比CVI以及19个数据集来做对比实验。3个模糊聚类算法分别是FCM算法、PFCM算法和KFCM算法；11个对比CVI分别是CH、Dunn、DB、MB、IMI、XBI、VCVI、FSI、WLI、SMI和TCR指标；19个数据集分别是9个UCI数据集、9个人造数据集和Olivetti Face数据集。实验的软件环境如下：操作系统是Windows 11OS，编程软件是专业数学分析软件。实验的硬件环境如下：CPU是Intel(R) Core(TM)i9-12900 KF，显卡是NVIDIA GeForce RTX3090，内存是64 GB。
3.1 数据集与对比指标
在本实验中，主要采用3类数据集进行研究，分别为UCI数据集、人工合成数据集以及Olivetti Face数据集。本实验选取UCI数据集中的9个数据集，分别是Zoo、Hayes-Roth、Iris、Glass、Dermatology、Breast Cancer、Balance Scale、Libras、Letter数据集。其中Zoo数据集来自动物数据，数据维度为16维，共有101个样本点，正确的聚类数目为7类；Hayes-Roth数据集来自社科研究，数据维度为4维，共有132个样本点，正确的聚类数目为3类；Iris数据集来自不同品种的鸢尾花数据，数据维度为4维，共有150个样本点，正确的聚类数目为3类；Glass数据集来自具有不同元素含量的玻璃的数据，数据维度为9维，共有214个样本点，正确的聚类数目为6类；Dermatology数据集来自一种疾病的医疗数据，数据维度为34维，共有366个样本点，正确的聚类数目为6类；Breast Cancer数据集来自肿瘤数据，用于预测肿瘤的性质，数据维度为30维，共有569个样本点，正确的聚类数目为2类；Balance Scale数据集来自模拟心理学实验结果，数据维度为4维，共有625个样本点，正确的聚类数目为3类；Libras数据集来自人手部动作数据，数据维度为90维，共有360个样本点，正确的聚类数目为15类；Letter数据集来自字符图像数据，数据维度为16维，共有
20000 个样本点，正确的聚类数目为26类。为了避免实验的数据集的类型单一，本实验同样选取部分人造数据集进行实验来增强实验的可信性。人工数据集作为评估聚类算法在不同结构、密度、维度和噪声条件下性能的工具，其允许研究者精确控制簇的结构、形状、密度、重叠度及噪声水平的特性，能够针对不同的被测对象设计对应的测试内容，从而系统地评估被测对象的鲁棒性、可拓展性和对特定模式的识别能力。人工数据集常常通过高斯分布采样或者数据点，再通过高斯噪声引入坐标扰动，通过不同的设计与配比得到满足要求的数据集合。其中包含有9个人造数据集，分别为Data_60、Data_150、Circle、Jain、X8D5K、Data_77、E6、Dim_128和Dim_256数据集。Data_60数据集的数据维度为2维，共有60个样本点，正确的聚类数目为3类；Data_150数据集的数据维度为2维，共有150个样本点，正确的聚类数目为3类；Circle数据集的数据维度为2维，共有150个样本点，正确的聚类数目为2类；Jain数据集的数据维度为2维，共有373个样本点，正确的聚类数目为2类；X8D5K数据集的数据维度为8维，共有1000 个样本点，正确的聚类数目为5类；Data_77数据集的数据维度为2维，共有1000 个样本点，正确的聚类数目为7类；E6数据集的数据维度为2维，共有8537 个样本点，正确的聚类数目为4类；Dim_128数据集的数据维度为128维，共有1024 个样本点，正确的聚类数目为16类；Dim_256数据集的数据维度为256维，共有1024 个样本点，正确的聚类数目为16类。同时，本实验选取Olivetti Face数据集，来验证实验在图像数据上的准确性。实验前对Olivetti Face数据集进行切割处理，处理后的数据集包含40类人脸图像，每类10张图像，10张图像是同一个人在不同状态下的面部图像，每张图像大小为
4096 个像素点。图1给出了部分上述数据集在正确聚类数目下的分布情况。其中维度大于2的数据集采用TSNE方法降维到3维后给出。Olivetti Face数据集的缩略图如图2所示。
图 1 数据集的分布Fig. 1 Distribution of datasets
下载:
全尺寸图片
本实验选取另外11个CVI作为对比指标，分别是CH、Dunn、DB、MB、IMI、XBI、VCVI、FSI、WLI、SMI和TCR指标。通过与各种不同CVI进行对比实验，来验证提出的GDD指标具有更强的适应性和更高的准确性。
3.2 对比实验
本实验采用FCM算法、PFCM算法和KFCM 算法对CVI的准确性进行验证。在正确聚类数目为2~10的数据集上，每个数据集进行10轮实验，每轮实验的K值从2变到10；在正确聚类数目为2~30的数据集上，每个数据集进行30轮实验，每轮实验的K值从2变到30。实验结束后，收集所有实验数据，并根据不同CVI最优值的分布统计各轮实验中CVI对应的最优聚类数目。表2给出了UCI数据集在上述3种算法下的实验结果，其中的数据表示各轮实验中最优聚类数目及其出现的频次。例如，数据“2733”表示在10轮实验中，聚类数目为2的最优值出现了7次，而聚类数目为3的最优值出现了3次。
表 2 UCI数据集的实验结果Table 2 Experimental results of UCI dataset算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Zoo 210 210 210 710 5278 210 283141 310 2377 710 710 710 Hayes-Roth 210 93107 310 310 2337 213742 213544 3248 310 310 233641 310 Iris 210 3951 310 310 3852 310 364153 1010 310 310 2139 310 Glass 210 2634 310 210 225266 5367 210 385161 475162 5961 5268 610 Dermatology 2832 223256 210 475261 6773 6773 210 2238 415564 2763 4367 4268 Breast Cancer 210 2862 210 210 210 2832 2832 210 283151 210 210 210 Balance Scale 283151 3248 2733 2852 233245 213346 3862 253253 315762 273251 224761 4159 Libras 22233
5471215312
4321535
4101822208 1441520
1661391415
15622533
623030 1471517
176216106
114154103132
1420155114142
1522162Letter 22036
42522631747 230 210318
5226102718
3022052215
23425621953
103142
1532825291
3042422518
264276230 2212625
2723022222623
275PFCM Zoo 210 210 210 710 516178 210 2842 310 2377 4278 710 710 Hayes-Roth 310 2192107 310 310 263351 3842 3743 354372 3941 310 223642 3941 Iris 210 3951 310 2238 384151 310 364252 1010 310 310 310 310 Glass 210 2733 213851 210 5367 415168 210 310 4367 415861 5268 610 Dermatology 2832 223157 2852 445165 416772 6773 210 2238 5763 2763 425167 4169 Breast Cancer 210 2862 210 2941 210 210 210 210 2832 210 210 210 Balance Scale 2832 213247 2733 284151 213346 3347 3862 2753 5862 273251 2248 510 Libras 22333
54215310
436221535
49711821206
2431421521
1662011361415
15617322433
621013030 1441517
1762032161010
1541031423
1541141525
161Letter 22236
4226317
4582230 210318
516126102720 2215239
256223103
1421522825292
3032518266
276230 2625273
3022222620
275283KFCM Zoo 210 210 210 2179 415178 210 2941 3753 224177 5179 710 710 Hayes-Roth 310 21109 310 2238 210 310 213841 213743 310 3763 364272 310 Iris 210 3941 310 2238 2139 3852 375281 1010 310 310 310 310 Glass 210 273261 310 210 5268 215168 210 310 214663 225761 315267 4268 Dermatology 2832 4258 210 4466 216772 6872 210 3852 325761 275261 4268 6971 Breast Cancer 210 283161 210 210 210 210 210 210 2832 210 210 210 Balance Scale 2832 2149 253342 253342 213445 223345 376271 210 5862 275162 214653 5961 Libras 22232
5410221539
447221533
410521531821
2052411441522
1641371417
15622134
653030 1517176
20721631
109154103132
14211541421522
166Letter 21934
42527326319
45230 210318
5224526
1027152042215
23525622142103
1421522824294
3022518266
273303230 204222
26212732222624
273291表2第一部分是FCM算法下CVI的实验结果。以其中的Dermatology数据集为例，Dermatology数据集的正确聚类数目为6类，MB指标10轮的结果中7轮是4类为最优值，2轮是5类为最优值，1轮是6类为最优值，其他CVI不再赘述。统计出现次数最多的最优值聚类数目作为该指标的评价结果，MB指标结果为4类，WLI指标结果为5类，GDD指标结果为6类。可以看出，MB指标和WLI指标的结果不正确，GDD指标正确得出了Dermatology数据集的聚类数目。
图 2 Olivetti Face数据集Fig. 2 Olivetti Face dataset下载:
全尺寸图片
统计表2中的数据，选取实验结果中出现次数最多的聚类数目作为最终的指标评价结果，形成表3。例如FCM算法下，Dermatology数据集Dunn指标的实验结果是“475261”，比较不同聚类数目出现的次数，得出最终的聚类数目为4类。
表 3 UCI数据集的Eff统计结果Table 3 Eff statistical results of UCI dataset算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Zoo 2 2 2 7 7 2 2 3 7 7 7 7 Hayes-Roth 2 10 3 3 3 3 3 4 3 3 3 3 Iris 2 3 3 3 3 3 3 10 3 3 3 3 Glass 2 2 3 2 6 6 2 3 4 5 6 6 Dermatology 2 5 2 4 6 6 2 3 5 2 6 6 Breast Cancer 2 2 2 2 2 2 2 2 2 2 2 2 Balance Scale 2 4 2 2 4 4 3 2 5 2 4 5 Libras 2 2 2 18 15 14 2 30 15 2 14 15 Letter 2 3 2 3 27 22 2 28 25 2 26 26 Eff 0.11 0.22 0.33 0.44 0.78 0.56 0.44 0.11 0.56 0.44 0.78 0.89 PFCM Zoo 2 2 2 7 7 2 2 3 7 7 7 7 Hayes-Roth 3 10 3 3 2 3 3 3 3 3 3 3 Iris 2 3 3 3 3 3 3 10 3 3 3 3 Glass 2 2 3 2 6 6 2 3 6 5 6 6 Dermatology 2 5 2 6 6 6 2 3 5 2 6 6 Breast Cancer 2 2 2 2 2 2 2 2 2 2 2 2 Balance Scale 2 4 2 2 4 4 3 2 5 2 4 5 Libras 2 2 2 18 15 14 2 30 15 2 14 15 Letter 2 3 2 3 27 22 2 28 25 2 26 26 Eff 0.22 0.22 0.33 0.44 0.67 0.56 0.44 0.22 0.67 0.44 0.78 0.89 KFCM Zoo 2 2 2 7 7 2 2 3 7 7 7 7 Hayes-Roth 3 10 3 3 2 3 3 3 3 3 3 3 Iris 2 3 3 3 3 3 3 10 3 3 3 3 Glass 2 2 3 2 6 6 2 3 4 5 6 6 Dermatology 2 5 2 6 6 6 2 3 5 2 6 6 Breast Cancer 2 2 2 2 2 2 2 2 2 2 2 2 Balance Scale 2 4 2 2 4 4 3 2 5 2 4 5 Libras 2 2 2 18 15 14 2 30 15 2 14 15 Letter 2 3 2 3 27 22 2 28 25 2 26 26 Eff 0.22 0.22 0.33 0.56 0.67 0.56 0.44 0.22 0.56 0.44 0.78 0.89 注：加粗代表该数值和正确的聚类数目一致。 此时需要借助评价因子来对CVI的性能进行评价。选取的评价因子为有效性比率(effectiveness ratio，Eff)[37]，其值为CVI得到正确聚类数目结果的数据集个数与总的数据集个数的比值。Eff的计算公式为
$$ L_{\mathrm{Eff}}=\frac{1}{D}\sum \limits_{d=1}^{D}\theta , \theta =\begin{cases} 1, \quad k\mathrm{是正确聚类数}\\ 0, \quad \mathrm{其他}\\ \end{cases} $$ 分析表3的统计数据可以看出，本文提出的GDD指标在UCI数据集上的实验结果中相较于其他CVI准确率更高。GDD指标在FCM算法、PFCM算法和KFCM算法上均是有1个数据集的结果错误，准确率达到89%。其他准确率较高的指标，例如IMI指标和TCR指标，其在FCM算法上的准确率大致在78%左右，在PFCM算法和KFCM算法上的准确率稍低一点在70%左右。剩余的指标准确率大多都在60%以下。从实验结果可以分析出，本文提出的GDD指标在3个算法上的准确率均高于其他CVI，说明GDD指标对于不同算法的适应力均优于其他CVI。同时对比不同CVI在不同算法下的准确率，例如WLI指标在FCM算法上的准确率为56%，而在PFCM算法下的准确率为67%，这在一定程度上说明不同的CVI有着更契合CVI本身的算法。
为了更精细地确定一个CVI的评价效果和稳定程度，在此引入另外一个评价因子来对实验结果进行评价。引入的评价因子为有效性偏差(Bias)，其值为实验所得的聚类数目和正确聚类数目之间差值的绝对值。Bias的计算公式为
$$ L_{\mathrm{Bias}}=\sum\limits_{d=1}^D|k-k_{\mathrm{true}}| $$ 应用Bias评价因子后得到表4。
表 4 UCI数据集的Bias统计结果Table 4 Bias statistical results of UCI dataset算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Zoo 5 5 5 0 0 5 5 4 0 0 0 0 Hayes-Roth 1 7 0 0 0 0 0 1 0 0 0 0 Iris 1 0 0 0 0 0 0 7 0 0 0 0 Glass 4 4 3 4 0 0 4 3 2 1 0 0 Dermatology 4 1 4 2 0 0 4 3 1 4 0 0 Breast Cancer 0 0 0 0 0 0 0 0 0 0 0 0 Balance Scale 1 1 1 1 1 1 0 1 2 1 1 2 Libras 13 13 13 3 0 1 13 15 0 13 1 0 Letter 24 23 24 23 1 4 24 2 1 24 0 0 Bias 53 54 50 33 2 11 50 36 6 43 2 2 PFCM Zoo 5 5 5 0 0 5 5 4 0 0 0 0 Hayes-Roth 0 7 0 0 1 0 0 0 0 0 0 0 Iris 1 0 0 0 0 0 0 7 0 0 0 0 Glass 4 4 3 4 0 0 4 3 0 1 0 0 Dermatology 4 1 4 0 0 0 4 3 1 4 0 0 Breast Cancer 0 0 0 0 0 0 0 0 0 0 0 0 Balance Scale 1 1 1 1 1 1 0 1 2 1 1 2 Libras 13 13 13 3 0 1 13 15 0 13 1 0 Letter 24 23 24 23 1 4 24 2 1 24 0 0 Bias 52 54 50 31 3 11 50 35 4 43 2 2 KFCM Zoo 5 5 5 0 0 5 5 4 0 0 0 0 Hayes-Roth 0 7 0 0 1 0 0 0 0 0 0 0 Iris 1 0 0 0 0 0 0 7 0 0 0 0 Glass 4 4 3 4 0 0 4 3 2 1 0 0 Dermatology 4 1 4 0 0 0 4 3 1 4 0 0 Breast Cancer 0 0 0 0 0 0 0 0 0 0 0 0 Balance Scale 1 1 1 1 1 1 0 1 2 1 1 2 Libras 13 13 13 3 0 1 13 15 0 13 1 0 Letter 24 23 24 23 1 4 24 2 1 24 0 0 Bias 52 54 50 31 3 11 50 35 6 43 2 2 分析表4中的数据，以KFCM算法下的运行结果为例，Bias值比较低的有IMI指标、WLI指标、TCR指标和GDD指标，其中GDD指标的Bias值最低，足以说明本文提出的GDD指标在UCI数据集上有更好的评价效果和更稳定的评价能力，即使在GDD指标给出错误评价结果的情况下，得到的错误聚类数目和正确的聚类数目也不会相差太多。相反，其他CVI，如CH指标、Dunn指标和DB指标，这些CVI的Bias值都在50上下，相较于其他CVI高出很多。这说明CH指标、Dunn指标和DB指标这些CVI在错误评价后得到的聚类数目会和正确的聚类数目相差较大，其稳定性较差。在其他几个算法下，GDD的Bias值也是最低的。
同时，为了更直观地体现不同CVI在不同数据集下的评价结果和正确值之间的差距波动，选取FCM算法下实验结果绘制图3，其中红色点画线是当前数据集的正确聚类数。分析图3中的折线图可以发现，本文提出的GDD指标是12个CVI中比较稳定的指标，在绝大多数数据集上评价结果都是正确的，在评价错误的数据集Balance Scale上，GDD指标的结果也和正确的聚类数目相差不多。相较于其他CVI，例如CH指标、Dunn指标和FSI指标，这些CVI在大部分数据集上评价结果都和正确的聚类数目相差较大。
图 3 FCM算法下UCI数据集的统计结果Fig. 3 Statistical results of UCI dataset under the FCM algorithm下载:
全尺寸图片
图4给出了12个指标在FCM算法下的Dermatology数据集的计算结果数值变化，其中红色“·”形状标记表示当前聚类数目下的CVI取最优值。这里，FSI本应为值越小越好，在图4中将其纵坐标翻转后标记为最大值为最优聚类数。通过分析图3、图4，可以发现IMI指标、XBI指标、TCR指标和GDD指标在当前数据集上的聚类结果是正确的，其中正确的聚类数目为6类。然而分析数值曲线的走势，可以发现CH指标和VCVI指标的数值曲线随聚类数目K值的变化呈单调变化趋势，这表明这些CVI在当前数据集上的评价结果失去实际意义，难以有效反映聚类的真实质量。
图 4 FCM算法下Dermatology数据集运行结果Fig. 4 Results of Dermatology dataset under FCM algorithm下载:
全尺寸图片
表5中间部分是PFCM算法下CVI的实验结果。以其中的Data77数据集为例，Data77数据集的正确聚类数目为7类，IMI指标10轮的结果中5轮是5类为最优值，4轮是7类为最优值，1轮是2类为最优值，DB指标10轮的结果中8轮是3类为最优值，1轮是2类为最优值，1轮是4类为最优值，新提出的GDD指标10轮的结果中7轮是7类为最优值，3轮是5类为最优值，其他CVI不再赘述。统计出现次数最多的最优值聚类数目作为该指标的评价结果，IMI指标结果为5类，DB指标结果为3类，GDD指标结果为7类。可以看出，IMI指标和DB指标的结果都不正确，GDD指标正确得出了Data77数据集的聚类数目。统计表5中的数据，选取实验结果中出现次数最多的聚类数目作为最终的指标评价结果。
表 5 人造数据集的实验结果Table 5 Experimental results of artificial dataset算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Data_60 3941 3743 310 310 3842 310 310 310 3941 310 3842 310 Data_150 310 2139 223751 310 2139 310 213841 310 310 310 2139 310 Circle 223741 223642 2634 310 210 210 210 210 210 210 210 210 FCM Jain 2238 2337 233651 210 210 243343 2931 3248 2842 210 2743 273142 X8D5K 210 415871 2951 310 4258 354253 214653 410 510 576172 3159 510 Data_77 2941 210 213742 6872 415673 4258 510 510 435671 224355 556372 526177 E6 210 2654 4258 210 2456 410 213346 210 2248 410 4951 410 Dim_128 22443
6322233
547122033
47217310
5391159
16161741417155
16720121539
4254241273
28930171011417
15516722941 91112132
1571618103122
1551620Dim_256 22032
456321937
426221935
6627312
56105102152
1619177123145
151816426314
58102289294
30171471517
163173230 91142
15141613103152
1621174PFCM Data_60 310 374261 310 310 3951 310 213742 310 2139 310 2238 3941 Data_150 310 2238 3941 310 310 310 310 2238 310 310 310 310 Circle 2436 243343 263242 310 210 210 210 210 2931 210 210 210 Jain 210 2238 233651 210 210 243343 210 2248 283141 210 210 283141 X8D5K 210 21415771 210 310 4258 3753 410 4753 510 510 3258 510 Data_77 2941 210 213841 526771 215574 4357 546373 510 314257 214455 556174 415178 E6 210 264153 214158 210 2456 410 4654 210 2248 410 214653 410 Dim_128 22134
436222343
5422033
449321431152
92111102158
161717396149
155161021439
4255241272
281130161410154
1615201230 1321511
16162011561620
174Dim_256 22545 22135
4292230 21439
56711521620
178102145
152016323316
58632622873021 1418155162
172203230 15181612 101142
1621176KFCM Data_60 310 310 310 310 310 310 310 310 310 310 310 310 Data_150 310 3743 310 310 310 310 2139 310 310 310 310 310 Circle 2337 3644 2733 310 2842 210 210 210 210 210 210 210 Jain 223741 374251 223642 210 210 243343 210 213148 283141 210 2743 233443 X8D5K 2931 4258 210 2436 4654 213841 410 410 4258 510 3456 510 Data_77 2852 210 354253 5268 415673 425761 510 510 314356 435571 546373 415277 E6 210 2654 4258 210 234156 410 334651 210 2248 410 2149 410 Dim_128 22531
426222134
5372230 21639
5273102158
16161741011417
15516724316
4553722452510
30151420155
175230 1411514
1615144152
1624Dim_256 22245
6322235
4261230 29315
55711421620
1781421522
16518125315510 25123018 1414166
171022535 1421516
16121521622
176和UCI数据集类似，同样在统计结果上使用Eff和Bias两个评价因子来对结果进行统计分析，形成Eff统计表和Bias统计表如表6、表7所示。分析表6的统计数据可以看出，本文提出的GDD指标在人造数据集上的实验结果中相较于其他CVI准确率更高。GDD指标在FCM算法、PFCM算法上对所有人造数据集的评价结果都是正确的，在KFCM算法上对Jain数据集的评价结果错误，准确率分别达到100%、100%和89%。其他准确率较高的指标，例如IMI指标和TCR指标，其在FCM算法和PFCM算法上的准确率在78%左右，在KFCM算法上的准确率稍低一点，在70%左右。WLI指标和SMI指标的准确率稍低一点，在67%左右。剩余的指标准确率大多都在60%以下。从实验结果可以分析出，新提出的GDD指标在3个算法上的准确率均高于其他CVI，说明GDD指标对于不同算法的适应力均优于其他CVI。同时对比不同CVI在不同算法下的准确率，例如XBI指标在FCM算法和KFCM算法上的准确率为56%，而在PFCM算法下的准确率为67%，这在一定程度上说明不同的CVI有着更契合CVI本身的算法。
表 6 人造数据集的Eff统计结果Table 6 Eff statistical results of artificial dataset算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Data_60 3 3 3 3 3 3 3 3 3 3 3 3 Data_150 3 3 3 3 3 3 3 3 3 3 3 3 FCM Circle 3 3 2 3 2 2 2 2 2 2 2 2 Jain 3 3 3 2 2 2 2 4 2 2 2 2 X8D5K 2 5 2 3 5 3 4 4 5 5 5 5 Data_77 2 2 3 6 5 5 5 5 5 5 5 7 E6 2 2 5 2 5 4 4 2 4 4 4 4 Dim_128 2 2 2 2 16 14 2 30 14 2 16 16 Dim_256 2 2 2 3 16 15 3 30 15 2 15 16 Eff 0.22 0.33 0.33 0.33 0.78 0.56 0.56 0.33 0.67 0.67 0.78 1 PFCM Data_60 3 3 3 3 3 3 3 3 3 3 3 3 Data_150 3 3 3 3 3 3 3 3 3 3 3 3 Circle 3 2 2 3 2 2 2 2 2 2 2 2 Jain 2 3 3 2 2 2 2 4 2 2 2 2 X8D5K 2 5 2 3 5 3 4 4 5 5 5 5 Data_77 2 2 3 6 5 5 5 5 5 5 5 7 E6 2 2 5 2 5 4 4 2 4 4 4 4 Dim_128 2 2 2 2 16 16 2 30 16 2 16 16 Dim_256 2 2 2 2 16 15 3 30 14 2 15 16 Eff 0.33 0.44 0.33 0.33 0.78 0.67 0.56 0.33 0.78 0.67 0.78 1 KFCM Data_60 3 3 3 3 3 3 3 3 3 3 3 3 Data_150 3 3 3 3 3 3 3 3 3 3 3 3 Circle 3 3 2 3 2 2 2 2 2 2 2 2 Jain 3 3 3 2 2 2 2 4 2 2 2 3 X8D5K 2 5 2 3 4 3 4 4 5 5 5 5 Data_77 2 2 3 6 5 5 5 5 5 5 5 7 E6 2 2 5 2 5 4 4 2 4 4 4 4 Dim_128 2 2 2 2 16 14 3 30 14 2 16 16 Dim_256 2 2 2 3 16 15 3 30 14 2 15 16 Eff 0.22 0.33 0.33 0.33 0.67 0.56 0.56 0.33 0.67 0.67 0.78 0.89 注：加粗代表该数值和正确的聚类数目一致。 表 7 人造数据集的Bias统计结果Table 7 Bias statistical results of artificial dataset算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Data_60 0 0 0 0 0 0 0 0 0 0 0 0 Data_150 0 0 0 0 0 0 0 0 0 0 0 0 Circle 1 1 0 1 0 0 0 0 0 0 0 0 Jain 1 1 1 0 0 0 0 2 0 0 0 0 X8D5K 3 0 3 2 0 2 1 1 0 0 0 0 Data_77 5 5 4 1 2 2 2 2 2 2 2 0 E6 2 2 1 2 1 0 0 2 0 0 0 0 Dim_128 14 14 14 14 0 2 14 14 2 14 0 0 Dim_256 14 14 14 13 0 1 13 14 1 14 1 0 Bias 40 37 37 33 3 7 30 35 5 30 3 0 PFCM Data_60 0 0 0 0 0 0 0 0 0 0 0 0 Data_150 0 0 0 0 0 0 0 0 0 0 0 0 Circle 1 0 0 1 0 0 0 0 0 0 0 0 Jain 0 1 1 0 0 0 0 2 0 0 0 0 X8D5K 3 0 3 2 0 2 1 1 0 0 0 0 Data_77 5 5 4 1 2 2 2 2 2 2 2 0 E6 2 2 1 2 1 0 0 2 0 0 0 0 Dim_128 14 14 14 14 0 0 14 14 0 14 0 0 Dim_256 14 14 14 14 0 1 13 14 2 14 1 0 Bias 39 36 37 34 3 5 30 35 4 30 3 0 KFCM Data_60 0 0 0 0 0 0 0 0 0 0 0 0 Data_150 0 0 0 0 0 0 0 0 0 0 0 0 Circle 1 1 0 1 0 0 0 0 0 0 0 0 Jain 1 1 1 0 0 0 0 2 0 0 0 1 X8D5K 3 0 3 2 1 2 1 1 0 0 0 0 Data_77 5 5 4 1 2 2 2 2 2 2 2 0 E6 2 2 1 2 1 0 0 2 0 0 0 0 Dim_128 14 14 14 14 0 2 13 14 2 14 0 0 Dim_256 14 14 14 13 0 1 13 14 2 14 1 0 Bias 40 37 37 33 4 7 29 35 6 30 3 1 分析表7中的数据，以FCM算法下的运行结果为例，Bias值比较低的有IMI指标、WLI指标、TCR指标和GDD指标，其中GDD指标的Bias值最低，足以说明本文提出的GDD指标在人造数据集上有更好的评价效果和更稳定的评价能力，即使在GDD指标给出错误的评价结果的情况下，得到的错误聚类数目和正确的聚类数目也不会相差太多。相反，其他CVI例如CH指标、Dunn指标和DB指标，这些CVI的Bias值都在40上下，相较于其他CVI高出很多。这说明CH指标、Dunn指标和DB指标这些CVI在错误评价后得到的聚类数目会和正确的聚类数目相差较大，其稳定性较差。
同时，为了更直观地体现不同CVI在不同数据集下的评价结果和正确值之间的差距波动，选取FCM算法下实验结果绘制图5，其中红色点画线是当前数据集的正确聚类数。分析图5中的折线图，可以发现，本文提出的GDD指标是12个CVI中比较稳定的指标，在绝大多数数据集上评价结果都是正确的，在KFCM算法下评价错误的数据集Jain上，GDD指标的结果也和正确的聚类数目相差不多。如CH指标、Dunn指标和FSI指标，这些CVI在大部分数据集上评价结果都和正确的聚类数目相差较大。
图 5 FCM算法下人造数据集的统计结果Fig. 5 Statistical results of artificial dataset under FCM algorithm下载:
全尺寸图片
接下来使用Olivetti Face数据集进行实验来检验本文提出的GDD指标面对图像类数据集的效果，验证其能否适应不同类型的数据。表8是Olivetti Face数据集在FCM、PFCM和KFCM这3种算法下的运行结果。统计表8中的数据，选取实验结果中出现次数最多的聚类数目作为最终的指标评价结果，同时应用Eff和Bias评价因子以形成表9。
表 8 Olivetti Face数据集的实验结果Table 8 Experimental results of Olivetti Face dataset算法 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM 3030 21735
4563230 22332
416292951023
122256295
30192134425 3030 5283
951020230 10201110 8593
1022PFCM 3030 22131
4553230 22153
941022182
941023223254
284301935425 3030 7391
1023113230 821019
1151445194
1021124KFCM 251291
3028210316
5371230 22545 8294
1022202224295
302132421
551023030 951022113 230 931022
113142951019
112134表 9 Olivetti Face数据集的统计结果Table 9 Statistical results of Olivetti Face dataset算法 评价因子 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Value 30 2 2 2 10 30 4 30 10 2 10 10 Eff 0 0 0 0 1 0 0 0 1 0 1 1 Bias 20 8 8 8 0 20 6 20 0 8 0 0 PFCM Value 30 2 2 2 10 30 4 30 10 2 10 10 Eff 0 0 0 0 1 0 0 0 1 0 1 1 Bias 20 8 8 8 0 20 6 20 0 8 0 0 KFCM Value 30 3 2 2 10 30 4 30 10 2 10 10 Eff 0 0 0 0 1 0 0 0 1 0 1 1 Bias 20 7 8 8 0 20 6 20 0 8 0 0 注：加粗代表该数值和正确的聚类数目一致。 评估一个CVI的优劣不仅需要各种类型、各种结构的数据集进行实验，同样也需要检测CVI在含有噪声的数据集上的效果。一个稳定的CVI应该能适应添加有不同程度噪声数据的数据集，并且能得出正确的结果。接下来选取X8D5K数据集，X8D5K数据集的数据维度为8维，共有
1000 个样本点，正确的聚类数目为5类。向其中加入不同程度的噪声数据，分别为2%、4%、6%、8%和10%。在这5种噪声下的数据集上进行实验，分别使用FCM算法、PFCM算法和KFCM算法。统计实验后的结果如表10所示。表 10 噪声数据集的统计结果Table 10 Statistical results of noisy dataset算法 噪声比例/% CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM 0 2 5 2 3 5 3 4 4 5 5 5 5 2 3 5 2 3 5 4 5 4 5 4 5 5 4 2 5 2 3 4 4 4 4 5 4 5 5 6 2 4 3 3 3 3 3 6 4 4 5 5 8 2 4 3 3 3 4 3 6 3 3 6 5 10 2 3 3 3 2 3 3 5 2 3 4 4 PFCM 0 2 5 2 3 5 3 4 4 5 5 5 5 2 2 5 2 3 5 3 4 3 5 4 5 5 4 3 5 3 3 5 4 3 4 5 5 5 5 6 3 4 3 3 4 5 3 3 4 7 4 5 8 2 3 4 3 3 5 3 2 3 4 3 5 10 2 3 5 3 3 4 2 2 3 4 3 5 KFCM 0 2 5 2 3 4 3 4 4 5 5 5 5 2 2 5 5 3 5 3 4 3 5 5 5 5 4 2 4 5 3 4 4 4 4 5 4 5 5 6 2 3 4 3 4 3 3 3 4 5 4 5 8 2 4 3 3 3 3 3 3 3 4 4 5 10 2 2 3 4 3 2 4 3 3 3 3 6 注：加粗代表该数值和正确的聚类数目一致。 4. 结束语
1) 本文提出了一个新的模糊聚类有效性评价指标GDD。GDD指标采用簇内紧致度与簇间分离度比值的形式抑制了聚类结果数目单调递增的情况，同时在簇内紧致度中在计算单个簇紧致度的基础上引入了该簇样本占总样本的比值，构建了更客观的紧致度表达；在簇间分离度中在计算聚类中心到聚类中心均值的基础上增加了该簇样本站总样本的比值，构建了更合理的簇间分离度表达。
2)在复杂度分析中，虽然GDD指标拥有与Dunn和SMI指标相同的时间复杂度，但是其拥有更加优异的性能，并且性能同样优于其他时间复杂度更低的指标，说明了GDD在能接受的时间复杂度下达到了比较指标中最好的性能。
3)在面对3个模糊聚类算法、11个对比CVI的实验中，GDD指标在UCI数据集中均优于其他指标，在人造数据集的实验中GDD仅在KFCM算法下的Jain数据集出现了错误，在人脸数据集Olivetti Face中GDD同样得到了较为优秀的效果。
4)在噪声实验中，FCM算法下噪声为8%时只有GDD指标得到了正确结果，而噪声为10%时只有FSI得到了正确结果。PFCM算法下当噪声为10%时只有DB和GDD能够得到正确结果。KFCM算法下当噪声为8%时只有GDD得到了正确结果，而噪声为10%时则没有指标得到正确聚类数。
综上，GDD指标具有全新的指标设计思路、可接受的时间复杂度与较好的实验表现，在噪声实验中体现了其较强的鲁棒性。在未来研究中，将试图结合模糊逻辑的思想来进行聚类有效性评价指标的设计与应用。
-
图 1 数据集的分布
Fig. 1 Distribution of datasets
下载:
全尺寸图片
图 2 Olivetti Face数据集
Fig. 2 Olivetti Face dataset
下载:
全尺寸图片
图 3 FCM算法下UCI数据集的统计结果
Fig. 3 Statistical results of UCI dataset under the FCM algorithm
下载:
全尺寸图片
图 4 FCM算法下Dermatology数据集运行结果
Fig. 4 Results of Dermatology dataset under FCM algorithm
下载:
全尺寸图片
图 5 FCM算法下人造数据集的统计结果
Fig. 5 Statistical results of artificial dataset under FCM algorithm
下载:
全尺寸图片
表 1 12个指标的时间复杂度
Table 1 Time complexity of 12 indicators
序号 CVI 时间复杂度 1 CH $ O(K\tau d) $ 2 Dunn $ O({K}^{2}{\tau }^{2}d) $ 3 DB $ O(K{\tau }^{2}d) $ 4 MB $ O(Knd) $ 5 IMI $ O(Kn(d+K)) $ 6 XBI $ O(Knd) $ 7 VCVI $ O(K\tau d) $ 8 FSI $ O(Knd) $ 9 WLI $ O(Knd) $ 10 SMI $ O({K}^{2}{\tau }^{2}d+Knd) $ 11 TCR $ O(Kn(d+K)) $ 12 GDD $ O(K{\tau }^{2}d+nd) $ 表 2 UCI数据集的实验结果
Table 2 Experimental results of UCI dataset
算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Zoo 210 210 210 710 5278 210 283141 310 2377 710 710 710 Hayes-Roth 210 93107 310 310 2337 213742 213544 3248 310 310 233641 310 Iris 210 3951 310 310 3852 310 364153 1010 310 310 2139 310 Glass 210 2634 310 210 225266 5367 210 385161 475162 5961 5268 610 Dermatology 2832 223256 210 475261 6773 6773 210 2238 415564 2763 4367 4268 Breast Cancer 210 2862 210 210 210 2832 2832 210 283151 210 210 210 Balance Scale 283151 3248 2733 2852 233245 213346 3862 253253 315762 273251 224761 4159 Libras 22233
5471215312
4321535
4101822208 1441520
1661391415
15622533
623030 1471517
176216106
114154103132
1420155114142
1522162Letter 22036
42522631747 230 210318
5226102718
3022052215
23425621953
103142
1532825291
3042422518
264276230 2212625
2723022222623
275PFCM Zoo 210 210 210 710 516178 210 2842 310 2377 4278 710 710 Hayes-Roth 310 2192107 310 310 263351 3842 3743 354372 3941 310 223642 3941 Iris 210 3951 310 2238 384151 310 364252 1010 310 310 310 310 Glass 210 2733 213851 210 5367 415168 210 310 4367 415861 5268 610 Dermatology 2832 223157 2852 445165 416772 6773 210 2238 5763 2763 425167 4169 Breast Cancer 210 2862 210 2941 210 210 210 210 2832 210 210 210 Balance Scale 2832 213247 2733 284151 213346 3347 3862 2753 5862 273251 2248 510 Libras 22333
54215310
436221535
49711821206
2431421521
1662011361415
15617322433
621013030 1441517
1762032161010
1541031423
1541141525
161Letter 22236
4226317
4582230 210318
516126102720 2215239
256223103
1421522825292
3032518266
276230 2625273
3022222620
275283KFCM Zoo 210 210 210 2179 415178 210 2941 3753 224177 5179 710 710 Hayes-Roth 310 21109 310 2238 210 310 213841 213743 310 3763 364272 310 Iris 210 3941 310 2238 2139 3852 375281 1010 310 310 310 310 Glass 210 273261 310 210 5268 215168 210 310 214663 225761 315267 4268 Dermatology 2832 4258 210 4466 216772 6872 210 3852 325761 275261 4268 6971 Breast Cancer 210 283161 210 210 210 210 210 210 2832 210 210 210 Balance Scale 2832 2149 253342 253342 213445 223345 376271 210 5862 275162 214653 5961 Libras 22232
5410221539
447221533
410521531821
2052411441522
1641371417
15622134
653030 1517176
20721631
109154103132
14211541421522
166Letter 21934
42527326319
45230 210318
5224526
1027152042215
23525622142103
1421522824294
3022518266
273303230 204222
26212732222624
273291表 3 UCI数据集的Eff统计结果
Table 3 Eff statistical results of UCI dataset
算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Zoo 2 2 2 7 7 2 2 3 7 7 7 7 Hayes-Roth 2 10 3 3 3 3 3 4 3 3 3 3 Iris 2 3 3 3 3 3 3 10 3 3 3 3 Glass 2 2 3 2 6 6 2 3 4 5 6 6 Dermatology 2 5 2 4 6 6 2 3 5 2 6 6 Breast Cancer 2 2 2 2 2 2 2 2 2 2 2 2 Balance Scale 2 4 2 2 4 4 3 2 5 2 4 5 Libras 2 2 2 18 15 14 2 30 15 2 14 15 Letter 2 3 2 3 27 22 2 28 25 2 26 26 Eff 0.11 0.22 0.33 0.44 0.78 0.56 0.44 0.11 0.56 0.44 0.78 0.89 PFCM Zoo 2 2 2 7 7 2 2 3 7 7 7 7 Hayes-Roth 3 10 3 3 2 3 3 3 3 3 3 3 Iris 2 3 3 3 3 3 3 10 3 3 3 3 Glass 2 2 3 2 6 6 2 3 6 5 6 6 Dermatology 2 5 2 6 6 6 2 3 5 2 6 6 Breast Cancer 2 2 2 2 2 2 2 2 2 2 2 2 Balance Scale 2 4 2 2 4 4 3 2 5 2 4 5 Libras 2 2 2 18 15 14 2 30 15 2 14 15 Letter 2 3 2 3 27 22 2 28 25 2 26 26 Eff 0.22 0.22 0.33 0.44 0.67 0.56 0.44 0.22 0.67 0.44 0.78 0.89 KFCM Zoo 2 2 2 7 7 2 2 3 7 7 7 7 Hayes-Roth 3 10 3 3 2 3 3 3 3 3 3 3 Iris 2 3 3 3 3 3 3 10 3 3 3 3 Glass 2 2 3 2 6 6 2 3 4 5 6 6 Dermatology 2 5 2 6 6 6 2 3 5 2 6 6 Breast Cancer 2 2 2 2 2 2 2 2 2 2 2 2 Balance Scale 2 4 2 2 4 4 3 2 5 2 4 5 Libras 2 2 2 18 15 14 2 30 15 2 14 15 Letter 2 3 2 3 27 22 2 28 25 2 26 26 Eff 0.22 0.22 0.33 0.56 0.67 0.56 0.44 0.22 0.56 0.44 0.78 0.89 注：加粗代表该数值和正确的聚类数目一致。 表 4 UCI数据集的Bias统计结果
Table 4 Bias statistical results of UCI dataset
算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Zoo 5 5 5 0 0 5 5 4 0 0 0 0 Hayes-Roth 1 7 0 0 0 0 0 1 0 0 0 0 Iris 1 0 0 0 0 0 0 7 0 0 0 0 Glass 4 4 3 4 0 0 4 3 2 1 0 0 Dermatology 4 1 4 2 0 0 4 3 1 4 0 0 Breast Cancer 0 0 0 0 0 0 0 0 0 0 0 0 Balance Scale 1 1 1 1 1 1 0 1 2 1 1 2 Libras 13 13 13 3 0 1 13 15 0 13 1 0 Letter 24 23 24 23 1 4 24 2 1 24 0 0 Bias 53 54 50 33 2 11 50 36 6 43 2 2 PFCM Zoo 5 5 5 0 0 5 5 4 0 0 0 0 Hayes-Roth 0 7 0 0 1 0 0 0 0 0 0 0 Iris 1 0 0 0 0 0 0 7 0 0 0 0 Glass 4 4 3 4 0 0 4 3 0 1 0 0 Dermatology 4 1 4 0 0 0 4 3 1 4 0 0 Breast Cancer 0 0 0 0 0 0 0 0 0 0 0 0 Balance Scale 1 1 1 1 1 1 0 1 2 1 1 2 Libras 13 13 13 3 0 1 13 15 0 13 1 0 Letter 24 23 24 23 1 4 24 2 1 24 0 0 Bias 52 54 50 31 3 11 50 35 4 43 2 2 KFCM Zoo 5 5 5 0 0 5 5 4 0 0 0 0 Hayes-Roth 0 7 0 0 1 0 0 0 0 0 0 0 Iris 1 0 0 0 0 0 0 7 0 0 0 0 Glass 4 4 3 4 0 0 4 3 2 1 0 0 Dermatology 4 1 4 0 0 0 4 3 1 4 0 0 Breast Cancer 0 0 0 0 0 0 0 0 0 0 0 0 Balance Scale 1 1 1 1 1 1 0 1 2 1 1 2 Libras 13 13 13 3 0 1 13 15 0 13 1 0 Letter 24 23 24 23 1 4 24 2 1 24 0 0 Bias 52 54 50 31 3 11 50 35 6 43 2 2 表 5 人造数据集的实验结果
Table 5 Experimental results of artificial dataset
算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Data_60 3941 3743 310 310 3842 310 310 310 3941 310 3842 310 Data_150 310 2139 223751 310 2139 310 213841 310 310 310 2139 310 Circle 223741 223642 2634 310 210 210 210 210 210 210 210 210 FCM Jain 2238 2337 233651 210 210 243343 2931 3248 2842 210 2743 273142 X8D5K 210 415871 2951 310 4258 354253 214653 410 510 576172 3159 510 Data_77 2941 210 213742 6872 415673 4258 510 510 435671 224355 556372 526177 E6 210 2654 4258 210 2456 410 213346 210 2248 410 4951 410 Dim_128 22443
6322233
547122033
47217310
5391159
16161741417155
16720121539
4254241273
28930171011417
15516722941 91112132
1571618103122
1551620Dim_256 22032
456321937
426221935
6627312
56105102152
1619177123145
151816426314
58102289294
30171471517
163173230 91142
15141613103152
1621174PFCM Data_60 310 374261 310 310 3951 310 213742 310 2139 310 2238 3941 Data_150 310 2238 3941 310 310 310 310 2238 310 310 310 310 Circle 2436 243343 263242 310 210 210 210 210 2931 210 210 210 Jain 210 2238 233651 210 210 243343 210 2248 283141 210 210 283141 X8D5K 210 21415771 210 310 4258 3753 410 4753 510 510 3258 510 Data_77 2941 210 213841 526771 215574 4357 546373 510 314257 214455 556174 415178 E6 210 264153 214158 210 2456 410 4654 210 2248 410 214653 410 Dim_128 22134
436222343
5422033
449321431152
92111102158
161717396149
155161021439
4255241272
281130161410154
1615201230 1321511
16162011561620
174Dim_256 22545 22135
4292230 21439
56711521620
178102145
152016323316
58632622873021 1418155162
172203230 15181612 101142
1621176KFCM Data_60 310 310 310 310 310 310 310 310 310 310 310 310 Data_150 310 3743 310 310 310 310 2139 310 310 310 310 310 Circle 2337 3644 2733 310 2842 210 210 210 210 210 210 210 Jain 223741 374251 223642 210 210 243343 210 213148 283141 210 2743 233443 X8D5K 2931 4258 210 2436 4654 213841 410 410 4258 510 3456 510 Data_77 2852 210 354253 5268 415673 425761 510 510 314356 435571 546373 415277 E6 210 2654 4258 210 234156 410 334651 210 2248 410 2149 410 Dim_128 22531
426222134
5372230 21639
5273102158
16161741011417
15516724316
4553722452510
30151420155
175230 1411514
1615144152
1624Dim_256 22245
6322235
4261230 29315
55711421620
1781421522
16518125315510 25123018 1414166
171022535 1421516
16121521622
176表 6 人造数据集的Eff统计结果
Table 6 Eff statistical results of artificial dataset
算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Data_60 3 3 3 3 3 3 3 3 3 3 3 3 Data_150 3 3 3 3 3 3 3 3 3 3 3 3 FCM Circle 3 3 2 3 2 2 2 2 2 2 2 2 Jain 3 3 3 2 2 2 2 4 2 2 2 2 X8D5K 2 5 2 3 5 3 4 4 5 5 5 5 Data_77 2 2 3 6 5 5 5 5 5 5 5 7 E6 2 2 5 2 5 4 4 2 4 4 4 4 Dim_128 2 2 2 2 16 14 2 30 14 2 16 16 Dim_256 2 2 2 3 16 15 3 30 15 2 15 16 Eff 0.22 0.33 0.33 0.33 0.78 0.56 0.56 0.33 0.67 0.67 0.78 1 PFCM Data_60 3 3 3 3 3 3 3 3 3 3 3 3 Data_150 3 3 3 3 3 3 3 3 3 3 3 3 Circle 3 2 2 3 2 2 2 2 2 2 2 2 Jain 2 3 3 2 2 2 2 4 2 2 2 2 X8D5K 2 5 2 3 5 3 4 4 5 5 5 5 Data_77 2 2 3 6 5 5 5 5 5 5 5 7 E6 2 2 5 2 5 4 4 2 4 4 4 4 Dim_128 2 2 2 2 16 16 2 30 16 2 16 16 Dim_256 2 2 2 2 16 15 3 30 14 2 15 16 Eff 0.33 0.44 0.33 0.33 0.78 0.67 0.56 0.33 0.78 0.67 0.78 1 KFCM Data_60 3 3 3 3 3 3 3 3 3 3 3 3 Data_150 3 3 3 3 3 3 3 3 3 3 3 3 Circle 3 3 2 3 2 2 2 2 2 2 2 2 Jain 3 3 3 2 2 2 2 4 2 2 2 3 X8D5K 2 5 2 3 4 3 4 4 5 5 5 5 Data_77 2 2 3 6 5 5 5 5 5 5 5 7 E6 2 2 5 2 5 4 4 2 4 4 4 4 Dim_128 2 2 2 2 16 14 3 30 14 2 16 16 Dim_256 2 2 2 3 16 15 3 30 14 2 15 16 Eff 0.22 0.33 0.33 0.33 0.67 0.56 0.56 0.33 0.67 0.67 0.78 0.89 注：加粗代表该数值和正确的聚类数目一致。 表 7 人造数据集的Bias统计结果
Table 7 Bias statistical results of artificial dataset
算法 数据集 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Data_60 0 0 0 0 0 0 0 0 0 0 0 0 Data_150 0 0 0 0 0 0 0 0 0 0 0 0 Circle 1 1 0 1 0 0 0 0 0 0 0 0 Jain 1 1 1 0 0 0 0 2 0 0 0 0 X8D5K 3 0 3 2 0 2 1 1 0 0 0 0 Data_77 5 5 4 1 2 2 2 2 2 2 2 0 E6 2 2 1 2 1 0 0 2 0 0 0 0 Dim_128 14 14 14 14 0 2 14 14 2 14 0 0 Dim_256 14 14 14 13 0 1 13 14 1 14 1 0 Bias 40 37 37 33 3 7 30 35 5 30 3 0 PFCM Data_60 0 0 0 0 0 0 0 0 0 0 0 0 Data_150 0 0 0 0 0 0 0 0 0 0 0 0 Circle 1 0 0 1 0 0 0 0 0 0 0 0 Jain 0 1 1 0 0 0 0 2 0 0 0 0 X8D5K 3 0 3 2 0 2 1 1 0 0 0 0 Data_77 5 5 4 1 2 2 2 2 2 2 2 0 E6 2 2 1 2 1 0 0 2 0 0 0 0 Dim_128 14 14 14 14 0 0 14 14 0 14 0 0 Dim_256 14 14 14 14 0 1 13 14 2 14 1 0 Bias 39 36 37 34 3 5 30 35 4 30 3 0 KFCM Data_60 0 0 0 0 0 0 0 0 0 0 0 0 Data_150 0 0 0 0 0 0 0 0 0 0 0 0 Circle 1 1 0 1 0 0 0 0 0 0 0 0 Jain 1 1 1 0 0 0 0 2 0 0 0 1 X8D5K 3 0 3 2 1 2 1 1 0 0 0 0 Data_77 5 5 4 1 2 2 2 2 2 2 2 0 E6 2 2 1 2 1 0 0 2 0 0 0 0 Dim_128 14 14 14 14 0 2 13 14 2 14 0 0 Dim_256 14 14 14 13 0 1 13 14 2 14 1 0 Bias 40 37 37 33 4 7 29 35 6 30 3 1 表 8 Olivetti Face数据集的实验结果
Table 8 Experimental results of Olivetti Face dataset
算法 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM 3030 21735
4563230 22332
416292951023
122256295
30192134425 3030 5283
951020230 10201110 8593
1022PFCM 3030 22131
4553230 22153
941022182
941023223254
284301935425 3030 7391
1023113230 821019
1151445194
1021124KFCM 251291
3028210316
5371230 22545 8294
1022202224295
302132421
551023030 951022113 230 931022
113142951019
112134表 9 Olivetti Face数据集的统计结果
Table 9 Statistical results of Olivetti Face dataset
算法 评价因子 CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM Value 30 2 2 2 10 30 4 30 10 2 10 10 Eff 0 0 0 0 1 0 0 0 1 0 1 1 Bias 20 8 8 8 0 20 6 20 0 8 0 0 PFCM Value 30 2 2 2 10 30 4 30 10 2 10 10 Eff 0 0 0 0 1 0 0 0 1 0 1 1 Bias 20 8 8 8 0 20 6 20 0 8 0 0 KFCM Value 30 3 2 2 10 30 4 30 10 2 10 10 Eff 0 0 0 0 1 0 0 0 1 0 1 1 Bias 20 7 8 8 0 20 6 20 0 8 0 0 注：加粗代表该数值和正确的聚类数目一致。 表 10 噪声数据集的统计结果
Table 10 Statistical results of noisy dataset
算法 噪声比例/% CH Dunn DB MB IMI XBI VCVI FSI WLI SMI TCR GDD FCM 0 2 5 2 3 5 3 4 4 5 5 5 5 2 3 5 2 3 5 4 5 4 5 4 5 5 4 2 5 2 3 4 4 4 4 5 4 5 5 6 2 4 3 3 3 3 3 6 4 4 5 5 8 2 4 3 3 3 4 3 6 3 3 6 5 10 2 3 3 3 2 3 3 5 2 3 4 4 PFCM 0 2 5 2 3 5 3 4 4 5 5 5 5 2 2 5 2 3 5 3 4 3 5 4 5 5 4 3 5 3 3 5 4 3 4 5 5 5 5 6 3 4 3 3 4 5 3 3 4 7 4 5 8 2 3 4 3 3 5 3 2 3 4 3 5 10 2 3 5 3 3 4 2 2 3 4 3 5 KFCM 0 2 5 2 3 4 3 4 4 5 5 5 5 2 2 5 5 3 5 3 4 3 5 5 5 5 4 2 4 5 3 4 4 4 4 5 4 5 5 6 2 3 4 3 4 3 3 3 4 5 4 5 8 2 4 3 3 3 3 3 3 3 4 4 5 10 2 2 3 4 3 2 4 3 3 3 3 6 注：加粗代表该数值和正确的聚类数目一致。 -
[1] TANG Yiming, PAN Zhifu, HU Xianghui, et al. Knowledge-induced multiple kernel fuzzy clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 2023, 45(12): 14838−14855. doi: 10.1109/TPAMI.2023.3298629 [2] TANG Yiming, PAN Zhifu, PEDRYCZ W, et al. Viewpoint-based kernel fuzzy clustering with weight information granules[J]. IEEE transactions on emerging topics in computational intelligence, 2023, 7(2): 342−356. doi: 10.1109/TETCI.2022.3201620 [3] TANG Yiming, REN Fuji, PEDRYCZ W. Fuzzy C-Means clustering through SSIM and patch for image segmentation[J]. Applied soft computing, 2020, 87: 1−16. doi: 10.1016/j.asoc.2019.105928 [4] TANG Yiming, WU Wenbin, PEDRYCZ W, et al. Clustering interval and triangular granular data: modeling, execution, and assessment[J]. IEEE transactions on neural networks and learning systems, 2025, 36(6): 10000−10014. doi: 10.1109/TNNLS.2024.3499996 [5] TANG Yiming, LI Bing, PEDRYCZ W, et al. A clustering validity index with multi-granularity fusion for multiple fuzzy clustering algorithms[J]. IEEE transactions on pattern analysis and machine intelligence, 2025, 47(10): 8379−8396. doi: 10.1109/TPAMI.2025.3577171 [6] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability. Berkeley: University of California, 1965. [7] ROSS H H, SOKAL R R, SNEATH P H A, et al. Principles of numerical taxonomy[J]. Systematic zoology, 1964, 13(2): 106. doi: 10.4324/9780203766804-11 [8] CAMPELLO R J G B, MOULAVI D, SANDER J. Density-based clustering based on hierarchical density estimates[C]//The 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Gold Coast: PAKDD, 2013. [9] 吕莉, 陈威, 肖人彬, 等. 面向密度分布不均数据的加权逆近邻密度峰值聚类算法[J]. 智能系统学报, 2024, 19(1): 165−175. LYU Li, CHEN Wei, XIAO Renbin, et al. Density peak clustering algorithm based on weighted reverse nearestneighbor for uneven density datasets[J]. CAAI transactions on intelligent systems, 2024, 19(1): 165−175. [10] ZHAO Yanchang, SONG Junde. GDILC: a grid-based density-isoline clustering algorithm[C]//Proceedings of the International Conference on Information Technology and Intelligent Network. Beijing: IEEE, 2001. [11] VIJAY R K, NANDA S J, SHARMA A. A spatio-temporal binary grid-based clustering model for seismicity analysis[J]. Pattern analysis and applications, 2024, 27(1): 14. doi: 10.1007/s10044-024-01234-7 [12] 孙林, 梁娜, 徐久成. 基于邻域互信息与 K-means 特征聚类的特征选择[J]. 智能系统学报, 2024, 19(4): 983−996. doi: 10.11992/tis.202208012 SUN Lin, LIANG Na, XU Jiucheng. Feature selection using neighborhood mutual information and feature cluster-ing with K-means[J]. CAAI transactions on intelligent systems, 2024, 19(4): 983−996. doi: 10.11992/tis.202208012 [13] DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J]. Journal of cybernetics, 1973, 3(3): 32−57. doi: 10.1080/01969727308546046 [14] BEZDEK J C, EHRLICH R, FULL W. FCM. The fuzzy c-means clustering algorithm[J]. Computers & geosciences, 1984, 10(2/3): 191−203. [15] KRISHNAPURAM R, KELLER J M. A possibilistic approach to clustering[J]. IEEE transactions on fuzzy systems, 1993, 1(2): 98−110. doi: 10.1109/91.227387 [16] PAL N R, PAL K, BEZDEK J C. A mixed C-means clustering model[C]//Proceedings of 6th International Fuzzy Systems Conference. Barcelona: IEEE, 1997. [17] ANTOINE V, GUERRERO J A, ROMERO G. Possibilistic fuzzy c-means with partial supervision[J]. Fuzzy sets and systems, 2022, 449: 162−186. doi: 10.1016/j.fss.2022.08.003 [18] ZHANG Daoqiang, CHEN Songcan, PAN Zhisong, et al. Kernel-based fuzzy clustering incorporating spatial constraints for image segmentation[C]//Proceedings of the 2003 International Conference on Machine Learning and Cybernetics. Washington: IEEE, 2003. [19] PUNIT R, ZAHRA G, BEZDEK J C, et al. Approximating Dunn's cluster validity indices for partitions of big data[J]. IEEE transactions on cybernetics, 2018, 49(5): 1629−1641. doi: 10.1109/tcyb.2018.2806886 [20] HASSAN B A, TAYFOR N B, HASSAN A A, et al. From a-to-z review of clustering validation indices[J]. Neurocomputing, 2024, 601: 128−198. [21] FUKUI K, NUMAO M. Neighborhood-based smoothing of external cluster validity measures[C]//Proceedings of the 16th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin: Springer, 2012: 354−365. [22] 唐益明, 陈仁好, 李冰. 面向模糊C均值算法的 MAME聚类有效性指标[J]. 智能系统学报, 2023, 18(5): 945−956. TANG Yiming, CHEN Renhao, LI Bing. A clustering validity index called MAME for the fuzzy c-means algorithm[J]. CAAI transactions on intelligent systems, 2023, 18(5): 945−956. [23] VENDRAMIN L, CAMPELLO R J G B, HRUSCHKA E R. Relative clustering validity criteria: a comparative overview[J]. Statistical analysis & data mining, 2010, 3(4): 209−235. doi: 10.1002/sam.10080 [24] CALINSKI R B, HARABASZ J. A dendrite method for cluster analysis[J]. Communications in statistics, 1974, 3(1): 1−27. doi: 10.1080/03610917408548446 [25] DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE transactions on pattern analysis and machine intelligence, 1979, 2(1): 224−227. [26] XIE X L, BENI G. A validity measure for fuzzy clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 1991, 13(8): 841−847. doi: 10.1109/34.85677 [27] FUKUYAMA Y, SUGENO M. A new method of choosing the number of clusters for the fuzzy c-means method[C]// Proceedings of the 5th Fuzzy Systems Symposium. Tokyo: Japan Society for Fuzzy Theory and Systems, 1989. [28] WU Chihhung, OUYANG Chensen, CHEN Liwen, et al. A new fuzzy clustering validity index with a median factor for centroid-based clustering [J] IEEE transactions on fuzzy systems, 2015, 23(3): 701−718. [29] LIU Yun, JIANG Yanfang, HOU Tao, et al. A new robust fuzzy clustering validity index for imbalanced data sets[J]. Information sciences, 2021, 547: 579−591. doi: 10.1016/j.ins.2020.08.041 [30] MITTAL H, SARASWAT M. A new fuzzy cluster validity index for hyperellipsoid or hyperspherical shape close clusters with distant centroids[J]. IEEE transactions on fuzzy systems, 2020, 29(11): 3249−3258. doi: 10.1109/tfuzz.2020.3016339 [31] ZHU Erzhuo, MA Zhujuan, LI Xuejun, et al. An effective partitional clustering algorithm based on new clustering validity index[J]. Applied soft computing, 2018, 71: 608−621. doi: 10.1016/j.asoc.2018.07.026 [32] MAULIKH U, BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE transactions on pattern analysis and machine intelligence, 2002, 24(12): 1650−1654. doi: 10.1109/TPAMI.2002.1114856 [33] TANG Yiming, HUANG Jiajia, PEDRYCZ W, et al. A fuzzy clustering validity index induced by triple center relation[J]. IEEE transactions on cybernetics, 2023, 53(8): 5024−5036. doi: 10.1109/TCYB.2023.3263215 [34] LIU Yun, HOU Tao, LIU Fu, et al. Improving fuzzy c-means method for unbalanced dataset[J]. Electronics letters, 2015, 51(23): 1880−1881. [35] ZHOU Kaile, YANG Shanlin. Exploring the uniform effect of FCM clustering: a data distribution perspective[J]. Knowledge-based systems, 2016, 96: 76−83. doi: 10.1016/j.knosys.2016.01.001 [36] DUA D, GRAFF C. UCI machine learning repository [EB/OL]. (2017−01−01)[2025−03−20]. http://archive.ics.uci.edu/ml. [37] SALEM S A, NANDI A K. Development of assessment criteria for clustering algorithms[J]. Pattern analysis and applications, 2009, 12(1): 79−98. doi: 10.1007/s10044-007-0099-1
