第8章模糊模式識(shí)別8.1模糊集合8.2模糊模式識(shí)別的基本方法8.3模糊聚類分析8.4聚類有效性評(píng)價(jià)

1965年，Zadeh提出了模糊集合概念，創(chuàng)建了一門新的學(xué)科——模糊數(shù)學(xué)。模糊集合是對(duì)一類客觀事物和性質(zhì)的更合理的抽象和描述，是對(duì)傳統(tǒng)集合的一種推廣。

在主客觀世界普遍存在的不確定性中，隨機(jī)性和模糊性是最重要的兩種形式。隨機(jī)性是由于條件不充分而導(dǎo)致的結(jié)果的不確定性，它反映了因果律的破缺。模糊性是指事物的性態(tài)或類屬的不分明而引起的判斷上的不確定性，其根源是事物之間存在過渡性的事物或狀態(tài)，模糊性所反映的是排中律的破缺。隨機(jī)性的事物應(yīng)該采用概率論加以處理和分析，模糊性的事物則需要模糊數(shù)學(xué)來描述和研究。因此，人們普遍認(rèn)為模糊數(shù)學(xué)是解決很多人工智能問題，尤其是常識(shí)性問題的最合適的數(shù)學(xué)工具。

在模式識(shí)別領(lǐng)域，人們利用模糊技術(shù)對(duì)傳統(tǒng)的一些模式識(shí)別方法進(jìn)行了改進(jìn)，這些研究逐漸形成了模糊模式識(shí)別這一新的學(xué)科分支。模糊模式識(shí)別利用模糊數(shù)學(xué)的理論和方法解決模式識(shí)別問題，其基本思想是將各個(gè)模式類看成模糊集合，將模式的屬性轉(zhuǎn)化為對(duì)于模糊集合的隸屬程度，然后利用隸屬函數(shù)、模糊推理和模糊關(guān)系進(jìn)行分類識(shí)別。

本章介紹模糊集合的相關(guān)知識(shí)，主要討論模糊模式識(shí)別的基本方法，并重點(diǎn)討論模糊聚類分析法。

8.1模糊集合

8.1.1模糊集合的定義及表示

集合是數(shù)學(xué)的一個(gè)基本概念，集合論是近代數(shù)學(xué)的基礎(chǔ)理論，是研究現(xiàn)代科技最重要的理論工具之一。在普通集合論中，一個(gè)元素要么屬于某一集合，要么不屬于該集合，二者必居其一，且二者僅居其一。模糊集合是普通集合的推廣，其中，每個(gè)元素都是以一定的程度(隸屬度)屬于某個(gè)模糊集合，也可以屬于多個(gè)模糊集合。模糊集合主要用來描述不精確的、模糊的概念。下面首先給出普通集合的定義。定義8.1給定論域U及某一性質(zhì)P，U中具有性質(zhì)P的元素的全體稱為一個(gè)集合，記為A={x|P(x)}，其中，

P(x)表示元素x具有性質(zhì)P。

如果x屬于A，記x∈A，否則記x

A。一個(gè)集合可以用特征函數(shù)來表示。令A(yù)是論域U上的一個(gè)集合，它由映射CA：U→{0，1}]唯一確定。對(duì)x∈U，令特征函數(shù)

χA(x)在x0處的取值χA(x0)稱為x0∈U對(duì)A的隸屬度。(8-1)集合A可由它的特征函數(shù)χA(x)唯一確定，A是由隸屬度等于1的元素組成的。顯然，普通集合中元素的歸屬是明確的。將普通集合中特征函數(shù)的取值范圍由{0，1}推廣到［0，1］，就得到模糊集合的定義。下面給出模糊集合的定義。

定義8.2對(duì)于論域U上的集合，對(duì)任意x∈U都指定了一個(gè)數(shù)用于表示x屬于的程度，即有映射，利用所確定的集合稱為U上的一個(gè)模糊集合，稱為模糊集合的隸屬度函數(shù)。對(duì)于某一x∈U，表示元素x對(duì)的隸屬度。

的值越接近1，表示x屬于的程度越高；的值越接近0，表示x屬于的程度越低。模糊集合的定義表明，模糊集合由其隸屬度函數(shù)唯一確定。模糊集合是普通集合的一般化，普通集合是特殊的模糊集合。

一個(gè)模糊集合可表示為

如果U是可列有限集合，則可表示為(8-2)(8-3)如果U為無限不可列集合，則可表示為

其中，“”與“”并不是求和與積分，它們表示模糊集合中各個(gè)元素與隸屬度函數(shù)對(duì)應(yīng)關(guān)系的一個(gè)總括。(8-4)8.1.2模糊集合的運(yùn)算

1.基本運(yùn)算

具有共同論域的模糊集合可以定義相等、包含以及集合運(yùn)算，這些操作是通過對(duì)隸屬度作相應(yīng)運(yùn)算來實(shí)現(xiàn)的。

(1)相等：設(shè)和為論域U上的兩個(gè)模糊集合，當(dāng)且僅當(dāng)，時(shí)，稱和相等，即

(8-5)

(2)包含：設(shè)和為論域U上的兩個(gè)模糊集合，若

，，則稱包含或包含于，即

(3)空集：設(shè)為論域U上的模糊集合，若，

，則稱為空集，記為，即(8-6)(8-7)

(4)補(bǔ)集：設(shè)和為論域U上的兩個(gè)模糊集合，若，

則稱為的補(bǔ)集。

(5)全集：設(shè)為論域U上的模糊集合，若，，則稱為全集，記為Ω，即(8-8)(8-9)

(6)并集：設(shè)和和為論域U上的模糊集合，若，，則稱為與和的并集，即

(7)交集：設(shè)、和為論域U上的模糊集合，若，，則稱為

與的交集，即(8-10)(8-11)

2.模糊集合運(yùn)算的基本性質(zhì)

(1)冪等律；

(2)交換律；

(3)結(jié)合律；

(8-14)

(4)吸收律(8-12)(8-13)(8-15)

(5)分配律：

(6)復(fù)原律；

(7)對(duì)偶律；

(8)定常律；(8-16)(8-17)(8-18)(8-19)與普通集合不同，在模糊集合上排中律一般不成立，即(8-20)

8.2模糊模式識(shí)別的基本方法

模糊模式識(shí)別方法就是在模式識(shí)別中引入模糊數(shù)學(xué)的概念、原理和方法，用模糊技術(shù)對(duì)客觀事物進(jìn)行更為有效的分類與識(shí)別，與統(tǒng)計(jì)模式識(shí)別方法存在一定程度上的相似之處。該類方法首先將類別和待識(shí)別對(duì)象看成模糊集合及其元素，然后將普通意義上的特征值變?yōu)槟：卣鳎⒛：系碾`屬度函數(shù)，或建立元素之間的模糊相似關(guān)系并確定這個(gè)關(guān)系的隸屬函數(shù)，最后運(yùn)用模糊數(shù)學(xué)的原理和方法進(jìn)行分類識(shí)別。本節(jié)首先介紹模糊模式識(shí)別的基本過程，然后給出常用的隸屬度函數(shù)，最后介紹模糊模式識(shí)別的兩個(gè)最重要的判決原則：最大隸屬度原則和擇近原則。

8.2.1模糊模式識(shí)別的基本過程

模糊模式識(shí)別包括如下的基本過程。

1.特征的變換

在模糊模式識(shí)別中，特征的變換是指根據(jù)一定的模糊化規(guī)則把普通意義下的一個(gè)或幾個(gè)特征變量變成多個(gè)特征變量，并且使得每個(gè)特征值是原始特征的某一局部更本質(zhì)特征的隸屬度，利用這些特征來表示原來的對(duì)象，這個(gè)工作又稱為特征的模糊化。其中，模糊化規(guī)則通常是根據(jù)具體應(yīng)用領(lǐng)域的專門知識(shí)、人為確定或通過試算確定的。這些新的特征能更好地反映對(duì)象的本質(zhì)，為后續(xù)分類器的設(shè)計(jì)提供了很大的方便。

舉例來說，在統(tǒng)計(jì)模式識(shí)別中，人的身高是一個(gè)數(shù)字化的特征。在模糊模式識(shí)別中，我們可以把人的身高特征分為“偏矮”、“中等”和“偏高”三個(gè)模糊特征。每個(gè)模糊特征是一個(gè)連續(xù)變量，分別表示身高屬于偏矮、中等和偏高的程度，而不是身高的具體數(shù)值。

2.建立隸屬度函數(shù)

為了能運(yùn)用模糊數(shù)學(xué)進(jìn)行分類識(shí)別，應(yīng)根據(jù)具體情況建立模糊集的隸屬度函數(shù)。下面介紹建立隸屬度函數(shù)的主流方法。

(1)專家確定法。

專家確定法是根據(jù)專家的經(jīng)驗(yàn)和認(rèn)識(shí)，給出對(duì)象隸屬度的具體數(shù)值。最常用的專家確定法是德爾菲法。

(2)模糊統(tǒng)計(jì)法。

模糊統(tǒng)計(jì)法以調(diào)查統(tǒng)計(jì)結(jié)果得出的經(jīng)驗(yàn)曲線作為隸屬度函數(shù)，一般采用集值統(tǒng)計(jì)的方法來確定隸屬度函數(shù)。

(3)二元對(duì)比排序法。

在很多情況下，要直接給出論域上一個(gè)模糊集的隸屬度函數(shù)是比較困難的，但是比較論域中兩個(gè)元素的隸屬度大小往往比較容易，此時(shí)，可以先排序再用一些數(shù)學(xué)方法處理得到隸屬度函數(shù)。

(4)綜合加權(quán)法。

在實(shí)際問題中，有些模糊集是由若干因素相互作用而成的，可以先求出各個(gè)因素的模糊集的隸屬度函數(shù)，再用綜合加權(quán)的方法復(fù)合出這個(gè)模糊集的隸屬度函數(shù)。

(5)函數(shù)近似法。

最簡(jiǎn)單的確定隸屬度函數(shù)的方法是采用一些常見的帶參數(shù)的函數(shù)來近似表示，所選的函數(shù)應(yīng)盡量符合模糊變量的本質(zhì)特征，函數(shù)的參數(shù)一般通過實(shí)驗(yàn)來確定。

我們?cè)?.2.2節(jié)將詳細(xì)介紹常用的隸屬度函數(shù)。

3.建立模糊相似關(guān)系

對(duì)于論域U={x1，x2，…，xn}，根據(jù)實(shí)際情況，可以運(yùn)用集值統(tǒng)計(jì)法、模糊集的貼近度法或者第6章介紹的相似性測(cè)度等建立模糊相似矩陣，其中，矩陣元素表示對(duì)象xi和xj相似關(guān)系的隸屬度。

4.模糊模式識(shí)別

根據(jù)對(duì)象的特點(diǎn)，采用適當(dāng)?shù)哪：Ｊ阶R(shí)別方法進(jìn)行識(shí)別。模糊模式識(shí)別方法大致可以分為兩種，即根據(jù)最大隸屬度原則進(jìn)行識(shí)別的直接法和根據(jù)擇近原則進(jìn)行歸類的間接法。

5.模糊結(jié)果的處理

與統(tǒng)計(jì)模式識(shí)別不同，模糊模式識(shí)別獲得的分類結(jié)果不表示一個(gè)樣本明確地屬于某一類或不屬于某一類，而是以一定的隸屬度屬于多個(gè)類，這樣的結(jié)果可以反映出分類過程中的不確定性，有利于用戶根據(jù)結(jié)果進(jìn)行決策。如果分類識(shí)別系統(tǒng)是多級(jí)的，則這樣的結(jié)果有益于下一級(jí)的決策。如果這是最后一級(jí)決策，而且要求一個(gè)明確的類別判決，則可以根據(jù)樣本對(duì)各個(gè)類的隸屬度或其他一些指標(biāo)進(jìn)行硬性分類。8.2.2常用的隸屬度函數(shù)

1.矩形隸屬度函數(shù)

(1)偏小型矩形隸屬度函數(shù)(參見圖8.1(a))；

(2)偏大型矩形隸屬度函數(shù)(參見圖8.1(b))；

(3)中間型矩形隸屬度函數(shù)(參見圖8.1(c))；圖8.1矩形分布隸屬度函數(shù)

2.梯形隸屬度函數(shù)

(1)偏小型梯形隸屬度函數(shù)(參見圖8.2(a))；

(2)偏大型梯形隸屬度函數(shù)(參見圖8.2(b))；

(3)中間型梯形隸屬度函數(shù)(參見圖8.2(c))；圖8.2梯形分布隸屬度函數(shù)

3.K次梯形隸屬度函數(shù)

(1)偏小型K次梯形隸屬度函數(shù)(參見圖8.3(a))：

(2)偏大型K次梯形隸屬度函數(shù)(參見圖8.3(b))；

(3)中間型K次梯形隸屬度函數(shù)(參見圖8.3(c))；圖8.3K次梯形分布隸屬度函數(shù)

4.正態(tài)形隸屬度函數(shù)

(1)偏小型正態(tài)形分布隸屬度函數(shù)(參見圖8.4(a))；

(2)偏大型正態(tài)形分布隸屬度函數(shù)(參見圖8.4(b))；

(3)中間型正態(tài)形分布隸屬度函數(shù)(參見圖8.4(c))；圖8.4正態(tài)形分布隸屬度函數(shù)

5.柯西形隸屬度函數(shù)

(1)偏小型柯西形隸屬度函數(shù)(參見圖8.5(a))：

(2)偏大型柯西形隸屬度函數(shù)(參見圖8.5(b))；

(3)中間型柯西形隸屬度函數(shù)(參見圖8.5(c))；圖8.5柯西形分布隸屬度函數(shù)

6.嶺形隸屬度函數(shù)

(1)偏小型嶺形隸屬度函數(shù)(參見圖8.6(a))：

(2)偏大型嶺形隸屬度函數(shù)(參見圖8.6(b))；

(3)中間型嶺形隸屬度函數(shù)(參見圖8.6(c))；圖8.6嶺形分布隸屬度函數(shù)8.2.3最大隸屬度原則

模糊模式識(shí)別中的最大隸屬度原則是直接利用樣本對(duì)各個(gè)類的隸屬度，將其歸入對(duì)應(yīng)于最大隸屬度的類別中。設(shè)

表示論域U上的c個(gè)模糊集合，其中，每個(gè)模糊集表示一個(gè)模糊模式類ωi。設(shè)表示論域中元素x對(duì)模糊集合的隸屬度，如果對(duì)于論域中的元素xj∈U,有

則判或者xj屬于ωk類。例8.1考慮三角形的識(shí)別問題。設(shè)U是所有待識(shí)別的三角形所構(gòu)成的集合，由于每一個(gè)三角形完全是由三個(gè)內(nèi)角所決定的，因此可以利用三角形三個(gè)內(nèi)角α、β和γ作為衡量指標(biāo)對(duì)三角形進(jìn)行識(shí)別。于是，論域U可以表示為

U={x=(α，β，γ)|α≥β≥γ≥0，α+β+γ=180°}

設(shè)A是U上的一個(gè)近似等腰三角形，其對(duì)應(yīng)的隸屬度函數(shù)為給定已知三個(gè)內(nèi)角角度的4個(gè)三角形x1=(90°，55°，35°)，x2=(100°，45°，35°)，x3=(125°，38°，17°)，x4=(80°，56°，44°)，嘗試用最大隸屬度原則識(shí)別這4個(gè)三角形中哪個(gè)優(yōu)先歸類于近似等腰三角形。

解根據(jù)隸屬度函數(shù)的定義，可以計(jì)算得到；

μA(x1)≈0.444,μA(x2)≈0.694

μA(x3)≈0.423,μA(x4)=0.64

μA(x2)=max{μA(x1),

μA(x2)，μA(x3)，μA(x4)}

按照最大隸屬度原則，x2應(yīng)該優(yōu)先歸類于近似等腰三角形。例8.2根據(jù)人的年齡，把人分為年輕、中年和老年三類，分別對(duì)應(yīng)三個(gè)模糊子集。設(shè)論域U=(0，100］，的隸屬度函數(shù)分別為：李四今年35歲，請(qǐng)利用最大隸屬度原則判斷其屬于年輕人、中年人還是老年人。解根據(jù)上述隸屬度函數(shù)，有，，，根據(jù)最大隸屬度原則，李四屬于中年人。最大隸屬度原則主要應(yīng)用于個(gè)體的識(shí)別。下面介紹可應(yīng)用于群體模型識(shí)別的擇近原則。8.2.4擇近原則

在模糊數(shù)學(xué)中，貼近度用于衡量模糊集合之間的接近程度。設(shè)表示論域U上的c個(gè)模糊集合，待識(shí)對(duì)象也是U上的模糊集，如果與最貼近，則把

歸入ωk類，這個(gè)準(zhǔn)則被稱為擇近原則。下面首先給出貼近度的具體定義。

定義8.3對(duì)于論域U上的模糊集合之集F(U)，其上的貼近度s是如下的映射；(8-22)s滿足以下條件：

(1)當(dāng)時(shí)，；

(2)當(dāng)，時(shí)，；

(3)對(duì)于任意，，有；

(4)對(duì)于任意，若或，有，。

下面介紹幾個(gè)常用的貼近度函數(shù)。

1.格貼近度

設(shè)，和之間的格貼近度定義為(8-23)有時(shí)也取

其中，和分別表示模糊集和之間的內(nèi)積和外積運(yùn)算。無限論域和有限論域上的內(nèi)積運(yùn)算分別定義為

無限論域和有限論域上的外積運(yùn)算分別定義為在上面兩個(gè)公式中，“∨”和“∧”分別表示“取大”和“取小”操作。(8-24)(8-25)例8.3設(shè)論域U為實(shí)數(shù)域，和是U上的兩個(gè)模糊子集，它們對(duì)應(yīng)的隸屬度函數(shù)分別為和

，其中，σ1，σ2>0，利用格貼近度求解。

解模糊集合和對(duì)應(yīng)的隸屬度函數(shù)如圖8.7所示。圖8.7和的隸屬度函數(shù)從圖中可知，和之間的內(nèi)積為

和之間的外積為

由，即，可得

求解上述等式，得到，與x1相比，x2不是最大值點(diǎn)，故選擇x*=x1。于是有

由，可得。

由格貼近度公式(8-23)，可得

例8.4設(shè)論域U={x1，x2，x3，x4}上的三個(gè)模糊集合為

，和

，利用格貼近度判斷和中哪個(gè)與

最貼近。

解首先分別計(jì)算和與的內(nèi)積和外積；由格貼近度公式(8-23)，與以及與之間的貼近度分別為；

因此，比貼近于。

可以驗(yàn)證，格貼近度不滿足貼近度定義中的條件(1)。然而，格貼近度非常適合于衡量?jī)蓚€(gè)模糊集的相對(duì)位置。

2.最大最小貼近度

設(shè)，U={x1，x2，…，xn}為有限論域，

和之間的最大最小貼近度為

可以驗(yàn)證，最大最小貼近度滿足貼近度定義中的條件(1)~(4)。(8-26)例8.5根據(jù)茶葉的形狀、色澤、凈度、湯色、香氣和滋味，可以把茶葉分成“特等”、“優(yōu)等”、“良等”、“中等”和“差等”五個(gè)等級(jí)，它們對(duì)應(yīng)于論域U上的五個(gè)模糊子集：

其中，論域U={形狀，色澤，凈度，湯色，香氣，滋味}。待識(shí)別的茶葉模型對(duì)應(yīng)于U上的模糊子集：

請(qǐng)采用最大最小貼近度，根據(jù)擇近原則判斷待識(shí)別茶葉的等級(jí)。解根據(jù)最大最小貼近度公式(8-26)，可得：

根據(jù)擇近原則，待識(shí)別的茶葉等級(jí)為“特等”。

3.距離貼近度

(1)海明距離貼近度。

設(shè)，x2，…，xn}為有限論域，和之間的海明距離貼近度定義為

進(jìn)一步，當(dāng)U為實(shí)數(shù)域上的閉區(qū)間［a，b］時(shí)，有(8-27)(8-28)

(2)歐氏距離貼近度。

設(shè)，U={x1，x2，…，xn}為有限論域，

和之間的歐氏距離貼近度定義為

進(jìn)一步，當(dāng)U為實(shí)數(shù)域上的閉區(qū)間［a，b］時(shí)，有(8-29)(8-30)

(3)明氏距離貼近度。

設(shè)，U={x1，x2，…，xn}為有限論域，和之間的明氏距離貼近度定義為

進(jìn)一步，當(dāng)U為實(shí)數(shù)域上的閉區(qū)間［a，b］時(shí)，有(8-31)(8-32)可以驗(yàn)證，這三個(gè)距離貼近度都滿足貼近度定義中的條件(1)~(4)。

8.3模糊聚類分析

第6章介紹的聚類分析是數(shù)理統(tǒng)計(jì)中的一種多元分析方法，它用數(shù)學(xué)方法定量地確定樣本的類屬程度。然而，事物之間的界限有些是確定的，也有一些則是模糊的。例如,人群中的面貌相像程度之間的界限是模糊的，天氣陰、晴之間的界限也是模糊的。當(dāng)聚類涉及事物之間的模糊界限時(shí)，就需要運(yùn)用模糊聚類分析的方法來處理。本節(jié)介紹兩種模糊聚類分析方法：模糊等價(jià)關(guān)系法和模糊c-均值聚類法。8.3.1模糊等價(jià)關(guān)系法

利用模糊等價(jià)關(guān)系進(jìn)行模式分類的方法稱之為模糊等價(jià)關(guān)系法。下面首先介紹模糊關(guān)系、模糊矩陣和模糊等價(jià)關(guān)系，然后詳細(xì)討論模糊等價(jià)關(guān)系法。

1.模糊關(guān)系

設(shè)X，Y是兩個(gè)論域，X與Y之間的笛卡爾乘積定義為

X×Y={(x，y)|x∈X，y∈Y}

(8-33)

定義8.4

設(shè)X，Y是兩個(gè)論域，X×Y上的一個(gè)模糊集

稱為X到Y(jié)上的一個(gè)模糊關(guān)系，也記為。模糊關(guān)系的隸屬函數(shù)為

表示(x，y)滿足關(guān)系的程度。若X=Y，則稱為論域X上的一個(gè)模糊關(guān)系。

對(duì)于有限論域X={x1，x2，…，xm}和Y={y1，y2，…，yn}，X到Y(jié)的模糊關(guān)系可用一個(gè)矩陣R表示：

R=(rij)m×n

(8-35)

其中，，稱矩陣R為模糊矩陣。若rij∈{0，1}，則矩陣R退化為布爾矩陣，即表達(dá)一個(gè)普通關(guān)系。因此，普通關(guān)系是模糊關(guān)系的特例。(8-34)(8-36)(8-37)(8-38)此外，若對(duì)所有的i和j都有rij=sij，則稱R與S相等，記為R=S；若對(duì)所有的i和j都有rij≤sij，則稱S包含R，記為。定義8.5設(shè)模糊關(guān)系對(duì)應(yīng)的模糊矩陣為R=(rij)m×n，對(duì)任意λ∈［0，1］，記Rλ=(λij)m×n，其中

稱Rλ為R的λ截矩陣，它所對(duì)應(yīng)的關(guān)系稱為的截關(guān)系。(8-39)

3.模糊等價(jià)關(guān)系

定義8.6設(shè)是論域X上的一個(gè)模糊關(guān)系，若有，則稱滿足自反性;若，則稱具有非自反性。

定義8.7設(shè)是論域X上的一個(gè)模糊關(guān)系，若x，y∈X有(即，其相應(yīng)的模糊矩陣滿足RT=R)，則稱滿足對(duì)稱性。若

，則稱具有非對(duì)稱性。定義8.8設(shè)是論域X上的一個(gè)模糊關(guān)系，若

，均有，則稱

滿足傳遞性。

定義8.9若模糊關(guān)系僅滿足自反性與對(duì)稱性，則稱

是相似關(guān)系。

定義8.10若模糊關(guān)系滿足自反性、對(duì)稱性與傳遞性，則稱是等價(jià)關(guān)系，相應(yīng)的模糊矩陣R是等價(jià)矩陣?？梢宰C明，模糊矩陣R是等價(jià)矩陣，當(dāng)且僅當(dāng)對(duì)于任意λ∈［0，1］，其截矩陣Rλ都是等價(jià)的布爾矩陣。定義8.11設(shè)是論域X上的一個(gè)模糊關(guān)系，包含的最小模糊傳遞關(guān)系稱為的傳遞閉包，記為。

定理8.1模糊關(guān)系的傳遞閉包為

。

易證，具有傳遞性的充要條件是。

定理8.2若為有限論域X={x1，x2，…，xn}上的模糊關(guān)系，則存在一個(gè)正整數(shù)k≤n，使得的傳遞閉包

。

設(shè)模糊關(guān)系對(duì)應(yīng)的模糊矩陣為R，對(duì)應(yīng)的模糊矩陣(即包含R的最小模糊傳遞矩陣)稱為R的傳遞閉包,記為t(R)定理8.3對(duì)于任意的n×n模糊矩陣R，存在一個(gè)正整數(shù)k≤n，使得R的傳遞閉包

4.模糊等價(jià)關(guān)系法

一個(gè)模糊等價(jià)關(guān)系與一個(gè)模糊等價(jià)矩陣一一對(duì)應(yīng)。模糊等價(jià)關(guān)系法實(shí)際上是利用模糊等價(jià)矩陣來進(jìn)行聚類。若為模糊等價(jià)關(guān)系，其對(duì)應(yīng)的模糊矩陣為R，則對(duì)于給定的λ∈［0，1］，可以得到相應(yīng)的普通等價(jià)關(guān)系，其對(duì)應(yīng)的λ截矩陣為Rλ，從而得到一個(gè)λ水平的分類。進(jìn)一步，若0≤λ≤ξ≤1，可知截矩陣Rξ所分出的每一類均是截矩陣Rλ所分出的某一類的子類，即Rξ的分類是Rλ分類的“加細(xì)”。當(dāng)λ從1逐漸降為0時(shí)，分類結(jié)果逐漸變粗，從而形成一個(gè)動(dòng)態(tài)聚類圖。下面以一個(gè)樣本集為例介紹模糊等價(jià)關(guān)系法是如何分類的。設(shè)X={x1，x2，x3，x4，x5}表示一個(gè)數(shù)據(jù)集，R為其對(duì)應(yīng)的模糊矩陣；可以驗(yàn)證，R具有自反性、對(duì)稱性和傳遞性，則R對(duì)應(yīng)一個(gè)模糊等價(jià)關(guān)系。根據(jù)不同λ取值下的截矩陣Rλ，可以獲得數(shù)據(jù)集X不同的分類結(jié)果：

(1)若0.56<λ≤1，對(duì)應(yīng)的截矩陣為

此時(shí)得到“最細(xì)”的分類：{x1}，{x2}，{x3}，{x4}，{x5}，即每個(gè)元素自成一類。

(2)若0.45<λ≤0.56，對(duì)應(yīng)的截矩陣為

此時(shí)得到四個(gè)聚類：{x1，x3}，{x2}，{x4}，{x5}。

(3)若0.38<λ≤0.45，對(duì)應(yīng)的截矩陣為

此時(shí)得到三個(gè)聚類：{x1，x2，x3}，{x4}，{x5}。

(4)若0.31<λ≤0.38，對(duì)應(yīng)的截矩陣為：

此時(shí)得到兩個(gè)聚類：{x1，x2，x3，x5}，{x4}。

(5)若0≤λ≤0.31，對(duì)應(yīng)的截矩陣Rλ的元素全為1，此時(shí)得到“最粗”的分類，即5個(gè)樣本合為一類。8.3.2模糊c-均值聚類算法

在第6章的6.5.1節(jié)，我們介紹了硬c-均值聚類算法(即HCM算法)。該算法把每個(gè)待聚類的對(duì)象嚴(yán)格地劃分到某個(gè)類中。然而，現(xiàn)實(shí)生活中的很多事物并沒有明確的屬性，它們的類別歸屬存在中介性，具有亦此亦彼的性質(zhì)。模糊聚類分析方法采用模糊的方法來進(jìn)行聚類，為解決此類問題提供了有力的分析工具。將模糊集合和模糊劃分的思想應(yīng)用到HCM算法，就得到模糊c-均值聚類算法(Fuzzyc-meansClusteringAlgorithm，F(xiàn)CM)。FCM算法給出了樣本對(duì)于各個(gè)類別的不確定性程度，更能客觀地反映現(xiàn)實(shí)世界，是一種非常有效的聚類算法。對(duì)于給定的數(shù)據(jù)集X={x1，x2，…，xn}，F(xiàn)CM算法采用下式作為目標(biāo)函數(shù)；

其中，vi表示第i個(gè)聚類的中心，uij表示數(shù)據(jù)點(diǎn)xj對(duì)于第i個(gè)聚類的隸屬程度，滿足uij∈［0，1］，(8-40)，m∈［1，∞)為加權(quán)指數(shù)。由uij(1≤i≤c，1≤j≤n)構(gòu)成的矩陣稱為模糊劃分矩陣，記為U=(uij)c×n。

FCM算法通過不斷更新各個(gè)聚類的中心和模糊劃分矩陣U，使得式(8-40)中的目標(biāo)函數(shù)越來越小。運(yùn)用拉格朗日乘子法，F(xiàn)CM算法的目標(biāo)函數(shù)可以轉(zhuǎn)化為如下無約束的函數(shù)形式；

上式取極小值的必要條件是L(uij，vi，λj)關(guān)于uij和λj的偏導(dǎo)數(shù)為零，即(8-41)(8-42)(8-43)從式(8-42)可以得到：

把式(8-44)帶入式(8-43)，可以得到：

再把式(8-45)帶入式(8-44)，可以得到：(8-44)(8-45)(8-46)需要指出的是，如果j，l使得||xj－vl||2=0，則令ulj=1，且對(duì)i≠l，uij=0。

類似地，求L關(guān)于vi的偏導(dǎo)數(shù)并設(shè)它為零，可以得到：

從式(8-47)可以得到：(8-47)(8-48)

下面給出FCM算法的步驟：

(1)確定聚類數(shù)目c、模糊指數(shù)m、閾值ε和算法最大迭代次數(shù)T；

(2)初始化模糊劃分矩陣U(1)，設(shè)置迭代次數(shù)k=1；

(3)利用式(8-48)計(jì)算各個(gè)聚類的中心

；

(4)利用式(8-46)計(jì)算隸屬度函數(shù)；

(5)如果||U(k+1)－U(k)||<ε或者算法的迭代次數(shù)k>T，則算法結(jié)束；否則，k=k+1，執(zhí)行步驟(3)。

上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。圖8.8給出了FCM算法的迭代過程示意圖。在迭代的初期，所有的聚類中心都在樣本的均值處。經(jīng)過3次迭代后，算法收斂到最終的聚類中心。

FCM算法的輸出是c個(gè)聚類中心向量和一個(gè)模糊劃分矩陣U，矩陣U中的元素表示的是每個(gè)樣本點(diǎn)對(duì)于每個(gè)類的隸屬程度。根據(jù)這個(gè)劃分矩陣，按照最大隸屬原則可以確定每個(gè)樣本點(diǎn)歸為哪個(gè)類。聚類中心表示的是每個(gè)類的平均特征，可以認(rèn)為是每個(gè)類的代表點(diǎn)。從FCM算法的推導(dǎo)過程不難看出，算法對(duì)于滿足正態(tài)分布的數(shù)據(jù)聚類效果會(huì)很好。

圖8.8FCM算法迭代過程示意圖

8.4聚類有效性評(píng)價(jià)

不管給定的樣本集結(jié)構(gòu)如何，聚類算法總能對(duì)樣本進(jìn)行聚類，但是有可能產(chǎn)生錯(cuò)誤的聚類結(jié)果。因此,需要對(duì)聚類算法的結(jié)果進(jìn)行定量評(píng)價(jià)，這一任務(wù)一般稱為聚類有效性評(píng)價(jià)。需要指出，相對(duì)于本章介紹的模糊聚類算法，第6章介紹的聚類算法稱為硬聚類算法。下面分別針對(duì)硬聚類和模糊聚類介紹常用的聚類有效性評(píng)價(jià)指標(biāo)。8.4.1硬聚類有效性評(píng)價(jià)

硬聚類有效性評(píng)價(jià)指標(biāo)有Dunn指標(biāo)、Davies-Bouldin(DB)指標(biāo)、輪廓指標(biāo)和Gap統(tǒng)計(jì)指標(biāo)等。其中，Dunn指標(biāo)和DB指標(biāo)是最常用的兩個(gè)評(píng)價(jià)指標(biāo)，下面對(duì)它們進(jìn)行具體介紹。關(guān)于其他指標(biāo)讀者可以參考相關(guān)文獻(xiàn)。

1.Dunn指標(biāo)

對(duì)于特定的聚類數(shù)目c，Dunn指標(biāo)的具體定義如下：(8-49)其中，Dij為聚類ωi和ωj之間的最小距離(見式(6-29))，diam(ωk)表示聚類ωk的直徑，定義如下；

可以看出，ωk的直徑就是該聚類中兩個(gè)最遠(yuǎn)的樣本之間的距離，它可以作為聚類分散程度的測(cè)量。(8-50)從Dunn指標(biāo)的定義可以看出，如果數(shù)據(jù)集中包含致密且分散程度很好的聚類，則聚類間的距離很大而各個(gè)聚類的直徑很小，此時(shí)Dunn指標(biāo)將會(huì)很大。需要指出，Dunn指標(biāo)的變化趨勢(shì)與聚類數(shù)目c無關(guān)，因此可以通過判斷該指標(biāo)的最大值來尋找數(shù)據(jù)的聚類數(shù)目。Dunn指標(biāo)的缺點(diǎn)是計(jì)算時(shí)間較長(zhǎng)，且對(duì)數(shù)據(jù)集中的噪聲向量敏感。為了降低Dunn指標(biāo)對(duì)于噪聲向量的敏感性，Pal提出了三個(gè)類Dunn指標(biāo)，感興趣的讀者可以參考相關(guān)文獻(xiàn)。

2.Davies-Bouldin(DB)指標(biāo)

對(duì)于特定的聚類數(shù)目c，Davies-Bouldin(DB)指標(biāo)定義為

其中，，i=1，2，…，c。Sij表示聚類ωi和ωj之間的相似性，定義如下；

其中，Dij表示聚類ωi和ωj之間的距離，σi和σj分別表示這兩個(gè)聚類的類內(nèi)離散度，具體定義為；(8-51)(8-52)(8-53)(8-54)其中，mi和mj分別表示聚類ωi和ωj的均值向量，ni表示聚類ωi中樣本的數(shù)目，l表示樣本x的維數(shù)。需要指出，聚類ωi和ωj之間的相似性指標(biāo)Sij應(yīng)該滿足以下條件：

(1)Sij≥0；

(2)Sij=Sji；

(3)如果σi=0且σj=0，則Sij=0；

(4)如果σi=σj且Dik<Djk，則Sik>Sjk；

(5)如果σi>σj且Dik=Djk，則Sik>Sjk。

條件(1)和條件(2)意味著Sij是非負(fù)的和對(duì)稱的；條件(3)意味著如果兩個(gè)聚類的離散程度為0，則相似性為0；條件(4)意味著如果兩個(gè)聚類ωi和ωj的離散程度相同、但與第三個(gè)聚類ωk的距離不同，則聚類ωk更加相似于距離較近的聚類；條