模式識(shí)別中的聚類(lèi)分析

姓名：趙偉強(qiáng)學(xué)號(hào)：1212122947PD病癥的綜述與模式識(shí)別相關(guān)的學(xué)科統(tǒng)計(jì)學(xué)概率論線性代數(shù)（矩陣計(jì)算）形式語(yǔ)言機(jī)器學(xué)習(xí)人工智能圖像處理計(jì)算機(jī)視覺(jué)…PD病癥的綜述教材/參考文獻(xiàn)R.Duda,P.Hart,D.Stork,PatternClassification,secondedition,2000（有中譯本）.邊肇祺，模式識(shí)別（第二版），清華大學(xué)出版社，2000。蔡元龍，模式識(shí)別，西北電訊工程學(xué)院出版社，1986。PD病癥的綜述機(jī)構(gòu)、會(huì)議、刊物1973年IEEE發(fā)起了第一次關(guān)于模式識(shí)別的國(guó)際會(huì)議“ICPR”（此后兩年一次），成立了國(guó)際模式識(shí)別協(xié)會(huì)---“IAPR”1977年IEEE成立PAMI委員會(huì)，創(chuàng)立IEEETrans.onPAMI，并支持ICCV,CVPR兩個(gè)會(huì)議其他刊物PatternRecognition(PR)PatternRecognitionLetters(PRL)PatternAnalysisandApplication(PAA)InternationalJournalofPatternRecognitionandArtificialIntelligence(IJPRAI)PD病癥的綜述第一章模式識(shí)別概論P(yáng)D病癥的綜述什么是模式？廣義地說(shuō)，存在于時(shí)間和空間中可觀察的物體，如果我們可以區(qū)別它們是否相同或是否相似，都可以稱(chēng)之為模式。模式所指的不是事物本身，而是從事物獲得的信息，因此，模式往往表現(xiàn)為具有時(shí)間和空間分布的信息。模式的直觀特性:可觀察性可區(qū)分性相似性PD病癥的綜述模式識(shí)別的概念模式識(shí)別–直觀，無(wú)所不在，“人以類(lèi)聚，物以群分”周?chē)矬w的認(rèn)知：桌子、椅子人的識(shí)別：張三、李四聲音的辨別：汽車(chē)、火車(chē)，狗叫、人語(yǔ)氣味的分辨：炸帶魚(yú)、紅燒肉人和動(dòng)物的模式識(shí)別能力是極其平常的，但對(duì)計(jì)算機(jī)來(lái)說(shuō)卻是非常困難的。PD病癥的綜述模式識(shí)別的研究目的：利用計(jì)算機(jī)對(duì)物理對(duì)象進(jìn)行分類(lèi)，在錯(cuò)誤概率最小的條件下，使識(shí)別的結(jié)果盡量與客觀物體相符合。Y=F(X)X的定義域取自特征集Y的值域?yàn)轭?lèi)別的標(biāo)號(hào)集F是模式識(shí)別的判別方法PD病癥的綜述模式識(shí)別簡(jiǎn)史1929年G.Tauschek發(fā)明閱讀機(jī)，能夠閱讀0-9的數(shù)字。30年代Fisher提出統(tǒng)計(jì)分類(lèi)理論，奠定了統(tǒng)計(jì)模式識(shí)別的基礎(chǔ)。50年代NoamChemsky提出形式語(yǔ)言理論——傅京蓀提出句法結(jié)構(gòu)模式識(shí)別。60年代L.A.Zadeh提出了模糊集理論，模糊模式識(shí)別方法得以發(fā)展和應(yīng)用。80年代以Hopfield網(wǎng)、BP網(wǎng)為代表的神經(jīng)網(wǎng)絡(luò)模型導(dǎo)致人工神經(jīng)元網(wǎng)絡(luò)復(fù)活，并在模式識(shí)別得到較廣泛的應(yīng)用。90年代小樣本學(xué)習(xí)理論，支持向量機(jī)也受到了很大的重視。PD病癥的綜述模式識(shí)別的應(yīng)用（舉例）生物學(xué)自動(dòng)細(xì)胞學(xué)、染色體特性研究、遺傳研究天文學(xué)天文望遠(yuǎn)鏡圖像分析、自動(dòng)光譜學(xué)經(jīng)濟(jì)學(xué)股票交易預(yù)測(cè)、企業(yè)行為分析醫(yī)學(xué)心電圖分析、腦電圖分析、醫(yī)學(xué)圖像分析PD病癥的綜述模式識(shí)別的應(yīng)用（舉例）工程產(chǎn)品缺陷檢測(cè)、特征識(shí)別、語(yǔ)音識(shí)別、自動(dòng)導(dǎo)航系統(tǒng)、污染分析軍事航空攝像分析、雷達(dá)和聲納信號(hào)檢測(cè)和分類(lèi)、自動(dòng)目標(biāo)識(shí)別安全指紋識(shí)別、人臉識(shí)別、監(jiān)視和報(bào)警系統(tǒng)PD病癥的綜述模式識(shí)別方法模式識(shí)別系統(tǒng)的目標(biāo)：在特征空間和解釋空間之間找到一種映射關(guān)系，這種映射也稱(chēng)之為假說(shuō)。特征空間：從模式得到的對(duì)分類(lèi)有用的度量、屬性或基元構(gòu)成的空間。解釋空間：將c個(gè)類(lèi)別表示為 其中為所屬類(lèi)別的集合，稱(chēng)為解釋空間。PD病癥的綜述假說(shuō)的兩種獲得方法監(jiān)督學(xué)習(xí)、概念驅(qū)動(dòng)或歸納假說(shuō)：在特征空間中找到一個(gè)與解釋空間的結(jié)構(gòu)相對(duì)應(yīng)的假說(shuō)。在給定模式下假定一個(gè)解決方案，任何在訓(xùn)練集中接近目標(biāo)的假說(shuō)也都必須在“未知”的樣本上得到近似的結(jié)果。依靠已知所屬類(lèi)別的的訓(xùn)練樣本集，按它們特征向量的分布來(lái)確定假說(shuō)（通常為一個(gè)判別函數(shù)），只有在判別函數(shù)確定之后才能用它對(duì)未知的模式進(jìn)行分類(lèi)；對(duì)分類(lèi)的模式要有足夠的先驗(yàn)知識(shí)，通常需要采集足夠數(shù)量的具有典型性的樣本進(jìn)行訓(xùn)練。PD病癥的綜述假說(shuō)的兩種獲得方法（續(xù)）非監(jiān)督學(xué)習(xí)、數(shù)據(jù)驅(qū)動(dòng)或演繹假說(shuō)：在解釋空間中找到一個(gè)與特征空間的結(jié)構(gòu)相對(duì)應(yīng)的假說(shuō)。這種方法試圖找到一種只以特征空間中的相似關(guān)系為基礎(chǔ)的有效假說(shuō)。在沒(méi)有先驗(yàn)知識(shí)的情況下，通常采用聚類(lèi)分析方法，基于“物以類(lèi)聚”的觀點(diǎn)，用數(shù)學(xué)方法分析各特征向量之間的距離及分散情況；如果特征向量集聚集若干個(gè)群，可按群間距離遠(yuǎn)近把它們劃分成類(lèi)；這種按各類(lèi)之間的親疏程度的劃分，若事先能知道應(yīng)劃分成幾類(lèi)，則可獲得更好的分類(lèi)結(jié)果。PD病癥的綜述模式分類(lèi)的主要方法數(shù)據(jù)聚類(lèi)統(tǒng)計(jì)分類(lèi)結(jié)構(gòu)模式識(shí)別神經(jīng)網(wǎng)絡(luò)PD病癥的綜述第二章聚類(lèi)分析2.1聚類(lèi)分析的相關(guān)概念2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則2.3基于試探的聚類(lèi)搜索算法2.4系統(tǒng)聚類(lèi)法2.5動(dòng)態(tài)聚類(lèi)法2.6聚類(lèi)結(jié)果的評(píng)價(jià)PD病癥的綜述2.1聚類(lèi)分析的相關(guān)概念定義 對(duì)一批沒(méi)有標(biāo)出類(lèi)別的模式樣本集，按照樣本之間的相似程度分類(lèi)，相似的歸為一類(lèi)，不相似的歸為另一類(lèi)，這種分類(lèi)稱(chēng)為聚類(lèi)分析，也稱(chēng)為無(wú)監(jiān)督分類(lèi)。PD病癥的綜述2.1聚類(lèi)分析的相關(guān)概念模式相似/分類(lèi)的依據(jù) 把整個(gè)模式樣本集的特征向量看成是分布在特征空間中的一些點(diǎn)，點(diǎn)與點(diǎn)之間的距離即可作為模式相似性的測(cè)量依據(jù)。

聚類(lèi)分析是按不同對(duì)象之間的差異，根據(jù)距離函數(shù)的規(guī)律（大?。┻M(jìn)行模式分類(lèi)的。PD病癥的綜述2.1聚類(lèi)分析的相關(guān)概念聚類(lèi)分析的有效性

聚類(lèi)分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點(diǎn)的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠(yuǎn)，則很容易聚類(lèi)；若樣本集的向量分布聚成一團(tuán)，不同群的樣本混在一起，則很難分類(lèi)；對(duì)具體對(duì)象做聚類(lèi)分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開(kāi)。PD病癥的綜述2.1聚類(lèi)分析的相關(guān)概念兩類(lèi)模式分類(lèi)的實(shí)例：一攤黑白圍棋子選顏色作為特征進(jìn)行分類(lèi)，用“1”代表白，“0”代表黑，則很容易分類(lèi)；選大小作為特征進(jìn)行分類(lèi)，則白子和黑子的特征相同，不能分類(lèi)（把白子和黑子分開(kāi)）。PD病癥的綜述2.1聚類(lèi)分析的相關(guān)概念特征選擇的維數(shù)

在特征選擇中往往會(huì)選擇一些多余的特征，它增加了維數(shù)，從而增加了聚類(lèi)分析的復(fù)雜度，但對(duì)模式分類(lèi)卻沒(méi)有提供多少有用的信息。在這種情況下，需要去掉相關(guān)程度過(guò)高的特征（進(jìn)行降維處理）。降維方法結(jié)論：若rij->1，則表明第i維特征與第j維特征所反映的特征規(guī)律接近，因此可以略去其中的一個(gè)特征，或?qū)⑺鼈兒喜橐粋€(gè)特征，從而使維數(shù)降低一維。PD病癥的綜述2.1聚類(lèi)分析的相關(guān)概念模式對(duì)象特征測(cè)量的數(shù)字化 計(jì)算機(jī)只能處理離散的數(shù)值，因此根據(jù)識(shí)別對(duì)象的不同，要進(jìn)行不同的數(shù)據(jù)化處理。連續(xù)量的量化：用連續(xù)量來(lái)度量的特性，如長(zhǎng)度、重量、面積等等，僅需取其量化值；量級(jí)的數(shù)量化：度量時(shí)不需要詳盡的數(shù)值，而是相應(yīng)地劃分成一些有次序的量化等級(jí)的值。病人的病程名義尺度：指定性的指標(biāo)，即特征度量時(shí)沒(méi)有數(shù)量關(guān)系，也沒(méi)有明顯的次序關(guān)系，如黑色和白色的關(guān)系，男性和女性的關(guān)系等，都可將它們分別用“0”和“1”來(lái)表示。超過(guò)2個(gè)狀態(tài)時(shí)，可用多個(gè)數(shù)值表示。PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則2.2.1相似性測(cè)度目的：為了能將模式集劃分成不同的類(lèi)別，必須定義一種相似性的測(cè)度，來(lái)度量同一類(lèi)樣本間的類(lèi)似性和不屬于同一類(lèi)樣本間的差異性。歐氏距離量綱對(duì)分類(lèi)的影響（下頁(yè)圖例）公式:D=||x-z||例：x=(x1,x2),z=(z1,z2)馬氏距離特點(diǎn)：排除了模式樣本之間的相關(guān)性問(wèn)題：協(xié)方差矩陣在實(shí)際應(yīng)用中難以計(jì)算PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則一般化的明氏距離公式：D(x,y)=它是歐氏距離的擴(kuò)展，當(dāng)m=2時(shí)，即為歐氏距離。角度相似性函數(shù)特點(diǎn)：反映了幾何上相似形的特征，對(duì)于坐標(biāo)系的旋轉(zhuǎn)、放大和縮小等變化是不變的。PD病癥的綜述量綱對(duì)分類(lèi)的影響（圖例）PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則2.2.2聚類(lèi)準(zhǔn)則 有了模式的相似性測(cè)度，還需要一種基于數(shù)值的聚類(lèi)準(zhǔn)則，能將相似的模式樣本分在同一類(lèi)，相異的模式樣本分在不同的類(lèi)。試探方法聚類(lèi)準(zhǔn)則函數(shù)法PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則2.2.2聚類(lèi)準(zhǔn)則試探方法 憑直觀感覺(jué)或經(jīng)驗(yàn)，針對(duì)實(shí)際問(wèn)題定義一種相似性測(cè)度的閾值，然后按最近鄰規(guī)則指定某些模式樣本屬于某一個(gè)聚類(lèi)類(lèi)別。例如對(duì)歐氏距離，它反映了樣本間的近鄰性，但將一個(gè)樣本分到不同類(lèi)別中的哪一個(gè)時(shí)，還必須規(guī)定一個(gè)距離測(cè)度的閾值作為聚類(lèi)的判別準(zhǔn)則。PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則2.2.2聚類(lèi)準(zhǔn)則聚類(lèi)準(zhǔn)則函數(shù)法依據(jù)：由于聚類(lèi)是將樣本進(jìn)行分類(lèi)以使類(lèi)別間可分離性為最大，因此聚類(lèi)準(zhǔn)則應(yīng)是反映類(lèi)別間相似性或分離性的函數(shù)；由于類(lèi)別是由一個(gè)個(gè)樣本組成的，因此一般來(lái)說(shuō)類(lèi)別的可分離性和樣本的可分離性是直接相關(guān)的；可以定義聚類(lèi)準(zhǔn)則函數(shù)為模式樣本集{x}和模式類(lèi)別{Sj,j=1,2,…,c}的函數(shù)，從而使聚類(lèi)分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問(wèn)題。PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則2.2.2聚類(lèi)準(zhǔn)則聚類(lèi)準(zhǔn)則函數(shù)法一種聚類(lèi)準(zhǔn)則函數(shù)J的定義c為聚類(lèi)類(lèi)別的數(shù)目，Sj第j個(gè)類(lèi)別樣本的集合mj為屬于Sj集合的樣本的均值向量,

Nj為Sj中的樣本數(shù)目PD病癥的綜述2.2模式相似性的測(cè)度和聚類(lèi)準(zhǔn)則以均值向量mj為sj中樣本的代表，用均值來(lái)代表每個(gè)樣本的中心。同一類(lèi)局的越緊密，函數(shù)值J就越小。J代表了屬于c個(gè)聚類(lèi)類(lèi)別的全部模式樣本與其相應(yīng)類(lèi)別模式均值之間的誤差平方和。對(duì)于不同的聚類(lèi)形式，J值是不同的。目的：求取使J值達(dá)到最小的聚類(lèi)形式。PD病癥的綜述2.3基于試探的聚類(lèi)搜索算法2.3.1按最近鄰規(guī)則的簡(jiǎn)單試探法算法:給定N個(gè)分類(lèi)的模式樣本{x1,x2,…,xN},要求按距離閾值T，將它們分到聚類(lèi)中心z1,z2,…。第一步：任取一樣本x1作為一個(gè)聚焦中心的初始值，令z1=x1,計(jì)算D21=||x2-z1||,若D21>T,則確定一個(gè)新的聚類(lèi)中心z2=x2;否則x2屬于以z1為中心的聚類(lèi)。第二步：假設(shè)已有聚類(lèi)中心z1,z2,計(jì)算D31=||x3-z1||,D32=||x3-z2||,若D31>T且D32>T,則得一個(gè)新的聚類(lèi)中心z3=x3,否則x3屬于離z1和z2中的最近者?！绱酥貜?fù)下去，直至將N個(gè)模式樣本分類(lèi)完畢。

PD病癥的綜述2.3基于試探的聚類(lèi)搜索算法2.3.1按最近鄰規(guī)則的簡(jiǎn)單試探法討論在實(shí)際中，對(duì)于高維模式樣本很難獲得準(zhǔn)確的先驗(yàn)知識(shí)，因此只能選用不同的閾值和起始點(diǎn)來(lái)試探，所以這種方法在很大程度上依賴(lài)于以下因素：第一個(gè)聚類(lèi)中心的位置待分類(lèi)模式樣本的排列次序距離閾值T的大小樣本分布的幾何性質(zhì)PD病癥的綜述2.3基于試探的聚類(lèi)搜索算法2.3.1按最近鄰規(guī)則的簡(jiǎn)單試探法討論距離閾值T對(duì)聚類(lèi)結(jié)果的影響PD病癥的綜述2.3基于試探的聚類(lèi)搜索算法2.3.2最大最小距離算法基本思想：以試探類(lèi)間歐氏距離為最大作為預(yù)選出聚類(lèi)中心的條件。PD病癥的綜述2.3基于試探的聚類(lèi)搜索算法2.3.2最大最小距離算法算法（實(shí)例）：有10個(gè)模式識(shí)別樣本點(diǎn)：第一步：任選一個(gè)模式樣本點(diǎn)作為第一聚類(lèi)中心，如z1=x1.第二步：選距離z1最遠(yuǎn)的點(diǎn)作為下一個(gè)聚類(lèi)中心。經(jīng)計(jì)算，||x6-z1||最大，所以z2=x6。第三步：逐個(gè)計(jì)算各模式樣本{xi,i=1,2,…,N}與{z1,z2}之間的距離，即Di1=||xi-z1||,Di2=||xi-z2||并選出其中最小的距離min(Di1,Di2),i=1,2,…,NPD病癥的綜述2.3基于試探的聚類(lèi)搜索算法第四步：在所有模式樣本最小值中選出最大距離，若該最大值達(dá)到||z1-z2||的一定比例以上，則相應(yīng)的基本點(diǎn)取為第三個(gè)聚類(lèi)中心z3,即若max{min(Di1,Di2),i=1,2,…,N}>θ||z1-z2||,則z3=xr,否則，若找不到適合要求的樣本作為新的聚類(lèi)中心，則找聚類(lèi)中心的過(guò)程結(jié)束這里，θ可用試探法取一固定分?jǐn)?shù)，如1/2。在此例中，當(dāng)k=7時(shí)，符合上述條件，故z3=x7。第五步：若有z3存在，則計(jì)算max{min(Di1,Di2),i=1,2,…,N}.若該值超過(guò)||z1-z2||的一定比例，則存在z4,否則找聚類(lèi)中心的過(guò)程結(jié)束。在此例中，無(wú)z4滿(mǎn)足條件。第六步：將模式樣本{xi,i=1,2,…,N}按最近距離分到最近的聚類(lèi)中心。最后，還可以在每一類(lèi)中計(jì)算各樣本的均值得到更具代表性的聚類(lèi)中心。PD病癥的綜述2.4系統(tǒng)聚類(lèi)法基本思想 將模式樣本按距離準(zhǔn)則逐步分類(lèi)，類(lèi)別由多到少，直到獲得合適的分類(lèi)要求為止。PD病癥的綜述2.4系統(tǒng)聚類(lèi)法算法：第一步：設(shè)初始模式樣本共有N個(gè)，每個(gè)樣本自成一類(lèi)，即建立N類(lèi)，G(0)1,G(0)2,…,G(0)N,計(jì)算各類(lèi)間的距離。得到一個(gè)N*N維的距離矩陣D(0).這里，標(biāo)號(hào)（0）表示聚類(lèi)開(kāi)始運(yùn)算前的狀態(tài)。第二步:假設(shè)千億布局類(lèi)運(yùn)算中已求得距離矩陣D(n),n為逐次聚類(lèi)合并的次數(shù)，則求D(n)中的最小元素。如果他是G(n)i和G(n)j兩類(lèi)之間的距離，則將G(n)i和G(n)j兩類(lèi)合并為一類(lèi)G(n+1)m,由此建立新的分類(lèi)：G(n+1)1,G(n+1)2,…第三步：計(jì)算合并后新類(lèi)別之間的距離，得D(n+1),計(jì)算G(n+1)m與其它沒(méi)有發(fā)生合并的G(n+1)1,G(n+1)2,…之間的