0x00kNN思想
kNN(k-NearestNeighbor)，也就是k最近邻算法。顾名思义，所谓K最近邻，就是k个最近的邻居的意思。也就是在数据集中，认为每个样本可以用离他最距离近的k个邻居来代表。
0x01kNN算法流程
通过理解算法思想，可以将其简化为“找邻居+投票”。K近邻法使用的模型，实际上是特征空间的划分。模型由三个基本要素决定：距离度量、k值、分类决策规则
其中两个实例点之间的距离反映了相似程度，一般来说使用欧氏距离来计算。
梳理kNN算法流程如下：
1.计算测试对象到训练集中每个对象的距离
2.按照距离的远近排序
3.选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
4.统计这k个邻居的类别频率
5.k个邻居里频率最高的类别，即为测试对象的类别
0x02 算法实现
sklearn中的kNN
流程是：训练数据集 -> 机器学习算法 -fit-> 模型 输入样例 -> 模型 -predict-> 输出结果
kNN算法没有模型，模型其实就是训练数据集，predict的过程就是求k近邻的过程。
class
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)
参数
n_neighbors: int, 可选参数(默认为 5)。用于kneighbors查询的默认邻居的数量。
weights（权重）: str or callable(自定义类型), 可选参数(默认为 ‘uniform’)。用于预测的权重参数，可选参数如下：
uniform : 统一的权重. 在每一个邻居区域里的点的权重都是一样的。
distance : 权重点等于他们距离的倒数。
使用此函数，更近的邻居对于所预测的点的影响更大。
[callable] : 一个用户自定义的方法，此方法接收一个距离的数组，然后返回一个相同形状并且包含权重的数组。
algorithm（算法）: {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, 可选参数（默认为 ‘auto’）。计算最近邻居用的算法：
ball_tree 使用算法BallTree
kd_tree 使用算法KDTree
brute 使用暴力搜索
auto 会基于传入fit方法的内容，选择最合适的算法。
注意 : 如果传入fit方法的输入是稀疏的，将会重载参数设置，直接使用暴力搜索。
leaf_size（叶子数量）: int, 可选参数(默认为 30)。传入BallTree或者KDTree算法的叶子数量。此参数会影响构建、查询BallTree或者KDTree的速度，以及存储BallTree或者KDTree所需要的内存大小。此可选参数根据是否是问题所需选择性使用。
p: integer, 可选参数(默认为 2)。用于Minkowski metric（闵可夫斯基空间）的超参数。p = 1, 相当于使用曼哈顿距离，p = 2, 相当于使用欧几里得距离]，对于任何 p ，使用的是闵可夫斯基空间。
metric（矩阵）: string or callable, 默认为 ‘minkowski’。用于树的距离矩阵。默认为闵可夫斯基空间，如果和p=2一块使用相当于使用标准欧几里得矩阵. 所有可用的矩阵列表请查询 DistanceMetric 的文档。
metric_params（矩阵参数）: dict, 可选参数(默认为 None)。给矩阵方法使用的其他的关键词参数。
n_jobs: int, 可选参数(默认为 1)。用于搜索邻居的，可并行运行的任务数量。如果为-1, 任务数量设置为CPU核的数量。不会影响fit。
方法
KNeighborsClassifier的方法：
fit(X, y)：使用X作为训练数据，y作为目标值（类似于标签）来拟合模型。
get_params([deep])：获取估值器的参数。
neighbors([X, n_neighbors, return_distance])：查找一个或几个点的K个邻居。
kneighbors_graph([X, n_neighbors, mode])：计算在X数组中每个点的k邻居的（权重）图。
predict(X)：给提供的数据预测对应的标签。
predict_proba(X)：返回测试数据X的概率估值。
score(X, y[, sample_weight])：返回给定测试数据和标签的平均准确值。
set_params(**params)：设置估值器的参数。
0x03
判断模型好坏
1.将原始数据中的一部分作为训练数据、另一部分作为测试数据。使用训练数据训练模型，再用测试数据其好坏。
两种方法：
# 方法1
# 使用concatenate函数进行拼接，因为传入的矩阵必须具有相同的形状。因此需要对label进行reshape操作，reshape(-1,1)表示行数自动计算，1列。axis=1表示纵向拼接。
tempConcat = np.concatenate((X, y.reshape(-1,1)), axis=1)
# 拼接好后，直接进行乱序操作
np.random.shuffle(tempConcat)
# 再将shuffle后的数组使用split方法拆分
shuffle_X,shuffle_y = np.split(tempConcat, [4], axis=1)
# 设置划分的比例
test_ratio = 0.2
test_size = int(len(X) * test_ratio)
# 方法2
# 将x长度这么多的数，返回一个新的打乱顺序的数组，注意，数组中的元素不是原来的数据，而是混乱的索引
shuffle_index = np.random.permutation(len(X))
# 指定测试数据的比例
test_ratio = 0.2
test_size = int(len(X) * test_ratio)
2.在划分出测试数据集后，我们就可以验证其模型准确率了。accuracy（分类准确度），还有精度（查准率）和召回率（查全率）等。
0x04 超参数
超参数，是在机器学习算法模型执行之前需要指定的参数。（调参调的就是超参数） 如kNN算法中的k。与之相对的概念是模型参数，即算法过程中学习的属于这个模型的参数（kNN中没有模型参数，回归算法有很多模型参数）
4.1寻找好的k
需要注意，如果最好的k值在设定的取值范围中间，在边界上，我们需要稍微扩展一下取值范围。
4.2 另一个超参数：权重
假设考虑距离，一般认为，距离样本数据点最近的节点，对其影响最大，那么使用距离的倒数作为权重。在 sklearn.neighbors 的构造函数 KNeighborsClassifier 中有一个参数：weights，默认是uniform即不考虑距离，也可以写distance来考虑距离权重(默认是欧拉距离，如果要是曼哈顿距离，则可以写参数p（明可夫斯基距离的参数），这个也是超参数)
因为有两个超参数，因此使用双重循环，找最合适的两个参数。
4.3 超参数网格搜索
sklearn中专门封装了一个超参数网格搜索方法Grid Serach，一次性得到最好的超参数组合，以解决搜索过程中可能遇到的，超参数过多、超参数之间相互依赖等问题。
使用网格搜索，需要先定义一个搜索的参数param_search。（是一个数组，数组中的每个元素是个字典，字典中的是对应的一组网格搜索，每一组网格搜索是这一组网格搜索每个参数的取值范围。键是参数的名称，值是键所对应的参数的列表。）
0x05 数据归一化
在实际场景中，样本不同特征的单位不同，会在求距离时造成很大的影响，也不能反映样本中每一个特征的重要程度，因此需要对特征数据进行归一化。
常用的数据归一化：
1.最值归一化(normalization)： 把所有数据映射到0-1之间。
最值归一化的使用范围是特征的分布具有明显边界的(分数0～100分、灰度0～255)，受outlier的影响比较大。
x_{scale} = \frac {x - x_{min}} {x_{max} - x_{min}}
2.均值方差归一化(standardization)： 把所有数据归一到均值为0方差为1的分布中。
适用于数据中没有明显的边界，有可能存在极端数据值的情况。
x_{scale} = \frac {x - x_{mean}} {S}
5.1Sklearn中的归一化
sklearn中用StandardScaler方法来进行数据归一化的方法。
注意：训练数据集中的均值和方差要保留。因为
测试数据是模拟的真实环境，真实环境中可能无法得到均值和方差，（只能够使用公式(x_test - mean_train) / std_train），在对测试数据集进行归一化时，仍然要使用训练数据集的均值train_mean和方差std_train。
0x06
KD树 (
kNN优化之一)
6.1 kd树的原理
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，kd树是一种二叉树，表示对k维空间的一个划分。
k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
6.2 kd树的构建
常规的k-d tree的构建过程为：
1.循环依序取数据点的各维度来作为切分维度，
2.取数据点在该维度的中值作为切分超平面，
3.将中值左侧的数据点挂在其左子树，将中值右侧的数据点挂在其右子树，
4.递归处理其子树，直至所有数据点挂载完毕。
对于构建过程，有两个优化点：
1.选择切分维度：根据数据点在各维度上的分布情况，方差越大，分布越分散，从方差大的维度开始切分，有较好的切分效果和平衡性。
2.确定中值点：预先对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。也可以从原始数据点中随机选择固定数目的点，然后对其进行排序，每次从这些样本点中取中值，来作为分割超平面。该方式在实践中被证明可以取得很好性能及很好的平衡性。
0x07 kNN优缺点
KNN的主要优点有：
1.理论成熟，思想简单，既可以用来做分类也可以用来做回归。
2.天然解决多分类问题，也可用于回归问题。
3.和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感。
4.由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN的主要缺点有：
1.计算量大，效率低。即使优化算法，效率也不高。
2.高度数据相关，样本不平衡的时候，对稀有类别的预测准确率低
3.相比决策树模型，KNN模型可解释性不强
4.维数灾难：
随着维度的增加，“看似相近”的两个点之间的距离越来越大，而knn非常依赖距离
参考阅读：
2.《机器学习》周志华著，10.1 k近邻学习(P225)
代码另附。
