一、问题描述
已知有一些数据集$(x_1,x_2,…x_m)$,其中$x_i$为$(x_{i1},x_{i2},…x_{in})$的维向量，其标记为$y_k$。现在有一个新的数据$x$,需要判断它的标记为多少？
二、算法思想
- 计算出待分类样本与训练样本中各个数据的距离
- 取距离最近的K个样本
- 从K个样本中确定待分类样本的标记
算法的核心有三个要素和一个选择和一个注意：
- 如何去定义距离？
- K的取值为多少？
- 使用何种方法去确定待分类样本的标记？
- 当数据量特别大时，如何去计算各自距离？（如何选择算法实现）
- 如何对数据进行归一化处理？（注意）
2.1 定义距离：
定义距离我们一般使用数学中度量的定义，即满足那三个条件。
- 非负性
- 对称性
- 三角不等式
但要注意的是第三个条件三角不等式不一定是成立的，比如在a,b,c三个物品的相似度，很可能a与b相似，b与c相似，但a与c并不相似。
一般情况下我们选择使用p-范数或者矩阵范数对向量或者矩阵进行距离的定义。
2.2 K值的选择
K值的选择直接关系到模型最后的决策，我们取极端情况。当K的值为所用样本集的值时，这个模型就过于简单，对于待测值的归类仅仅是样本集中最多的类别。所以K值过大，模型过于简单，相反K值越小，模型过于复杂，容易出现过拟和的情况。
2.3 如何确定待分类标记
我们一般选取最简单原则，最近的K的数据中，谁的标记最多，就是哪个标记
2.4 计算算法的实现
两种算法： KD树算法与球算法
2.4.1 KD树算法
KD树算法的思想就是按照样本的特征的维数进行建树、搜索最近邻居、最后预测三步骤。
首先对样本m个样本集进行二叉树的建立。分别计算所有特征的取值的方差，取最大的方差的特征作为根结点，以其取值的中位数作为划分点，划为左右两个子树，然后递归的生成二叉树KD树。注意每个子树代表的都是一个n纬的区域
现在输入一个目标点，首先在KD树的叶子节点中找到一个包含目标点的叶子节点。以目标点为圆心，叶子节点到目标点为半径形成一个超球体，那么最近邻点一定就在这个超球内。。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。
从上面的描述可以看出，KD树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。
我们知道如何寻找最近邻之后，我们就可以寻找最近的K邻。重复进行K次，每次将最近邻标记，下次略过就可以了。
2.4.2球树实现原理
KD树算法虽然提高了KNN搜索的效率，但是在某些时候效率并不高，比如当处理不均匀分布的数据集时,不管是近似方形，还是矩形，甚至正方形，都不是最好的使用形状，因为他们都有角。这样在求超球和矩形的交集时就会出现很多的不应该判断的情况。
球树，顾名思义，就是每个分割块都是超球体，而不是KD树里面的超矩形体。
我们看看具体的建树流程：
-
先构建一个超球体，这个超球体是可以包含所有样本的最小球体。
-
从球中选择一个离球的中心最远的点，然后选择第二个点离第一个点最远，将球中所有的点分配到离这两个聚类中心最近的一个上，然后计算每个聚类的中心，以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体，和KD树里面的左右子树对应。
-
对于这两个子超球体，递归执行步骤2). 最终得到了一个球树。
可以看出KD树和球树类似，主要区别在于球树得到的是节点样本组成的最小超球体，而KD得到的是节点样本组成的超矩形体，这个超球体要与对应的KD树的超矩形体小，这样在做最近邻搜索的时候，可以避免一些无谓的搜索。
使用球树找出给定目标点的最近邻方法是首先自上而下贯穿整棵树找出包含目标点所在的叶子，并在这个球里找出与目标点最邻近的点，这将确定出目标点距离它的最近邻点的一个上限值，然后跟KD树查找一样，检查兄弟结点，如果目标点到兄弟结点中心的距离超过兄弟结点的半径与当前的上限值之和，那么兄弟结点里不可能存在一个更近的点；否则的话，必须进一步检查位于兄弟结点以下的子树。
检查完兄弟节点后，我们向父节点回溯，继续搜索最小邻近值。当回溯到根节点时，此时的最小邻近值就是最终的搜索结果。
从上面的描述可以看出，KD树在搜索路径优化时使用的是两点之间的距离来判断，而球树使用的是两边之和大于第三边来判断，相对来说球树的判断更加复杂，但是却避免了更多的搜索，这是一个权衡。
2.5数据的归一化
在计算的时候需要注意，每个数据的贡献量的问题。在向量或者矩阵中，每个位置的数的取值可能波动会比较大，如果我们假设每个位置的特征贡献量是相等的，那么我们就需要对数据做归一化处理，如果不是相等的，就需要对每个特征做一个权的估计。那么如何去估计这个权呢？（我们也可以统一做完归一化处理后，再考虑权重问题）
三、程序实现
KNN分类树的类：
KNeighborsClassifter
KNN回归树的类：
KNeighborsRegressor
参数说明：
n_neighbors :K值
weights:近邻权重 uniform,权重都一样。distance,权重和距离成反比
自定义权重，自己来滴ing一
algorithm:蛮力，KD树、球树，自动三种算法选择对应为brute,kd_tree,ball_tree,auto
leaf_size:停止建树的节点阀值
metric:'euclidean','manhattan','chebyshev','minikowski'
随机生成测试数据
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_classification
# X为样本特征，Y为样本类别输出， 共1000个样本，每个样本2个特征，输出有3个类别，没有冗余特征，每个类别一个簇
X, Y = make_classification(n_samples=1000, n_features=2, n_redundant=0,
n_clusters_per_class=1, n_classes=3)
plt.scatter(X[:, 0], X[:, 1], marker='o', c=Y)
plt.show()
训练数据导入：
from sklearn import neighbors
clf = neighbors.KNeighborsClassifier(n_neighbors = 15 , weights='distance')
clf.fit(X, Y)
predict=clf.predict([[0.5,0.5]])
#注意这个地方的数据类型不要搞错了
四、个人体会
暂时没有啥体会，因为现在还太LOW，有了更多的经验后，后续再补充。
