KNN分类器
該部分為轉(zhuǎn)載部分
KNN最鄰近規(guī)則，主要應(yīng)用領(lǐng)域是對(duì)未知事物的識(shí)別，即判斷未知事物屬于哪一類(lèi)，判斷思想是，基于歐幾里得定理，判斷未知事物的特征和哪一類(lèi)已知事物的的特征最接近；
K最近鄰(k-Nearest Neighbor，KNN)分類(lèi)算法，是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類(lèi)別，則該樣本也屬于這個(gè)類(lèi)別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類(lèi)的對(duì)象。該方法在定類(lèi)決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類(lèi)別來(lái)決定待分樣本所屬的類(lèi)別。 KNN方法雖然從原理上也依賴(lài)于極限定理，但在類(lèi)別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周?chē)邢薜泥徑臉颖?#xff0c;而不是靠判別類(lèi)域的方法來(lái)確定所屬類(lèi)別的，因此對(duì)于類(lèi)域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。
KNN算法不僅可以用于分類(lèi)，還可以用于回歸。通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比（組合函數(shù)）。
該算法在分類(lèi)時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類(lèi)的樣本容量很大，而其他類(lèi)樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類(lèi)的樣本占多數(shù)。 該算法只計(jì)算“最近的”鄰居樣本，某一類(lèi)的樣本數(shù)量很大，那么或者這類(lèi)樣本并不接近目標(biāo)樣本，或者這類(lèi)樣本很靠近目標(biāo)樣本。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果。可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類(lèi)的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類(lèi)作用不大的樣本。該算法比較適用于樣本容量比較大的類(lèi)域的自動(dòng)分類(lèi)，而那些樣本容量較小的類(lèi)域采用這種算法比較容易產(chǎn)生誤分。
K-NN可以說(shuō)是一種最直接的用來(lái)分類(lèi)未知數(shù)據(jù)的方法。基本通過(guò)下面這張圖跟文字說(shuō)明就可以明白K-NN是干什么的
簡(jiǎn)單來(lái)說(shuō)，K-NN可以看成：有那么一堆你已經(jīng)知道分類(lèi)的數(shù)據(jù)，然后當(dāng)一個(gè)新數(shù)據(jù)進(jìn)入的時(shí)候，就開(kāi)始跟訓(xùn)練數(shù)據(jù)里的每個(gè)點(diǎn)求距離，然后挑離這個(gè)訓(xùn)練數(shù)據(jù)最近的K個(gè)點(diǎn)看看這幾個(gè)點(diǎn)屬于什么類(lèi)型，然后用少數(shù)服從多數(shù)的原則，給新數(shù)據(jù)歸類(lèi)。
?
算法步驟：
step.1---初始化距離為最大值
step.2---計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離dist
step.3---得到目前K個(gè)最臨近樣本中的最大距離maxdist
step.4---如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本
step.5---重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離都算完
step.6---統(tǒng)計(jì)K-最近鄰樣本中每個(gè)類(lèi)標(biāo)號(hào)出現(xiàn)的次數(shù)
step.7---選擇出現(xiàn)頻率最大的類(lèi)標(biāo)號(hào)作為未知樣本的類(lèi)標(biāo)號(hào)
?
?
KNN的matlab簡(jiǎn)單實(shí)現(xiàn)代碼
function target=KNN(in,out,test,k)% in:?????? training samples data,n*d matrix
% out: training samples' class label,n*1
% test:???? testing data
% target:?? class label given by knn
% k:??????? the number of neighbors
ClassLabel=unique(out);
c=length(ClassLabel);
n=size(in,1);
% target=zeros(size(test,1),1);
dist=zeros(size(in,1),1);
for j=1:size(test,1)
??? cnt=zeros(c,1);
??? for i=1:n
??????? dist(i)=norm(in(i,:)-test(j,:));
??? end
??? [d,index]=sort(dist);
??? for i=1:k
??????? ind=find(ClassLabel==out(index(i)));
??????? cnt(ind)=cnt(ind)+1;
??? end
??? [m,ind]=max(cnt);
??? target(j)=ClassLabel(ind);
end
?下面是基于opencv的一個(gè)實(shí)例：
#include "opencv/ml.h"
#include "opencv/highgui.h"#include<iostream>
#include<opencv2\ml\ml.hpp>
#include<opencv2\highgui\highgui.hpp>
using namespace std;
using namespace cv;
int main(int argc, char** argv)
{
//k為分級(jí)，0~9，分類(lèi)完成后，accurency均大于等于5。
const int K = 9;
int i, j, k, accuracy;
float response;
int train_sample_count = 100;
//CvRNG rng_state = cvRNG(-1);
CvRNG rng_state(-1);//整形隨機(jī)數(shù)產(chǎn)生，取-1時(shí)最大值取0xffffffff
CvMat* trainData = cvCreateMat(train_sample_count, 2, CV_32FC1);//數(shù)據(jù)，該處為點(diǎn)坐標(biāo)，為二維數(shù)據(jù)
CvMat* trainClasses = cvCreateMat(train_sample_count, 1, CV_32FC1);//相對(duì)應(yīng)的數(shù)據(jù)分類(lèi)
IplImage* img = cvCreateImage(cvSize(500, 500), 8, 3);
float _sample[2];
CvMat sample = cvMat(1, 2, CV_32FC1, _sample);
cvZero(img);
RNG rng(1);
double a = (double)rng_state;
double b = (int)rng_state;
//cout << a << endl << b << endl;
CvMat trainData1, trainData2, trainClasses1, trainClasses2;
// form the training samples
cvGetRows(trainData, &trainData1, 0, train_sample_count / 2);
cvRandArr(&rng_state, &trainData1, CV_RAND_NORMAL, cvScalar(200, 200), cvScalar(50, 50));
cvShowImage("img1", &trainData1);
//cout << trainData1.cols << endl << trainData1.rows << endl;
cvGetRows(trainData, &trainData2, train_sample_count / 2, train_sample_count);
cvRandArr(&rng_state, &trainData2, CV_RAND_NORMAL, cvScalar(300, 300), cvScalar(50, 50));
cvGetRows(trainClasses, &trainClasses1, 0, train_sample_count / 2);
cvSet(&trainClasses1, cvScalar(1));
cvGetRows(trainClasses, &trainClasses2, train_sample_count / 2, train_sample_count);
cvSet(&trainClasses2, cvScalar(2));
for (int i = 1; i < 101; i++)
{
float* pData=trainData->data.fl + i*trainData->step / 4;
for (int j = 0; j < 2; j++)
{
cout << *(pData + j - trainData->step / 4)<<" ";
}
cout << endl;
}
//Mat img1(trainData);
//Rect roi(0, 0, 1, train_sample_count / 2);
//Mat img=img1(roi);
//cv::imshow("img", img1);
// learn classifier
CvKNearest knn(trainData, trainClasses, 0, false, K);//訓(xùn)練完成
CvMat* nearests = cvCreateMat(1, K, CV_32FC1);
for (i = 0; i < img->height; i++)
{
for (j = 0; j < img->width; j++)
{
sample.data.fl[0] = (float)j;
sample.data.fl[1] = (float)i;
// estimates the response and get the neighbors' labels
response = knn.find_nearest(&sample, K, 0, 0, nearests, 0);
// compute the number of neighbors representing the majority
for (k = 0, accuracy = 0; k < K; k++)
{
if (nearests->data.fl[k] == response)
accuracy++;
}
// highlight the pixel depending on the accuracy (or confidence)
/*
cvSet2D(img, i, j, response == 1 ?
(accuracy > 5 ? CV_RGB(180, 0, 0) : CV_RGB(180, 120, 0)) :
(accuracy > 5 ? CV_RGB(0, 180, 0) : CV_RGB(120, 120, 0)));
*/
if (accuracy < 6)
{
//cout << response << " "<<accuracy<<endl;
}
cvSet2D(img, i, j, response == 1 ? CV_RGB(accuracy * 25, 0, 255 - accuracy * 25) : CV_RGB(255 - accuracy * 25, 0, accuracy * 25));
}
}
cvShowImage("result", img);
// display the original training samples
for (i = 0; i < train_sample_count / 2; i++)
{
CvPoint pt;
pt.x = cvRound(trainData1.data.fl[i * 2]);
pt.y = cvRound(trainData1.data.fl[i * 2 + 1]);
cvCircle(img, pt, 2, CV_RGB(255, 0, 0), CV_FILLED);
pt.x = cvRound(trainData2.data.fl[i * 2]);
pt.y = cvRound(trainData2.data.fl[i * 2 + 1]);
cvCircle(img, pt, 2, CV_RGB(0, 255, 0), CV_FILLED);
}
cvNamedWindow("classifier result", 1);
cvShowImage("classifier result", img);
cvWaitKey(0);
cvReleaseMat(&trainClasses);
cvReleaseMat(&trainData);
return 0;
}
總結(jié)
- 上一篇： 有关opencv光流法的解释
- 下一篇： 运动分析和对象跟踪