模式識(shí)別第2章課件聚類分析.ppt

第二章聚類分析,分類與聚類的區(qū)別,分類：用已知類別的樣本訓(xùn)練集來(lái)設(shè)計(jì)分類器（監(jiān)督學(xué)習(xí)）聚類（集群）：用事先不知類別的樣本，而利用樣本的先驗(yàn)知識(shí)來(lái)構(gòu)造分類器（無(wú)監(jiān)督學(xué)習(xí)）,2.1聚類分析的概念,基本思想：對(duì)一批沒(méi)有標(biāo)明類別及類數(shù)的模式樣本集，根據(jù)模式間的相似程度，按照物以類聚、人以群分的思想，將相似的模式分為一類，不相似的分為另一類。,特征的類型,1.低層特征：無(wú)序尺度：有明確的數(shù)量和數(shù)值。有序尺度：有先后、好壞的次序關(guān)系，如酒分為上，中，下三個(gè)等級(jí)。名義尺度：無(wú)數(shù)量、無(wú)次序關(guān)系，如有紅，黃兩種顏色2.中層特征：經(jīng)過(guò)計(jì)算，變換得到的特征3.高層特征：在中層特征的基礎(chǔ)上有目的的經(jīng)過(guò)運(yùn)算形成例如：椅子的重量=體積*比重體積與長(zhǎng)，寬，高有關(guān)；比重與材料，紋理，顏色有關(guān)。這里低、中、高三層特征都有了。,方法的有效性,特征選取不當(dāng)特征過(guò)少特征過(guò)多量綱問(wèn)題,主要聚類分析技術(shù),譜系法（系統(tǒng)聚類，層次聚類法）基于目標(biāo)函數(shù)的聚類法（動(dòng)態(tài)聚類）圖論聚類法模糊聚類分析法,2.2模式相似度度量,各種距離表示相似性：絕對(duì)值距離已知兩個(gè)樣本xi=(xi1,xi2,xi3,xin)Txj=(xj1,xj2,xj3,xjn)T,歐幾里德距離明考夫斯基距離其中當(dāng)q=1時(shí)為絕對(duì)值距離，當(dāng)q=2時(shí)為歐氏距離,切比雪夫距離q趨向無(wú)窮大時(shí)明氏距離的極限情況馬哈拉諾比斯距離其中xi，xj為特征向量，為協(xié)方差。使用的條件是樣本符合正態(tài)分布,夾角余弦為xixj的均值即樣本間夾角小的為一類，具有相似性例：x1,x2,x3的夾角如圖：因?yàn)閤1,x2的夾角小，所以x1,x2最相似。,x2,x3,相關(guān)系數(shù)為xixj的均值注意：在求相關(guān)系數(shù)之前，要將數(shù)據(jù)標(biāo)準(zhǔn)化,2.3類的定義和與類間距離,用距離進(jìn)行定義類（書）,非監(jiān)督學(xué)習(xí)方法分類,1、基于概率密度函數(shù)估計(jì)的直接方法(不實(shí)用）2、基于樣本間相似性度量的間接聚類方法,兩類間的距離,1、最短距離：兩類中相距最近的兩樣本間的距離。,2、最長(zhǎng)距離：兩類中相距最遠(yuǎn)的兩個(gè)樣本間的距離。3、中間距離：最短距離和最長(zhǎng)距離都有片面性，因此有時(shí)用中間距離。設(shè)1類和23類間的最短距離為d12，最長(zhǎng)距離為d13，23類的長(zhǎng)度為d23，則中間距離為：上式推廣為一般情況：,4、重心距離：均值間的距離5、類平均距離：兩類中各個(gè)元素兩兩之間的距離平方相加后取平均值,6、離差平方和：設(shè)N個(gè)樣品原分q類，則定義第i類的離差平方和為：離差平方和增量：設(shè)樣本已分成p,q兩類，若把p,q合為r類，則定義離差平方：,聚類準(zhǔn)則,類內(nèi)距離越小越好類間距離越大越好一些準(zhǔn)則函數(shù),聚類分析三要素,相似性測(cè)度聚類準(zhǔn)則聚類算法,2.4聚類的算法,（1)根據(jù)相似性閾值和最小距離原則的簡(jiǎn)單聚類法（2）按照最小距離原則不斷進(jìn)行兩類合并的方法（3）依據(jù)準(zhǔn)則函數(shù)的動(dòng)態(tài)動(dòng)態(tài)聚類算法,系統(tǒng)聚類的算法,譜系聚類的算法原理、步驟例：如下圖所示1、設(shè)全部樣本分為6類，2、作距離矩陣D(0),3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距離矩陣D(1),6、若合并的類數(shù)沒(méi)有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、8,5,2合并,9=（2,5,4,6）,分解聚類,分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標(biāo)函數(shù)兩類均值方差,N：總樣本數(shù)，：1類樣本數(shù)：2類樣本數(shù)，,分解聚類框圖：,對(duì)分算法：略例：已知21個(gè)樣本，每個(gè)樣本取二個(gè)特征，原始資料矩陣如下表：,解：第一次分類時(shí)計(jì)算所有樣本，分別劃到,時(shí)的E值，找出最大的。1、開始時(shí)，,2、分別計(jì)算當(dāng)劃入,時(shí)的E值,把劃入,時(shí)有,然后再把劃入時(shí)對(duì)應(yīng)的E值，找出一個(gè)最大的E值。把劃為的E值最大。,E(1)=56.6,再繼續(xù)進(jìn)行第二，第三次迭代計(jì)算出E(2),E(3),次數(shù)E值156.6279.16390.904102.615120.116137.157154.108176.159195.2610213.0711212.01,第10次迭代劃入時(shí)，E最大。于是分成以下兩類：,每次分類后要重新計(jì)算的值?？捎靡韵逻f推公式：,動(dòng)態(tài)聚類兼顧系統(tǒng)聚類和分解聚類,一、動(dòng)態(tài)聚類的方法概要先選定某種距離作為樣本間的相似性的度量;確定評(píng)價(jià)聚類結(jié)果的準(zhǔn)則函數(shù);給出某種初始分類，用迭代法找出使準(zhǔn)則函數(shù)取極值的最好的聚類結(jié)果。,動(dòng)態(tài)聚類框圖,二、代表點(diǎn)的選取方法：代表點(diǎn)就是初始分類的聚類中心數(shù)k憑經(jīng)驗(yàn)選代表點(diǎn)，根據(jù)問(wèn)題的性質(zhì)、數(shù)據(jù)分布，從直觀上看來(lái)較合理的代表點(diǎn)k;將全部樣本隨機(jī)分成k類，計(jì)算每類重心，把這些重心作為每類的代表點(diǎn);,按密度大小選代表點(diǎn)：以每個(gè)樣本作為球心，以d為半徑做球形;落在球內(nèi)的樣本數(shù)稱為該點(diǎn)的密度，并按密度大小排序。首先選密度最大的作為第一個(gè)代表點(diǎn)，即第一個(gè)聚類中心。再考慮第二大密度點(diǎn)，若第二大密度點(diǎn)距第一代表點(diǎn)的距離大于d1（人為規(guī)定的正數(shù)）則把第二大密度點(diǎn)作為第二代表點(diǎn)，否則不能作為代表點(diǎn)，這樣按密度大小考察下去，所選代表點(diǎn)間的距離都大于d1。d1太小，代表點(diǎn)太多，d1太大，代表點(diǎn)太小，一般選d12d。對(duì)代表點(diǎn)內(nèi)的密度一般要求大于T。T>0為規(guī)定的一個(gè)正數(shù)。用前k個(gè)樣本點(diǎn)作為代表點(diǎn)。,三、初始分類和調(diào)整選一批代表點(diǎn)后，代表點(diǎn)就是聚類中心，計(jì)算其它樣本到聚類中心的距離，把所有樣本歸于最近的聚類中心點(diǎn)，形成初始分類，再重新計(jì)算各聚類中心，稱為成批處理法。選一批代表點(diǎn)后,依次計(jì)算其它樣本的歸類，當(dāng)計(jì)算完第一個(gè)樣本時(shí)，把它歸于最近的一類，形成新的分類。再計(jì)算新的聚類中心，再計(jì)算第二個(gè)樣本到新的聚類中心的距離，對(duì)第二個(gè)樣本歸類。即每個(gè)樣本的歸類都改變一次聚類中心。此法稱為逐個(gè)處理法。直接用樣本進(jìn)行初始分類，先規(guī)定距離d,把第一個(gè)樣品作為第一類的聚類中心，考察第二個(gè)樣本，若第二個(gè)樣本距第一個(gè)聚類中心距離小于d，就把第二個(gè)樣本歸于第一類，否則第二個(gè)樣本就成為第二類的聚類中心，再考慮其它樣本，根據(jù)樣本到聚類中心距離大于還是小于d，決定分裂還是合并。,最佳初始分類。如圖所示，隨著初始分類k的增大，準(zhǔn)則函數(shù)下降很快，經(jīng)過(guò)拐點(diǎn)A后，下降速度減慢。拐點(diǎn)A就是最佳初始分類。,四、C平均算法例：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，數(shù)據(jù)分布如下圖,第一步：令C=2，選初始聚類中心為,第三步：根據(jù)新分成的兩類建立新的聚類中心,第四步：轉(zhuǎn)第二步。第二步：重新計(jì)算到z1(2),z2(2)的距離，把它們歸為最近聚類中心，重新分為兩類，,第三步，更新聚類中心,第四步，第二步，第三步，更新聚類中心,迭代自組織數(shù)據(jù)分析算法（ISOData）,方法步驟（1）任選初始值（中心），C個(gè)（2）將N個(gè)樣本分到C類中（3）計(jì)算距離：（4）要求對(duì)中心分裂，合并新的中心（5）判斷。,上機(jī)作業(yè),已知50個(gè)樣本（隨機(jī)產(chǎn)生），每個(gè)樣本2個(gè)特征（取值在010），數(shù)據(jù)如下：用c平均算法和ISODATA算法分類，編程上機(jī)，并畫出分類圖。,