

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、3.9 聚類分析,2013539應用數學孫琨秋,聚類分析指將物理或抽象對象的集合分組成為由類似的對象組成的多個,類的分析過程。聚類分析是一種探索性的分析,在分類的過程中,人們不必,事先給出一個分類的標準,聚類分析能夠從樣本數據出發(fā),自動進行分類。,聚類分析所使用方法的不同,常常會得到不同的結論。不同研究者對于同一,組數據進行聚類分析,所得到的聚類數未必一致。聚類分析在商業(yè)、生物、,地理、保險行業(yè)、因特網、電子商務等方面都得到了廣泛
2、應用。,“人以群分,物以類聚”。聚類是一種重要的人類行為,通過適當聚類,,事物才便于研究,事物內部規(guī)律才可能為人類所把握。聚類是按照事物的某,些特性,把事物聚集成類,使類間的相似性盡量小,類內的相似性盡量大,的,按照相似程度的大小,將事物逐一分類。,但是聚類和模式分類是有區(qū)別的,也就是分類時需要預先知道分類所依,據的屬性值,而聚類是由聚類學習算法自動找到這個分類屬性值。,目前聚類算法主要分為三類:,(1)層次聚類算法:適合小型數據集的分
3、類,(2)劃分式聚類算法 :需要預先指定聚類數目或者聚類中心,(3)基于網格和密度的聚類算法 :適合大型數據集的分類,3.9節(jié)主要介紹與劃分式聚類算法有關的F聚類算法,我講的是3.9.1 基于F等價矩陣模糊類分析的一般步驟。,3.9.1 基于F等價矩陣模糊聚類分析的一般步驟,3.9.2 模糊C均值聚類算法,3.9.1基于F等價矩陣模糊聚類分析的一般步驟,1、數據標準化,(1)數據矩陣,設論域,為被分類對象,每個對象又由
4、19898; 個指標表示其特征:,于是,得到原始數據矩陣,為,(2)數據標準化 根據F矩陣的要求,一般將數據壓縮到區(qū)間,上,可采用下面方法實現:,,①平移——標準差變換,其中,,經過變換后,每個變量的均值為0,標準差為1,消除了不同量綱的影響, 但處理后的數據不一定在[0,1]上。 ②平移——極差變換,變換后,數據都落入[0,1]范圍內。,,2、建立F相似關系,設,為待分類的全體。其中每一待分類對象由一組數
5、據,表征如下:,現在的問題是如何建立,和,之間的相似關系。這有許多方法,我們挑,選一些進行學習,我們可以考按照際情況,選其中一種來求,和,似關系,的相,① 數量積法,其中,為一適當選擇的正數,滿足,②相關系數法,其中,③最大最小法,④算術平均最小法,⑤幾何平均最小法,⑥ 絕對值指數法,,⑦絕對值減數法,其中,c適當選取,使,除上述方法外,還可請專家或又多人打分再取平均值。 選擇哪一個方法好,要按實際情況而定。在實際應用
6、時,最好采用多種方法,選取分類最符合實際的結果。3 、改造相似關系為等價關系 由第二步得到的矩陣,一般只滿足自反性和對稱性,即,是相似矩陣,,它改造成,等價矩陣。為此,采用平方法求出,的傳遞閉包,,,便是所,求,等價矩陣。通過,便可對,進行分類。,4、聚類并畫動態(tài)聚類圖,選取適當的閾值,對等價矩陣,,按,截關系進行動態(tài)聚類。,例1 環(huán)境單元分類,每個環(huán)境單元包括空氣、水分、土壤、作物四個因素。環(huán)境單元的污染,狀況由污染物在四要
7、素中含量的超限度來描述。,現有五個環(huán)境單元,他們的污染數據如下:,設 U={Ⅰ,Ⅱ,Ⅲ,Ⅳ,Ⅴ},Ⅰ=(5,5,3,2) Ⅱ=(2,3,4,5) Ⅲ =(5,5,2,3 ),Ⅳ =(1,5,3,1) Ⅴ=(2,4,5,1),試對U分類。,首先,按方法⑦建立F相似關系,取,得F相似矩陣,其次,用平方法求傳遞閉包,所以,,是傳遞閉包,也就是所求的等價矩陣。,最后,聚類:,當,時,U分為一類:{Ⅰ,Ⅱ,Ⅲ,
8、Ⅳ,Ⅴ};,當,時,U分為二類:{Ⅰ,Ⅲ,Ⅳ,Ⅴ} ,{Ⅱ} ;,當,時,U分為三類:{Ⅰ,Ⅲ} ,{Ⅳ,Ⅴ}, {Ⅱ} ;,當,當,時,U分為四類: {Ⅰ,Ⅲ} ,{Ⅱ} ,{Ⅳ} ,{Ⅴ} ;,時,U分為五類: {Ⅰ},{Ⅱ} ,{Ⅲ} ,{Ⅳ} ,{Ⅴ} ;,聚類圖如圖3-5所示。,例2 設,表示由父、子、女、鄰居、母五人組成的一個組,合,請陌生人對這五人按相貌相像程度進行F分類。,首先,求相似關系。對五人中任意兩人按相貌相
9、像程度打分,用[0,1]上,的數表示。于是得到F相似矩陣,自己與自己的相貌完全相像,故對角線上的元素都為1;,,表示母女相貌相像程度為90%;,,表示父親與鄰居的相貌相像程度為10%。,由于,即R不具有傳遞性,故不是F等價矩陣。,第二,求傳遞閉包。,因此,,是U上的F等價矩陣,用它對U聚類。,最后,聚類:,當,當,當,當,時,U分為一類:,時,U分為二類:,當,時,U分為三類:,時,U分為四類:,時,U分為五類:,聚類圖見圖3-6,當,
10、時,,(鄰居)就不屬于他們(一家)一類,這是符合實際的。,上述方法是應用F等價關系將元素聚類。當被分類的元素比較多時,,這個方法顯得麻煩,下面介紹比較簡單的辦法。,一、直接聚類法,1、F關系圖,在同一論域中,一條路可以定義成一個元素序列,(3.1),S是有限數,元素可以重復出現。,叫起點,,叫終點。這條路是由下面這,些箭頭連接起來的:,(3.2),其中,每個剪頭叫做一步,這條路有S -1步。 S -1又叫它的長度,每個箭頭,上邊標的數,
11、稱為這步路的權重。一條路上最輕的一步權重叫做路的權重。,路(3.1)的權重是,(3.3),兩條路的起點和終點相同,稱兩條路等效。,一個F矩陣,對應著一個由,個元素及,個箭頭(即有,個,)所組成的帶權圖。,對應的圖與,圖的差別,僅僅在于權重。在,圖中,每一個箭頭的權重等于在,圖中與它等效的二步路中最重的一條二步,路的權重(見圖3-7)。,例如:,從運算可得(圖3-7),同理,在,這就說明,在,圖中,每一步的權重等于在,圖中與它等效的,步路
12、中最,重的一條路的權重。,的關系中 ,,與,在,水平上同類,而在,圖中必存,在一條權重不低于,的路 聯結,與,由此及§3.5性質⑤推論,得下述聚類原則。,2、聚類原則,與,在,水平上分類,在,圖中,存在一條權重不低于,的路 聯結,與,由此,不需改造,,可直接根據聚類原則進行聚類。,例 3 照片分類。,現有三個家庭,每個家庭由4~7人組成,每人1張照片,共有16張。試,通過照片按相貌相像程度分類,把三個家庭區(qū)分開來。,解
13、 建立相似關系。任取兩張照片,請若干中學生按相貌相像程度打分,取,平均數再折合成隸屬度,得到相像關系的F矩陣,(見表3-1)。由于矩陣是,對稱的,只需寫出下三角形。,這個矩陣的傳遞閉包,,因此,若改造,為等價矩陣,則需平方,4次,麻煩程度可想而知。,但按聚類原則,不需改造,,直接將,圖中權重,不低于,聯結起來,在一條路上的元素就是一類。取,的路,從1到0,便可得到所有的分類。,例如,取,,權重不低于0.8的路如圖3-8所示,共五條路(包
14、括③,單獨一條),共分為五類。,若取,,則 權重不低于0.6 的路在上述路上把①和?聯起來 。這時,,除③外,其余15張照片可分為三類(即三家),聚類圖見圖3-9。,二、編網法,按聚類原則,以例3照片分類為例。,取矩陣,,將對角線填入元素符號。在對角線左下方以*取代1,以空,格代0。將*所在的位置稱為結點,向對角線引經線(豎線)及緯線(橫線)。,所謂編網,就是在結點處將經過的經緯線捆綁起來(見圖3-10),這樣來實,現分類。通過打結而能
15、互相聯結的點屬于同一類。,由圖3-10可見,得分類:,{1,6,8,13,16},{2,5,7,11,14},{4,9,10,12,15},{3},結果與前述一致。,三、最大樹法,在F相似矩陣,中,按,的大小順序依次用直線將元素連接起來,并,標上權重。若在某一步出現回路,便不畫這一步,直到所有元素連通為止。,這樣,就得到一顆所謂的最大樹(可以不唯一)。取定,,去掉權重低于,的連線,即可將元素分類,互相連通的元素歸為一類。,仍以例3照片分
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論