基于猶豫模糊Canopy-K均值聚類算法的研究與應(yīng)用

張子璇，沙秀艷,2，肖 霏，粟寶嬋，隋雨陸，孟子宸

(1.曲阜師范大學(xué)統(tǒng)計(jì)與數(shù)據(jù)科學(xué)學(xué)院，山東 濟(jì)寧 273165； 2.山東農(nóng)業(yè)大學(xué)經(jīng)管學(xué)院，山東 泰安 271018)

0 引 言

新冠疫情對(duì)全球經(jīng)濟(jì)造成了嚴(yán)重的沖擊[1-2]。受疫情影響，我國(guó)工業(yè)產(chǎn)值下滑，服務(wù)業(yè)生產(chǎn)總值下降，市場(chǎng)銷售額減少，固定資產(chǎn)投資額降低[3-6]。隨疫情防控工作的周密進(jìn)行和中央宏觀經(jīng)濟(jì)政策力度的加強(qiáng)，企業(yè)積極復(fù)工復(fù)產(chǎn)[7]，總體經(jīng)濟(jì)復(fù)蘇進(jìn)程加快，就業(yè)情況有望好轉(zhuǎn)。疫情后企業(yè)復(fù)工復(fù)產(chǎn)狀況會(huì)直接影響一個(gè)地區(qū)的經(jīng)濟(jì)發(fā)展[8]，所以，及時(shí)、準(zhǔn)確地建立疫情后企業(yè)復(fù)工復(fù)產(chǎn)對(duì)地方經(jīng)濟(jì)恢復(fù)影響力的評(píng)價(jià)指標(biāo)是經(jīng)濟(jì)健康、持續(xù)發(fā)展的關(guān)鍵問(wèn)題[9-10]。

在傳統(tǒng)的綜合指標(biāo)中原始數(shù)據(jù)通常是以點(diǎn)值(實(shí)數(shù))的形式給出的。但隨著社會(huì)的發(fā)展，評(píng)價(jià)環(huán)境越來(lái)越復(fù)雜，評(píng)價(jià)者往往受到自身一些主觀和客觀因素的影響，如知識(shí)結(jié)構(gòu)、判斷水平和個(gè)人偏好等，所做出的評(píng)價(jià)很大程度上具有不確定性或模糊性[11]。在疫情后企業(yè)復(fù)工復(fù)產(chǎn)對(duì)地方經(jīng)濟(jì)恢復(fù)影響水平評(píng)價(jià)中，由于存在很多不確定的因素，專家在打分時(shí)具有猶豫心理[12]，或是多個(gè)專家對(duì)其有多個(gè)不同的判定結(jié)果。Zadeh[13]于1965年提出了模糊集的概念，允許某個(gè)元素屬于一個(gè)集合的隸屬度可以任取在[0,1]區(qū)間上的某一個(gè)值，奠定了模糊集的理論基礎(chǔ)。Torra等人[14-15]提出了猶豫模糊集的定義，當(dāng)決策者猶豫不定時(shí)，可以選定多個(gè)數(shù)值作為最終的隸屬度值。徐澤水團(tuán)隊(duì)[16-17]提出了猶豫模糊集間的距離測(cè)度和相似性度量公式，并給出了證明。夏梅梅[18]提出了一系列的猶豫模糊距離和相似度公式。

聚類是把一系列的對(duì)象、方案或事件等分成若干個(gè)類的過(guò)程，每個(gè)類中對(duì)象的特征比其他類有更高的相似性。聚類分析是利用數(shù)學(xué)的方法按照確定的標(biāo)準(zhǔn)對(duì)客觀事物進(jìn)行分類，將樣本的相似程度作為劃分原則，這樣選擇合適的相似度就成為聚類的關(guān)鍵。面對(duì)不同的模糊環(huán)境，人們提出了各種聚類算法來(lái)處理不同類型的模糊數(shù)據(jù)，如直覺模糊聚類算法[19]、二型模糊聚類算法[20]等。2015年，陳娜[21]在模糊信息集成算子和距離測(cè)度的基礎(chǔ)上，提出了對(duì)猶豫模糊信息進(jìn)行聚類的算法。2008年，吳春旭等人[22]將K均值算法應(yīng)用到模糊聚類中。

在傳統(tǒng)K均值聚類算法中，由于初始的聚類中心是隨機(jī)的，有時(shí)需要迭代多次才能得到最終的聚類結(jié)果，在一定程度上影響了聚類效率。Canopy算法屬于一種“粗”聚類算法，通過(guò)簡(jiǎn)單、快捷的距離計(jì)算就可以把猶豫模糊集分為若干可重疊的子集[23]。而且，相對(duì)于傳統(tǒng)K均值聚類算法，它不需要預(yù)先制定聚類數(shù)。因此，為簡(jiǎn)化聚類算法中的迭代次數(shù)，本文提出一種基于Canopy算法的K均值猶豫模糊聚類算法。

1 猶豫模糊集基礎(chǔ)理論

1.1 猶豫模糊集的距離公式

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

2)當(dāng)且僅當(dāng)M=N時(shí)，d(M,N)=0成立；

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

在上述給定的條件下，定義猶豫模糊加權(quán)歐氏距離公式為：

(1)

1.2 猶豫模糊數(shù)的集成

設(shè)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的平均函數(shù)公式為[21]：

(3)

2 猶豫模糊Canopy-K均值聚類算法

本文提出的基于Canopy算法的K均值猶豫模糊聚類算法，以Canopy聚類(程序Ⅰ)作為預(yù)聚類得到K均值初始類中心，隨后通過(guò)K均值聚類(程序Ⅱ)得到最終聚類結(jié)果。具體步驟如下：

2.1 程序Ⅰ

步驟1 假設(shè)k個(gè)猶豫模糊集{M1}，{M2}，…，{Mk}。

步驟2 從中任意取出一個(gè)類Mp，由公式(1)計(jì)算類Mp與其余k-1個(gè)類之間的距離D。根據(jù)先驗(yàn)知識(shí)設(shè)定2個(gè)距離閾值T1、T2的值，其中T1>T2。

如果T2

如果D≤T2，給R一個(gè)強(qiáng)標(biāo)記，表示R屬于該Canopy，且和質(zhì)心非常接近，并將R從集合中刪除，以后不再作為中心點(diǎn)；

如果D>T1，則R形成一個(gè)新的聚簇，并將R從集合中刪除。

步驟3 重復(fù)步驟2直至各集合內(nèi)的元素不再發(fā)生變化，此時(shí)會(huì)形成c個(gè)Canopy(1≤c≤k)，每個(gè)Canopy中包含一個(gè)或多個(gè)猶豫模糊集M。本文將各Canopy記作猶豫模糊集Mj(j=1,2,…,c)。

步驟4 由公式(3)將Mj(j=1,2,…,c)中的猶豫模糊集M合并，計(jì)算各Mj的類中心。

2.2 程序Ⅱ

步驟5 從程序Ⅰ獲得聚類的類別數(shù)c和初始的聚類中心。

步驟6 通過(guò)公式(1)計(jì)算猶豫模糊集Mj(j=1,2,…,c)與類中心之間的距離，將Mj并入距離類中心最近的類。

步驟7 由公式(3)計(jì)算新的類中心。

步驟8 重復(fù)步驟6和步驟7，直到迭代穩(wěn)定。

為了更加清晰地表明本文提出的猶豫模糊Canopy-K均值聚類算法的具體實(shí)現(xiàn)過(guò)程，下面給出算法的流程圖，見圖1。

3 實(shí)例分析

為了更好地說(shuō)明本文提出的猶豫模糊Canopy-K均值聚類算法的有效性和穩(wěn)定性，首先結(jié)合實(shí)例數(shù)據(jù)給出新提出算法的具體聚類過(guò)程。然后，將其與基于層次分析法的K均值聚類算法進(jìn)行對(duì)比分析。

3.1 猶豫模糊Canopy-K均值聚類算法

通過(guò)分析地方企業(yè)對(duì)當(dāng)?shù)亟?jīng)濟(jì)的作用機(jī)制以及地方企業(yè)應(yīng)重點(diǎn)建設(shè)的指標(biāo)，并邀請(qǐng)幾位專家對(duì)復(fù)工復(fù)產(chǎn)的5個(gè)企業(yè)Mi(i=1,2…,5)的發(fā)展情況分別從6個(gè)指標(biāo)[25-26](技術(shù)創(chuàng)新、財(cái)力資源、償債融資能力、人才吸引、企業(yè)管理、企業(yè)所在地疫情緩解程度)進(jìn)行評(píng)估，這6個(gè)指標(biāo)用特征向量X={x1,x2,…,x6}來(lái)表示，其重要性程度用權(quán)重向量表示：

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

考慮不同專家對(duì)項(xiàng)目的屬性可能給出不同的評(píng)估值，用猶豫模糊集Mi(i=1,2…,5)來(lái)表示對(duì)5個(gè)復(fù)工復(fù)產(chǎn)企業(yè)的發(fā)展?fàn)顩r的評(píng)估信息。具體數(shù)據(jù)如表1所示。

表1 猶豫模糊評(píng)估信息

本文提出的猶豫模糊Canopy-K均值聚類算法的具體實(shí)現(xiàn)過(guò)程如下：

程序Ⅰ

步驟1 每個(gè)猶豫模糊集Mj(j=1,2,…,5)各自為一類：{M1},{M2},…{M5}。

步驟2 從中任意取一個(gè)類Mp，由公式(1)計(jì)算類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

經(jīng)計(jì)算，2個(gè)距離閾值T1=0.3232，T2=0.2499。首先選擇M1為一個(gè)Canopy的類中心，根據(jù)計(jì)算得到的d(M1,Mj)進(jìn)行Canopy預(yù)聚類。

步驟3 對(duì)各猶豫模糊集Mj(j=1,2,…,5)進(jìn)行上述操作，直至各集合內(nèi)的元素不再發(fā)生變化，此時(shí)形成了3個(gè)Canopy(如圖2所示)。其中M3既屬于以M1為中心的Canopy，又屬于以M2為中心的Canopy，但由于d(M3,M1)>d(M3,M2)，因此將M3歸類為以M2為中心的Canopy。同理，將M4歸類為以M2為中心的Canopy。因此Canopy聚類的最終結(jié)果為：{M1},{M2,M3,M4},{M5}。

圖2 Canopy聚類結(jié)果圖

步驟4 由公式(3)將M2、M3、M4合并為M6，3個(gè)Canopy的類中心分別為C1、C234、C5，其中：

C1={,,,,,}

C234={,,,,,}

C5={,,,,,}

程序Ⅱ

步驟5 從程序Ⅰ可以獲得聚類的類別數(shù)K為3，初始類中心為C1、C234、C5。

步驟6 通過(guò)公式(1)計(jì)算猶豫模糊集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

由上面的計(jì)算結(jié)果可知，M2、M3、M4與類中心C234距離最近，因此M2、M3、M4歸類到集合M6。M1、M5分別與C1、C5距離為0，因此M1、M5自成一類。

因此，依據(jù)6個(gè)評(píng)價(jià)指標(biāo)(技術(shù)創(chuàng)新，財(cái)力資源、償債融資能力、人才吸引、企業(yè)管理、企業(yè)所在地疫情緩解程度)的猶豫模糊信息，對(duì)5個(gè)企業(yè)進(jìn)行聚類分析，得到3個(gè)類別：{M1}、{M2,M3,M4}、{M5}，聚類過(guò)程及結(jié)果如表2所示。

表2 本文算法迭代過(guò)程及結(jié)果

3.2 對(duì)比分析

為了更好地說(shuō)明本文提出的猶豫模糊Canopy-K均值聚類算法的有效性和穩(wěn)定性，下面將其與文獻(xiàn)[21]采用的基于層次分析法的K均值聚類算法進(jìn)行對(duì)比分析。層次結(jié)構(gòu)是信息處理中一種被廣泛采用的技術(shù)，該算法將層次凝聚聚類的結(jié)果作為K均值算法的初始化方法。層次技術(shù)可以提供K均值聚類所需要的初始類別[27]，且技術(shù)非常靈活。層次凝聚聚類的聚類思想為：對(duì)不同猶豫模糊集之間的距離進(jìn)行比較，合并具有最短距離的2個(gè)類別，并不斷更新類中心，直到所有猶豫模糊集聚成一類，迭代結(jié)束。

對(duì)上節(jié)實(shí)例，由程序Ⅰ步驟2得到各個(gè)類別的猶豫模糊歐氏距離，并且得到集合M2、M3距離最短，因此Mj(j=1,2,…,5)被分為下面4類：{M1},{M2,M3},{M4},{M5}，由公式(3)計(jì)算新的類中心。通過(guò)合并距離最短的2個(gè)集合并不斷更新類中心。

選擇層次聚類的結(jié)果作為K均值聚類的初始類別，K值為3，初始類為：{M1},{M2,M3},{M4,M5}。通過(guò)K均值聚類步驟不斷更新類中心，迭代5次后得到最終分類：{M1,M2,M3},{M4},{M5}。迭代過(guò)程見表3。

表3 對(duì)比算法迭代過(guò)程及結(jié)果

對(duì)比算法的最終聚類結(jié)果與Canopy-K均值聚類結(jié)果不同。但從圖2各類別分布圖可以看出，M2、M3、M4這3類位置更加接近。并且由M1～M5各類別的猶豫模糊數(shù)，M2、M3、M4這6個(gè)指標(biāo)特征x1～x6的猶豫模糊數(shù)更接近，聚為一類效果更好。

此外，對(duì)比算法需要迭代5次才能得到最終結(jié)果，而采用本文提出的猶豫模糊Canopy-K均值聚類算法只需1次迭代就可以完成聚類(本文算法與對(duì)比算法的聚類結(jié)果如表4所示)。這主要是因?yàn)椴捎肅anopy算法的聚類結(jié)果作為K均值聚類算法的初始聚類中心，有效地解決了傳統(tǒng)的K均值聚類算法對(duì)初始值敏感的問(wèn)題。

表4 本文算法與對(duì)比算法對(duì)比結(jié)果

4 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)的K均值聚類算法對(duì)初始聚類中心點(diǎn)敏感、需要人為給定初始類中心和聚類數(shù)目、迭代次數(shù)較多的缺點(diǎn)，結(jié)合Canopy算法對(duì)傳統(tǒng)的K均值聚類進(jìn)行了優(yōu)化。引入Canopy算法作為K均值算法的預(yù)聚類，形成多個(gè)數(shù)據(jù)重合的Canopy中心集合，把各個(gè)Canopy中心作為K均值聚類算法的初始聚類中心。通過(guò)分析地方企業(yè)對(duì)當(dāng)?shù)亟?jīng)濟(jì)的作用機(jī)制以及地方企業(yè)應(yīng)重點(diǎn)建設(shè)的指標(biāo)，并邀請(qǐng)幾位專家對(duì)復(fù)工復(fù)產(chǎn)的5個(gè)企業(yè)的發(fā)展情況分別從6個(gè)方面(技術(shù)創(chuàng)新、財(cái)力資源、償債融資能力、人才吸引、企業(yè)管理、企業(yè)所在地疫情緩解程度)進(jìn)行評(píng)估，并結(jié)合具體的實(shí)例數(shù)據(jù)，得到本文算法和基于層次分析法的K均值聚類算法的迭代過(guò)程及結(jié)果(如表2、表3所示)。表4列出2種算法在迭代次數(shù)和分類結(jié)果上的不同，通過(guò)對(duì)比分析，新提出的猶豫模糊Canopy-K均值聚類算法迭代次數(shù)少，聚類結(jié)果更加合理、穩(wěn)定和有效。