KNN分类算法思想
①给定一个训练数据集T={Xi=(x1, x2,..., xn, Yi}, i=1,2,...,m. 利用训练集训练KNN模型。
②对于新的输入样例，在前面训练集训练的模型中找到与该样例距离最邻近的k个实例
③根据这k个实例对应的类别，求类别最多的作为此输入样例的类别。
算法的描述：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
分类决策规则
分类误差最小即经验风险最小，所以多数表决规则等价于经验风险最小化。
距离空间度量
-
1. 欧氏距离，最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：image
(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：
image
(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：
image
(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：
image
也可以用表示成向量运算的形式：
image
K值选择
K值一般不大于20的奇数，奇数可以防止出现两个类别相同的情况
模型训练
构造平衡kd树算法：
①确定分裂规则：计算所有数据各个维度上的方差，选择方差最大的维度作为首先分裂的节点。
②确定分裂节点：在第①阶段得到的方差最大的维度中数据中位数那个样本作为分裂节点。
③确定左右子树：大于中位数的样本作为右子树样本子空间，小于中位数的样本作为左子树的样本子空间。
④迭代计算子树：循环①②③步骤，直到叶子节点。
每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有 Data Set 实例为止
随着树的深度增加，循环的选取坐标轴，作为分割超平面的法向量。
对于3-d tree来说，根节点选取x轴，根节点的孩子选取y轴，根节点的孙子选取z轴，根节点的曾孙子选取x轴，这样循环下去。
最邻近搜索算法
已构造好kd树，即训练好了KNN模型，输入一个样例，该如何分类呢？
①在kd树中找到包含目标点x的叶节点，即在已经划分好的样本空间中找到包含x实例的样本子空间
②把此节点当作临时“当前最邻近点”
③递归向上回溯，在每个节点执行以下操作：
（a）如果该结点保存的实例点比当前最近点距离目标点更近，则更新“当前最近点”，也就是说以该实例点为“当前最近点”。
（b）当前最近点一定存在于该结点一个子结点对应的区域，检查子结点的父结点的另一子结点对应的区域是否有更近的点。具体做法是，检查另一子结点对应的区域是否以目标点位球心，以目标点与“当前最近点”间的距离为半径的圆或超球体相交：
- 如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，接着，继续递归地进行最近邻搜索；
- 如果不相交，向上回溯。
④当回退到根结点时，搜索结束，最后的“当前最近点”即为x 的最近邻点。
KD树的插入
KD树是一个二叉搜索树，所以插入的原理是差不多，只不过比较大小不是根据一维数据，而是根据K维的值来实现。
KD树的删除
KD树的删除也与二叉搜索树差不多，分四种情况，父节点是祖父的左节点还是右节点，被删除的节点是否有左右子节点
KNN的优缺点
①kd树更适用于训练实例数远大于空间维数时的k近邻搜索
KNN的改进——KD树近邻搜索算法的BBF改进算法
原因：“回退到根结点时，搜索结束”，每个最近邻点的查询比较都要回退到根结点而结束搜索，这导致了许多不必要回溯访问和需要比较的结点，这些多余的时间损耗在高维度数据查找的时候，搜索效率将变得相当之低下
from numpy import *
import operator
class KNN:
def createDataset(self):
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']
return group,labels
def KnnClassify(self,testX,trainX,labels,K):
[N,M]=trainX.shape
#calculate the distance between testX and other training samples
difference = tile(testX,(N,1)) - trainX # tile for array and repeat for matrix in Python, == repmat in Matlab
difference = difference ** 2 # take pow(difference,2)
distance = difference.sum(1) #行向量分别相加，从而得到新的一个行向量
distance = distance ** 0.5
sortdiffidx = distance.argsort() #argsort()根据元素的值从大到小对元素进行排序，返回下标
# find the k nearest neighbours
vote = {} #create the dictionary
for i in range(K):
ith_label = labels[sortdiffidx[i]];
vote[ith_label] = vote.get(ith_label,0)+1 #get(ith_label,0) : if dictionary 'vote' exist key 'ith_label', return vote[ith_label]; else return 0
sortedvote = sorted(vote.iteritems(),key = lambda x:x[1], reverse = True)
# 'key = lambda x: x[1]' can be substituted by operator.itemgetter(1)
return sortedvote[0][0]
k = KNN() #create KNN object
group,labels = k.createDataset()
cls = k.KnnClassify([0,0],group,labels,3)
print cls
运行
import sys
sys.path.append("...文件路径...")
import KNN
from numpy import *
dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("测试数据为:",input,"分类结果为：",output)
过程：
[1] 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法 (非常经典，讲解的非常详细，值得参考)
[2] K NEAREST NEIGHBOR 算法（全部是关于KNN的应用题型，可以用来理解KNN的实际应用，有助于理解算法的使用）
[3] 机器学习算法-K最近邻从原理到实现 (代码实现)
[4] 机器学习（一）——K-近邻（KNN）算法 (代码实现比较多，可以多参考实现）
