KNN學(xué)習(xí)（K-Nearest Neighbor algorithm，K最鄰近方法）是一種統(tǒng)計(jì)分類(lèi)器，屬于惰性學(xué)習(xí)，對(duì)包容型數(shù)據(jù)的特征變量篩選尤其有效。KNN的基本思想是：輸入沒(méi)有標(biāo)簽即未經(jīng)分類(lèi)的新數(shù)據(jù)，首先提取新數(shù)據(jù)的特征并與測(cè)試集中的每一個(gè)數(shù)據(jù)特征進(jìn)行比較；然后從樣本中提取k個(gè)最鄰近（最相似）數(shù)據(jù)特征的分類(lèi)標(biāo)簽，統(tǒng)計(jì)這K個(gè)最鄰近數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類(lèi)，將其作為新數(shù)據(jù)的類(lèi)別。

一、KNN算法

KNN按一定的規(guī)則，將相似的數(shù)據(jù)樣本進(jìn)行歸類(lèi)。首先，計(jì)算待分類(lèi)數(shù)據(jù)特征與訓(xùn)練數(shù)據(jù)特征之間的距離并排序，取出距離最近的k個(gè)訓(xùn)練數(shù)據(jù)集特征；然后，根據(jù)這k個(gè)相近訓(xùn)練數(shù)據(jù)特征所屬的類(lèi)別來(lái)判定新樣本的類(lèi)別：如果它們都屬于同一類(lèi)，那么新樣本也屬于這一類(lèi)；否則，對(duì)每個(gè)候選類(lèi)別進(jìn)行評(píng)分，按照某種規(guī)則確定新樣本的類(lèi)別。

一般采用投票規(guī)則，即少數(shù)服從多數(shù)，期望的k值是一個(gè)奇數(shù)。精確的投票方法是計(jì)算每一個(gè)測(cè)試樣本與k個(gè)樣本之間的距離。

如下圖小圓形要被歸為哪一類(lèi)，是三角形還是矩形？如果k = 3,由于矩形所占比例為2/3，小圓形將被歸為矩形一類(lèi)；如果k = 9， 由于三角形比例為5/9，因此小圓形被歸為三角形一類(lèi)。

假設(shè)數(shù)據(jù)集為：

這些數(shù)據(jù)分別屬于c種不同類(lèi)別，其中Ni是第i個(gè)分類(lèi)wi的樣本個(gè)數(shù)。對(duì)于一個(gè)待測(cè)數(shù)據(jù)x，分別計(jì)算它與這N個(gè)已知類(lèi)別的樣本的距離，將其判定為距離最近的那個(gè)樣本所屬的類(lèi)。

wi類(lèi)的判決函數(shù)為：

判決規(guī)則為：

上述方法僅根據(jù)距離待識(shí)模式最近的一個(gè)樣本類(lèi)別決定其類(lèi)別，稱(chēng)為最鄰近法或1-鄰近法。

為了克服單個(gè)樣本類(lèi)別的偶然性，增加分類(lèi)的可靠性，可以考察待測(cè)數(shù)據(jù)的k個(gè)最鄰近樣本，統(tǒng)計(jì)這k個(gè)最鄰近樣本屬于哪一類(lèi)別的樣本最多，就將x歸為該類(lèi)。

設(shè)k1, k2, ..., kc分別是x的k個(gè)樣本屬w1, w2, ..., wc的樣本數(shù)，定義wi的判決函數(shù)為：

判決規(guī)則為：

該方法稱(chēng)為k鄰近算法，即KNN學(xué)習(xí)。

在樣本數(shù)有限的情況下，KNN算法的誤判概率和具體測(cè)測(cè)度有直接的關(guān)系，因此在選擇最近樣本數(shù)時(shí)利用適當(dāng)?shù)木嚯x函數(shù)，能夠提高分類(lèi)的正確率。通常KNN可采用Euclidean，Manhattan，Mahalanobis等距離用于計(jì)算。

Euclidean距離為：

Manhattan距離為：

Mahalanobis距離為：

其中，n為輸入特征的維數(shù)，V是x和y所在數(shù)據(jù)集的協(xié)方差函數(shù)。

二、回歸

得到k個(gè)最相似訓(xùn)練數(shù)據(jù)后，求取這些訓(xùn)練數(shù)據(jù)屬性的平均值，并將該平均值作為待處理數(shù)據(jù)的屬性值，這一求取待處理數(shù)據(jù)屬性的過(guò)程被稱(chēng)為KNN學(xué)習(xí)回歸。

進(jìn)一步地，根據(jù)每一個(gè)最相似訓(xùn)練數(shù)據(jù)和待處理數(shù)據(jù)的實(shí)際距離，賦予每一個(gè)最相似訓(xùn)練數(shù)據(jù)不同的權(quán)值，然后再進(jìn)行加權(quán)平均，這樣得到的回歸值更為有效。

三、算法改進(jìn)

KNN學(xué)習(xí)易受噪聲影響，尤其是樣本中孤立點(diǎn)對(duì)分類(lèi)或回歸處理的影響較大。因此通常應(yīng)先對(duì)已知樣本進(jìn)行濾波和篩選，去除掉對(duì)分類(lèi)有干擾的樣本。

1、基于組合分類(lèi)器的KNN改進(jìn)算法

常用的組合分類(lèi)器方法有投票法、非投票法、動(dòng)態(tài)法和靜態(tài)法等，如簡(jiǎn)單投票法中所有的基分類(lèi)器對(duì)分類(lèi)采用相同的權(quán)值；權(quán)值投票法中每個(gè)基分類(lèi)器具有相關(guān)的動(dòng)態(tài)權(quán)重，該權(quán)重可以隨時(shí)間變化。

首先隨機(jī)選擇屬性子集，構(gòu)建多個(gè)k鄰近分類(lèi)器，然后對(duì)未分類(lèi)元組進(jìn)行預(yù)分類(lèi)；最后把分類(lèi)器的分類(lèi)結(jié)果按照投票法進(jìn)行組合，將得票最多的分類(lèi)器結(jié)果作為最終組合鄰近分類(lèi)器的輸出。

2、基于核映射的KNN改進(jìn)算法

將原空間中的樣本x映射到一個(gè)高維空間F中，突出不同類(lèi)別之間的特征差異，使得樣本在核空間中變得線性可分或近似線性可分。

首先，進(jìn)行非線性映射：

然后，在高維的核空間，待分類(lèi)的樣本變?yōu)?#xff0c;任意兩個(gè)樣本和之間的距離為：

其中K(*,*)為核函數(shù)，在此基礎(chǔ)上進(jìn)行KNN分類(lèi)。

3、基于預(yù)聚類(lèi)的KNN改進(jìn)算法

這里定義C為全體數(shù)據(jù)集合，N代表確定的臨近點(diǎn)的集合，I為最近間隔，P為競(jìng)爭(zhēng)點(diǎn)集，即可能成為臨近點(diǎn)的集合。

首先計(jì)算聚類(lèi)后指定點(diǎn)x到每個(gè)聚類(lèi)中心的距離d，如下圖所示，根據(jù)這些距離，離x最近的的聚類(lèi)為C0，下一個(gè)較近的聚類(lèi)為C1，一次類(lèi)推。

然后，將聚類(lèi)C0中的所有點(diǎn)加入到P中，計(jì)算P中所有點(diǎn)與x的距離，將滿足條件的點(diǎn)轉(zhuǎn)移到集合N中，這樣臨近點(diǎn)的搜索區(qū)域就可以被大致定位了。

4、基于超球搜索的KNN改進(jìn)算法

通過(guò)對(duì)特征空間的預(yù)組織，使分類(lèi)在以待分樣本為中心的超球內(nèi)進(jìn)行，超球半徑由0開(kāi)始，逐漸增大至超球內(nèi)包含K個(gè)以上模式樣本為止。超球搜索分為兩個(gè)階段：第一階段為組織階段，將模式空間進(jìn)行有效的劃分和編碼；第二階段為搜索判決階段，找出待識(shí)樣本的K鄰近。

首先將n維模式空間劃分成若干個(gè)體積相等的超立方體（基元超立方體），并依次編碼；然后在以待分樣本為中心的超球體內(nèi)（由若干個(gè)基元超立方體覆蓋）進(jìn)行搜索，逐漸擴(kuò)大超球半徑直至超球內(nèi)包含K個(gè)樣本為止；然后該超球內(nèi)的KNN即為整個(gè)空間內(nèi)的K鄰近。

附KNN算法C語(yǔ)言實(shí)現(xiàn)示例：

#include <stdlib.h> #include <stdio.h> #include <math.h> #define M 4000 #define N 100//定義一個(gè)字符的結(jié)構(gòu)體 struct letter {char c;int array[16];float distance; };//定義訓(xùn)練字符結(jié)構(gòu)體數(shù)組,共有M個(gè)訓(xùn)練樣本 letter letters[M]; //識(shí)別字符類(lèi)數(shù)組，共有N個(gè)對(duì)比樣本 letter nletters[N]; float t;//定義讀取訓(xùn)練文件函數(shù)，將訓(xùn)練樣本從磁盤(pán)文件letter.txt讀入letters[M]數(shù)組中 void Get_from_letters() {FILE *fp;int i,j;fp=fopen("letter.txt","r");for(i=0; i<M; i++){fscanf(fp,"%c ",&letters[i].c);for(j=0; j<16; j++)fscanf(fp,"%d ",&letters[i].array[j]);}fclose(fp); }//定義讀取測(cè)試文件，將測(cè)試樣本從磁盤(pán)文件素描sum1.txt讀入到nletters中 void Get_from_nletters() {int i,j;FILE *fp;fp=fopen("sum.txt","r");for(i=0; i<N; i++){fscanf(fp,"%c ",&nletters[i].c);for(j=0; j<16; j++)fscanf(fp,"%d ",&nletters[i].array[j]);}fclose(fp); }//定義歐式距離函數(shù)，計(jì)算一個(gè)測(cè)試樣本與各個(gè)訓(xùn)練樣本之間的距離 void Distance(letter *p) {int i,j;float s=0.0;for(i=0; i<M; i++){for(j=0; j<16; j++){s+=((letters[i].array[j]-(*p).array[j])*(letters[i].array[j]-(*p).array[j]));}letters[i].distance=sqrt(s);//恢復(fù)到原始值s=0.0;}}//排序函數(shù)將letters距離按由小到大排列 void Sort() {int i,j;letter t;for(i=0; i<M-1; i++){for(j=i+1; j<M; j++){if(letters[i].distance>letters[j].distance){t=letters[i];letters[i]=letters[j];letters[j]=t;}}}}//根據(jù)用戶(hù)輸入的k值，確定分類(lèi) char Knn(int q) {int i,j,max;int array[26];for(i=0; i<26; i++){array[i]=0;}for(i=0; i<q; i++){switch(letters[i].c){case'A':array[0]++;break;case'B':array[1]++;break;case'C':array[2]++;break;case'D':array[3]++;break;case'E':array[4]++;break;case'F':array[5]++;break;case'G':array[6]++;break;case'H':array[7]++;break;case'I':array[8]++;break;case'J':array[9]++;break;case'K':array[10]++;break;case'L':array[11]++;break;case'M':array[12]++;break;case'N':array[13]++;break;case'O':array[14]++;break;case'P':array[15]++;break;case'Q':array[16]++;break;case'R':array[17]++;break;case'S':array[18]++;break;case'T':array[19]++;break;case'U':array[20]++;break;case'V':array[21]++;break;case'W':array[22]++;break;case'X':array[23]++;break;case'Y':array[24]++;break;case'Z':array[25]++;break;}}max=array[0];j=0;for(i=0; i<26; i++){if(array[i]>max){max=array[i];j=i;}}return (char)(j+65); }//主函數(shù) int main() {int i,j,k=0;int m=0,n=0;letter * p;char c;printf("訓(xùn)練樣本為%d\n",M);Get_from_letters();printf("測(cè)試樣本為%d\n",N);Get_from_nletters();printf("請(qǐng)輸入K值：\n");scanf("%d",&k);for(i=0; i<N; i++){p=&nletters[i];Distance(p);Sort();c=Knn(k);if(nletters[i].c==c){printf("該字符屬于%c類(lèi),識(shí)別正確\n",nletters[i].c);m++;}else{printf("該字符屬于%c類(lèi)，識(shí)別錯(cuò)誤\n",nletters[i].c);n++;}printf("%f",letters[0].distance);}printf("正確個(gè)數(shù)為%d",m);printf("錯(cuò)誤個(gè)數(shù)為%d",n);printf("正確率為%f",(float)(m)/N);scanf("%d",&i);return 0; }

2017.11.20

總結(jié)

以上是生活随笔為你收集整理的【Machine Learning】KNN学习算法与C语言实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。