模糊數(shù)學(xué)--聚類函數(shù)

1、3.9 聚類分析,2013539應(yīng)用數(shù)學(xué)孫琨秋,聚類分析指將物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè),類的分析過程。聚類分析是一種探索性的分析，在分類的過程中，人們不必,事先給出一個(gè)分類的標(biāo)準(zhǔn)，聚類分析能夠從樣本數(shù)據(jù)出發(fā)，自動(dòng)進(jìn)行分類。,聚類分析所使用方法的不同，常常會(huì)得到不同的結(jié)論。不同研究者對(duì)于同一,組數(shù)據(jù)進(jìn)行聚類分析，所得到的聚類數(shù)未必一致。聚類分析在商業(yè)、生物、,地理、保險(xiǎn)行業(yè)、因特網(wǎng)、電子商務(wù)等方面都得到了廣泛

2、應(yīng)用。,“人以群分，物以類聚”。聚類是一種重要的人類行為，通過適當(dāng)聚類，,事物才便于研究，事物內(nèi)部規(guī)律才可能為人類所把握。聚類是按照事物的某,些特性，把事物聚集成類，使類間的相似性盡量小，類內(nèi)的相似性盡量大,的，按照相似程度的大小，將事物逐一分類。,但是聚類和模式分類是有區(qū)別的，也就是分類時(shí)需要預(yù)先知道分類所依,據(jù)的屬性值，而聚類是由聚類學(xué)習(xí)算法自動(dòng)找到這個(gè)分類屬性值。,目前聚類算法主要分為三類：,（1）層次聚類算法：適合小型數(shù)據(jù)集的分

3、類,（2）劃分式聚類算法 ：需要預(yù)先指定聚類數(shù)目或者聚類中心,（3）基于網(wǎng)格和密度的聚類算法 ：適合大型數(shù)據(jù)集的分類,3.9節(jié)主要介紹與劃分式聚類算法有關(guān)的F聚類算法,我講的是3.9.1 基于F等價(jià)矩陣模糊類分析的一般步驟。,3.9.1 基于F等價(jià)矩陣模糊聚類分析的一般步驟,3.9.2 模糊C均值聚類算法,3.9.1基于F等價(jià)矩陣模糊聚類分析的一般步驟,1、數(shù)據(jù)標(biāo)準(zhǔn)化,（1）數(shù)據(jù)矩陣,設(shè)論域,為被分類對(duì)象，每個(gè)對(duì)象又由

4、19898; 個(gè)指標(biāo)表示其特征：,于是，得到原始數(shù)據(jù)矩陣,為,（2）數(shù)據(jù)標(biāo)準(zhǔn)化 根據(jù)F矩陣的要求，一般將數(shù)據(jù)壓縮到區(qū)間,上，可采用下面方法實(shí)現(xiàn)：,,①平移——標(biāo)準(zhǔn)差變換,其中，,經(jīng)過變換后，每個(gè)變量的均值為0，標(biāo)準(zhǔn)差為1，消除了不同量綱的影響， 但處理后的數(shù)據(jù)不一定在[0,1]上。 ②平移——極差變換,變換后，數(shù)據(jù)都落入[0,1]范圍內(nèi)。,,2、建立F相似關(guān)系,設(shè),為待分類的全體。其中每一待分類對(duì)象由一組數(shù)

5、據(jù),表征如下：,現(xiàn)在的問題是如何建立,和,之間的相似關(guān)系。這有許多方法，我們挑,選一些進(jìn)行學(xué)習(xí)，我們可以考按照際情況，選其中一種來求,和,似關(guān)系,的相,① 數(shù)量積法,其中,為一適當(dāng)選擇的正數(shù)，滿足,②相關(guān)系數(shù)法,其中,③最大最小法,④算術(shù)平均最小法,⑤幾何平均最小法,⑥ 絕對(duì)值指數(shù)法,,⑦絕對(duì)值減數(shù)法,其中，c適當(dāng)選取，使,除上述方法外，還可請專家或又多人打分再取平均值。 選擇哪一個(gè)方法好，要按實(shí)際情況而定。在實(shí)際應(yīng)用

6、時(shí)，最好采用多種方法，選取分類最符合實(shí)際的結(jié)果。3 、改造相似關(guān)系為等價(jià)關(guān)系 由第二步得到的矩陣,一般只滿足自反性和對(duì)稱性，即,是相似矩陣，,它改造成,等價(jià)矩陣。為此，采用平方法求出,的傳遞閉包,，,便是所,求,等價(jià)矩陣。通過,便可對(duì),進(jìn)行分類。,4、聚類并畫動(dòng)態(tài)聚類圖,選取適當(dāng)?shù)拈撝?對(duì)等價(jià)矩陣,，按,截關(guān)系進(jìn)行動(dòng)態(tài)聚類。,例1 環(huán)境單元分類,每個(gè)環(huán)境單元包括空氣、水分、土壤、作物四個(gè)因素。環(huán)境單元的污染,狀況由污染物在四要

7、素中含量的超限度來描述。,現(xiàn)有五個(gè)環(huán)境單元，他們的污染數(shù)據(jù)如下：,設(shè) U={Ⅰ，Ⅱ，Ⅲ，Ⅳ，Ⅴ},Ⅰ=（5，5，3，2） Ⅱ=（2，3，4，5） Ⅲ =（5，5，2，3 ）,Ⅳ =（1，5，3，1） Ⅴ=（2，4，5，1）,試對(duì)U分類。,首先，按方法⑦建立F相似關(guān)系，取,得F相似矩陣,其次，用平方法求傳遞閉包,所以，,是傳遞閉包，也就是所求的等價(jià)矩陣。,最后，聚類：,當(dāng),時(shí)，U分為一類：{Ⅰ，Ⅱ，Ⅲ，

8、Ⅳ，Ⅴ}；,當(dāng),時(shí)，U分為二類：{Ⅰ，Ⅲ，Ⅳ，Ⅴ} ，{Ⅱ} ；,當(dāng),時(shí)，U分為三類：{Ⅰ，Ⅲ} ，{Ⅳ，Ⅴ}, {Ⅱ} ；,當(dāng),當(dāng),時(shí)，U分為四類： {Ⅰ，Ⅲ} ，{Ⅱ} ，{Ⅳ} ，{Ⅴ} ；,時(shí)，U分為五類： {Ⅰ}，{Ⅱ} ，{Ⅲ} ，{Ⅳ} ，{Ⅴ} ；,聚類圖如圖3-5所示。,例2 設(shè),表示由父、子、女、鄰居、母五人組成的一個(gè)組,合，請陌生人對(duì)這五人按相貌相像程度進(jìn)行F分類。,首先，求相似關(guān)系。對(duì)五人中任意兩人按相貌相

9、像程度打分，用[0,1]上,的數(shù)表示。于是得到F相似矩陣,自己與自己的相貌完全相像，故對(duì)角線上的元素都為1；,，表示母女相貌相像程度為90%；,，表示父親與鄰居的相貌相像程度為10%。,由于,即R不具有傳遞性，故不是F等價(jià)矩陣。,第二，求傳遞閉包。,因此，,是U上的F等價(jià)矩陣，用它對(duì)U聚類。,最后，聚類：,當(dāng),當(dāng),當(dāng),當(dāng),時(shí)，U分為一類：,時(shí)，U分為二類：,當(dāng),時(shí)，U分為三類：,時(shí)，U分為四類：,時(shí)，U分為五類：,聚類圖見圖3-6,當(dāng),

10、時(shí)，,（鄰居）就不屬于他們（一家）一類，這是符合實(shí)際的。,上述方法是應(yīng)用F等價(jià)關(guān)系將元素聚類。當(dāng)被分類的元素比較多時(shí)，,這個(gè)方法顯得麻煩，下面介紹比較簡單的辦法。,一、直接聚類法,1、F關(guān)系圖,在同一論域中，一條路可以定義成一個(gè)元素序列,（3.1）,S是有限數(shù)，元素可以重復(fù)出現(xiàn)。,叫起點(diǎn)，,叫終點(diǎn)。這條路是由下面這,些箭頭連接起來的：,（3.2）,其中，每個(gè)剪頭叫做一步，這條路有S -1步。 S -1又叫它的長度，每個(gè)箭頭,上邊標(biāo)的數(shù),

11、稱為這步路的權(quán)重。一條路上最輕的一步權(quán)重叫做路的權(quán)重。,路（3.1）的權(quán)重是,（3.3）,兩條路的起點(diǎn)和終點(diǎn)相同，稱兩條路等效。,一個(gè)F矩陣,對(duì)應(yīng)著一個(gè)由,個(gè)元素及,個(gè)箭頭（即有,個(gè),）所組成的帶權(quán)圖。,對(duì)應(yīng)的圖與,圖的差別，僅僅在于權(quán)重。在,圖中，每一個(gè)箭頭的權(quán)重等于在,圖中與它等效的二步路中最重的一條二步,路的權(quán)重（見圖3-7）。,例如：,從運(yùn)算可得（圖3-7）,同理，在,這就說明，在,圖中，每一步的權(quán)重等于在,圖中與它等效的,步路

12、中最,重的一條路的權(quán)重。,的關(guān)系中 ，,與,在,水平上同類，而在,圖中必存,在一條權(quán)重不低于,的路 聯(lián)結(jié),與,由此及§3.5性質(zhì)⑤推論,得下述聚類原則。,2、聚類原則,與,在,水平上分類,在,圖中，存在一條權(quán)重不低于,的路 聯(lián)結(jié),與,由此，不需改造,，可直接根據(jù)聚類原則進(jìn)行聚類。,例 3 照片分類。,現(xiàn)有三個(gè)家庭，每個(gè)家庭由4~7人組成，每人1張照片，共有16張。試,通過照片按相貌相像程度分類，把三個(gè)家庭區(qū)分開來。,解

13、 建立相似關(guān)系。任取兩張照片，請若干中學(xué)生按相貌相像程度打分，取,平均數(shù)再折合成隸屬度，得到相像關(guān)系的F矩陣,（見表3-1）。由于矩陣是,對(duì)稱的，只需寫出下三角形。,這個(gè)矩陣的傳遞閉包,，因此，若改造,為等價(jià)矩陣，則需平方,4次，麻煩程度可想而知。,但按聚類原則，不需改造,，直接將,圖中權(quán)重,不低于,聯(lián)結(jié)起來，在一條路上的元素就是一類。取,的路,從1到0，便可得到所有的分類。,例如，取,，權(quán)重不低于0.8的路如圖3-8所示，共五條路（包

14、括③,單獨(dú)一條），共分為五類。,若取,，則 權(quán)重不低于0.6 的路在上述路上把①和?聯(lián)起來 。這時(shí)，,除③外，其余15張照片可分為三類（即三家），聚類圖見圖3-9。,二、編網(wǎng)法,按聚類原則，以例3照片分類為例。,取矩陣,，將對(duì)角線填入元素符號(hào)。在對(duì)角線左下方以*取代1，以空,格代0。將*所在的位置稱為結(jié)點(diǎn)，向?qū)蔷€引經(jīng)線（豎線）及緯線（橫線）。,所謂編網(wǎng)，就是在結(jié)點(diǎn)處將經(jīng)過的經(jīng)緯線捆綁起來（見圖3-10），這樣來實(shí),現(xiàn)分類。通過打結(jié)而能

15、互相聯(lián)結(jié)的點(diǎn)屬于同一類。,由圖3-10可見，得分類：,{1，6，8，13，16}，{2，5，7，11，14}，{4，9，10，12，15}，{3},結(jié)果與前述一致。,三、最大樹法,在F相似矩陣,中，按,的大小順序依次用直線將元素連接起來，并,標(biāo)上權(quán)重。若在某一步出現(xiàn)回路，便不畫這一步，直到所有元素連通為止。,這樣，就得到一顆所謂的最大樹（可以不唯一）。取定,，去掉權(quán)重低于,的連線，即可將元素分類，互相連通的元素歸為一類。,仍以例3照片分