內(nèi)容提要問題提出：愛情片or動(dòng)作片KNN算法問題求解：愛情片or動(dòng)作片總結(jié)與練習(xí)問題提出：愛情片or動(dòng)作片問題提出愛情片vs

動(dòng)作片問題提出：愛情片or動(dòng)作片問題提出景愛情片動(dòng)作片問題提出：愛情片or動(dòng)作片問題提出鏡頭次數(shù)vs

打斗場(chǎng)景次數(shù)名稱打斗次數(shù)次數(shù)類型California

Man3104RomanceHe’s

Not

Really

into

Dudes2100RomanceBeautiful

Woman181RomanceKevin

Longblade10110ActionRobo

Slayer

3000995ActionAmped

II982Action?1890Unknown問題提出：愛情片or動(dòng)作片200問題提出鏡頭次數(shù)vs

打斗場(chǎng)景次數(shù)1200204060打斗場(chǎng)景次數(shù)80100120KNN（K最近鄰）算法KNN算法KNN(K-Nearest

Neighbor,K最近鄰)算法基于實(shí)例的學(xué)習(xí)方法數(shù)據(jù)挖掘十大經(jīng)典算法之一著名的模式識(shí)別統(tǒng)計(jì)學(xué)方法之一最好的文本分類算法之一KNN算法KNN算法基本思想如果一個(gè)實(shí)例在特征空間

中的K個(gè)最相似（即特征空間中最近鄰）的實(shí)例中的

大多數(shù)屬于某一個(gè)類別，

則該實(shí)例也屬于這個(gè)類別。所選擇的鄰居都是已經(jīng)正

確分類的實(shí)例。少數(shù)服從多數(shù)KNN算法KNN算法基本思想算法分析：算法原理：設(shè)有N個(gè)樣本分布到c個(gè)類為1，…,i，…c，每類有Ni個(gè)樣本，i=1…c。在全部樣本中找出k個(gè)最近距離的近鄰，k個(gè)近鄰分布于c個(gè)類中的數(shù)目用ki表示。k近鄰的判別函數(shù)為：gi

(x)

ki

,KNN算法KNN算法基本思想算法分析：決策規(guī)則：如果g

j

(x)

a為x

j，那么決策如右圖示例中：k1=4，k2=0，k3=1，所以j=1，。ix

1KNN算法KNN算法主要因素實(shí)例集實(shí)例x表示為特征向量<a1(x)，a2(x)，...，an(x)>其中ar(x)表示實(shí)例x的第r個(gè)屬性值。例如：人<

，身高，體重><30,

175,

140>，黃藥師<78,

170,

120>KNN算法KNN算法主要因素距離或相似的衡量(Euclidean)距離【歐式距離】計(jì)算曼哈頓(Manhattan)距離、切比(Chebyshev)距離、明

(Minkowsky)距離等KNN算法KNN算法主要因素K的大小K太小：分類結(jié)果易受噪聲點(diǎn)影響K太大：近鄰中又可能包含太多的其他類別的點(diǎn)K值可采用交叉檢驗(yàn)來確定經(jīng)驗(yàn)規(guī)則：K一般低于訓(xùn)練樣本數(shù)的平方根KNN算法KNN算法描述計(jì)算出樣本數(shù)據(jù)和待分類數(shù)據(jù)的距離為待分類數(shù)據(jù)選擇K個(gè)與其距離最小的樣本統(tǒng)計(jì)出K個(gè)樣本中大多數(shù)樣本所屬的分類判別：確定待分類數(shù)據(jù)所屬的分類KNN算法KNN算法實(shí)現(xiàn)：偽代碼1

搜索k近鄰的算法：kNN(A[n],k)23

#輸入：A[n]為N個(gè)訓(xùn)練樣本在空間中的坐標(biāo)，k為近鄰數(shù)4

#輸出：x所屬的類別56

取A[1]~A[k]作為x的初始近鄰，計(jì)算與測(cè)試樣本x間的歐式距離d(x,A[i]),i=1,2,.....,k；7

按d(x,

A[i])升序排序8

取最遠(yuǎn)樣本距離D=max{d(x,a[j])

|

j=1,2,...,k}910

for(i=k+1;i<=n;i++)#繼續(xù)計(jì)算剩下的n-k個(gè)數(shù)據(jù)的歐氏距離111213計(jì)算A[i]與x間的距離d(x,A[i])if(d(x,A[i]))<Dthen

用A[i]代替最遠(yuǎn)樣本#將后面計(jì)算的數(shù)據(jù)直接進(jìn)行即可14最后的K個(gè)數(shù)據(jù)是有大小順序的，再進(jìn)行K個(gè)樣本的統(tǒng)計(jì)即可計(jì)算前k個(gè)樣本A[i](i=1,2,..,k)所屬類別的概率具有最大概率的類別即為樣本x的類問題求解：愛情片or動(dòng)作片問題求解距離計(jì)算（歐式距離）2ba11

bK值選取按照經(jīng)驗(yàn)規(guī)則選取K值k

6

≈

2問題求解：愛情片or動(dòng)作片問題求解計(jì)算結(jié)果名稱類別與未知

的距離California

ManRomance20.5He’s

Not

Really

into

DudesRomance18.7Beautiful

WomanRomance19.2Kevin

LongbladeAction115.3Robo

Slayer

3000Action117.4Amped

IIAction118.9問題求解：愛情片or動(dòng)作片問題求解分類決策（判別）K=2No1:

18.7

--

He’s

Not

Really

into

Dudes

–

RomanceNo2:

19.2

--

Beautiful

Woman

--

Romance名稱打斗次數(shù)次數(shù)類型?1890Romance總結(jié)與練習(xí)總結(jié)優(yōu)點(diǎn)：易于理解，易于實(shí)現(xiàn)，無需訓(xùn)練精度高，對(duì)個(gè)別異常值不敏感缺點(diǎn)：計(jì)算量較大，空間開銷較大總結(jié)與練習(xí)擴(kuò)展學(xué)習(xí)利用KNN算法改進(jìn)的配對(duì)效果（MachineLearning

in

Action《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》）-總結(jié)與練習(xí)練習(xí)編程實(shí)現(xiàn)KNN算法，處理品質(zhì)數(shù)據(jù)。

的品