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

1、3.9 聚類分析,2013539應(yīng)用數(shù)學(xué)孫琨秋,聚類分析指將物理或抽象對象的集合分組成為由類似的對象組成的多個(gè),類的分析過程。聚類分析是一種探索性的分析，在分類的過程中，人們不必,事先給出一個(gè)分類的標(biāo)準(zhǔn)，聚類分析能夠從樣本數(shù)據(jù)出發(fā)，自動(dòng)進(jìn)行分類。,聚類分析所使用方法的不同，常常會(huì)得到不同的結(jié)論。不同研究者對于同一,組數(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è)論域,為被分類對象，每個(gè)對象又由

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è),為待分類的全體。其中每一待分類對象由一組數(shù)

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

6、時(shí)，最好采用多種方法，選取分類最符合實(shí)際的結(jié)果。3 、改造相似關(guān)系為等價(jià)關(guān)系 由第二步得到的矩陣,一般只滿足自反性和對稱性，即,是相似矩陣，,它改造成,等價(jià)矩陣。為此，采用平方法求出,的傳遞閉包,，,便是所,求,等價(jià)矩陣。通過,便可對,進(jìn)行分類。,4、聚類并畫動(dòng)態(tài)聚類圖,選取適當(dāng)?shù)拈撝?對等價(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）,試對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è)組,合，請陌生人對這五人按相貌相像程度進(jìn)行F分類。,首先，求相似關(guān)系。對五人中任意兩人按相貌相

9、像程度打分，用[0,1]上,的數(shù)表示。于是得到F相似矩陣,自己與自己的相貌完全相像，故對角線上的元素都為1；,，表示母女相貌相像程度為90%；,，表示父親與鄰居的相貌相像程度為10%。,由于,即R不具有傳遞性，故不是F等價(jià)矩陣。,第二，求傳遞閉包。,因此，,是U上的F等價(jià)矩陣，用它對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矩陣,對應(yīng)著一個(gè)由,個(gè)元素及,個(gè)箭頭（即有,個(gè),）所組成的帶權(quán)圖。,對應(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）。由于矩陣是,對稱的，只需寫出下三角形。,這個(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照片分類為例。,取矩陣,，將對角線填入元素符號。在對角線左下方以*取代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照片分