博客

最近邻算法knn原理：

找到最近的k个邻居（样本），在前k个样本中选择频率最高的类别作为预测结果。

算法步骤为：

1）算距离：给定测试对象，计算它与训练集中的每个对象的距离

2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻

3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类

上图是一张手写数字图，大小为2000*1000，这张图中有0~9十个数字，每五行为一个数字，共五十行——5000个手写数字。

我们首先要做的事是将这张图分割为5000个以手写数字为单元的小图块。经计算可得每个小图块的大小：20*20。直接将每个小图块序列化，最终得到一个400*5000的特征矩阵。宽为400，高为5000.取其前3000个样本来进行训练。

以下程序可分为三步：

1.截取图片进行数据预处理

2.KNN算法训练

3.代入原图片进行测试，并将测试结果与正确结果对比计算得出正确率。

#include <opencv2/opencv.hpp>
#include <iostream>
#include <stdio.h>
using namespace std;
using namespace cv;
using namespace cv::ml;

int main()
{
	Mat img = imread("E:/opencv/opencv/sources/samples/data/digits.png");
	Mat gray;
	cvtColor(img, gray, CV_BGR2GRAY);
	int b = 20;
	int m = gray.rows / b;   //原图为1000*2000
	int n = gray.cols / b;   //裁剪为5000个20*20的小图块
	Mat data, labels;   //特征矩阵
	for (int i = 0; i < n; i++)
	{
		int offsetCol = i*b; //列上的偏移量
		for (int j = 0; j < m; j++)
		{
			int offsetRow = j*b;  //行上的偏移量
								  //截取20*20的小块
			Mat tmp;
			gray(Range(offsetRow, offsetRow + b), Range(offsetCol, offsetCol + b)).copyTo(tmp);
			data.push_back(tmp.reshape(0, 1));  //序列化后放入特征矩阵,（reshape是改变图像通道数和将图像按列或按行序列化的函数，此处作用是不改变通道数并将原图像按行序列化）
			labels.push_back((int)j / 5);  //每个数字对应的标注，每五行数字一个标注
		}

	}
	data.convertTo(data, CV_32F); //uchar型转换为cv_32f
	int samplesNum = data.rows;
	int trainNum = 3000;
	Mat trainData, trainLabels;
	trainData = data(Range(0, trainNum), Range::all());   //前3000个样本为训练数据
	trainLabels = labels(Range(0, trainNum), Range::all());

	//使用KNN算法
	int K = 5;
	Ptr<TrainData> tData = TrainData::create(trainData, ROW_SAMPLE, trainLabels);//Ptr<xx>是指创建一个类型为xx的指针，此处是创建一个cv::ml库中TrainData类的一个指针
	Ptr<KNearest> model = KNearest::create();
	model->setDefaultK(K);
	model->setIsClassifier(true);
	model->train(tData);

	//预测分类
	double train_hr = 0, test_hr = 0;
	Mat response;
	// compute prediction error on train and test data
	for (int i = 0; i < samplesNum; i++)
	{
		Mat sample = data.row(i);
		float r = model->predict(sample);   //对所有行进行预测
											//预测结果与原结果相比，相等为1，不等为0
		r = std::abs(r - labels.at<int>(i)) <= FLT_EPSILON ? 1.f : 0.f;

		if (i < trainNum)
			train_hr += r;  //累积正确数
		else
			test_hr += r;
	}

	test_hr /= samplesNum - trainNum;
	train_hr = trainNum > 0 ? train_hr / trainNum : 1.;

	printf("accuracy: train = %.1f%%, test = %.1f%%\n",
		train_hr*100., test_hr*100.);
	waitKey(0);
	return 0;
}