KNN算法

原理参考：
K近邻算法（Python实现）
K-邻近算法(KNN)详解+Python实现
python实现：

import numpy as np
import operator

class KNN():
    def __init__(self, x, y, k, p):
        self.k = k
        self.p = p
        self.x = x
        self.y = y

    def predict(self, x):    
        diff = np.tile(x, (self.x.shape[0], 1)) - self.x  #计算预测数据和训练数据的差值
        dist=np.linalg.norm(diff, ord=self.p, axis=1, keepdims=False) #计算范数
        dist_sorted=dist.argsort() #返回从小到大排序的索引

        #分类投票
        count = {}
        for i in range(self.k):
            vote = self.y[dist_sorted[i]]
            count[vote] = count.get(vote, 0) + 1

        #对分类投票数从低到高进行排序
        count_sorted = sorted(count.items(), key=operator.itemgetter(1), reverse=True)
        return count_sorted[0][0]
      

if __name__=='__main__':
    x=np.array([[0, 10], [1, 8], [10, 1], [7, 4]])
    y=np.array([0, 0, 1, 1])
    knn=KNN(x, y, 3, 2)
    print("预测值为：",knn.predict(np.array([[6, 2]])))

python调包：

import numpy as np
from sklearn.neighbors import KNeighborsClassifier


if __name__=='__main__':
    x=np.array([[0, 10], [1, 8], [10, 1], [7, 4]])
    y=np.array([0, 0, 1, 1])
    knn=KNeighborsClassifier(n_neighbors=3, p=2)      
    knn.fit(x, y)   
    print("预测值为：", knn.predict(np.array([[6, 2]])))

C++实现：

#include 
#include 
#include 
#include 

//k邻近模型
class KNN
{
public:
	KNN(std::vector<std::vector<float>> x, std::vector<float> y, int k, float p) : m_x(x), m_y(y), m_k(k), m_p(p) {};

	int predict(std::vector<std::vector<float>> x)
	{
		x.resize(m_x.size());
		for (size_t i = 0; i < x.size(); i++)
		{
			x[i] = x[0];
		}

		//计算预测数据和训练数据的差值
		std::vector<std::vector<float>> diff = x;
		for (size_t i = 0; i < diff.size(); i++)
		{
			for (size_t j = 0; j < diff[0].size(); j++)
			{
				diff[i][j] -= m_x[i][j];
			}
		}

		//计算范数
		std::vector<float> dist(diff.size(), 0);
		for (size_t i = 0; i < diff.size(); i++)
		{
			for (size_t j = 0; j < diff[0].size(); j++)
			{
				dist[i] += pow(diff[i][j], m_p);
			}
			dist[i] = pow(dist[i], 1.0 / m_p);
		}

		//返回从小到大排序的索引
		std::vector<int>  dist_sorted(dist.size());
		for (size_t i = 0; i != dist_sorted.size(); ++i) dist_sorted[i] = i;
		std::sort(dist_sorted.begin(), dist_sorted.end(), [&dist](size_t i, size_t j) {return dist[i] <  dist[j]; });

		//分类投票
		std::map<float, int> count;
		for (size_t i = 0; i < m_k; i++)
		{
			float vote = m_y[dist_sorted[i]];
			count[vote] += 1;
		}

		//返回投票最多的类别标签
		return count.rbegin()->first;
	}
	
private:
	std::vector<std::vector<float>> m_x;
	std::vector<float> m_y;
	int m_k;
	float m_p;
};


int main(int argc, char* argv[])
{
	std::vector<std::vector<float>> x = { { 0, 10 },{ 1, 8 },{ 10, 1 },{ 7, 4 } };
	std::vector<float> y = { 0, 0, 1, 1 };

	KNN knn = KNN(x, y, 3, 2);
	std::cout << "预测值为：" << knn.predict({ {6,2} }) << std::endl;

	system("pause");
	return EXIT_SUCCESS;
}