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

章距離分類器和

聚類分析

2021/5/912.1距離分類器一、模式的距離度量2021/5/92距離函數(shù)應(yīng)滿足的條件對稱性：非負(fù)性：三角不等式：2021/5/93常用的距離函數(shù)歐幾里德距離：(EucideanDistance)2021/5/94常用的距離函數(shù)街市距離：(ManhattanDistance)2021/5/95常用的距離函數(shù)明氏距離：(MinkowskiDistance)2021/5/96常用的距離函數(shù)角度相似函數(shù)：(AngleDistance)是X與Y之間的內(nèi)積為矢量X的長度，也稱為范數(shù)

2021/5/97二、單個標(biāo)準(zhǔn)樣本距離分類器M個類別：每個類別有一個標(biāo)準(zhǔn)樣本：對待識樣本X進(jìn)行分類。2021/5/98建立分類準(zhǔn)則如果有：則判別：2021/5/99距離分類器2021/5/910三、多標(biāo)準(zhǔn)樣本的距離分類器M個類別：第m個類別有訓(xùn)練樣本集合：對待識樣本X進(jìn)行分類。2021/5/911多標(biāo)準(zhǔn)樣本的距離分類器平均樣本法 對每一類求一個標(biāo)準(zhǔn)樣本T(m)，使T(m)到所有訓(xùn)練樣本的平均距離最?。?021/5/912平均樣本法的特點(diǎn)算法簡單存儲量小計算量小效果不一定很好2021/5/913平均距離法

已知Ωi類有訓(xùn)練樣本集：

定義待識模式X與類別Ωi的距離：2021/5/914最近鄰法

待識模式X與類別Ωi的距離：2021/5/915最近鄰法的改進(jìn)平均樣本法：用一點(diǎn)代表一個類別，過于集中；最近鄰法：以類內(nèi)的每一點(diǎn)代表類別，過于分散；改進(jìn)最近鄰法：將每個類別的訓(xùn)練樣本劃分為幾個子集，以子集的平均樣本作為代表樣本。2021/5/916K-近鄰法計算X與所有訓(xùn)練樣本的距離；對所計算出的距離從小到大排序；統(tǒng)計前K個中各類樣本的個數(shù)Ni；如果： 則判別：2021/5/9172.2聚類分析簡單聚類法系統(tǒng)聚類法動態(tài)聚類法2021/5/918簡單聚類法（試探法）最近鄰規(guī)則的簡單試探法最大最小距離算法2021/5/919最近鄰規(guī)則的簡單試探法

已知：N個待分類模式{X1，X2，…，XN}，閾值T(每個樣本到其聚類中心的最大距離)，分類到Ω1，Ω2，…，類別中心為Z1，Z2，…2021/5/920最近鄰規(guī)則的簡單試探法第一步：取任意的樣本作為第一個聚類中 心，Z1=X1； 計算D21=||X2-Z1||； 如果D21>T，則增加新類別：Z1=X1； 否則，X2歸入Ω1類，重新計算：

Z1=(X1+X2)/22021/5/921最近鄰規(guī)則的簡單試探法第二步：設(shè)已有M個類別，加入樣本Xk

計算Dk1=||Xk-Z1||，Dk2=||Xk-Z2||…； 如果Dki>T，則增加新類別ΩM+1 ZM+1=Xk； 否則，Xk歸入最近的一類，重新計算該 類的聚類中心：2021/5/922最大最小距離算法基本思路：以最大距離原則選取新的聚類中心，以最小距離原則進(jìn)行模式歸類；已知：N個待識模式{X1，X2，…，XN}，閾值比例系數(shù)θ。2021/5/923最大最小距離算法任選樣本作為第一個聚類中心Z1；從樣本集中選擇距離Z1最遠(yuǎn)的樣本Xi作為第二個聚類中心，Z2=Xi，設(shè)定閾值：T=θ||Z1-Z2||；2021/5/924最大最小距離算法計算未被作為聚類中心的各樣本Xi與Z1，Z2之間的距離，以其中的最小值作為該樣本的距離di；若di>T，將Xi作為第3個聚類中心，Z3=Xi，轉(zhuǎn)3；否則，轉(zhuǎn)5按照最小距離原則，將所有樣本分到各類別中。

2021/5/925系統(tǒng)聚類法基本思路：首先每一個樣本自成一類，然后按照距離準(zhǔn)則逐步合并，類別數(shù)由多到少，達(dá)到合適的類別數(shù)為止。已知：N個待識模式{X1，X2，…，XN}，類別數(shù)M。2021/5/926類與類之間的距離最短距離：最長距離：平均距離：2021/5/927系統(tǒng)聚類算法第一步建立N個初始類別，每個樣本一個類別，計算距離矩陣D=(Dij)；第二步尋找D中的最小元素，合并相應(yīng)的兩個類別，建立新的分類，重新計算距離矩陣D；重復(fù)第二步，直到類別數(shù)為M為止。2021/5/928動態(tài)聚類法基本思想：首先選擇若干個樣本點(diǎn)作為聚類中心，然后各樣本點(diǎn)向各個中心聚集，得到初始分類；判斷初始分類是否合理，如果不合理，則修改聚類中心。包括：K-均值算法，ISODATA算法。2021/5/929K-均值算法(C-均值)第一步：任選K個初始聚類中心；第二步：將每一個待分類樣本分到K個類別