模式識別第二章_距離分類器

1、第二章 距離分類器和 聚類分析2.1 距離分類器n一、模式的距離度量距離函數(shù)應滿足的條件 n對稱性： ,ddX YY X,0dX Y,dddX YX ZY Zn非負性： 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的長度，也稱為范數(shù) 二、單個標準樣本距離分類器M個類別：12,M 每個類別有一個標準樣本：12MT,T ,T對待識樣本X進行分類。建立分類準則如果有：0argmin,iiidX T則判別：0iX距離分類器三、多標準樣本的距離分類器 M個類別：12,M 第m個類別有訓練樣本集合：對待識樣本X進行分類。 12,mmmmKXXX多標準樣本的距離分類器n平均樣本法對每一類求一個標準樣本T(m)，使T(m)到所有訓練樣本的平均距離最小： 11mKmmiimKTX平均樣本法的特點n算法簡單n存儲量小n計算量小n效果不一定很好平均距離法已知i類有訓練樣本集：定義待識模式X與類別i的距離： 12,ii

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

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

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

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