K近邻算法

算法解决的是：给定训练数据集，每一个数据已经贴好标签，对于新引入的测试数据，算法如何根据已有的训练集正确分类，因此该算法是一个懒惰学习的分类算法。

采用的策略也是多数表决法，即确定k值后，在训练数据中选出k个度量距离最近的数据，选择多数的数据类别给测试数据贴上标签。

度量距离推荐采用普遍性更强的Lp范数。

KD树的构造

构造二叉平衡树，采用分治法，在一次递归中，对数据进行某一维度上的排序（一般选取方差最大的一个维度），后选取中点作为pivot划分。

K近邻搜索

在二叉搜索的基础上加入了回溯算法，避免最优解在未搜索的子树。

python代码实现

笔者本打算使用c++手搓后放弃转python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
import numpy as np

iris = datasets.load_iris()
iris_x = iris.data
iris_y = iris.target
print("num of data:", len(iris_x))

indices = np.random.permutation(len(iris_x))
iris_train = iris_x[indices[:-10]]  # 随机获取140个数据作为训练样本
iris_train_label = iris_y[indices[:-10]]  # 训练数据的标签
iris_test = iris_x[indices[-10:]]  # 获取剩下的10个样本作为测试数据
iris_test_label = iris_y[indices[-10:]]  # 测试的10个数据的真实类别

knn = KNeighborsClassifier()  # 一个分类器对象
knn.fit(iris_train, iris_train_label)  # 训练过程
iris_train_predict = knn.predict(iris_test)
print("the real label is:", iris_test_label)
print("the predict is:   ", iris_train_predict)
1
2
3
4
E:\annaconda\envs\tf_env\python.exe C:\Users\shaoy\Desktop\pythonProject\main.py 
num of data: 150
the real label is: [2 0 2 2 2 1 2 2 0 1]
the predict is:    [2 0 2 2 2 1 1 2 0 1]