基于加權(quán)直覺模糊蘭氏距離的密度峰值聚類算法

徐 鑫，曹 原

(山東理工大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，山東 淄博 255000)

聚類分析的目的是將對(duì)象按照某種規(guī)則劃分成不同的簇，使得簇內(nèi)相似性較大、簇間相似性較小。目前，聚類分析在文本挖掘[1-2]、生物醫(yī)學(xué)[3]、金融管理[4]、工業(yè)發(fā)展[5]等領(lǐng)域得到了廣泛應(yīng)用。從機(jī)器學(xué)習(xí)角度看，聚類分析屬于無監(jiān)督學(xué)習(xí)方法，根據(jù)學(xué)習(xí)算法自動(dòng)確定無標(biāo)簽數(shù)據(jù)的標(biāo)記。大數(shù)據(jù)時(shí)代的數(shù)據(jù)規(guī)模越來越龐大，數(shù)據(jù)類型也更加豐富，很難使用人工去定性分析龐大的數(shù)據(jù)集群，因此適用于大數(shù)據(jù)環(huán)境的聚類算法便應(yīng)運(yùn)而生。

傳統(tǒng)的聚類方法主要包括k均值算法(k-means)、k中心點(diǎn)算法(k-medoids)、基于密度的噪聲應(yīng)用空間聚類算法(density-based spatial clustering of applications with noise，DBSCAN)和凝聚型層次聚類算法等。這些算法各有優(yōu)點(diǎn)，原理簡單且易于實(shí)現(xiàn)，因此廣泛應(yīng)用于各個(gè)領(lǐng)域。但上述算法同樣存在一定的不足，如k-means算法的類別個(gè)數(shù)難以確定、迭代過程中易受噪聲點(diǎn)干擾；DBSCAN算法受參數(shù)影響較大，因此Dong等[6]將兩種算法結(jié)合，克服了兩種算法的缺點(diǎn)，提高了聚類精度。除了集成聚類算法外，還和其他優(yōu)化算法相結(jié)合，如Kapil等[7]基于遺傳算法改進(jìn)k-means算法，優(yōu)化了算法參數(shù)的選擇。此外，Rodriguez等[8]提出了一種新的快速搜索和發(fā)現(xiàn)聚類中心的算法，利用局部密度和相對(duì)距離2個(gè)變量來刻畫聚類中心，可以大大減少算法的運(yùn)行時(shí)間。近年來，隨著深度學(xué)習(xí)的迅猛發(fā)展，越來越多的聚類算法與其相結(jié)合，體現(xiàn)出了強(qiáng)大的算力，Xu等[9]提出了一種基于SDAE和Gath-Geva(GG)聚類算法的無數(shù)據(jù)標(biāo)簽滾動(dòng)軸承故障診斷方法,大大提高了檢測的準(zhǔn)確性。

上述方法通常適用于確定性數(shù)據(jù)集下的聚類問題。然而在現(xiàn)實(shí)生活中，很多問題不能用確定性數(shù)據(jù)進(jìn)行表示，如在決策過程中，決策者對(duì)一個(gè)元素屬于某集合和不屬于某集合的程度，即隸屬度和非隸屬度是不確定的。對(duì)此，Zadeh在1965年首次提出模糊集的概念[10]，更加細(xì)膩地表達(dá)決策過程中的不確定問題。近幾年，模糊集被廣泛應(yīng)用于水利抗洪、信息安全、創(chuàng)新收入關(guān)系分析等領(lǐng)域。許多學(xué)者對(duì)模糊集進(jìn)行拓展延伸，提出更加符合實(shí)際問題的直覺模糊集、猶豫模糊集、畢達(dá)哥拉斯模糊集等。1986年Atanassov[11]提出的直覺模糊集(IFS)，可以表示決策者對(duì)一個(gè)元素屬于某個(gè)集合的支持、反對(duì)和猶豫的程度，通過這3個(gè)變量的刻畫，更加全面地反映決策者對(duì)實(shí)際問題的評(píng)判結(jié)果。在直覺模糊集的基礎(chǔ)上，Shu等[12]定義了三角形直覺模糊數(shù)，并將其與故障樹分析技術(shù)相結(jié)合，靈活地估計(jì)故障區(qū)間。在直覺模糊集聚類方面，Li等[13]提出新的直覺模糊相似度與熵，利用傳遞閉包法進(jìn)行聚類分析，提高了直覺模糊聚類的準(zhǔn)確性。但是，上述聚類算法僅適用于小規(guī)模樣本的直覺模糊集。隨著大數(shù)據(jù)時(shí)代的到來和機(jī)器學(xué)習(xí)算法的廣泛流行，有學(xué)者將機(jī)器學(xué)習(xí)算法應(yīng)用到樣本量較大的直覺模糊集中進(jìn)行聚類分析，Xu[14]提出了凝聚型直覺模糊層次聚類算法，優(yōu)化了直覺模糊集的聚類效果，但是其復(fù)雜度較高，不適用于解決大規(guī)模直覺模糊集聚類的問題。

針對(duì)大規(guī)模直覺模糊集的聚類問題，本文在文獻(xiàn)[14]的基礎(chǔ)上提出了新的直覺模糊聚類算法。首先，給出了改進(jìn)蘭氏距離在直覺模糊集上的計(jì)算公式，并利用直覺模糊熵計(jì)算屬性權(quán)重；其次，對(duì)于聚類過程中算法復(fù)雜度較大的情況，本文利用密度峰值算法進(jìn)行聚類，使聚類算法能夠適應(yīng)大規(guī)模樣本環(huán)境，具有一定的實(shí)用性。同時(shí)，將UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行直覺模糊化并進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性。

1 相關(guān)定義

1.1 直覺模糊集的相關(guān)定義

現(xiàn)實(shí)生活中有很多概念不能簡單地用“是”或“否”來描述，模糊集合指具有某個(gè)模糊概念所描述的屬性對(duì)象的全體。由于概念本身不是清晰的、界限分明的，因而對(duì)象對(duì)集合的隸屬關(guān)系也不是明確的、非此即彼的。Zadeh提出了模糊集的概念用于描述模糊性現(xiàn)象。

定義1[10]設(shè)X是一個(gè)給定的非空對(duì)象集合，則定義模糊集A是由X集合通過函數(shù)f映射所得的一個(gè)新對(duì)象集合，fA(x)∈[0,1]的值表示集合A中元素x∈X的隸屬程度，簡稱隸屬度。

直覺模糊集(IFS)是一種模糊集的拓展與改進(jìn)理論，它最大的特點(diǎn)就是同時(shí)考慮了支持、反對(duì)和棄權(quán)的程度。

定義2[14]設(shè)X是一個(gè)固定集合，在X上的直覺模糊集合A定義為

A={〈x,μA(x),vA(x)〉|x∈X},

式中函數(shù)μA(x)和vA(x)分別表示在X中的元素x對(duì)集合A的隸屬度和非隸屬度,并滿足條件

0≤μA(x)≤1,0≤vA(x)≤1,

0≤μA(x)+vA(x)≤1,

其中πA(x)=1-μA(x)-vA(x)表示x對(duì)集合A的猶豫度。當(dāng)X中只有一個(gè)元素x時(shí)，IFS表示為A={〈x,μA(x),vA(x)〉}，稱為直覺模糊元。

定義3[15]給定兩個(gè)直覺模糊集A={〈x,μA(x),vA(x)〉|x∈X}和B={〈x,μB(x),vB(x)〉|x∈X},其運(yùn)算法則如下：

1)A?B當(dāng)且僅當(dāng)?x∈X，有μA(x)≤μB(x)且vA(x)≥vB(x);

2)A=B當(dāng)且僅當(dāng)?x∈X，有μA(x)=μB(x)且vA(x)=vB(x);

3)Ac={〈x,vA(x),μA(x)〉|x∈X};

4)An={〈x,[μA(x)]n,[1-vA(x)]n〉|x∈X}。

為刻畫直覺模糊集的距離，文獻(xiàn)[15]給出直覺模糊集的距離度量的一般定義。

定義4[15]稱映射D:SIF(X)×SIF(X)→[0,1]為論域X上的直覺模糊集的距離度量，若對(duì)任意直覺模糊集A、B、C∈SIFs(X)，D滿足：

1)D(A,B)≥0，D(A,B)=0當(dāng)且僅當(dāng)A=B;

2)D(A,B)=D(B,A);

3)D(A,C)≤D(A,B)+D(B,C);

4)如果A?B?C,即相應(yīng)的隸屬度和非隸屬度分別滿足μA(xi)≤μB(xi)≤μC(xi)且vA(xi)≥vB(xi)≥vC(xi)；

那么D(A,C)≥D(A,B),D(A,C)≥D(B,C)。

文獻(xiàn)[16]給出了兩個(gè)直覺模糊集之間的Hammning距離dH(A,B)、標(biāo)準(zhǔn)化Hamming距離dHn(A,B)、歐氏距離dE(A,B)和標(biāo)準(zhǔn)化歐氏距離dEn(A,B)，表示如下：

|vA(xi)-vB(xi)|+

|πA(xi)-πB(xi)|];

(1)

|vA(xi)-vB(xi)|+

|πA(xi)-πB(xi)|];

(2)

(vA(xi)-vB(xi))2+

(πA(xi)-πB(xi))2];

(3)

(vA(xi)-vB(xi))2+

(πA(xi)-πB(xi))2]。

(4)

其中：n表示集合A中直覺模糊元的個(gè)數(shù)，即屬性值個(gè)數(shù)；μA(xi)、vA(xi)和πA(xi)分別表示第i個(gè)屬性對(duì)集合A的隸屬度、非隸屬度和猶豫度。由于這些算子中都包含猶豫度的計(jì)算部分，因此不滿足定義4中的4)。

直覺模糊集通常由直覺模糊補(bǔ)構(gòu)造[17]。建立直覺模糊補(bǔ)的常用方法有Yager生成函數(shù)和 Sugeno生成函數(shù)?；谶@兩種生成函數(shù)可以將模糊集拓展成直覺模糊集。根據(jù)Yager生成函數(shù)[18]，得到的直覺模糊集為

B={〈x,μB(x),(1-μB)β)1/β〉|x∈X}。

(5)

其中，β∈(0,∞)是非隸屬度和猶豫度的控制參數(shù)，則猶豫度由下式計(jì)算：

πB(x)=1-μB(x)-vB(x)=

1-μB(x)-(1-μB(x)β)1/β。

(6)

根據(jù)Sugeno生成函數(shù)[19]，得到的直覺模糊集為

C={〈x,μC(x),(1-μC(x))/(1+λμC(x))〉|

x∈X}。

(7)

其中，λ∈(0,∞)是猶豫度的控制參數(shù)，則猶豫度由下式計(jì)算：

πC(x)=1-μC(x)-vC(x)=1-μC(x)-

(1-μC(x))/(1+λμC(x))。

(8)

1.2 IFSHC算法

層次聚類分析法是聚類分析中較為常用的算法，它的思想簡單，易于實(shí)現(xiàn)。文獻(xiàn)[14]利用自底向上的層次聚類算法對(duì)直覺模糊集進(jìn)行聚類，擴(kuò)展了直覺模糊集的聚類方法。

定義5[16]設(shè)任意兩個(gè)直覺模糊集A={〈x,μA(x),vA(x)〉|x∈X}和B={〈x,μB(x),vB(x)〉|x∈X}，為方便起見，Xu[20]將直覺模糊元(IFNs)記為A=〈μ,v〉，具有以下運(yùn)算法則：

3)A⊕B={〈μA+μB-μAμB,vAvB〉};

4)A?B=〈μAμB,vA+vB-vAvB〉。

基于加性算子和乘性算子，文獻(xiàn)[20]提出了直覺模糊加權(quán)平均算子(IFWA)和直覺模糊加權(quán)幾何算子(IFWG)。

(9)

(10)

當(dāng)權(quán)向量取值相同時(shí)，即wi=1/n，此時(shí)IFWA就退化成了標(biāo)準(zhǔn)直覺模糊平均算子(NIFWA)：

(11)

算法1 IFSHC算法輸入:數(shù)據(jù)集S輸出:數(shù)據(jù)對(duì)象的聚類結(jié)果步驟1:根據(jù)(4)式計(jì)算直覺模糊集中數(shù)據(jù)對(duì)象的距離dij;步驟2:選擇其中距離較小的兩個(gè)簇進(jìn)行連接;步驟3:根據(jù)(10)式計(jì)算連接后的簇中心數(shù)據(jù)對(duì)象;步驟4:重復(fù)步驟1^3,直到數(shù)據(jù)對(duì)象合并成一個(gè)簇。

在IFSHC算法中，步驟1通常利用(4)式計(jì)算直覺模糊集中數(shù)據(jù)對(duì)象的距離，若數(shù)據(jù)對(duì)象中出現(xiàn)偏移較大的屬性值，則聚類結(jié)果也會(huì)受到較大影響。步驟2體現(xiàn)了層次聚類的不可逆性，由于對(duì)象在合并后，下一次聚類將在前一次聚類的基礎(chǔ)上進(jìn)行，若在一次聚類中出錯(cuò)，則會(huì)產(chǎn)生較差的聚類效果。在合并兩個(gè)類之后，算法在步驟3需要利用(9)式或(10)式重新計(jì)算合并后的簇中心，這使得算法的復(fù)雜度較高，不適用于解決大規(guī)模樣本的聚類問題。針對(duì)上述問題，本文提出了一種基于加權(quán)直覺模糊蘭氏距離的密度峰值聚類(WIFDPL)算法，以降低直覺模糊集聚類對(duì)異常值的敏感性，提高算法的效率。

2 WIFDPL算法

2.1 基于蘭氏距離的直覺模糊集距離度量

在利用歐氏距離直覺模糊算子計(jì)算樣本點(diǎn)之間的距離時(shí)，計(jì)算結(jié)果會(huì)受到異常值的影響，導(dǎo)致聚類結(jié)果不穩(wěn)定。因此，距離度量的選擇對(duì)整個(gè)聚類算法有著至關(guān)重要的作用。蘭氏距離[21]由Lance和Williams最早提出，是聚類分析中用于確定樣本間距離的一種方法，其克服了閔可夫斯基距離與各指標(biāo)量綱有關(guān)的缺點(diǎn)，且蘭氏距離對(duì)大的奇異值不敏感，這使其特別適合高度偏移的數(shù)據(jù)。蘭氏距離的計(jì)算方法如下：

(i,j=1,2,…,n)。

(12)

由定義式(12)可知，蘭氏距離的應(yīng)用范圍要求xij>0。但是,在直覺模糊數(shù)據(jù)集中經(jīng)常有隸屬度、非隸屬度或猶豫度為0的情況，因此本文在定義式的分母中加入屬性個(gè)數(shù)的倒數(shù)，即避免分母為0的情況出現(xiàn)，又利用數(shù)據(jù)屬性信息減少數(shù)據(jù)的偏移程度。本文提出了改進(jìn)標(biāo)準(zhǔn)化的直覺模糊蘭氏距離dL(A,B)和改進(jìn)加權(quán)直覺模糊蘭氏距離dLw(A,B)，表達(dá)式如下：

(13)

(14)

其中,wi表示第i個(gè)屬性的權(quán)重，一般根據(jù)屬性的重要程度對(duì)其進(jìn)行人工設(shè)置。當(dāng)對(duì)屬性權(quán)重沒有特殊要求時(shí)，取wi=1/n，這時(shí)加權(quán)直覺模糊蘭氏距離退化為標(biāo)準(zhǔn)化的直覺模糊蘭氏距離。下證改進(jìn)的直覺模糊蘭氏距離滿足定義4。

證明1)和2)顯然成立，此證略。

由于

則

同理

則dL(A,B)+dL(B,C)≥dL(A,C)。

4)設(shè)A?B?C,即μA≤μB≤μC,vA≥vB≥vC,則

同理得

即dL(A,C)-dL(A,B)≥0,則dL(A,C)≥dL(A,B)。同理可證dL(A,C)≥dL(B,C)。證畢。

考慮3個(gè)具有明確態(tài)度的直覺模糊集A={[0.5,0.4],[0.3,0.5],[0.4,0.6]}，B={[0.9,0.1],[0.8,0.1],[0.7,0.2]},C={[0.1,0.9],[0.2,0.8],[0.2,0.7]},可以直觀看出,A偏向中立態(tài)度，B偏向支持態(tài)度，C偏向反對(duì)態(tài)度。利用(2)、(4)和(13)式計(jì)算得到3個(gè)直覺模糊集的距離如表 1所示。后3列為具有異常屬性值的偏移直覺模糊集,A′={[0.5,0.4],[0.3,0.5],[0.4,0.6],[0,1]},C′={[0.9,0.1],[0.8,0.1],[0.7,0.2],[0,1]},

表1 不同算子的距離

B′={[0.1,0.9],[0.2,0.8],[0.2,0.7],[1,0]}。

通過計(jì)算得到3個(gè)算子的偏移量,如表2所示(加粗代表偏移量最小)。分析得到利用改進(jìn)的蘭氏距離算子計(jì)算的距離，其偏移量明顯小于其他算子。因此,相比于其他算子，本文提出的蘭氏距離計(jì)算公式不僅滿足直覺模糊集的距離度量的定義，還在有異常值的情況下減少了數(shù)據(jù)的偏移程度，在進(jìn)行聚類分析時(shí)能夠降低異常值對(duì)聚類效果的影響。

表2 不同算子的偏移量

2.2 WIFDPL算法

針對(duì)IFSHC算法的缺陷，提出基于密度峰值思想和改進(jìn)蘭氏距離的加權(quán)直覺模糊聚類算法(weighted intuitionistic fuzzy algorithm based on density peaks and Lance distance, WIFDPL)。

針對(duì)需要人為設(shè)定屬性權(quán)重的問題，文獻(xiàn)[14]在沒有特殊說明的情況下采取了屬性權(quán)重一致的做法，沒有充分利用數(shù)據(jù)集本身的性質(zhì)。汪凌[22]給出了一種利用直覺模糊熵確定屬性權(quán)重的方法。首先計(jì)算直覺模糊集A中各屬性的直覺模糊熵

(15)

E(A)越大，直覺模糊數(shù)的不確定性越高，說明決策者對(duì)此屬性的意見分歧就越大，因此要相應(yīng)減小此屬性的權(quán)重。記第j個(gè)屬性的總體直覺模糊熵為

(16)

決策者關(guān)于第j個(gè)屬性的權(quán)重可以表示為

(17)

在IFSHC算法中，每次計(jì)算都只能依據(jù)距離大小合并2個(gè)簇，計(jì)算繁瑣，很容易受到較大的異常值影響，而且不能自動(dòng)確定聚類的簇?cái)?shù)。本文采取密度峰值聚類算法確定簇心，既避免了繁瑣的數(shù)據(jù)計(jì)算過程，又優(yōu)化了聚類個(gè)數(shù)的選擇。密度峰值聚類算法(DPC)要求聚類中心滿足兩個(gè)特點(diǎn)：本身密度比較大，即聚類中心被密度均不超過它的數(shù)據(jù)點(diǎn)包圍；聚類中心與其他密度較大的數(shù)據(jù)點(diǎn)之間的距離相對(duì)更大。因此，需要利用局部密度ρi和高局部密度點(diǎn)之間的距離δi兩個(gè)數(shù)據(jù)指標(biāo)來刻畫聚類中心。

定義7[8]設(shè)Xi為數(shù)據(jù)集S的一個(gè)數(shù)據(jù)對(duì)象，它的局部密度可以用S中與Xi之間距離小于dc的點(diǎn)的個(gè)數(shù)來表示，具體公式如下：

(18)

(19)

上式是離散和的形式，適用于數(shù)據(jù)量大的情況。在數(shù)據(jù)量小的情況下，為了降低局部密度數(shù)值一致的概率，需要采用連續(xù)值高斯核的形式：

(20)

其中:dc表示截?cái)嗑嚯x，通常取樣本量的1%～2%作為dc的取值;dij表示直覺模糊集第i個(gè)數(shù)據(jù)對(duì)象到第j個(gè)數(shù)據(jù)對(duì)象的距離，通過(14)式計(jì)算得到。存在數(shù)據(jù)1,2,…,N的一個(gè)全排列q1,q2,…,qN，有ρq1≥ρq2≥…≥ρqN,距離δqi為

(21)

上式說明，當(dāng)xi是局部密度最大的點(diǎn)時(shí)，相應(yīng)的距離δi也會(huì)較大；否則，δi表示在局部密度比xi大的所有點(diǎn)中，與xi距離最小的點(diǎn)的距離。確定了ρ和δ之后，就可以根據(jù)這兩個(gè)數(shù)據(jù)指標(biāo)來選擇聚類中心點(diǎn)，從ρ-δ決策圖中可以選取兩者都較大的數(shù)據(jù)點(diǎn)作為聚類中心。若在決策圖中難以選取聚類中心，文獻(xiàn)[8]提出一種定量選擇聚類中心的方法，即通過計(jì)算γi=ρi×δi，將γi從大到小排序，選取有明顯斷層的前k個(gè)ri對(duì)應(yīng)的數(shù)據(jù)點(diǎn)作為聚類中心。確定聚類中心以后，剩余的點(diǎn)將分配到距離自身最近的聚類中心所在的類中，從而完成直覺模糊集的聚類。

本文基于上述思想，總結(jié)新的直覺模糊集聚類算法基本步驟。

算法2 WIFDPL算法輸入:數(shù)據(jù)集S,參數(shù)dc輸出:數(shù)據(jù)對(duì)象的聚類結(jié)果步驟1:根據(jù)(16)和(17)式計(jì)算屬性權(quán)重wj;步驟2:根據(jù)(14)式計(jì)算數(shù)據(jù)對(duì)象之間的距離;步驟3:根據(jù)(18)或(20)式計(jì)算數(shù)據(jù)對(duì)象的局部密度ρi,根據(jù)(21)式計(jì)算數(shù)據(jù)對(duì)象的距離δi;步驟4:通過ρ-δ決策圖或者γ值確定聚類中心;步驟5:分配除簇心外的其他數(shù)據(jù)對(duì)象到距離自身近且局部密度比自身大的數(shù)據(jù)對(duì)象所在的簇中。

在WIFDPL算法中，步驟1利用直覺模糊熵計(jì)算屬性權(quán)重，反映決策者對(duì)各個(gè)屬性的重視程度。步驟2利用改進(jìn)的加權(quán)直覺模糊蘭氏距離計(jì)算數(shù)據(jù)對(duì)象之間的距離，降低了由偏移數(shù)據(jù)引起的計(jì)算結(jié)果不準(zhǔn)確的影響。步驟3～5是密度峰值聚類，僅通過距離矩陣就可以完成整個(gè)聚類過程，算法復(fù)雜度較低。

2.3 WIFDPL算法的復(fù)雜度分析

算法的復(fù)雜度[23]分為時(shí)間復(fù)雜度和空間復(fù)雜度。在時(shí)間復(fù)雜度上，計(jì)算權(quán)重的復(fù)雜度為O(nd)，計(jì)算距離的復(fù)雜度為O(n2)，計(jì)算局部密度和相對(duì)距離的復(fù)雜度分別為O(n(n-1))和O(n(n-1)/2)，尋找聚類中心時(shí)計(jì)算γ值并排序的復(fù)雜度為O(n+nlog2n)，因此時(shí)間復(fù)雜度為O(n2)；在空間復(fù)雜度上，存儲(chǔ)權(quán)重的復(fù)雜度為O(d)，存儲(chǔ)距離的復(fù)雜度為O(n2)，因此空間復(fù)雜度為O(n2)。

在IFSHC算法中，時(shí)間復(fù)雜度上，計(jì)算距離的復(fù)雜度為O(n2)，合并兩個(gè)較小的類時(shí)需要比較大小的次數(shù)為(n3-n)/6次，則復(fù)雜度為O(n3)，計(jì)算類中心的復(fù)雜度為O(n)，因此時(shí)間復(fù)雜度為O(n3)；空間復(fù)雜度主要為存儲(chǔ)距離矩陣的O(n2)。

由兩個(gè)算法復(fù)雜度的比較結(jié)果可知，IFSHC算法時(shí)間復(fù)雜度較高，隨著數(shù)據(jù)量規(guī)模的擴(kuò)大，算法所需計(jì)算時(shí)間較多，不適于解決數(shù)據(jù)量較大的實(shí)際問題。本文提出的WIFDPL算法的時(shí)間復(fù)雜度比IFSHC算法降低了一個(gè)指數(shù)級(jí)，更適于解決現(xiàn)實(shí)生活中大規(guī)模直覺模糊數(shù)據(jù)聚類的問題。

3 仿真實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)1

利用文獻(xiàn)[14]中的例子對(duì)算法做出說明。如表3所示，實(shí)例由5個(gè)直覺模糊集組成，每個(gè)直覺模糊集有8個(gè)維度。

表3 直覺模糊集

首先確定屬性權(quán)重，將每個(gè)屬性所對(duì)應(yīng)的直覺模糊元帶入(16)式計(jì)算總體直覺模糊熵，得到結(jié)果E1=0.317,E2=0.266,E3=0.200,E4=0.292,E5=0.366,E6=0.335,E7=0.391,E8=0.338;再將其帶入(17)式計(jì)算出屬性權(quán)重，最終結(jié)果為w1=0.12,w2=0.11,w3=0.08,w4=0.13,w5=0.15,w6=0.13,w7=0.15,w8=0.14。

根據(jù)加權(quán)直覺模糊蘭氏距離計(jì)算每個(gè)數(shù)據(jù)對(duì)象之間的距離。由于距離矩陣是對(duì)稱矩陣，因此根據(jù)(14)式計(jì)算得到上三角距離矩陣，結(jié)果如表 4所示。

表4 直覺模糊集之間的距離

得到直覺模糊對(duì)象之間的距離后，就可以計(jì)算得到ρi和δi值。根據(jù)這2個(gè)值發(fā)現(xiàn)，A2、A5、A1的γ值分別為0.138 5、0.091 3、0.063 6，明顯高于γ3=0.014和γ4=0.004，因此可以判斷該數(shù)據(jù)集可以分為3簇，簇中心為A2、A5和A1。最后分配簇以外的數(shù)據(jù)對(duì)象，最終得到聚類結(jié)果為{A1}、{A2,A3}、{A4,A5}。

文獻(xiàn)[14]中IFSHC算法的聚類結(jié)果如表5所示。

表5 IFSHC算法聚類結(jié)果

從表5的第3行可知，當(dāng)聚類類別數(shù)為3時(shí)，聚類結(jié)果為{A1}、{A2,A3}、{A4,A5}，與本文算法一致。IFSHC算法將聚類結(jié)果分為了4種情況，不能選擇出合適的聚類類別數(shù)。基于密度峰值聚類算法可以根據(jù)決策圖或值的變化選擇適合的聚類中心和聚類簇?cái)?shù)，能夠更好地解決現(xiàn)實(shí)生活中的聚類問題。

3.2 實(shí)驗(yàn)2

為了驗(yàn)證本文算法適用于較大規(guī)模直覺模糊數(shù)據(jù)的聚類，本文在Python仿真環(huán)境中進(jìn)行驗(yàn)證，選取經(jīng)典UCI機(jī)器學(xué)習(xí)庫中常用的Seeds、Iris和Spiral數(shù)據(jù)集以及文獻(xiàn)[8]中的Aggregation數(shù)據(jù)集和R15數(shù)據(jù)集，以此說明本文提出算法的有效性。表 6為各個(gè)數(shù)據(jù)集的描述，圖1為利用t-SNE降維后數(shù)據(jù)集的直觀展示。

圖1 人工可視化數(shù)據(jù)集

表6 數(shù)據(jù)集描述

為了使數(shù)據(jù)集適用于直覺模糊環(huán)境，需要對(duì)數(shù)據(jù)集進(jìn)行直覺模糊化處理。首先將數(shù)據(jù)規(guī)范化，公式為uij=(uij-min(uj))/(max(uj)-min(uj))。其中：uij表示第i個(gè)數(shù)據(jù)點(diǎn)的第j個(gè)屬性；max(uj)和min(uj)表示第j個(gè)屬性中的最大值和最小值。規(guī)范化后的數(shù)據(jù)uij作為第i個(gè)數(shù)據(jù)對(duì)象對(duì)第j個(gè)屬性的隸屬度。非隸屬度和猶豫度由(5)～(8)式進(jìn)行設(shè)置。在進(jìn)行非隸屬度和猶豫度的設(shè)置時(shí)，需要設(shè)置適當(dāng)?shù)姆请`屬度和猶豫度的控制參數(shù)。本文在區(qū)間[0,500]內(nèi)尋找聚類效果最好的參數(shù)[17]，每一組參數(shù)設(shè)置見表7和表8的第2列。實(shí)驗(yàn)中截?cái)嗑嚯x均取包含2%的樣本量。聚類性能的評(píng)價(jià)采用3種常用指標(biāo)。

1)標(biāo)準(zhǔn)化互信息[24]

標(biāo)準(zhǔn)化互信息(normalized mutual information，NMI，本文用NMI表示)可以用來衡量兩種聚類結(jié)果的相似度，是聚類中最常用的評(píng)價(jià)指標(biāo)之一。NMI越接近1意味著兩種聚類結(jié)果越相似，

(22)

其中:I(X,Y)是X和Y的互信息，

(23)

H(X)是X的信息熵，

(24)

2)蘭德系數(shù)[25]

蘭德系數(shù)(Rand index，RI，本文用RI表示)用來衡量預(yù)測結(jié)果與真實(shí)結(jié)果成對(duì)的匹配程度。m表示預(yù)測結(jié)果與真實(shí)結(jié)果相同的對(duì)數(shù)，n表示樣本點(diǎn)的個(gè)數(shù)。RI越大，聚類效果越好，

(25)

(3)F1得分[26]

F1得分(F1-score,F1，本文用F1表示)計(jì)算了準(zhǔn)確率評(píng)分和召回率評(píng)分的調(diào)和平均值。F1越大，聚類效果越好，

(26)

表7和表8分別是通過Yager生成函數(shù)和Sugeno生成函數(shù)將實(shí)數(shù)集轉(zhuǎn)換成直覺模糊集后的聚類結(jié)果。直覺模糊集之間的距離分別采用(7)式的改進(jìn)直覺模糊蘭氏距離和(4)式的直覺模糊歐氏距離進(jìn)行計(jì)算，加粗顯示的數(shù)據(jù)表示在當(dāng)前數(shù)據(jù)集中相對(duì)最優(yōu)的指標(biāo)數(shù)據(jù)。由兩個(gè)距離度量計(jì)算得到的對(duì)比結(jié)果可知，利用改進(jìn)蘭氏距離得到的聚類結(jié)果比利用歐氏距離得到的聚類結(jié)果更好。這是由于蘭氏距離是一個(gè)無量綱量，克服了歐氏距離與各指標(biāo)量綱有關(guān)的缺點(diǎn)，且蘭氏距離對(duì)異常值不敏感，對(duì)高度偏移數(shù)據(jù)的聚類效果較好。

表7 利用Yager生成函數(shù)設(shè)置的直覺模糊集聚類結(jié)果

表8 利用Sugeno生成函數(shù)設(shè)置的直覺模糊集聚類結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出，對(duì)于真實(shí)數(shù)據(jù)集Seeds和Iris，利用蘭氏距離計(jì)算得到的聚類效果比利用歐氏距離得到的聚類結(jié)果更好，在3個(gè)評(píng)價(jià)指標(biāo)上提高了5%～13%。這是因?yàn)樵诶帽疚乃惴〞r(shí)加入了調(diào)節(jié)屬性權(quán)重的系數(shù)，在進(jìn)行距離計(jì)算時(shí)更偏重?cái)?shù)據(jù)本身混亂程度較小的屬性，充分考慮了決策者的直覺模糊信息，從而提高了群決策的合理性和有效性。對(duì)于合成數(shù)據(jù)集Aggregation和R15，利用本文提出的距離算子進(jìn)行聚類得到的結(jié)果在3個(gè)指標(biāo)上提高了1%～5%。這2個(gè)數(shù)據(jù)集樣本量相對(duì)較大，聚類效果較好，因此本文提出的算法更適用于大規(guī)模的直覺模糊集聚類。

此外，從形狀數(shù)據(jù)集Spiral的聚類結(jié)果可以看到，算法對(duì)于非凸數(shù)據(jù)的聚類效果并不理想。這是由于不同類數(shù)據(jù)點(diǎn)之間的距離都較近，而且在直覺模糊的情況下，數(shù)據(jù)對(duì)象在某一維度不斷靠近另一個(gè)簇的數(shù)據(jù)對(duì)象，導(dǎo)致二者距離過近，從而容易形成球形簇。下一步工作是改進(jìn)直覺模糊相似度的計(jì)算方式，提高算法對(duì)于不同形狀樣本的識(shí)別能力。

為驗(yàn)證本文算法的高效性，使用改進(jìn)直覺模糊蘭氏距離的密度峰值聚類算法和凝聚型層次聚類算法，利用5組數(shù)據(jù)對(duì)象在同樣的運(yùn)行環(huán)境中進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表 9。

表9 運(yùn)行時(shí)間對(duì)比

由仿真實(shí)驗(yàn)的運(yùn)行時(shí)間可知，本文提出的直覺模糊聚類算法在較小數(shù)據(jù)集上效率提升不明顯;但是在較大規(guī)模的數(shù)據(jù)集上,顯著降低了算法的運(yùn)行時(shí)間，提高了聚類效率。

4 結(jié)語

本文針對(duì)現(xiàn)有直覺模糊距離算子不滿足距離度量定義的問題，提出了改進(jìn)加權(quán)直覺模糊蘭氏距離算子，減小異常值對(duì)計(jì)算結(jié)果的影響。同時(shí),將新提出的算子和密度峰值聚類算法應(yīng)用到直覺模糊集的聚類中，降低了直覺模糊集聚類算法的復(fù)雜度。仿真實(shí)驗(yàn)結(jié)果表明，新算法提高了直覺模糊集的聚類精度，在數(shù)據(jù)量較大的直覺模糊集中顯著提高了算法的運(yùn)行效率，具有廣闊的應(yīng)用前景。