模式識(shí)別第二章_距離分類器

1、第二章 距離分類器和 聚類分析2.1 距離分類器n一、模式的距離度量距離函數(shù)應(yīng)滿足的條件 n對(duì)稱性： ,ddX YY X,0dX Y,dddX YX ZY Zn非負(fù)性： n三角不等式： 常用的距離函數(shù)n歐幾里德距離：(Eucidean Distance) 1221,niiidxyX Y常用的距離函數(shù)n街市距離：(Manhattan Distance)1,niiidxyX Y常用的距離函數(shù)n明氏距離：(Minkowski Distance) 11,mnmiiidxyX Y常用的距離函數(shù)n角度相似函數(shù)：(Angle Distance) ,TdXYX YXY1nTiiix yXY是X與Y之間的內(nèi)積X

2、為矢量X的長(zhǎng)度，也稱為范數(shù) 二、單個(gè)標(biāo)準(zhǔn)樣本距離分類器M個(gè)類別：12,M 每個(gè)類別有一個(gè)標(biāo)準(zhǔn)樣本：12MT,T ,T對(duì)待識(shí)樣本X進(jìn)行分類。建立分類準(zhǔn)則如果有：0argmin,iiidX T則判別：0iX距離分類器三、多標(biāo)準(zhǔn)樣本的距離分類器 M個(gè)類別：12,M 第m個(gè)類別有訓(xùn)練樣本集合：對(duì)待識(shí)樣本X進(jìn)行分類。 12,mmmmKXXX多標(biāo)準(zhǔn)樣本的距離分類器n平均樣本法對(duì)每一類求一個(gè)標(biāo)準(zhǔn)樣本T(m)，使T(m)到所有訓(xùn)練樣本的平均距離最小： 11mKmmiimKTX平均樣本法的特點(diǎn)n算法簡(jiǎn)單n存儲(chǔ)量小n計(jì)算量小n效果不一定很好平均距離法已知i類有訓(xùn)練樣本集：定義待識(shí)模式X與類別i的距離： 12,ii

3、iiKTTT 11,iKiijjiddKXX T最近鄰法待識(shí)模式X與類別i的距離： 1,min,iiijj Kdd XX T最近鄰法的改進(jìn)n平均樣本法：用一點(diǎn)代表一個(gè)類別，過于集中； n最近鄰法：以類內(nèi)的每一點(diǎn)代表類別，過于分散；n改進(jìn)最近鄰法：將每個(gè)類別的訓(xùn)練樣本劃分為幾個(gè)子集，以子集的平均樣本作為代表樣本。 K-近鄰法n計(jì)算X與所有訓(xùn)練樣本的距離；n對(duì)所計(jì)算出的距離從小到大排序；n統(tǒng)計(jì)前K個(gè)中各類樣本的個(gè)數(shù)Ni；n如果：n則判別：01argmaxii MiN 0iX2.2 聚類分析聚類分析n簡(jiǎn)單聚類法 n系統(tǒng)聚類法 n動(dòng)態(tài)聚類法 簡(jiǎn)單聚類法（試探法） n最近鄰規(guī)則的簡(jiǎn)單試探法n最大最小距離

4、算法最近鄰規(guī)則的簡(jiǎn)單試探法已知：N個(gè)待分類模式X1，X2，XN，閾值T(每個(gè)樣本到其聚類中心的最大距離)，分類到1，2，類別中心為Z1，Z2，最近鄰規(guī)則的簡(jiǎn)單試探法第一步：取任意的樣本作為第一個(gè)聚類中 心， Z1=X1； 計(jì)算D21=|X2-Z1|； 如果D21 T，則增加新類別： Z1=X1； 否則，X2歸入1類，重新計(jì)算： Z1=(X1+ X2)/2最近鄰規(guī)則的簡(jiǎn)單試探法第二步：設(shè)已有M個(gè)類別，加入樣本Xk 計(jì)算Dk1=|Xk-Z1|，Dk2=|Xk-Z2|； 如果Dki T，則增加新類別M+1 ZM+1=Xk； 否則，Xk歸入最近的一類，重新計(jì)算該類的聚類中心：最大最小距離算法n基本思路

5、基本思路：以最大距離原則選取新的聚類中心，以最小距離原則進(jìn)行模式歸類；n已知已知：N個(gè)待識(shí)模式X1，X2，XN，閾值比例系數(shù)。最大最小距離算法n任選樣本作為第一個(gè)聚類中心Z1；n從樣本集中選擇距離Z1最遠(yuǎn)的樣本Xi作為第二個(gè)聚類中心， Z2= Xi，設(shè)定閾值：T= |Z1- Z2|；最大最小距離算法n計(jì)算未被作為聚類中心的各樣本Xi與Z1， Z2之間的距離，以其中的最小值作為該樣本的距離di；n若di T，將Xi作為第3個(gè)聚類中心， Z3= Xi，轉(zhuǎn)3；否則，轉(zhuǎn)5n按照最小距離原則，將所有樣本分到各類別中。 系統(tǒng)聚類法n基本思路基本思路：首先每一個(gè)樣本自成一類，然后按照距離準(zhǔn)則逐步合并，類別數(shù)

6、由多到少，達(dá)到合適的類別數(shù)為止。n已知已知：N個(gè)待識(shí)模式X1，X2，XN，類別數(shù)M。類與類之間的距離n最短距離： min,ijijlkDdXXn最長(zhǎng)距離： max,ijijlkDdXXn平均距離： 21,ijijlkijDdN NXX系統(tǒng)聚類算法n第一步 建立N個(gè)初始類別，每個(gè)樣本一個(gè)類別，計(jì)算距離矩陣D=(Dij)；n第二步 尋找D中的最小元素，合并相應(yīng)的兩個(gè)類別，建立新的分類，重新計(jì)算距離矩陣D；n重復(fù)第二步，直到類別數(shù)為M為止。動(dòng)態(tài)聚類法n基本思想基本思想：首先選擇若干個(gè)樣本點(diǎn)作為聚類中心，然后各樣本點(diǎn)向各個(gè)中心聚集，得到初始分類；判斷初始分類是否合理，如果不合理，則修改聚類中心。n包括包括：K-均值算法，ISODATA算法。K-均值算法(C-均值)n第一步：任選K個(gè)初始聚類中心；n第二步：將每一個(gè)待分類樣本分到K個(gè)類別中去；n第三步：計(jì)算各類的聚類中心；n第四步：檢驗(yàn)新的聚類