K-近邻(K-Nearest Neighbors, KNN)是一种很好理解的分类算法,简单说来就是从训练样本中找出K个与其最相近的样本,然后看这K个样本中哪个类别的样本多,则待判定的值(或说抽样)就属于这个类别。
KNN算法的步骤
- 计算已知类别数据集中每个点与当前点的距离;
- 选取与当前点距离最小的K个点;
- 统计前K个点中每个类别的样本出现的频率;
- 返回前K个点出现频率最高的类别作为当前点的预测分类。
OpenCV中使用CvKNearest
OpenCV中实现CvKNearest类可以实现简单的KNN训练和预测。
int main()
{
float labels[10] = {0,0,0,0,0,1,1,1,1,1};
Mat labelsMat(10, 1, CV_32FC1, labels);
cout<<labelsMat<<endl;
float trainingData[10][2];
srand(time(0));
for(int i=0;i<5;i++){
trainingData[i][0] = rand()%255+1;
trainingData[i][1] = rand()%255+1;
trainingData[i+5][0] = rand()%255+255;
trainingData[i+5][1] = rand()%255+255;
}
Mat trainingDataMat(10, 2, CV_32FC1, trainingData);
cout<<trainingDataMat<<endl;
CvKNearest knn;
knn.train(trainingDataMat,labelsMat,Mat(), false, 2 );
// Data for visual representation
int width = 512, height = 512;
Mat image = Mat::zeros(height, width, CV_8UC3);
Vec3b green(0,255,0), blue (255,0,0);
for (int i = 0; i < image.rows; ++i){
for (int j = 0; j < image.cols; ++j){
const Mat sampleMat = (Mat_<float>(1,2) << i,j);
Mat response;
float result = knn.find_nearest(sampleMat,1);
if (result !=0){
image.at<Vec3b>(j, i) = green;
}
else
image.at<Vec3b>(j, i) = blue;
}
}
// Show the training data
for(int i=0;i<5;i++){
circle( image, Point(trainingData[i][0], trainingData[i][1]),
5, Scalar( 0, 0, 0), -1, 8);
circle( image, Point(trainingData[i+5][0], trainingData[i+5][1]),
5, Scalar(255, 255, 255), -1, 8);
}
imshow("KNN Simple Example", image); // show it to the user
waitKey(10000);
}
使用的是之前
BP神经网络中的例子,分类结果如下:
预测函数find_nearest()除了输入sample参数外还有些其他的参数:
float CvKNearest::find_nearest(const Mat& samples, int k, Mat* results=0,
const float** neighbors=0, Mat* neighborResponses=0, Mat* dist=0 )
即,samples为样本数*特征数的浮点矩阵;K为寻找最近点的个数;results与预测结果;neibhbors为k*样本数的指针数组(输入为const,实在不知为何如此设计);neighborResponse为样本数*k的每个样本K个近邻的输出值;dist为样本数*k的每个样本K个近邻的距离。
另一个例子
OpenCV refman也提供了一个类似的示例,使用CvMat格式的输入参数:
int main( int argc, char** argv )
{
const int K = 10;
int i, j, k, accuracy;
float response;
int train_sample_count = 100;
CvRNG rng_state = cvRNG(-1);
CvMat* trainData = cvCreateMat( train_sample_count, 2, CV_32FC1 );
CvMat* trainClasses = cvCreateMat( train_sample_count, 1, CV_32FC1 );
IplImage* img = cvCreateImage( cvSize( 500, 500 ), 8, 3 );
float _sample[2];
CvMat sample = cvMat( 1, 2, CV_32FC1, _sample );
cvZero( img );
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) );
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) );
// learn classifier
CvKNearest knn( trainData, trainClasses, 0, false, K );
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;
// estimate 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)) );
}
}
// 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;
}
分类结果:
KNN的思想很好理解,也非常容易实现,同时分类结果较高,对异常值不敏感。但计算复杂度较高,不适于大数据的分类问题。
分享到:
相关推荐
k-近邻算法实例及数据集,包含测试集和训练集,代码中knn.py为主体代码,test.py为画散点图详细代码,example_1为test.py生产的散点图
KNN(k-Nearest Neighbor),是著名的模式识别统计学方法,也最简单的机器学习算法之一。其中心思想为近朱者赤,近墨者黑(相似即为同类)。 设计思路 KNN是一种通过测量不同特征值之间的距离进行分类的算法,其分类...
本资源是关于人工智能领域K近邻算法(KNN)的实例演示-鸢尾花识别-使用excel分辨鸢尾花种类,内容详细解读KNN如何解决分类问题,为大众提供一种解决问题的全新方法。内含各大公式作用指导,帮助大家进一步理解何为KNN...
K近邻法(k-nearestneighbor,k-NN)是1967年由CoverT和Hart P提出的一种基本分类与回归方法。它的工作原理是:存在一个样本数据集合,也称作为训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个...
模式识别k近邻法,knn分类算法,Knn分类器
K-NN(K近邻算法)实现手写字符的识别(C语言)实现,通过VS2010平台验证通过,代码详细易懂,是该算法上手的好资料.
介绍kNN算法,用python实现三个案例,包括简单分类器搭建、约会网站改进、手写字体识别,适合工科生用来介绍算法用
knn,即k最近邻算法是模式识别中的一种比较简单而经典的分类算法,,在邮局问题中得到了广泛的应用。对于最近邻搜索算法有个比较好的描述。
利用K-最近邻算法进行高识别率的信号特征五分类
基于k近邻算法的手写数字识别,K近邻学习(kNN)是一种常见的监督学习方法,给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测。通常在分类任务中可使用...
近邻算法改进约会网站的配对效果、使用k-近邻算法识别手写数字、使用决策树预测隐形眼镜类型、使用朴素贝叶斯过滤垃圾邮件、从疝气病症预测病马的死亡率、SVM手写识别问题回顾、利用AdaBoost元算法提高分类、线性...
针对支持向量机(SVM)在超平面附近进行不平衡数据(imbalanced datasets)分类的不准确性,提出了一种改进SVM-KNN算法,该算法在分类阶段计算测试样本与最优超平面的距离,如果距离差大于给定阈值可直接应用支持...
基于K近邻分类算法的情感识别matlab仿真+含代码操作演示视频 运行注意事项:使用matlab2021a或者更高版本测试,运行里面的Runme.m文件,不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口必须是当前...
Matlab实现基于PSO-NN、...KNN-k近邻, DT-决策树。 结果与SVM、KNN、TREE分类算法作为混淆矩阵和最终识别准确率进行比较。 “NH”(隐藏数)、“SwarmSize”和“MaxIteration”这三个重要参数会显着影响系统的性能。
本算法可以实现多种混合特征的聚类识别,将已知特征进行合理的划分
基于matlab采用KNN算法手写体数字识别实现 一、前言 KNN 全称是 K- Nearest Neighbors ,K-近邻。简单来说,K就是邻居个数,选出和测试样本最像的邻居(这里是欧式几何距离最短的K个邻居),那么样本的邻居是什么,...
(2) KNN 算法原理K-Nearest Neighbor(KNN)算法即 K 近邻算法,是机器学习中的一种分类算法。KNN 算法基本原理为:通过对比待分类点在特定距离 K 内各分类的样本点的数量,来确定待分类点的预测结果。如图所示,某待...
运用局部二值模式(LBP)提取特征,研究了遗传算法(GA)、粒子群算法(PSO)、蚁群算法(ACO)等元启发式优化算法在特征选择中的应用,采用基于种群的元启发式算法PSO对KNN分类器进行优化,利用提出的PSO-KNN算法进行人脸...
本次实验尝试通过将人脸的图像转化为特征向量,然后训练数据集,通过计算欧拉距离找到与待测人脸最接近的k个人脸,这样对人脸进行归类识别实现一个基于KNN 的人脸识别算法,来达到人脸识别的入门级学习。 算法简介:...
K最近邻(K-Nearest Neighbors,KNN)是一种基本的分类和回归方法,常用于模式识别和数据挖掘。以下是对KNN算法的介绍、要点、难点、实际应用、案例参考和代码解析: 算法介绍: 基本原理:KNN算法基于特征空间中...