基于犹豫模糊Canopy-K均值聚类算法的研究与应用

张子璇，沙秀艳,2，肖 霏，粟宝婵，隋雨陆，孟子宸

(1.曲阜师范大学统计与数据科学学院，山东 济宁 273165； 2.山东农业大学经管学院，山东 泰安 271018)

0 引 言

新冠疫情对全球经济造成了严重的冲击[1-2]。受疫情影响，我国工业产值下滑，服务业生产总值下降，市场销售额减少，固定资产投资额降低[3-6]。随疫情防控工作的周密进行和中央宏观经济政策力度的加强，企业积极复工复产[7]，总体经济复苏进程加快，就业情况有望好转。疫情后企业复工复产状况会直接影响一个地区的经济发展[8]，所以，及时、准确地建立疫情后企业复工复产对地方经济恢复影响力的评价指标是经济健康、持续发展的关键问题[9-10]。

在传统的综合指标中原始数据通常是以点值(实数)的形式给出的。但随着社会的发展，评价环境越来越复杂，评价者往往受到自身一些主观和客观因素的影响，如知识结构、判断水平和个人偏好等，所做出的评价很大程度上具有不确定性或模糊性[11]。在疫情后企业复工复产对地方经济恢复影响水平评价中，由于存在很多不确定的因素，专家在打分时具有犹豫心理[12]，或是多个专家对其有多个不同的判定结果。Zadeh[13]于1965年提出了模糊集的概念，允许某个元素属于一个集合的隶属度可以任取在[0,1]区间上的某一个值，奠定了模糊集的理论基础。Torra等人[14-15]提出了犹豫模糊集的定义，当决策者犹豫不定时，可以选定多个数值作为最终的隶属度值。徐泽水团队[16-17]提出了犹豫模糊集间的距离测度和相似性度量公式，并给出了证明。夏梅梅[18]提出了一系列的犹豫模糊距离和相似度公式。

聚类是把一系列的对象、方案或事件等分成若干个类的过程，每个类中对象的特征比其他类有更高的相似性。聚类分析是利用数学的方法按照确定的标准对客观事物进行分类，将样本的相似程度作为划分原则，这样选择合适的相似度就成为聚类的关键。面对不同的模糊环境，人们提出了各种聚类算法来处理不同类型的模糊数据，如直觉模糊聚类算法[19]、二型模糊聚类算法[20]等。2015年，陈娜[21]在模糊信息集成算子和距离测度的基础上，提出了对犹豫模糊信息进行聚类的算法。2008年，吴春旭等人[22]将K均值算法应用到模糊聚类中。

在传统K均值聚类算法中，由于初始的聚类中心是随机的，有时需要迭代多次才能得到最终的聚类结果，在一定程度上影响了聚类效率。Canopy算法属于一种“粗”聚类算法，通过简单、快捷的距离计算就可以把犹豫模糊集分为若干可重叠的子集[23]。而且，相对于传统K均值聚类算法，它不需要预先制定聚类数。因此，为简化聚类算法中的迭代次数，本文提出一种基于Canopy算法的K均值犹豫模糊聚类算法。

1 犹豫模糊集基础理论

1.1 犹豫模糊集的距离公式

1)0≤d(M,N)≤1；

2)当且仅当M=N时，d(M,N)=0成立；

3)d(M,N)=d(N,M)。

在上述给定的条件下，定义犹豫模糊加权欧氏距离公式为：

(1)

1.2 犹豫模糊数的集成

设Mj={〈xi,hAj(xi)〉|xi∈X}(j=1,2,…,k)是一组犹豫模糊集，则：

M⊕N={〈xi,∪r1∈hM(xi),r2∈hN(xi){r1+r2-r1r2}〉|xi∈X}

(2)

则Mj的平均函数公式为[21]：

(3)

2 犹豫模糊Canopy-K均值聚类算法

本文提出的基于Canopy算法的K均值犹豫模糊聚类算法，以Canopy聚类(程序Ⅰ)作为预聚类得到K均值初始类中心，随后通过K均值聚类(程序Ⅱ)得到最终聚类结果。具体步骤如下：

2.1 程序Ⅰ

步骤1 假设k个犹豫模糊集{M1}，{M2}，…，{Mk}。

步骤2 从中任意取出一个类Mp，由公式(1)计算类Mp与其余k-1个类之间的距离D。根据先验知识设定2个距离阈值T1、T2的值，其中T1>T2。

如果T2

如果D≤T2，给R一个强标记，表示R属于该Canopy，且和质心非常接近，并将R从集合中删除，以后不再作为中心点；

如果D>T1，则R形成一个新的聚簇，并将R从集合中删除。

步骤3 重复步骤2直至各集合内的元素不再发生变化，此时会形成c个Canopy(1≤c≤k)，每个Canopy中包含一个或多个犹豫模糊集M。本文将各Canopy记作犹豫模糊集Mj(j=1,2,…,c)。

步骤4 由公式(3)将Mj(j=1,2,…,c)中的犹豫模糊集M合并，计算各Mj的类中心。

2.2 程序Ⅱ

步骤5 从程序Ⅰ获得聚类的类别数c和初始的聚类中心。

步骤6 通过公式(1)计算犹豫模糊集Mj(j=1,2,…,c)与类中心之间的距离，将Mj并入距离类中心最近的类。

步骤7 由公式(3)计算新的类中心。

步骤8 重复步骤6和步骤7，直到迭代稳定。

为了更加清晰地表明本文提出的犹豫模糊Canopy-K均值聚类算法的具体实现过程，下面给出算法的流程图，见图1。

3 实例分析

为了更好地说明本文提出的犹豫模糊Canopy-K均值聚类算法的有效性和稳定性，首先结合实例数据给出新提出算法的具体聚类过程。然后，将其与基于层次分析法的K均值聚类算法进行对比分析。

3.1 犹豫模糊Canopy-K均值聚类算法

通过分析地方企业对当地经济的作用机制以及地方企业应重点建设的指标，并邀请几位专家对复工复产的5个企业Mi(i=1,2…,5)的发展情况分别从6个指标[25-26](技术创新、财力资源、偿债融资能力、人才吸引、企业管理、企业所在地疫情缓解程度)进行评估，这6个指标用特征向量X={x1,x2,…,x6}来表示，其重要性程度用权重向量表示：

w=(0.18,0.13,0.16,0.19,0.17,0.17)T

考虑不同专家对项目的属性可能给出不同的评估值，用犹豫模糊集Mi(i=1,2…,5)来表示对5个复工复产企业的发展状况的评估信息。具体数据如表1所示。

表1 犹豫模糊评估信息

本文提出的犹豫模糊Canopy-K均值聚类算法的具体实现过程如下：

程序Ⅰ

步骤1 每个犹豫模糊集Mj(j=1,2,…,5)各自为一类：{M1},{M2},…{M5}。

步骤2 从中任意取一个类Mp，由公式(1)计算类Mp与其余集合之间的距离：

d(M1,M2)=d(M2,M1)=0.3055

d(M1,M3)=d(M3,M1)=0.3162

d(M1,M4)=d(M4,M1)=0.3256

d(M1,M5)=d(M5,M1)=0.4047

d(M2,M3)=d(M3,M2)=0.2090

d(M2,M4)=d(M4,M2)=0.2352

d(M2,M5)=d(M5,M2)=0.3674

d(M3,M4)=d(M4,M3)=0.3403

d(M3,M5)=d(M5,M3)=0.4613

d(M4,M5)=d(M5,M4)=0.2907

可以得到：

d(M1,M2)=min{d(M1,M2),d(M1,M3),d(M1,M4),d(M1,M5)}=0.3055

d(M2,M3)=min{d(M2,M1),d(M2,M3),d(M2,M4),d(M2,M5)}=0.2090

d(M3,M2)=min{d(M3,M1),d(M3,M2),d(M3,M4),d(M3,M5)}=0.2090

d(M4,M2)=min{d(M4,M1),d(M4,M2),d(M4,M3),d(M4,M5)}=0.2352

d(M5,M4)=min{d(M5,M1),d(M5,M2),d(M5,M3),d(M5,M4)}=0.2907

经计算，2个距离阈值T1=0.3232，T2=0.2499。首先选择M1为一个Canopy的类中心，根据计算得到的d(M1,Mj)进行Canopy预聚类。

步骤3 对各犹豫模糊集Mj(j=1,2,…,5)进行上述操作，直至各集合内的元素不再发生变化，此时形成了3个Canopy(如图2所示)。其中M3既属于以M1为中心的Canopy，又属于以M2为中心的Canopy，但由于d(M3,M1)>d(M3,M2)，因此将M3归类为以M2为中心的Canopy。同理，将M4归类为以M2为中心的Canopy。因此Canopy聚类的最终结果为：{M1},{M2,M3,M4},{M5}。

图2 Canopy聚类结果图

步骤4 由公式(3)将M2、M3、M4合并为M6，3个Canopy的类中心分别为C1、C234、C5，其中：

C1={,,,,,}

C234={,,,,,}

C5={,,,,,}

程序Ⅱ

步骤5 从程序Ⅰ可以获得聚类的类别数K为3，初始类中心为C1、C234、C5。

步骤6 通过公式(1)计算犹豫模糊集Mj(j=1,2,…,5)与初始类中心之间的距离，得到距离为：

d(M1,C234)=d(C234,M1)=0.4623

d(M2,C234)=d(C234,M2)=0.2117

d(M3,C234)=d(C234,M3)=0.3092

d(M4,C234)=d(C234,M4)=0.1010

d(M5,C234)=d(C234,M5)=0.3013

d(M1,C5)=d(C5,M1)=0.4047

d(M2,C5)=d(C5,M2)=0.3674

d(M3,C5)=d(C5,M3)=0.4613

d(M4,C5)=d(C5,M4)=0.2907

d(M2,C1)=d(C1,M2)=0.3055

d(M3,C1)=d(C1,M3)=0.3162

d(M4,C1)=d(C1,M4)=0.3256

d(M5,C1)=d(C1,M5)=0.4047

由上面的计算结果可知，M2、M3、M4与类中心C234距离最近，因此M2、M3、M4归类到集合M6。M1、M5分别与C1、C5距离为0，因此M1、M5自成一类。

因此，依据6个评价指标(技术创新，财力资源、偿债融资能力、人才吸引、企业管理、企业所在地疫情缓解程度)的犹豫模糊信息，对5个企业进行聚类分析，得到3个类别：{M1}、{M2,M3,M4}、{M5}，聚类过程及结果如表2所示。

表2 本文算法迭代过程及结果

3.2 对比分析

为了更好地说明本文提出的犹豫模糊Canopy-K均值聚类算法的有效性和稳定性，下面将其与文献[21]采用的基于层次分析法的K均值聚类算法进行对比分析。层次结构是信息处理中一种被广泛采用的技术，该算法将层次凝聚聚类的结果作为K均值算法的初始化方法。层次技术可以提供K均值聚类所需要的初始类别[27]，且技术非常灵活。层次凝聚聚类的聚类思想为：对不同犹豫模糊集之间的距离进行比较，合并具有最短距离的2个类别，并不断更新类中心，直到所有犹豫模糊集聚成一类，迭代结束。

对上节实例，由程序Ⅰ步骤2得到各个类别的犹豫模糊欧氏距离，并且得到集合M2、M3距离最短，因此Mj(j=1,2,…,5)被分为下面4类：{M1},{M2,M3},{M4},{M5}，由公式(3)计算新的类中心。通过合并距离最短的2个集合并不断更新类中心。

选择层次聚类的结果作为K均值聚类的初始类别，K值为3，初始类为：{M1},{M2,M3},{M4,M5}。通过K均值聚类步骤不断更新类中心，迭代5次后得到最终分类：{M1,M2,M3},{M4},{M5}。迭代过程见表3。

表3 对比算法迭代过程及结果

对比算法的最终聚类结果与Canopy-K均值聚类结果不同。但从图2各类别分布图可以看出，M2、M3、M4这3类位置更加接近。并且由M1～M5各类别的犹豫模糊数，M2、M3、M4这6个指标特征x1～x6的犹豫模糊数更接近，聚为一类效果更好。

此外，对比算法需要迭代5次才能得到最终结果，而采用本文提出的犹豫模糊Canopy-K均值聚类算法只需1次迭代就可以完成聚类(本文算法与对比算法的聚类结果如表4所示)。这主要是因为采用Canopy算法的聚类结果作为K均值聚类算法的初始聚类中心，有效地解决了传统的K均值聚类算法对初始值敏感的问题。

表4 本文算法与对比算法对比结果

4 结束语

本文针对传统的K均值聚类算法对初始聚类中心点敏感、需要人为给定初始类中心和聚类数目、迭代次数较多的缺点，结合Canopy算法对传统的K均值聚类进行了优化。引入Canopy算法作为K均值算法的预聚类，形成多个数据重合的Canopy中心集合，把各个Canopy中心作为K均值聚类算法的初始聚类中心。通过分析地方企业对当地经济的作用机制以及地方企业应重点建设的指标，并邀请几位专家对复工复产的5个企业的发展情况分别从6个方面(技术创新、财力资源、偿债融资能力、人才吸引、企业管理、企业所在地疫情缓解程度)进行评估，并结合具体的实例数据，得到本文算法和基于层次分析法的K均值聚类算法的迭代过程及结果(如表2、表3所示)。表4列出2种算法在迭代次数和分类结果上的不同，通过对比分析，新提出的犹豫模糊Canopy-K均值聚类算法迭代次数少，聚类结果更加合理、稳定和有效。