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