PD病癥的綜述課件

模式識別中的聚類分析

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

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

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

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

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

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