模式識別(chapter3)

1、1第第3 3章章 聚類分析聚類分析 (Clustering Analysis) 3.1 3.1 聚類分析的概念聚類分析的概念3.2 3.2 模式相似性測度模式相似性測度3.3 3.3 類的定義與類間距離類的定義與類間距離3.4 3.4 聚類的算法聚類的算法23.1 3.1 聚類分析的概念聚類分析的概念一、聚類分析的基本思想一、聚類分析的基本思想 相似的歸為一類。相似的歸為一類。 模式相似性的度量和聚類算法。模式相似性的度量和聚類算法。 無監(jiān)督分類無監(jiān)督分類（Unsupervised） 。二、特征量的類型二、特征量的類型 物理量物理量-(-(重量、長度、速度重量、長度、速度) ) 次序量次序量-

2、(-(等級、技能、學識等級、技能、學識) ) 名義量名義量-(-(性別、狀態(tài)、種類性別、狀態(tài)、種類) )3三、方法的有效性三、方法的有效性 取決于分類算法和特征點取決于分類算法和特征點分布情況的匹配。分布情況的匹配。3.1 聚類分析的概念2w2W1w1W2x1xb分類無效時的情況分類無效時的情況1.1.特征選取特征選取不當不當使分類無效。使分類無效。42 2. .特征選取特征選取不足不足可能使不同可能使不同類別的模式判為一類。類別的模式判為一類。2w2W1w1W2x1x3w3W3 3. .特征選取特征選取過多過多可能無益反可能無益反而有害而有害, ,增加分析負擔并使增加分析負擔并使分析效果變差

3、。分析效果變差。2w2W1w1W2x1xb54 4. .量綱選取不當。量綱選取不當。6下列是一些動物的名稱：下列是一些動物的名稱：羊羊 （sheepsheep）狗狗 （dogdog）藍鯊（藍鯊（blue sharkblue shark） 蜥蜴蜥蜴 （lizardlizard）毒蛇（毒蛇（viperviper）貓貓 （catcat）麻雀（麻雀（sparrowsparrow）海鷗海鷗 （seagullseagull）金魚（金魚（gold fishgold fish）緋鯢鰹（緋鯢鰹（red-mulletred-mullet）蛙蛙 （frogfrog）要對這些動物進行分類，則不同的特征有不同的分法：要

4、對這些動物進行分類，則不同的特征有不同的分法：特征選取不同對聚類結果的影響特征選取不同對聚類結果的影響7羊羊, , 狗狗, , 貓貓藍鯊藍鯊蜥蜴蜥蜴, ,毒蛇毒蛇, ,麻雀麻雀, ,海鷗海鷗, ,金魚金魚, ,緋鯢鰹緋鯢鰹, , 青蛙青蛙(a) 按繁衍后代的方式分按繁衍后代的方式分哺乳動物哺乳動物非哺乳動物非哺乳動物(b) 按肺是否存在分按肺是否存在分金魚金魚緋鯢鰹緋鯢鰹藍鯊藍鯊羊羊, ,狗狗, ,貓貓蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鷗海鷗 青蛙青蛙無肺無肺有肺有肺8藍鯊藍鯊金魚金魚緋鯢鰹緋鯢鰹蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鷗海鷗 青蛙青蛙羊羊, ,狗狗, ,貓貓(d) 按繁衍后

5、代方式和肺是否存在分按繁衍后代方式和肺是否存在分非哺乳且有肺非哺乳且有肺哺乳且無肺哺乳且無肺哺乳且有肺哺乳且有肺非哺乳且無肺非哺乳且無肺(c) 按生活環(huán)境分按生活環(huán)境分青蛙青蛙羊羊, ,狗狗, ,貓貓 蜥蜥蜴蜴, ,毒蛇毒蛇麻雀麻雀, ,海鷗海鷗 金魚金魚緋鯢鰹緋鯢鰹 藍鯊藍鯊陸地陸地水里水里兩棲兩棲9距離測度不同距離測度不同,聚類結果也不同聚類結果也不同數(shù)據(jù)的粗聚類是兩類數(shù)據(jù)的粗聚類是兩類,細聚類為細聚類為4類類10綜上可見綜上可見:選擇什么特征？選擇什么特征？選擇多少個特征？選擇多少個特征？選擇什么樣的量綱？選擇什么樣的量綱？選擇什么樣的距離測度？選擇什么樣的距離測度？ 這些對分類結果都會

6、產(chǎn)生極大影響。這些對分類結果都會產(chǎn)生極大影響。11聚類過程遵循的基本步驟 一、特征選擇(feature selection) 盡可能多地包含任務關心的信息二、近鄰測度(proximity measure) 定量測定兩特征如何“相似”或“不相似”三、聚類準則（clustering criterion） 以蘊涵在數(shù)據(jù)集中類的類型為基礎四、聚類算法（clustering algorithm） 按近鄰測度和聚類準則揭示數(shù)據(jù)集的聚類結構五、結果驗證（validation of the results） 常用逼近檢驗驗證聚類結果的正確性六、結果判定（interpretation of the result

7、s） 由專家用其他方法判定結果的正確性12聚類應用的四個基本方向一、減少數(shù)據(jù) 許多時候，當數(shù)據(jù)量N很大時，會使數(shù)據(jù)處理變得很費力。因此可使用聚類分析的方法將數(shù)據(jù)分成幾組可判斷的聚類m（mN）來處理，每一個類可當作獨立實體來對待。從這個角度看，數(shù)據(jù)被壓縮了。13二、假說生成 在這種情況下，為了推導出數(shù)據(jù)性質(zhì)的一些假說，對數(shù)據(jù)集進行聚類分析。因此，這里使用聚類作為建立假說的方法，然后用其他數(shù)據(jù)集驗證這些假說。14三、假說檢驗 用聚類分析來驗證指定假說的有效性。例如：考慮這樣的假說例如：考慮這樣的假說“大公司在海外投資大公司在海外投資”。要驗證這個假說是否正確，就要對大公司和有要驗證這個假說是否正確

8、，就要對大公司和有代表性的公司按規(guī)模、海外活躍度、成功完成代表性的公司按規(guī)模、海外活躍度、成功完成項目的能力等進行聚類分析。從而來支持這個項目的能力等進行聚類分析。從而來支持這個假說。假說。15四、基于分組的預測 對現(xiàn)有數(shù)據(jù)進行聚類分析，形成模式的特征，并用特征表示聚類，接下來，對于一個未知模式，就可以用前面的聚類來確定是哪一類？例如：考慮被同種疾病感染的病人數(shù)據(jù)集。例如：考慮被同種疾病感染的病人數(shù)據(jù)集。先按聚類分析進行分類，然后對新的病人確定他先按聚類分析進行分類，然后對新的病人確定他適合的聚類，從而判斷他病情。適合的聚類，從而判斷他病情。163.2 3.2 模式相似性測度模式相似性測度 用

9、于描述各模式之間特征的相似程度用于描述各模式之間特征的相似程度 距距 離離 測測 度度 相相 似似 測測 度度 匹匹 配配 測測 度度17一、距離測度一、距離測度( (差值測度差值測度) )測度基礎：測度基礎：兩個矢量矢端的距離兩個矢量矢端的距離測度數(shù)值：測度數(shù)值：兩矢量各相應分量之差的函數(shù)兩矢量各相應分量之差的函數(shù)。時，等號成立；時，等號成立；0),(yxd，當且僅當，當且僅當xy),(),(xydyxd),(),(),(yzdzxdyxd18常用的距離測度有：常用的距離測度有：1.1.歐氏歐氏(Euclidean)(Euclidean)距離距離 194.明氏(Minkowski)距離 2.

10、絕對值距離(街坊距離或Manhattan距離) 3.切氏(Chebyshev)距離 2021注意！馬氏距離對一切非奇異線性變換都是不變的，這說明它不受特征量綱選擇的影響，并且是平移不變的。上面的V V的含義是這個矢量集的協(xié)方差陣的統(tǒng)計量，故馬氏距離加入了對特征的相關性的考慮。22現(xiàn)金識別例子現(xiàn)金識別例子( (歐氏平均距離歐氏平均距離) )數(shù)據(jù)樣本介紹：數(shù)據(jù)樣本介紹：10個文本文件個文本文件文件名：文件名：rmb00.txt rmb09.txt每個文件有每個文件有4個幣種的數(shù)據(jù)，分別是：個幣種的數(shù)據(jù)，分別是： 100圓、圓、50圓、圓、20圓、圓、10圓圓每個幣種有新舊兩種版本，每個幣種有新舊兩

11、種版本，4個方向，故有個方向，故有8個數(shù)據(jù)塊：個數(shù)據(jù)塊：如如100圓的圓的8個數(shù)據(jù)塊：個數(shù)據(jù)塊： data100a,data100b,data100c,data100ddata100a,data100b,data100c,data100d老版老版 data100e,data100f,data100g,data100hdata100e,data100f,data100g,data100h新版新版每個數(shù)據(jù)塊有每個數(shù)據(jù)塊有8個傳感器數(shù)據(jù)：個傳感器數(shù)據(jù)： 傳感器傳感器1，傳感器，傳感器2，傳感器，傳感器8每個傳感器有每個傳感器有60個采樣數(shù)據(jù)：個采樣數(shù)據(jù)： 數(shù)據(jù)數(shù)據(jù)1，數(shù)據(jù)，數(shù)據(jù)2，數(shù)據(jù)，數(shù)據(jù)6023

12、現(xiàn)金識別例子現(xiàn)金識別例子EuclidenEucliden=15.000000=15.000000Manhattan=33.000000Manhattan=33.000000ChebyshevChebyshev=11.000000=11.000000MinkowskiMinkowski=11.039449m=8=11.039449m=8100100元元A A面第面第1 1個樣本第個樣本第1010點和點和2020點的距離點的距離X:X: (75, 76,101, 83,102, 96, 91, 82) (75, 76,101, 83,102, 96, 91, 82)Y:Y: (70, 74, 90

13、, 76, 99, 96, 90, 86) (70, 74, 90, 76, 99, 96, 90, 86)X-Y: X-Y: 5, 2, 11, 7, 3, 0, 1, -45, 2, 11, 7, 3, 0, 1, -4距離測度距離測度rmbdis24二、相似測度測度基礎：以兩矢量的方向是否相近作為考慮的基礎,矢量長度并不重要。設1.角度相似系數(shù)(夾角余弦)注意：坐標系的旋轉(zhuǎn)和尺度的縮放是不變的,但對一般的線形變換和坐標系的平移不具有不變性。 252.相關系數(shù)它實際上是數(shù)據(jù)中心化后的矢量夾角余弦。 21)( )( )()( )(),(yyyyxxxxyyxxyxr3.指數(shù)相似系數(shù)niiii

14、yxnyxe122)(43exp1),(式中式中 為相應分量的協(xié)方差，為相應分量的協(xié)方差， 為矢量維數(shù)。為矢量維數(shù)。它不受量綱變化的影響。它不受量綱變化的影響。 2in26當特征只有兩個狀態(tài)（當特征只有兩個狀態(tài)（0 0，1 1）時，常用匹配測度。）時，常用匹配測度。0 0表示無此特征表示無此特征 ，1 1表示有此特征。故稱之為表示有此特征。故稱之為二值特征二值特征。 對于給定的對于給定的x x和和y y中的某兩個相應分量中的某兩個相應分量x xi i與與y yj j若若x xi i=1,y=1,yj j=1 =1 ，則稱，則稱 x xi i與與y yj j是是 (1-1)(1-1)匹配匹配；若

15、若x xi i=1,y=1,yj j=0 =0 ，則稱，則稱 x xi i與與y yj j是是 (1-0)(1-0)匹配；匹配；若若x xi i=0,y=0,yj j=1 =1 ，則稱，則稱 x xi i與與y yj j是是 (0-1)(0-1)匹配；匹配；若若x xi i=0,y=0,yj j=0 =0 ，則稱，則稱 x xi i與與y yj j是是 (0-0)(0-0)匹配。匹配。三、三、匹配測度匹配測度2728(1)Tanimoto測度測度yxyyxxyxcbaayxs),(2) RaoRao測度測度注：注：(1-1)匹配特征數(shù)目和所選用的特征數(shù)目之比。匹配特征數(shù)目和所選用的特征數(shù)目之比

16、。nyxecbaayxs),(3)(3)簡單簡單匹配系數(shù)匹配系數(shù)注：上式分子為注：上式分子為(1-1)匹配特征數(shù)目與匹配特征數(shù)目與(0-0)匹配特征數(shù)目之和，分母為匹配特征數(shù)目之和，分母為所考慮的特征數(shù)目。所考慮的特征數(shù)目。neayxm),(29例例 可以看出，它等于可以看出，它等于共同具有的特征數(shù)目共同具有的特征數(shù)目與分別與分別具有的特征種類總數(shù)之比。這里只考慮具有的特征種類總數(shù)之比。這里只考慮(1-1)(1-1)匹配而匹配而不考慮不考慮(0-0)(0-0)匹配。匹配。)0, 1, 1, 0, 1, 0(x) 1, 0, 1, 1, 0, 0(y 1 , 3 , 3yxyyxx511331)

17、,(yxs設設則則30(4) Dice系數(shù)系數(shù)(5) Kulzinsky系數(shù)系數(shù)的總數(shù)倆矢量中匹配個數(shù)11)-(12),(yyxxyxcbaayxm匹配個數(shù)匹配個數(shù)0)-(11)-(01)-(12),(yxyyxxyxcbayxm3133 類的定義與類間距離3.3.1 3.3.1 類的定義類的定義定義之定義之1 1 設集合設集合S S中任意元素中任意元素x xi i與與y yj j間的距離間的距離d dijij有有 d dijij h h其中其中h h為給定的閥值，稱為給定的閥值，稱S S對于閥值對于閥值h h組成一類。組成一類。 類的定義有很多種，類的劃分具有人為規(guī)定性，這類的定義有很多種，

18、類的劃分具有人為規(guī)定性，這反映反映在定義在定義的選取及參數(shù)的選擇上。一個分類結果的優(yōu)劣最后只能根據(jù)實際來評的選取及參數(shù)的選擇上。一個分類結果的優(yōu)劣最后只能根據(jù)實際來評價。價。323.3.2 3.3.2 類間距離測度方法類間距離測度方法 最近距離法最近距離法 最遠距離法最遠距離法 中間距離法中間距離法 重心距離法重心距離法 平均距離法平均距離法 離差平方和法離差平方和法33 最近距離法最近距離法 ijjikldD,minijdkixwljxw式中式中 表示表示 和和 之間的距離。之間的距離。 最遠最遠距離法距離法式中式中 表示表示 和和 之間的距離。之間的距離。 ijjikldD,maxijdk

19、ixwljxw34 中間中間距離法距離法pw wqw wkw wpqkpqDkqDklDkpDlw wpqkqkpklDDDD2222412121qplwww 重心距離法重心距離法22222)(pqqpqpkqqpqkpqppklDnnnnDnnnDnnnD35 平均平均距離法距離法wwqjpixxijqppqdnnD221 離差平方和法離差平方和法wtixtititxxxxs)()(qplwwwqplpqsssD2)()(2qpqpqpqppqxxxxnnnnDtxpxqx分別為對應類的重心分別為對應類的重心類內(nèi)離差平方和類內(nèi)離差平方和 2222pqlkkkqlkqkkplkpkklDnnn

20、DnnnnDnnnnD遞推公式為遞推公式為:36222222kqkppqkqqkppklDDDDDD 最近距離法最近距離法 1/2 1/2 0 -1/2 最遠距離法最遠距離法 1/2 1/2 0 1/2 中間距離法中間距離法 1/2 1/2 -1/4 0 重心距離法重心距離法 0 平均距離法平均距離法 0 0 可變平均法可變平均法 0 可變法可變法 0 離差平方和法離差平方和法 0pqqppnnnqpqnnnqpqppnnnqpqnnnqppnnn )1 (qpqnnn )1 (112121lkpknnnnlkqknnnnlkknnn373.3.3 3.3.3 聚類的準則函數(shù)聚類的準則函數(shù)判別

21、分類結果好壞的一般標準：判別分類結果好壞的一般標準：類內(nèi)距離小，類間距離大。類內(nèi)距離小，類間距離大。 某些算法需要一個能對分類過程或分類結果某些算法需要一個能對分類過程或分類結果的優(yōu)劣進行評估的準則函數(shù)。如果聚類準則函數(shù)的優(yōu)劣進行評估的準則函數(shù)。如果聚類準則函數(shù)選擇得好，聚類質(zhì)量就會高。聚類準則往往是和選擇得好，聚類質(zhì)量就會高。聚類準則往往是和類的定義有關的，是類的定義的某種體現(xiàn)。類的定義有關的，是類的定義的某種體現(xiàn)。38一、類內(nèi)距離準則一、類內(nèi)距離準則 設有待分類的模式集設有待分類的模式集 在某種相似性測在某種相似性測度基礎上被劃分為度基礎上被劃分為 類，類，類內(nèi)距離準則函數(shù)類內(nèi)距離準則函數(shù)

22、 定義為定義為:( 表示表示 類的模式均值矢量。類的模式均值矢量。)Nxxx,21cjjinicjx, 2 , 1;, 2 , 1)(；WJcjnijjiWjmxJ112)(jmjw39加權類內(nèi)距離準則加權類內(nèi)距離準則 : :WWJ21jcjjWWdNnJ2)()(2)()() 1(2jjijjkxxjkjijjjxxnndww式中，2)()(jkjixx表示jw類內(nèi)任兩個模式距離2) 1(jjnn 個組合數(shù)，所以2jd表示類內(nèi)Nnj表示jw類先驗概率的估計頻率。平方和，共有兩模式間的均方距離。N為待分類模式總數(shù)，4041加權類間距離準則加權類間距離準則: :對于兩類問題，類間距離有時取)()

23、(21212mmmmJB2BJ和WBJ的關系是221BWBJNnNnJmax)()(1cjjjjWBmmmmNnJ4243 的類內(nèi)離差陣定義為的類內(nèi)離差陣定義為 jw), 2 , 1()(1)(1)()(cjmxmxnSjjijnijijjWjmjjwjnijijjxnm1)(1), 2 , 1(cj式中式中 為類為類 的模式均值矢量的模式均值矢量 4445證明證明：jnijijicjjjTmxmxnNnS1)()(1)(1jnijjjjijjijcjjmmmmmxmxnNn1)()(1)()(1BWSSBWTSSSNiiiTmxmxNS1)(1jnijijicjmxmxN1)()(1)(1聚

24、類的基本目的是使聚類的基本目的是使 或或 。TrmaxBSTrminWS46 利用利用線形代數(shù)有關矩陣的跡和行列式的性質(zhì)線形代數(shù)有關矩陣的跡和行列式的性質(zhì), ,可可以定義如下以定義如下4 4個聚類的準則函數(shù)個聚類的準則函數(shù): : 11TrWBJS SBWSSJ1213TrWTJS STWSSJ14 由它們的構造可以看出，為得到好的聚類由它們的構造可以看出，為得到好的聚類結果，應該使它們盡量的大。這類準則也大量結果，應該使它們盡量的大。這類準則也大量用在特征提取和選擇中。用在特征提取和選擇中。 4734 聚類的算法 3.4.1 聚類的技術方案聚類的技術方案聚類分析有很多具體的算法聚類分析有很多具

25、體的算法,有的比較簡單有的比較簡單,有的相對復雜和完善有的相對復雜和完善,但歸納起來就是三大類但歸納起來就是三大類:1、按最小距離原則簡單聚類方法、按最小距離原則簡單聚類方法2、按最小距離原則進行兩類合并的方法、按最小距離原則進行兩類合并的方法3、依據(jù)準則函數(shù)動態(tài)聚類方法、依據(jù)準則函數(shù)動態(tài)聚類方法48(1) (1) 簡單聚類方法簡單聚類方法 針對具體問題確定相似性閾值，將模式到各聚針對具體問題確定相似性閾值，將模式到各聚類中心間的距離與閾值比較，當大于閾值時該模類中心間的距離與閾值比較，當大于閾值時該模式就作為另一類的類心，小于閾值時按最小距離式就作為另一類的類心，小于閾值時按最小距離原則將其

26、分劃到某一類中。原則將其分劃到某一類中。這類算法運行中模式的類別及類的中心一旦確這類算法運行中模式的類別及類的中心一旦確定將不會改變。定將不會改變。49首先視各模式自成一類首先視各模式自成一類, ,然后將距離最小的兩然后將距離最小的兩類合并成一類類合并成一類, ,不斷地重復這個過程，直到成為不斷地重復這個過程，直到成為兩類為止。兩類為止。(2) 按最小距離原則進行兩類合并的方法按最小距離原則進行兩類合并的方法這類算法運行中，類心不斷地修正，但模式這類算法運行中，類心不斷地修正，但模式類別一旦指定后就不再改變，就是模式一旦劃為類別一旦指定后就不再改變，就是模式一旦劃為一類后就不再被分劃開，這類算

27、法也稱為譜系聚一類后就不再被分劃開，這類算法也稱為譜系聚類法。類法。50(3) 依據(jù)準則函數(shù)動態(tài)聚類法依據(jù)準則函數(shù)動態(tài)聚類法設定一些分類的控制參數(shù)，定義一個能表征聚設定一些分類的控制參數(shù)，定義一個能表征聚類結果優(yōu)劣的準則函數(shù)，聚類過程就是使準則函類結果優(yōu)劣的準則函數(shù)，聚類過程就是使準則函數(shù)取極值的優(yōu)化過程。數(shù)取極值的優(yōu)化過程。算法運行中，類心不斷地修正，各模式的類別算法運行中，類心不斷地修正，各模式的類別的指定也不斷地更改。這類方法有的指定也不斷地更改。這類方法有C C均值法、均值法、ISODATAISODATA法等。法等。5134 聚類的算法-簡單聚類方法簡單聚類方法 Simple-clus

28、teringSimple-clustering5234 聚類的算法-簡單聚類方法簡單聚類方法 5334 聚類的算法-簡單聚類方法簡單聚類方法 5434 聚類的算法-簡單聚類方法簡單聚類方法 這類算法的突出優(yōu)點是算法簡單。但聚類過程這類算法的突出優(yōu)點是算法簡單。但聚類過程中，類的中心一旦確定將不會改變，模式一旦指定中，類的中心一旦確定將不會改變，模式一旦指定類后也不再改變。類后也不再改變。算法特點算法特點:從算法的過程可以看出，該算法結果很大程度從算法的過程可以看出，該算法結果很大程度上依賴于距離門限上依賴于距離門限T的選取及模式參與分類的次序。的選取及模式參與分類的次序。如果能有先驗知識指導門

29、限如果能有先驗知識指導門限T的選取，通?？色@得的選取，通?？色@得較合理的效果。也可考慮設置不同的較合理的效果。也可考慮設置不同的T和選擇不同和選擇不同的次序，最后選擇較好的結果進行比較。的次序，最后選擇較好的結果進行比較。5534 聚類的算法-簡單聚類方法簡單聚類方法 簡單聚類圖簡單聚類圖例例56例例.1：初始條件不同的簡單聚類結果：初始條件不同的簡單聚類結果初始中心不同門限不同樣本順序不同 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 10 9 8 10 9 8 8 7 6 8 7 6 11 6 7 11 6 7 9 10 11 9 10 1

30、15734 聚類的算法最大最小距離法最大最小距離法 maxminclusteringmaxminclustering5834 聚類的算法-最大最小距離法最大最小距離法 算法原理步驟算法原理步驟11xz 選任一模式特征矢量作為第一個聚類中心1z例如，。1z作為第二個聚類中心2z。 從待分類矢量集中選距離最遠的特征矢量59 計算未被作為聚類中心的各模式特征矢量 ix與1z、2z之間的距離，并求出它們之中的最小值，jiijzxd)2 , 1( j 21,miniiiddd ), 2 , 1(Ni為表述簡潔，雖然某些模式已選做聚類中心，但上面仍將所有模式下角標全部列寫出來，因這并不影響算法的正確性。即

31、602121),min(maxzzdddiiil則相應的特征矢量lx作為第三個聚類中心，lxz3然后轉(zhuǎn)至；否則，轉(zhuǎn)至最后一步。 若 設存在k個聚類中心，計算未被作為聚類中心ijd,并算出ikiiildddd,minmax21如果21zzdl，則lkxz1否則，轉(zhuǎn)至最后一步。的各特征矢量到各聚類中心的距離并轉(zhuǎn)至；61 當判斷出不再有新的聚類中心之后，將模式特Nxxx,21中去，即計算jiijzxd), 2 , 1;, 2 , 1(Nij當 ddijjilmin，則判l(wèi)ixw。征矢量按最小距離原則分到各類這種算法的聚類結果與參數(shù)心的選取有關。如果沒有先驗知識指導和1z取，可適當調(diào)整和1z選取最合理

32、的一種聚類。以及第一個聚類中的選，比較多次試探分類結果，623.4.3 3.4.3 層次層次聚類法聚類法 (Hierarchical Clustering Method) (系統(tǒng)聚類法、系統(tǒng)聚類法、 譜系聚類法）譜系聚類法） 算法思想算法思想 首先將首先將 N N 個模式視作各自成為一類，然后計算個模式視作各自成為一類，然后計算類與類之間的距離，選擇距離最小的一對合并成一類與類之間的距離，選擇距離最小的一對合并成一個新類，計算在新的類別分劃下各類之間的距離，個新類，計算在新的類別分劃下各類之間的距離，再將距離最近的兩類合并，直至所有模式聚成兩類再將距離最近的兩類合并，直至所有模式聚成兩類為止。

33、為止。636465例3.4.3：如下圖所示 1、設全部樣本分為6類， 2、作距離矩陣D(0) 3、求最小元素： 4、把1,3合并7=(1,3) 4,6合并8=(4,6) 5、作距離矩陣D(1)3G1G2G5G4G6Gx1234523314474855262685913D(0)66例3.4.3：如下圖所示 1、設全部樣本分為6類， 2、作距離矩陣D(0) 3、求最小元素： 4、把1,3合并7=(1,3) 4,6合并8=(4,6) 5、作距離矩陣D(1)3G1G2G5G4G6GxD(1)72823874552267 6 6、若合并的類數(shù)沒有達到要求，轉(zhuǎn)、若合并的類數(shù)沒有達到要求，轉(zhuǎn)3 3。否則停止

34、。否則停止。 3 3、求最小元素：、求最小元素： 4 4、8,5,28,5,2合并合并, 9=, 9=（2,5,4,62,5,4,6）枝狀圖1w5w2w3w4w6w7w8w9w10w52582dd68枝狀圖1w5w2w3w4w6w7w8w9w10w3G1G2G5G4G6Gx6934 聚類的算法最大距離和層次聚類算法的一個共同特點是某最大距離和層次聚類算法的一個共同特點是某個模式一旦劃分到某一類之后，在后繼的算法過程個模式一旦劃分到某一類之后，在后繼的算法過程中就不改變了，而簡單聚類算法中類心一旦選定后中就不改變了，而簡單聚類算法中類心一旦選定后在后繼算法過程中也不再改變了。因此，這些方法在后繼

35、算法過程中也不再改變了。因此，這些方法效果一般不會太理想。效果一般不會太理想。 70)()(12xxd2. 確定評估聚類質(zhì)量的準則函數(shù)。1. 確定模式和聚類的距離測度。當采用歐氏距離時，是計算此模式和該類中心的歐氏距離；為能反映出類的模式分布結構，應采用馬氏距離，設該類的均矢為，協(xié)方差陣為，則模式x和該類的x與該類均矢的馬氏距離：距離平方為3. 確定模式分劃及聚類合并或分裂的規(guī)則。34 聚類的算法動態(tài)聚類算法要點動態(tài)聚類算法要點7134 聚類的算法動態(tài)聚類的基本步驟動態(tài)聚類的基本步驟1. 建立初始聚類中心，進行初始聚類；2. 計算模式和類的距離，調(diào)整模式的類別；3. 計算各聚類的參數(shù)，刪除、合

36、并或分裂一些聚類；4. 從初始聚類開始，運用迭代算法動態(tài)地改變模式的類別和聚類的中心使準則函數(shù)取得極值或設定的參數(shù)達到設計要求時停止。7234 聚類的算法動態(tài)聚類的框圖動態(tài)聚類的框圖產(chǎn)生初始產(chǎn)生初始聚類中心聚類中心聚類聚類檢驗聚類檢驗聚類合理性合理性待分類模式待分類模式 分類結分類結果果合理合理再迭代再迭代/修改參數(shù)修改參數(shù)不合理不合理73 條件及約定條件及約定 設待分類的模式特征矢量集為：設待分類的模式特征矢量集為：類的數(shù)目類的數(shù)目C C是事先取定的。是事先取定的。Nxxx,2134 聚類的算法 3.4.3 動態(tài)聚類法動態(tài)聚類法C-均值法均值法 算法思想算法思想 該方法該方法取定取定 C C

37、個類別個類別和選取和選取 C C個初始聚類中個初始聚類中心心，按最小距離原則將各模式分配到按最小距離原則將各模式分配到 C C類中的某類中的某一類，之后不斷地一類，之后不斷地計算類心和調(diào)整各模式計算類心和調(diào)整各模式的類別，的類別，最終使各模式到其判屬類別中心的距離平方之和最終使各模式到其判屬類別中心的距離平方之和最小。最小。7434 聚類的算法 3.4.3 動態(tài)聚類法動態(tài)聚類法C-均值法均值法75選代表點選代表點初始分類初始分類分類合理否分類合理否4.4.動態(tài)聚類框圖動態(tài)聚類框圖34 聚類的算法 3.4.3 動態(tài)聚類法動態(tài)聚類法C-均值法均值法最終分類最終分類Y修改分類修改分類N76例例3.4

38、.2 3.4.2 使用聚類算法實現(xiàn)圖像分割使用聚類算法實現(xiàn)圖像分割在散射圖上形成了兩個聚類，利用模式識別的在散射圖上形成了兩個聚類，利用模式識別的方法將其分開，就實現(xiàn)了圖象的分割。方法將其分開，就實現(xiàn)了圖象的分割。77 例例.3：已知有已知有2020個樣本，每個樣本有個樣本，每個樣本有2 2個特征，數(shù)據(jù)個特征，數(shù)據(jù)分布分布如下圖如下圖, ,使用使用C C均值法實現(xiàn)樣本分類（均值法實現(xiàn)樣本分類（C=2C=2）。）。第一步第一步：令：令C=2C=2，選初始聚類中心為，選初始聚類中心為1122(1)(0, 0 );(1)(1, 0 )TTZxZx樣本序號樣本序號x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x8 8x x9 9x x1010特征特征x x1 10 01 10 01 12 21 12 23 36 67 7特征特征