凝聚中心猶豫度恒定的模糊層次聚類算法

王志飛，陸億紅

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

1 引 言

隨著信息時(shí)代的發(fā)展，數(shù)據(jù)呈現(xiàn)爆炸式的增長(zhǎng)，數(shù)據(jù)的處理以及數(shù)據(jù)隱性知識(shí)的發(fā)掘再次成為了學(xué)術(shù)界研究的熱點(diǎn).聚類分析作為數(shù)據(jù)挖掘一個(gè)重要的組成部分，受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注[1].聚類分析應(yīng)用于解決現(xiàn)實(shí)生活中的確定性數(shù)據(jù)問(wèn)題，通過(guò)數(shù)據(jù)集包含的信息，可以將相似的數(shù)據(jù)點(diǎn)劃分到同一個(gè)簇中，將不相似的數(shù)據(jù)點(diǎn)劃分到不同的簇中.聚類分析其主要分為基于劃分的方法、基于層次的方法、基于密度的方法以及基于網(wǎng)格的方法.在每個(gè)領(lǐng)域都有各自的代表算法，如基于劃分的K-means[2]、基于層次的AGNES[3]、基于密度的DPC[4]、基于網(wǎng)格的STING[5].

以上介紹的傳統(tǒng)聚類算法主要是用于解決確定性數(shù)據(jù)集，但是隨著科技的進(jìn)步以及信息時(shí)代的不斷發(fā)展，研究人員在解決數(shù)據(jù)方面的方法也是越來(lái)越豐富，還可以通過(guò)運(yùn)用元組不確定性概率和屬性值不確定性概率來(lái)對(duì)確定性數(shù)據(jù)集進(jìn)行研究分析[6].從模糊集合[7]理論產(chǎn)生以來(lái)，數(shù)學(xué)中的模糊概念與計(jì)算機(jī)方面的結(jié)合為處理確定性數(shù)據(jù)提供了一個(gè)新的研究方向，因此，越來(lái)越多的國(guó)內(nèi)外學(xué)者將模糊集理論應(yīng)用于聚類分析領(lǐng)域[8].在這種大環(huán)境下，模糊聚類算法主要分為兩個(gè)研究方向，一種是應(yīng)用于傳統(tǒng)的確定性數(shù)據(jù)集，另外一種則是應(yīng)用于模糊數(shù)據(jù)集.將模糊聚類算法應(yīng)用于傳統(tǒng)確定性數(shù)據(jù)集時(shí)，其比傳統(tǒng)的聚類算法更加靈活，數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)不再確定性的屬于某一個(gè)簇，每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)簇之間都有一個(gè)隸屬度來(lái)表示數(shù)據(jù)點(diǎn)在某個(gè)簇的所屬程度，典型的代表算法就是模糊C均值算法(FCM clustering algorithm--FCM)[9]，自此，越來(lái)越多的學(xué)者開(kāi)始關(guān)注模糊聚類算法[10]和模糊分類算法.

在模糊集概念出現(xiàn)后，K.T.Atanassov提出了直覺(jué)模糊集合的概念(A-IFS)[11]，直覺(jué)模糊集是模糊集的延伸，被稱為模糊集的包絡(luò).A-IFS由隸屬度函數(shù)和非隸屬度函數(shù)組成，直覺(jué)模糊集的研究也層出不窮，如基于Jaccard索引為相似性度量的直覺(jué)模糊集在聚類中的應(yīng)用[12]和將多粒度粗糙集與粗糙直覺(jué)模糊集相結(jié)合的模型研究[13]等.

在模糊集概念提出以來(lái)，衍生的相關(guān)概念與應(yīng)用也層出不窮，其與聚類分析、決策與群決策[14]的結(jié)合領(lǐng)域更是成為了研究熱點(diǎn).在前面介紹的兩個(gè)研究領(lǐng)域都是針對(duì)確定性數(shù)據(jù)集，但隨著時(shí)代的發(fā)展，數(shù)據(jù)也不再僅限于確定型數(shù)據(jù)，如生產(chǎn)零件，對(duì)于零件的尺寸要求就不再是一個(gè)確定性的值，是一個(gè)區(qū)間，這種是數(shù)據(jù)集本身的不確定性，現(xiàn)實(shí)生活中也充斥個(gè)各種各樣的不確定數(shù)據(jù)集急需處理.

2010年，Torra提出了猶豫模糊集合[15]并進(jìn)行了深入研究[16]，通過(guò)猶豫模糊集合提高了猶豫問(wèn)題的解決能力,Xu等人對(duì)猶豫模糊集方面的公式進(jìn)行了定義和總結(jié)[17].對(duì)于猶豫模糊集合，其通過(guò)定義一組函數(shù)來(lái)為數(shù)據(jù)集的每個(gè)對(duì)象計(jì)算出一個(gè)隸屬度的集合.這種情況就是不同的評(píng)審專家對(duì)于數(shù)據(jù)對(duì)象x屬于集合A有自己的評(píng)判標(biāo)準(zhǔn)，其每個(gè)評(píng)價(jià)就是數(shù)據(jù)對(duì)象x屬于集合A的隸屬度，組合起來(lái)就是數(shù)據(jù)對(duì)象x屬于集合A的隸屬度集合，如{0.3,0.5,0.7}，這種情況在決策中十分常見(jiàn).因?yàn)楠q豫模糊集合更加的符合現(xiàn)實(shí)情況，所以在剛提出不久，就被眾多的學(xué)者應(yīng)用于聚類分析[18，19].

猶豫模糊集合是在原來(lái)的模糊集合中演變而來(lái)，與直覺(jué)模糊集密切相關(guān)，猶豫模糊集合本質(zhì)上是一種不確定數(shù)據(jù)的表示方法，這一概念模型很好的詮釋了現(xiàn)實(shí)生活中的遇事“猶豫不決”以及不同人對(duì)于事物具有不同的看法這一觀點(diǎn)，是近年來(lái)較為熱門且具有研究?jī)r(jià)值的一個(gè)領(lǐng)域.

相關(guān)文獻(xiàn)[14,15,18]提出了猶豫模糊數(shù)據(jù)集的聚類問(wèn)題.在建立猶豫模糊對(duì)象距離函數(shù)等數(shù)學(xué)模型基礎(chǔ)上，給出了猶豫模糊數(shù)據(jù)集的層次聚類算法，并用實(shí)例驗(yàn)證了算法理論的正確性和算法的可用性.對(duì)于該領(lǐng)域的實(shí)際應(yīng)用有很好的貢獻(xiàn)，但同樣存在一些不足之處，主要體現(xiàn)在以下兩個(gè)方面：

1)文獻(xiàn)[18]采用的是加權(quán)距離函數(shù)，但在具體應(yīng)用時(shí)，僅僅使用平均權(quán)值，或使用人為主觀給出的權(quán)值，沒(méi)有給出具體的權(quán)值計(jì)算公式，更沒(méi)有考慮模糊數(shù)據(jù)集本身這個(gè)客觀因素對(duì)距離權(quán)值的影響.

2)文獻(xiàn)[18]在計(jì)算簇中心時(shí)，其時(shí)間復(fù)雜度和空間復(fù)雜度較高，均為指數(shù)級(jí).因此，該算法在處理數(shù)據(jù)量龐大的數(shù)據(jù)集時(shí)效果不理想，甚至無(wú)法使用，對(duì)于現(xiàn)實(shí)生活中來(lái)說(shuō)，該算法是無(wú)效的.

針對(duì)上述兩個(gè)問(wèn)題，本文提出了新的權(quán)重計(jì)算公式和簇中心計(jì)算公式，新提出的權(quán)重公式可以根據(jù)數(shù)據(jù)集本身的信息計(jì)算出更加適合的權(quán)重，而且在數(shù)據(jù)集的屬性重要性分布趨于平均分布時(shí)，權(quán)重公式兼顧了原有的平均分配原則；當(dāng)簇中包含的對(duì)象逐漸增多時(shí)，新提出的簇中心計(jì)算公式的計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度不會(huì)呈指數(shù)級(jí)增長(zhǎng)，可以將算法的時(shí)間復(fù)雜度和空間復(fù)雜度從指數(shù)級(jí)降為線性級(jí)，對(duì)于現(xiàn)實(shí)應(yīng)用更有意義.

2 相關(guān)定義

本部分主要對(duì)本文算法以及本文研究領(lǐng)域方面所用到的一些概念進(jìn)行普及及定義.

2.1 猶豫模糊集合

在現(xiàn)實(shí)生活的問(wèn)題中，一個(gè)元素屬于一個(gè)集合只用一個(gè)隸屬度來(lái)表示其歸屬是很難解決的，而是可能由一組不同的隸屬值來(lái)進(jìn)行表示.在這種情況下，Torra等人在文章中介紹了猶豫模糊集合[hesitant fuzzy set-HFS][15]作為模糊集新擴(kuò)展的概念，HFS是由幾個(gè)取值范圍在[0,1]之間的隸屬度組成，其定義如下:

定義1[15,16].令X為一個(gè)固定集(fixed set)，則X上的一個(gè)猶豫模糊集合(HFS)是集合X經(jīng)過(guò)函數(shù)h轉(zhuǎn)變成一個(gè)元素取值為[0，1]之間的集合.

此外，對(duì)于給定的一組模糊集，可以根據(jù)隸屬度的并集來(lái)定義HFS，如下所示：

定義2[15,16].令M={μ1,μ2,…,μc}為一組包含c個(gè)隸屬度函數(shù)的集合，并且x∈X.則與M相關(guān)的猶豫模糊集合(HFS)-hM定義如下：

hM(x)=∪μ∈M{μ(x)}

(1)

在此基礎(chǔ)上，Xia和Xu[16]通過(guò)數(shù)學(xué)總結(jié)給出了猶豫模糊集合(HFS)的表達(dá)公式如下：

A={}

(2)

其中的hA(x)是一個(gè)取值在[0，1]之間的集合，來(lái)表示元素x∈X的可能性的隸屬度.為了方便起見(jiàn)，hA(x)被稱為一個(gè)猶豫模糊元素(HFE)，是猶豫模糊集合(HFS)的基本單位.

上述定義1只是給出了猶豫模糊集合的語(yǔ)言描述，并未給出形式化的定義以及數(shù)學(xué)表達(dá)；定義2在定義1的基礎(chǔ)上更進(jìn)一步，給出了其數(shù)學(xué)表達(dá)的定義，但是其并不便應(yīng)用于解決聚類問(wèn)題.有鑒于此，本文會(huì)對(duì)數(shù)學(xué)符號(hào)以及數(shù)學(xué)公式進(jìn)行統(tǒng)一的形式化描述，以便有效地解決聚類問(wèn)題.

2.2 算法相關(guān)定義

定義3.設(shè)隸屬度函數(shù)集合u={u1(x),u2(x),…,ur(x)}，若存在x使得ut(x)∈[0,1](t=1,2,…,r),則稱u為猶豫模糊集，稱|u|為猶豫模糊集u的猶豫度.

在進(jìn)行后續(xù)的運(yùn)算時(shí)，我們需要對(duì)猶豫模糊集的元素進(jìn)行排序，也需要在計(jì)算的時(shí)候?qū)⑴c運(yùn)算的猶豫模糊集的猶豫度進(jìn)行統(tǒng)一，即將猶豫度小的進(jìn)行擴(kuò)充，使其與猶豫度大的猶豫模糊集的維度保持一致.

對(duì)于將猶豫模糊集進(jìn)行擴(kuò)充時(shí)應(yīng)該填入什么值，其實(shí)沒(méi)有什么固定的標(biāo)準(zhǔn)，這主要取決于研究者的風(fēng)險(xiǎn)偏好以及積累的經(jīng)驗(yàn).添加不同的值可能會(huì)影響決策結(jié)果，但是這是合理的，因?yàn)樘砑拥闹邓鶎?dǎo)致的決策結(jié)果是我們希望看到的結(jié)果，符合決策者的預(yù)期，本文對(duì)猶豫模糊集擴(kuò)充值的方法與文獻(xiàn)[18]保持一致，即選用集合中最小值進(jìn)行填補(bǔ).

為了計(jì)算方便，本文后續(xù)所采用的猶豫模糊集都默認(rèn)為有序，即猶豫模糊集的元素已按非減方式排序.

定義4.任意兩個(gè)升序排列的猶豫模糊集u={u1(x),u2(x),…,uw(x)}，v={v1(x),v2(x),…,vt(x)},兩個(gè)猶豫模糊集的猶豫度分別為|u|=w、|v|=t,若w

對(duì)于任意2個(gè)猶豫度相同的猶豫模糊集x，y，可定義如下運(yùn)算.

定義5.任意給定兩個(gè)猶豫模糊集x，y，則：

1)補(bǔ)集：xc=∪γ∈x{1-γ}

2)并集：x∪y=∪γ1∈x,γ2∈y{γ1,γ2}

3)交集：x∩y=∪{min(γyp,γxp)}xp∈x,x,yp∈y,

|x|=|y|=σ,p=1,2,…,σ

4)數(shù)乘：λx=∪γ∈x{1-(1-γ)λ}

5)指數(shù)：xλ=∪γ∈x{γλ}

補(bǔ)集的計(jì)算是猶豫模糊集中每一個(gè)隸屬度與1的差值取正后得到，最終得到的補(bǔ)集的猶豫度與原猶豫模糊集一致.并集則是將兩個(gè)猶豫模糊集合并在一起，合并后的猶豫度是兩個(gè)猶豫模糊集的猶豫度之和.交集的計(jì)算需要兩個(gè)猶豫模糊集合保持相同的猶豫度并有序，猶豫度不同的按照定義4進(jìn)行擴(kuò)充，計(jì)算后得到的猶豫模糊集的猶豫度與計(jì)算前兩個(gè)猶豫模糊集較大的猶豫度一致.數(shù)乘以及指數(shù)運(yùn)算，其計(jì)算后得到的猶豫模糊集的猶豫度與之前的猶豫度一致.

定義6.若d維向量X=(x1,x2,…,xd)的每個(gè)分量都是猶豫模糊集，則稱X為d維猶豫模糊對(duì)象，簡(jiǎn)稱猶豫模糊對(duì)象.

定義7.若集合S=(X1,X2,…,Xn)中每個(gè)元素X=(xi1,xi2,…,xid)都是d維猶豫模糊對(duì)象，則稱S為猶豫模糊對(duì)象集.

任意給定兩個(gè)猶豫度相同的猶豫模糊對(duì)象X、Y，所以基于傳統(tǒng)的漢明距離和歐式距離，可以得到猶豫模糊加權(quán)漢明距離和猶豫模糊加權(quán)歐式距離[18]的公式如下：

猶豫模糊加權(quán)漢明距離：

(3)

猶豫模糊加權(quán)歐式距離：

(4)

對(duì)于3個(gè)猶豫度相同的猶豫模糊對(duì)象X、Y、Z，它們之間的距離為d(X,Y)，其具有以下幾個(gè)特性：

1)d(X,Y)∈[0,1]

2)d(X,Y)=0當(dāng)且僅當(dāng)X=Y

3)對(duì)稱性：d(X,Y)=d(Y,X)

4)三角不等式：d(X,Y)≤d(Y,Z)+d(X,Z)

有猶豫模糊集x1={x11,x12},x2={x21,x22},y1={y11,y12},y2={y21,y22},z1={z11,z12},z2={z21,z22}包含兩個(gè)隸屬值的猶豫模糊集看作二維平面的點(diǎn)，則可得到：

d(x1,y1)≤d(x1,z1)+d(y1,z1)；d(x2,y2)≤d(x2,z2)+d(y2,z2)

?d(x1,y1)+d(x2,y2)≤d(x1,z1)+d(y1,z1)+d(x2,z2)+d(y2,z2)

其中x={x11,x12,x21,x22},y={y11,y12,y21,y22},z={z11,z12,z21,z22}.上述x1,x2兩個(gè)集合進(jìn)行合并后得到x.?2d(x,y)≤2(d(x,z)+d(y,z))?d(x,y)≤(d(x,z)+d(y,z))

x1，x2等之間的距離具有三角不等式，可得到猶豫模糊集之間的距離具有三角不等式性質(zhì).猶豫模糊對(duì)象之間的距離是每個(gè)分量上猶豫模糊集之間的距離的加權(quán)和，且距離都為正數(shù)，則加法不等號(hào)方向不變，可得到猶豫模糊對(duì)象之間的距離也具有三角不等式性質(zhì).

2.3 猶豫模糊層次聚類算法

層次聚類算法通過(guò)將數(shù)據(jù)分組到一個(gè)聚類樹(shù)中來(lái)進(jìn)行聚類工作.層次聚類算法可以進(jìn)一步分為凝聚型和分裂型，本文采用的是層次凝聚算法來(lái)進(jìn)行聚類分析.該算法則是將層次聚類算法運(yùn)用于猶豫模糊對(duì)象集上，來(lái)進(jìn)行聚類分析.

算法對(duì)于簇中心的更新以及和一些運(yùn)算法則給出了一些相應(yīng)的定義.

定義9[15].令E={x1,x2,…,xn″}，包含n″個(gè)猶豫模糊集，θ是E上的一個(gè)函數(shù)，并且θ:[0,1]N→[0,1]，可得到：

θE=∪γ∈{x1×x2×…×xn″}{θ(γ)}

(5)

Xia和Xu[16]在上述定義情況下給出了兩個(gè)猶豫度相同的猶豫模糊對(duì)象X={x1,x2,…,xd}和Y={y1,y2,…,yd}之間的一些運(yùn)算.

1)“加”：X⊕Y={x1⊕y1,x2⊕y2,…,xd⊕yd}

xj⊕yj=∪γ1∈xj,γ2∈yj{γ1+γ2-γ1γ2}

(j=1,2,…,d)

2)“乘”：X⊕Y={x1?y1,x2?y2,…,xd?yd}

xj?yj=∪γ1∈xj,γ2∈yj{γ1γ2}(j=1,2,…,d)

3)數(shù)乘：λX={λx1,λx2,…,λxd}

對(duì)象的數(shù)乘是每個(gè)分量的數(shù)乘

4)指數(shù)：Xλ={x1λ,x2λ,…,xdλ}

對(duì)象的指數(shù)運(yùn)算是每個(gè)分量的指數(shù)運(yùn)算

猶豫模糊對(duì)象的數(shù)乘與指數(shù)運(yùn)算是每個(gè)分量上的猶豫模糊集進(jìn)行計(jì)算，并不涉及跨分量，其計(jì)算規(guī)則與猶豫模糊集一致.猶豫模糊對(duì)象的“和”、“乘”運(yùn)算也是每個(gè)分量上的猶豫模糊集進(jìn)行計(jì)算，并不涉及跨分量，但是在運(yùn)算過(guò)程中，對(duì)于兩個(gè)猶豫模糊集，計(jì)算和、乘時(shí)，需要取遍兩個(gè)集合中的每個(gè)元素進(jìn)行計(jì)算，涉及兩個(gè)集合的全排列問(wèn)題，如兩個(gè)集合的猶豫度都為3，則進(jìn)行和、乘運(yùn)算后，得到的集合的猶豫度為3*3=9，故計(jì)算后的猶豫模糊集的猶豫度是兩個(gè)猶豫模糊集猶豫度的乘積.

根據(jù)上述的法則運(yùn)算可以得到簇中心的計(jì)算公式.

定義10[18].令Xi={xi1,xi2,…,xid|xij∈Xi}(i=1,2,…,n′;j=1,2,…,d)是一組猶豫模糊對(duì)象，則它們的簇{X1,X2,…,Xn′}的中心可以用“平均值”表示：

(6)

根據(jù)運(yùn)算法則將公式進(jìn)行轉(zhuǎn)換可以得到如下公式：

(7)

原有的猶豫模糊層次聚類算法(Hesitant fuzzy hierarchical clustering algorithm)在本文中稱為算法1，為描述方便，將該算法簡(jiǎn)稱為HFHC算法，本文后續(xù)所有描述均由HFHC算法指代猶豫模糊層次聚類算法.

算法1.HFHC算法

輸入：猶豫模糊對(duì)象集S={X1,X2,…,Xn}，輸入所需簇的個(gè)數(shù)q

輸出：含q個(gè)簇的一個(gè)聚類C={C1,C2,…,Cq}

1.將S的每個(gè)對(duì)象當(dāng)成一個(gè)初始簇，形成初始聚類C

2.REPEAT

3.根據(jù)公式(3)計(jì)算每個(gè)簇簇中心之間的距離取簇中心之間距離最小的兩個(gè)簇進(jìn)行合并，并根據(jù)公式(7)計(jì)算合并后的簇的聚類中心

4.UNTIL簇的數(shù)目等于q

5.輸出聚類C={C1,C2,…,Cq}

3 FHCA算法

猶豫模糊層次聚類算法是聚類算法在猶豫模糊集上的探索性的應(yīng)用，其時(shí)間復(fù)雜度與空間復(fù)雜度都是指數(shù)級(jí)的，在實(shí)際的大數(shù)據(jù)聚類應(yīng)用中可能是無(wú)效的，故不能在現(xiàn)實(shí)生活中普及性的來(lái)解決聚類分析問(wèn)題，本文提出的凝聚中心猶豫度恒定的模糊層次聚類算法(Fuzzy hierarchical clustering algorithm with constant hesitation of agglomeration center,簡(jiǎn)稱FHCA)，降低其龐大的時(shí)間和空間消耗，使得層次聚類算法可以有效的應(yīng)用于聚類分析領(lǐng)域.

3.1 公式定義

定義11.對(duì)于數(shù)據(jù)集S中的猶豫模糊對(duì)象之間的加權(quán)距離，其權(quán)重公式如下：

(8)

定義12.給定兩個(gè)猶豫模糊集x，y，則其之間的距離為：

(9)

計(jì)算兩個(gè)猶豫模糊對(duì)象距離時(shí)采用猶豫模糊加權(quán)漢明距離:

(10)

對(duì)于簇中心的計(jì)算，HFHC算法的公式最終得到的簇中心，因?yàn)橛?jì)算的時(shí)間復(fù)雜度以及空間復(fù)雜度都是呈現(xiàn)指數(shù)級(jí)的增長(zhǎng)，于現(xiàn)實(shí)生活中的聚類問(wèn)題的應(yīng)用是無(wú)效的.在此基礎(chǔ)上，對(duì)于原文的公式進(jìn)行分析，發(fā)現(xiàn)公式(6)中是猶豫模糊集合的一種“平均值”的計(jì)算方法，其在每一個(gè)猶豫模糊分量上求取其“平均值”，如若計(jì)算X1,X2,…,X8這8個(gè)猶豫模糊對(duì)象合并后在分量x1上的結(jié)果，則計(jì)算出來(lái)的結(jié)果在必在[min(∪γ∈xi1γ),max(∪γ∈xi1γ)](i=1,2,…,8)之間.由于其計(jì)算出來(lái)的猶豫模糊集合中的元素個(gè)數(shù)呈現(xiàn)指數(shù)級(jí)增長(zhǎng)，所以當(dāng)i=n，且n足夠大時(shí)，其猶豫模糊集合中的元素值會(huì)充滿區(qū)間[min(∪γ∈xijγ),max(∪γ∈xijγ)],則選擇最小值，最大值以及平均值保證了原來(lái)猶豫模糊集的3個(gè)特性.考慮到實(shí)例的猶豫模糊集的猶豫度較小，故將其簇中心進(jìn)行壓縮，使其猶豫度恒定不變，以此來(lái)有效的解決聚類問(wèn)題.

定義13.令E={x1,x2,…,xn″}，包含n″個(gè)猶豫模糊集，θ是E上的一個(gè)函數(shù)，可得到：

θE=(minγ,θ(γ),maxγ)γ∈{x1×x2×…×xn″}

(11)

給出兩個(gè)猶豫度相同的猶豫模糊對(duì)象X和Y，根據(jù)猶豫模糊集之間的運(yùn)算法則，可以定義兩個(gè)猶豫模糊對(duì)象之間的運(yùn)算規(guī)則，其之間的運(yùn)算如下所示：

3)數(shù)乘：λX={λx1,λx2,…,λxd}

對(duì)象的數(shù)乘是每個(gè)分量的數(shù)乘

4)指數(shù)：Xλ={x1λ,x2λ,…,xdλ}

對(duì)象的指數(shù)運(yùn)算是每個(gè)分量的指數(shù)運(yùn)算

并集、指數(shù)和數(shù)乘運(yùn)算參考猶豫模糊集，此處并不過(guò)多解釋.對(duì)于本文的定義和運(yùn)算，兩個(gè)猶豫模糊集計(jì)算后得到的猶豫模糊集的猶豫度為3，不會(huì)隨著原有的猶豫度而變化.

根據(jù)上述運(yùn)算規(guī)則，得到下面簇中心的計(jì)算公式.

定義14.若現(xiàn)有兩個(gè)將要進(jìn)行合并的簇Cr={Xr1,Xr2,…,Xre}、Cl={Xl1,Xl2,…,Xlg}，Rc={r1,r2,…,re,l1,l2,…,lg}其中簇Cr包含e個(gè)猶豫模糊對(duì)象，簇Cl包含g個(gè)猶豫模糊對(duì)象，則合并后的簇中心的公式如下：

(12)

其中xj代表若干個(gè)數(shù)據(jù)點(diǎn)聚集成一個(gè)簇后其第j個(gè)分量，p=1,2,…,mij.

根據(jù)前面的定義以及運(yùn)算法則，可以得到如下結(jié)論.

定理 1.給定兩個(gè)猶豫模糊集x，y；3個(gè)猶豫模糊對(duì)象X,Y,Z則有：

1)(xc)λ=(λx)c

2)λxc=(xλ)c

證明：為了敘述方便，在此只證明1),其他結(jié)論可類似證明得到.

xcλ=∪γ∈x{1-γ}λ=∪γ∈x{(1-γ)λ} (λx)c=∪γ∈x{1-(1-γ)λ}c=∪γ∈x{1-(1-(1-γ)λ)}=∪γ∈x{(1-γ)λ} 左邊=右邊，則xcλ=(λx)c

3.2 FHCA算法流程

將本文所提出的權(quán)重公式和簇中心更新公式應(yīng)用于層次聚類算法中解決猶豫模糊對(duì)象集問(wèn)題得到FHCA算法.

算法2.FHCA算法

輸入：猶豫模糊對(duì)象集S={X1,X2,…,Xn}，輸入所需簇的個(gè)數(shù)q

輸出：含q個(gè)簇的一個(gè)聚類C={C1,C2,…,Cq}

1.將S的每個(gè)對(duì)象當(dāng)成一個(gè)初始簇，形成初始聚類C

2.REPEAT

3.根據(jù)公式(10)計(jì)算每個(gè)簇簇中心之間的距離

4.取簇中心之間距離最小的兩個(gè)簇進(jìn)行合并，并根據(jù)公式(12)計(jì)算合并后的簇中心

5.UNTIL簇的數(shù)目等于q

6.輸出聚類C={C1,C2,…,Cq}

4 實(shí)例分析

下面將用兩個(gè)例子來(lái)對(duì)上述公式進(jìn)行驗(yàn)證，例子由8個(gè)猶豫模糊對(duì)象組成，其中4個(gè)猶豫模糊對(duì)象組成一個(gè)簇，另外4個(gè)組成另外一個(gè)簇，屬性維度為3，在簇中4個(gè)猶豫模糊對(duì)象的某一個(gè)屬性維度上的猶豫模糊集合的平均值相等，兩個(gè)簇在這一屬性維度上的平均值相差較大，以此來(lái)明確區(qū)分這兩個(gè)簇，具體數(shù)據(jù)如表1所示.

表1 猶豫模糊對(duì)象集Table 1 Hesitation blurry object sets

進(jìn)行第1次微簇合并時(shí)，每一個(gè)猶豫模糊對(duì)象就是一個(gè)簇，故簇中心就是猶豫模糊對(duì)象本身.本文采用猶豫模糊加權(quán)漢明距離公式來(lái)計(jì)算距離，則根據(jù)公式(8)，計(jì)算猶豫模糊分量所對(duì)應(yīng)的權(quán)重，得到ω1=0.2900，ω2=0.3318，ω3=0.3782.

根據(jù)距離式(9)、式(10)以及計(jì)算出來(lái)的權(quán)重，可以得到各簇中心之間的加權(quán)距離矩陣dFHCA，其中距離矩陣dFHCA中的行從左到右依次為X1,X2,…,X8，列從上到下依次為X1,X2,…,X8，由猶豫模糊對(duì)象之間的距離性質(zhì)3)對(duì)稱性可以得到矩陣沿左上至右下對(duì)角線對(duì)稱，是一個(gè)特殊的矩陣-對(duì)稱矩陣，故距離矩陣可寫(xiě)成上三角矩陣.如第3行第2列的值代表猶豫模糊對(duì)象X3和X2之間的距離為0.0697，即得到d(X2,X3)=0.0697.由對(duì)稱性和猶豫模糊集之間的距離性質(zhì)2)可以得到對(duì)角線元素全部為零.

如距離矩陣dFHCA所示，距離最近的兩個(gè)簇是{X7}和{X8}，所以選擇這兩個(gè)簇進(jìn)行合并，得到新的簇{X7,X8}，根據(jù)公式(12)計(jì)算新簇的簇中心，得到c{X7,X8}=f{X7,X8}={{0.57,0.75,0.95},{0.75,0.8,0.86},{0.6,0.7,0.8}},其余的簇簇中心不變則得到更新后的簇的簇中心數(shù)據(jù)表如表2所示.

后續(xù)計(jì)算過(guò)程此處略過(guò)，當(dāng)合并為一個(gè)簇時(shí)，算法終止.

表2 合并后數(shù)據(jù)對(duì)象表Table 2 Merged data objects

在實(shí)例上用HFHC算法進(jìn)行計(jì)算，得到相應(yīng)的結(jié)果，與FHCA算法的計(jì)算結(jié)果對(duì)比如表3所示.

從表3可以看出，本文方法與原文的方法最大的區(qū)別在形成4個(gè)簇以及3個(gè)簇的時(shí)候，我們可以先看數(shù)據(jù)的分布，然后再來(lái)看兩種方法形成的簇的優(yōu)劣.表1所示的猶豫模糊對(duì)象集，將其每個(gè)猶豫模糊元素中的值取平均值，結(jié)果如表4所示.

從表4可以看出，猶豫模糊對(duì)象X1,X2，X3，X4在屬性X3上的屬性值相等，猶豫模糊對(duì)象X5,X6，X7，X8在屬性X3上屬性值相等，故其在X3屬性上可不在圖形展示上展現(xiàn)出來(lái)，即可用二維坐標(biāo)系展現(xiàn)出數(shù)據(jù)點(diǎn)的大致分布圖，分布圖如圖1所示.

表3 HFHC和FHCA聚類結(jié)果對(duì)比表Table 3 Comparison results of HFHC and FHCA

表4 對(duì)象均值表Table 4 Mean values of objects

圖1 對(duì)象均值分布圖Fig.1 Distribution of the object mean values

從圖1可以看出，當(dāng)簇?cái)?shù)為4時(shí)，形成的簇為以下4種：

1){{X1,X2},{X3,X4},{X5,X6},{X7,X8}}

2){{X1,X3},{X2,X4},{X5,X6},{X7,X8}}

3){{X1,X2},{X3,X4},{X5,X7},{X6,X8}}

4){{X1,X3},{X2,X4},{X5,X7},{X6,X8}}

較為合理，本文形成的簇的情況為第2)種，比原文的簇的形成更加合理.

當(dāng)簇?cái)?shù)為3時(shí)，形成的簇為：

1){{X1,X2,X3,X4},{X5,X6},{X7,X8}}

2){{X1,X3},{X2,X4},{X5,X6,X7,X8}}

3){{X1,X2,X3,X4},{X5,X7},{X6,X8}}

4){{X1,X2},{X3,X4},{X5,X6,X7,X8}}

較為合理，本文形成的簇的情況為第1)種，也比原文的簇的形成更加合理，通過(guò)對(duì)比發(fā)現(xiàn)，F(xiàn)HCA算法優(yōu)勢(shì)明顯.

另外采用HFHC算法的例子進(jìn)行計(jì)算，最終結(jié)果如表5所示.

表5 HFHC和FHCA聚類結(jié)果對(duì)比表Table 5 Comparison results of HFHC and FHCA

從表5中可以看到，本文方法與原文方法的計(jì)算結(jié)果一致.總體來(lái)說(shuō)，兩個(gè)例子中，F(xiàn)HCA算法效果有一個(gè)表現(xiàn)與原文一致，另一個(gè)甚至優(yōu)于原文的方法，在此基礎(chǔ)上還降低了時(shí)間復(fù)雜度與空間復(fù)雜度，此部分后續(xù)會(huì)進(jìn)行詳細(xì)的分析.

5 復(fù)雜度分析

本部分將對(duì)新算法的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行相應(yīng)的分析，同時(shí)也會(huì)對(duì)原算法進(jìn)行分析，兩者進(jìn)行對(duì)應(yīng)的比較分析，來(lái)證實(shí)新算法的實(shí)用性.

5.1 時(shí)間復(fù)雜度分析

根據(jù)章節(jié)相關(guān)算法分析部分，可以得到相對(duì)應(yīng)的時(shí)間復(fù)雜度的分析，即進(jìn)行HFHC算法時(shí)，若最終聚集成一個(gè)簇時(shí)，則簇中包含n個(gè)猶豫模糊對(duì)象，則可以得到兩個(gè)算法的時(shí)間復(fù)雜度對(duì)比如表6所示.

表6 時(shí)間復(fù)雜度對(duì)比表Table 6 Time complexity of various methods

5.2 空間復(fù)雜度

從時(shí)間復(fù)雜度方面的計(jì)算可知，當(dāng)設(shè)置的算法停止條件為凝成一個(gè)簇時(shí)，即n個(gè)猶豫模糊對(duì)象在一個(gè)簇，則對(duì)其進(jìn)行相應(yīng)的分析.

FHCA算法因采用簇中心猶豫度恒定的方法，用最大值、最小值以及平均值來(lái)進(jìn)行簇中心的計(jì)算，從計(jì)算公式也可以得到相應(yīng)的結(jié)論，最終的空間復(fù)雜度為O(1)，得到兩個(gè)算法對(duì)比結(jié)果如表7所示.

表7 空間復(fù)雜度對(duì)比表Table 7 Space complexity of various methods

從上述兩方面的分析可以看出，在兩個(gè)例子的計(jì)算中，原文的例子，本文方法與原文方法效果相同，但是時(shí)間和空間開(kāi)銷都相應(yīng)的降低了；而另外一個(gè)例子，本文方法在降低時(shí)間和空間消耗時(shí)，也獲得了優(yōu)于原文的實(shí)驗(yàn)結(jié)果.

當(dāng)所處理的數(shù)據(jù)集中的數(shù)據(jù)對(duì)象規(guī)模巨大的時(shí)候，顯然原文這種高時(shí)間和空間成本是難以承受的，而本文則將時(shí)間和空間的復(fù)雜度從原來(lái)的指數(shù)級(jí)降低到現(xiàn)在的多項(xiàng)式級(jí)，而且實(shí)驗(yàn)效果并沒(méi)有變差，顯然是更加適用于現(xiàn)實(shí)應(yīng)用場(chǎng)景.

6 總 結(jié)

本文提出的基于數(shù)據(jù)集本身所含信息的權(quán)重公式以及簇中心的計(jì)算公式，通過(guò)理論分析以及實(shí)例證明，在將時(shí)間復(fù)雜度以及空間復(fù)雜度從指數(shù)級(jí)降至線性級(jí)的情況下，還可以得到理想的聚類效果，聚類精度有所改善，相比較而言更加的適用于現(xiàn)實(shí)生活，在沒(méi)有巨大的開(kāi)銷就可以解決現(xiàn)實(shí)生活中的“猶豫不決”等數(shù)據(jù)集問(wèn)題，提供決策支持.因沒(méi)有相關(guān)數(shù)據(jù)集，同時(shí)該領(lǐng)域研究用示例來(lái)演示，本文同樣用示例進(jìn)行了模擬展示，下一步的研究方向則是在數(shù)據(jù)集上的效果以及在聚類分析領(lǐng)域的拓展，例如在密度聚類等算法上的實(shí)際應(yīng)用問(wèn)題.