PD病癥的綜述課件

模式識別中的聚類分析

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

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

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

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

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

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