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

第2章

距離分類器2.1.1

距離分類器的一般形式將待識(shí)別樣本x分類到與其最相似的類別中輸入：需要識(shí)別的樣本x

；計(jì)算x與所有類別的相似度s

(x,wi，i

=

1,,c

；輸出：相似度最大的類別w

jj

=

arg

max

s

(x,wi1￡i￡c關(guān)鍵問題：如何度量樣本x與類別wi

的相似程度？2.1.2

模板匹配用“距離”度量樣本之間的相似度wi

fi

μi每個(gè)類別的“先驗(yàn)知識(shí)”就是一個(gè)樣本（模板μ）is

(x,wi=

s

(x,μi利用x與模板μi的相似度，作為x與類別wi

的相似度(

)2di

ix

-

mi

=1s

(x,

μ

=

-d

(x,

μ=-

x

-

μ

=

-2歐氏距離2.1.2

模板匹配?2矢量的“l(fā)2

范數(shù)”——矢量的長度2x

-

μ12x

-

μ22x

-

μc差矢量x

-μ

的l2范數(shù)——兩個(gè)點(diǎn)之間的歐氏距離模板匹配過程：j

=arg

min

d

(x,μi1￡i￡c2.1.2

模板匹配——判別界面c個(gè)模板將特征空間劃分成了c個(gè)區(qū)域兩個(gè)區(qū)域的交界稱為

“判別界面”2.1.3

最近鄰分類器每一個(gè)類別有多個(gè)訓(xùn)練樣本

{}1(i

)(i

)iniD

=

x

,,x類別i

=

1,,

c.

：第i類訓(xùn)練樣本個(gè)數(shù)ni樣本x與類別

wi

之間相似程度：y?

Dis

(x,wi=

-min

d

(x,

y2.1.3

最近鄰分類器2.1.3

最近鄰分類器-Voronoi網(wǎng)格2.1.3

最近鄰分類器-Matlab實(shí)現(xiàn)2.1.3

最近鄰分類器——特點(diǎn)分析訓(xùn)練樣本數(shù)量較多時(shí)效果良好。計(jì)算量大：每次識(shí)別時(shí)需要同所有訓(xùn)練樣本計(jì)算距離占用存儲(chǔ)空間大：需要保存所有的訓(xùn)練樣本，也比較易受樣本噪聲影響：最近鄰算法只依賴最近訓(xùn)練樣本，當(dāng)訓(xùn)練樣本某些特征有偏差、或者標(biāo)注錯(cuò)誤，導(dǎo)致錯(cuò)誤2.1.4

最近鄰分類器的加速轉(zhuǎn)化為單模板匹配用每個(gè)類別的訓(xùn)練樣本學(xué)習(xí)出一個(gè)模板μ問題：什么樣的μi最適合作為代表模板？模型：(

)(

)思路：距離訓(xùn)練樣本距離都比較近的點(diǎn)。niiikk

=1μ

=

arg

minμ?

Rdd

x

,μ求解：(

)2nii(i

)kk

=1

J

μ

=x-

μμi

=

arg

min

Ji

(μμ?

Rd歐氏距離誤差平方和準(zhǔn)則準(zhǔn)則函數(shù)何處取得極值？1）構(gòu)造準(zhǔn)則函數(shù)：2）最優(yōu)化：(

)(

)(2ni

niti(i

)k(i

)k(i

)k

J

μ

=x-

μ

=x-

μ

x-

μ

)(

)(

)niniii(i

)k(i

)k==

0k

=1k

=1?J

(μ

)Ji

(μ

)=2

x-

μ-1

=

2n

μ

-

2x?μ1nii(i

)kni

k

=1μ

=x2.1.4

最近鄰分類器的加速轉(zhuǎn)化為單模板匹配誤差平方和準(zhǔn)則函數(shù)：極值點(diǎn)導(dǎo)數(shù)為0：k

=1

范數(shù)的平方k

=1

內(nèi)積結(jié)論：計(jì)算每個(gè)類別訓(xùn)練樣本的均值作為匹配模板x

=

xt

xfunction

[Templates

Labels]

=

OneTemplateTrain(

X,

T

)n=size(X,1);

%樣本數(shù)Labels

=

unique(

T

);c=length(Labels);

%類別樹dim=size(X,2);

%特征維數(shù)

Templates=zeros(c,dim);for

i

=1:cid

=

find(T==Labels(i));Templates(i,:)

=

mean(X(id,:));end2.1.4

最近鄰分類器的加速單模板匹配——訓(xùn)練訓(xùn)練樣本矩陣（n×d）對應(yīng)樣本的類別標(biāo)簽（n×1）學(xué)習(xí)的模板（c×d）模板對應(yīng)的類別標(biāo)簽（c×1）function

Out

=

OneTemplatesClassify(

X,

Templates,

Labels

)Dist

=

pdist2(X,Templates);[y,id]

=

min(Dist,[],2);Out

=

Labels(id);2.1.4

最近鄰分類器的加速模板矩陣（c×d）單模板匹配——識(shí)別樣本矩陣(m×d)模板對應(yīng)的類別標(biāo)簽（c×1）分類結(jié)果（m×1）function

Out

=

OneTemplatesClassify(

X,

Templates,

Labels

)Dist

=

pdist2(X,Templates);[y,id]

=

min(Dist,[],2);Out

=

Labels(id);2.1.4

最近鄰分類器的加速模板矩陣（c×d）單模板匹配——識(shí)別樣本矩陣(m×d)模板對應(yīng)的類別標(biāo)簽（c×1）分類結(jié)果（m×1）2.1.4

最近鄰分類器的加速從“單模板”到“多模板”w12w1w關(guān)鍵問題：高維特征空間如何劃分？——聚類分析1w12w

21w

22w1w

322.1.4

最近鄰分類器的加速使用一個(gè)或多個(gè)模板能夠提高計(jì)算效率——減少匹配次數(shù)不能保證準(zhǔn)確率——改變了分類面形狀近鄰剪輯去掉對分類面“無用”的點(diǎn)——不改變分類面形狀2.1.5K-近鄰分類器最近鄰只依據(jù)距離最近的“一個(gè)”樣本的類別一個(gè)噪聲樣本就將導(dǎo)致一片錯(cuò)誤分類區(qū)域k-近鄰由距離最近的“K個(gè)”樣本投票來決定xx尋找樣本x最近的k=7個(gè)樣本投票6:1，正確識(shí)別function

output

=

KNNClassify(

X,

S,

T,K

)Labels

=

unique(

T

);c=length(Labels);

%類別數(shù)

m=size(X,1);%樣本數(shù)

Dist=pdist2(X,S);[y,id]

=

sort(

Dist,2,'ascend'

);k=zeros(c,m);

%記錄K近鄰中包含各類的樣本數(shù)

if

m==1for

i

=

1:ck(i)

=

sum(T(id(:,1:K))==Labels(i));endelsefor

i

=

1:ck(i,:)

=

sum(T(id(:,1:K))==Labels(i),2);endend[y,j]

=

max(k);output

=

Labels(j);X--識(shí)別樣本(m×d)S--訓(xùn)練樣本矩陣(n×d)T--樣本的類別標(biāo)號(hào)(n×1)K--算法參數(shù)2.1.5

K-近鄰分類器——特點(diǎn)K的選擇K值選擇的過小，算法的性能接近于最近鄰分類；K值選擇的過大，距離較遠(yuǎn)的樣本也會(huì)對分類結(jié)果產(chǎn)生作用，這樣也會(huì)引起分類誤差。適合的K值需要根據(jù)具體問題來確定。非平衡樣本集(某一類樣本數(shù)量很大，而其它類別樣本的數(shù)量相對較少)樣本數(shù)多的類別總是占優(yōu)勢計(jì)算量需要與每一個(gè)訓(xùn)練樣本計(jì)算距離。尋找與其最相近K個(gè)樣本?？焖俨檎?？先排序再查找——K-D樹2.1.5

從“排序查找”到“K-D樹”1維特征：排序查找訓(xùn)練樣本集：n個(gè)實(shí)數(shù)構(gòu)成的集合D待測樣本：給定實(shí)數(shù)x分類：D中尋找到與x最相近的K個(gè)數(shù)?！瓤焖倥判颍僬郯氩檎叶嗑S特征：K-D樹K-D樹構(gòu)建：用樹形結(jié)構(gòu)使得訓(xùn)練樣本有序化K-D樹搜索：有序結(jié)構(gòu)中快速查找與輸入最相近的樣本——基于排序查找思想，方法相對復(fù)雜2.1.5

最近鄰K-D樹1）K-D樹構(gòu)建：用樹形結(jié)構(gòu)使得訓(xùn)練樣本有序化1)計(jì)算得到方差最大的第s維特征2)根據(jù)第s維特征，對D升排序3)

選擇中間樣本為根節(jié)點(diǎn)、記錄s小于根節(jié)點(diǎn)放入左子集DL大于根節(jié)點(diǎn)放入右子集DR4)DL、DR遞歸建樹，得到K-D樹s

2

=

7.5714,s

2

=

3.90481

2s

=1(第1維特征)算法：輸入：訓(xùn)練樣本集D；舉例：{(3,

7)t

,(3,

4)t

,(1,

2)t

,(4,

2)t

,(6,1)t

,(7,

4)t

,(9,

3)t

}{(1,

2)t

,(3,

7)t

,(3,

4)t

,(4,

2)t

(6,1)t

,(7,

4)t

,(9,3)t

}根節(jié)點(diǎn)DLDR2）K-D樹搜索：有序結(jié)構(gòu)中快速查找2-1

深度優(yōu)先搜索，確定x所子區(qū)域以x

=(7,1.5)t

為例

首先與根節(jié)點(diǎn)比較，第1維特征大于4進(jìn)入右子樹與(9,3)t

第2維特征比較，進(jìn)入左子樹經(jīng)過3次比較，x處于右下角區(qū)域每次在與節(jié)點(diǎn)比較時(shí)，計(jì)算x與節(jié)點(diǎn)的距離，保存距離最近者3次比較后(7,1.5)t

的最近節(jié)點(diǎn)為(6,1)t最近節(jié)點(diǎn)就是最近鄰嗎？2.1.5

最近鄰K-D樹2.1.5

最近鄰K-D樹2）K-D樹搜索：有序結(jié)構(gòu)中快速查找深度優(yōu)先搜索到的最近節(jié)點(diǎn)，不一定是最近鄰，需要回溯搜索(7,2.5)t

畫圓，與(9.3)節(jié)點(diǎn)相交最近鄰點(diǎn)可能存在于上半?yún)^(qū)域回溯搜索右子樹(7,1.5)畫圓，與(9.3)節(jié)點(diǎn)不相交最近鄰點(diǎn)只存在于下方區(qū)域不需搜索右子樹O(log

n)2.1.5

最近鄰K-D樹2）K-D樹搜索：有序結(jié)構(gòu)中快速查找2-2回溯搜索，確定最近鄰以待測點(diǎn)為圓心、最近鄰距離為半徑畫圓回溯到上層節(jié)點(diǎn)當(dāng)最小距離圓與節(jié)點(diǎn)的分割線相交時(shí)，搜索另一半子樹2.2距離和相似性度量——街區(qū)距離

——切比雪夫距離世界上最遙遠(yuǎn)的距離，不是生與死，而是我就站在你面前，你卻不知道我愛你。世界上最遙遠(yuǎn)的距離，不是我就站在你面前你卻不知道我愛你，而是明明知道彼此相愛，卻又不能在一起；——泰戈?duì)枺凑皇菤W氏距離“距離”有很多種，如何選擇？如何定義？d

(x,

y

?

0d

(x,

y

=

d

(y,

xd

(x,

y

￡

d

(x,

z

+

d

(y,

z非負(fù)性：對稱性：自反性：三角不等式：d

(x,

y=0,當(dāng)且僅當(dāng)x

=y2.2.1

距離度量對于任意一個(gè)定義在兩個(gè)矢量x和y上的函數(shù)d

(x,y只要滿足如下4個(gè)性質(zhì)就可以稱作“距離度量”：11n2

2

i=1

=

(xi

-

yi

)

常用的距離函數(shù)歐氏距離：(Eucidean

Distance)d

(x,

y

=

x

-

y

2=

(x

-

y

)t

(x

-

y

)

2nti

ix

yi=1x

y

=是x與y之間的內(nèi)積2矢量的l

范數(shù)n=

xi

-

yii=1常用的距離函數(shù)街市距離：（Manhattan/city

block/taxicab

distance）d

(x,

y

=

x

-

y

1矢量的l1范數(shù)常用的距離函數(shù)切比雪夫距離：（Chebyshev

Distance）d

(x,

y

=

x

-

y

￥=

max

xi

-

yi1￡i￡d常用的距離函數(shù)閔可夫斯基距離（Minkowski

Distance）q

=1:街市距離q=2:歐氏距離q

=￥

:切比雪夫距離1n

q

q

i=1d

(x,

y

)=

xi

-

yi閔氏距離具有平移不變性旋轉(zhuǎn)

僅當(dāng)

q

=

2

時(shí)，具有旋轉(zhuǎn)不變性d

(x,0

=1特征量綱的影響（縮放坐標(biāo)軸）樣本規(guī)格化樣本規(guī)格化ijj

max

j

minxij

-

x

j

minx￠=x

-

x使樣本每一維特征都分布在相同或相似的范圍內(nèi)，計(jì)算距離度量時(shí)每一維特征上的差異都會(huì)得到相同的體現(xiàn)方法1-均勻縮放：假設(shè)各維特征服從均勻分布將 每一維特征都平移和縮放到[0,1]內(nèi)計(jì)算樣本集每一維特征的最大、最小值x

j

min

=

min

xij，xj

max

=

max

xij，j

=1,,

d1￡i￡n

1￡i￡n平移和縮放樣本的每一維特征：，i

=1,,

n，j

=1,,

d使樣本每一維特征都分布在相同或相似的范圍內(nèi)，計(jì)算距離度量時(shí)每一維特征上的差異都會(huì)得到相同的體現(xiàn)方法2-高斯縮放：假設(shè)每一維特征都符合高斯分布，平移、縮放為標(biāo)準(zhǔn)高斯分布樣本規(guī)格化(

)2nnjij

jij

jijj1n1nsi=1m

=x

-

mx

-

mx￠=i=11）計(jì)算每一維特征的均值和標(biāo)準(zhǔn)差：xij，s

j

=，j

=1,,

d2）規(guī)格化每一維特征：，i

=1,,

n，j

=1,,

d進(jìn)一步考慮各維特

征間的協(xié)方差關(guān)系？——馬氏距離克服量綱影響體現(xiàn)不同特征重要性樣本規(guī)格化，可以看做加權(quán)距離的特例：加權(quán)距離(

)(

)1djj

jjw

x2

2

j

=1加權(quán)歐氏距離：d

x,

y

=-

y

，w

?

0()21ijjj

max

j

minj

maxj

minxij

-

x

j

minfi

w

=x

-

xx

-

x均勻縮放：x￠

=ijjjijjjss2x

-

mx￠=

1fi=高斯縮放：w關(guān)鍵問題：計(jì)算距離時(shí)為“不同特征”引入“不同權(quán)重”如何確定每一維特征的權(quán)重漢明距離（Hamming

Distance）二值矢量計(jì)算兩個(gè)矢量對應(yīng)位置元素不同的數(shù)量(

)(

)2dj

jx

-

yd

x,

y

=x,y

?

{0,1}d（每個(gè)元素只取0或1

）j

=1例：x

=(1,1,0,0,1,1,1)t

，y

=(1,0,0,0,0,0,1)td

(x,

y

)=32.2.2相似性度量衡量相似度，不一定需要距離，可以選擇更直接的方法衡量相似度兩向量的夾角——角度相似性相關(guān)系數(shù)相似性度量隨著樣本間相似程度的增加而增大，距離則是隨著相似程度的增加而減小。為了保持一致性可以將相似度和距離進(jìn)行轉(zhuǎn)換：d

(x,

y

=

1

-

s

(x,

y角度相似性當(dāng)兩個(gè)樣本之間的相似程度只與它們之間的夾角有關(guān)、與矢量的長度無關(guān)時(shí)，可以使用矢量夾角的余弦來度量相似性。dd

diix

2

y

2=

i

=1

xi

yii

=1i

=1x

t

ys

(x

,

y

)=

cos

q

xy

=x

y將向量歸一為單位向量后做內(nèi)積。相關(guān)系數(shù)將矢量x、y視為兩個(gè)一維信號(hào)(

)(

)(

)(

)22td

di

xii

yii=1=

i=1

x

-

my

-

m(xi

-

mxi

)(yi

-

myi

)i=1xyx

-

μy

-

μs

(x,y

)=x

-

μxy

-

μy認(rèn)為矢量x、y分別來自于兩個(gè)樣本集樣本集的均值分別為μx，μy，相關(guān)系數(shù)定義為：d(

)(

)(

)(

)22ddxiyidtxyd

di

xi

y1d1di=1

i=1m

=m

==

i=1

x

-my

-mi=1i=1(xi

-mx

)(yi

-my

)

x

-m

e y

-m

es(x,y)=x

-mxey

-myex，y，e：所有元素均為1的d維矢量2.2.3

Matlab實(shí)現(xiàn)knnclassify（Bioinformatics

Toolbox

K-近鄰算法分類函數(shù)）Class

=

knnclassify(

Sample,

Training,

Group,

k,

distance,

rule

)參數(shù)：Sample--m×d矩陣；

Training--n×d矩陣；Group--n×1矩陣，與Training每一行對應(yīng)的類別標(biāo)簽；

k--K-近鄰算法參數(shù)，缺省為1（最近鄰算法）；distance

--

距離度量參數(shù)

euclidean

:

歐幾里得距離度量；cityblock：街市距離度量；

hamming：漢明距離度量；cosine：角度相似性度量，correlation： 相關(guān)系數(shù)；rule--分類參數(shù)；k設(shè)置為偶數(shù)時(shí)，出現(xiàn)票數(shù)相同情況下的處理規(guī)則返回：class--m×1矩陣，對應(yīng)Sample每一行的分類結(jié)果