机器学习实战笔记-KNN（k近邻法）篇
本文是作者学习机器学习KNN的学习记录与笔记，文章会从简介、kd树算法、代码实现等几个方面展开。本文的目的是为了记录作者的学习历程以及进行总结，为之后的复习做准备。当然，如果同时能够帮组到同样在入门机器学习的小伙伴当然就更好了。
一、简介
k近邻法是一种基本分类与回归方法，这篇文章只讨论分类问题中的k近邻法。k近邻法的输⼊为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k近邻法假设给定⼀个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实 例的类别，通过多数表决等⽅式进⾏预测。因此，k近邻法不具有显式的学习过程。k近邻法实际上利⽤ 训练数据集对特征向量空间进⾏划分，并作为其分类的“模型”。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。k近邻法1968年由Cover和Hart提出。
1、例子
有一种兔子叫作悲伤（Grief），它们的平均身高是5050厘米，平均体重55公斤。我们拿来一百个悲伤，分别测量它们的身高和体重，画在坐标图上，用绿色方块表示。还有一种兔子呢，叫作痛苦（Agony）。它们体型比较小，平均身高是3030厘米，平均体重是44公斤。我们将一百个痛苦的身高和体重画在同一个坐标图上，用蓝色三角表示。最后一种兔子叫绝望（Despair）。它们的平均身高45厘米，但体重较轻，平均只有2.5公斤。一百只绝望的数据用黄色圆圈表示。
image
在这些数据中，(身高,体重) 的二元组叫做特征（features），兔子的品种则是分类标签（class label）。我们想解决的问题是，给定一个未知分类的新样本的所有特征，通过已知数据来判断它的类别。
所以现在我们想解决的问题是，如果有一只新的兔子，我们知道它的身高和体重，然后我们想要知道它属于这三类的那一类。这个时候k邻近法就派上用场了。
我们对兔子进行建模，使其形成关于身高体重的特征向量，然后找到离新兔子在向量空间上举例最近的k个兔子（k由自己设定），然后根据这k个兔子的类型去预测判断新兔子的类型。
2、算法
image
2.1、距离度量
image
一般情况下，我们都是用p=2，也就是欧式距离。
2.2、k值选择
k值的选择会对k近邻法的结果产⽣重⼤影响。 如果选择较⼩的k值， 就相当于⽤较⼩的邻域中的训练实例进⾏预测， “学习”的近似误差 （approximation error）会减⼩，只有与输⼊实例较近的（相似的）训练实例才会对预测结果起作⽤。但缺点是“学习”的估计误差（estimation error）会增⼤，预测结果会对近邻的实例点⾮常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减⼩就意味着整体模型变得复杂，容易发⽣过 拟合。
如果选择较⼤的k值，就相当于⽤较⼤邻域中的训练实例进⾏预测。其优点是可以减少学习的估计 误差。但缺点是学习的近似误差会增⼤。这时与输⼊实例较远的（不相似的）训练实例也会对预测起作⽤，使预测发⽣错误。k值的增⼤就意味着整体的模型变得简单。
如果k＝N，那么⽆论输⼊实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模 型过于简单，完全忽略训练实例中的⼤量有⽤信息，是不可取的。
在应⽤中，k值⼀般取⼀个⽐较⼩的数值。通常采⽤交叉验证法来选取最优的k值。
3、概率KNN
简单的来说，就是结果是属于每一类的概率大小，而不是绝对的属于某一个类别。
二、kd树算法实现
本来打算贴上算法流程，但是看了一遍又一遍，感觉算法实在是晦涩难懂。干脆直接贴链接上例子。
https://www.joinquant.com/view/community/detail/c2c41c79657cebf8cd871b44ce4f5d97
三、代码实现
现导入需要使用到的包
from numpy import random
from sklearn import neighbors
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
生成期望、方差不同的三组随机数据
x1 = random.normal(50, 6, 200)
y1 = random.normal(5, 0.5, 200)
x2 = random.normal(30,6,200)
y2 = random.normal(4,0.5,200)
x3 = random.normal(45,6,200)
y3 = random.normal(2.5, 0.5, 200)
对数据进行可视化
plt.scatter(x1,y1,c='b',marker='s',s=50,alpha=0.8)
plt.scatter(x2,y2,c='r', marker='^', s=50, alpha=0.8)
plt.scatter(x3,y3, c='g', s=50, alpha=0.8)
image
从图中我们可以看出来，三类数据分布还是比较明显。
之后，我们进行数据的预处理，并且给数据分类到具体标签里
x_val = np.concatenate((x1,x2,x3))
y_val = np.concatenate((y1,y2,y3))
x_diff = max(x_val)-min(x_val)
y_diff = max(y_val)-min(y_val)
x_normalized = [x/(x_diff) for x in x_val]
y_normalized = [y/(y_diff) for y in y_val]
xy_normalized = zip(x_normalized,y_normalized)
xy_train = list(xy_normalized)
labels = [1]*200+[2]*200+[3]*200 # 三类标签，1（蓝色），2（红色），3（绿色）
开始训练模型
clf = neighbors.KNeighborsClassifier(30) # 设置k值为30， 其他默认
clf.fit(xy_train, labels)
进行预测
prediction = clf.predict([(50/x_diff, 5/y_diff),(30/x_diff, 3/y_diff)])
print(prediction)
image
可视化结果
plt.scatter(x1,y1,c='b',marker='s',s=50,alpha=0.8)
plt.scatter(x2,y2,c='r', marker='^', s=50, alpha=0.8)
plt.scatter(x3,y3, c='g', s=50, alpha=0.8)
plt.scatter(50,5, c='y',s = 50, alpha = 0.8)
plt.scatter(30,3, c='y',s = 50, alpha = 0.8)
image
我们可以看到，这两个黄色的新实例，第一个确实在1（蓝色）中，第二个感觉比较模糊，在2（红色）和3（绿色）之间，并没有很明显的差别。让我们看下概率KNN.
prediction_proba = clf.predict_proba([(50/x_diff, 5/y_diff),(30/x_diff, 3/y_diff)])
print(prediction_proba)
image
我们可以看到第一个是100%的概率在分类1中，而第二个实例分别是77%和23%的概率属于分类2或者分类3.
接下来，我们再生成一些新的实例来作为测试集，对我们的模型进行测试。
x1_test = random.normal(50, 6, 100)
y1_test = random.normal(5, 0.5, 100)
x2_test = random.normal(30,6,100)
y2_test = random.normal(4,0.5,100)
x3_test = random.normal(45,6,100)
y3_test = random.normal(2.5, 0.5, 100)
xy_test_normalized = zip(np.concatenate((x1_test,x2_test,x3_test))/x_diff,\
np.concatenate((y1_test,y2_test,y3_test))/y_diff)
xy_test = list(xy_test_normalized)
labels_test = [1]*100+[2]*100+[3]*100
来看下我们的模型分数
score = clf.score(xy_test, labels_test)
print(score)
image
可以看到我们的分数还不错，主要因为数据都是我们生成的，规律比较明显。以后还是要多用实际数据去试一试。
之前我们提到过，不同的k值会导致结果的不同。接下来我们就想看一下不同的k值，结果有什么不同，哪一个k值得结果最好。
record = []
for i in range(1,31):
clf = neighbors.KNeighborsClassifier(i)
clf.fit(xy_train, labels)
score = clf.score(xy_test, labels_test)
record.append(score)
print("when k = %i, score = %f"%(i,score))
image
k = []
for i, value in enumerate(record):
if value == np.max(record):
k.append(i+1)
print("when k = ", k)
print("the score is the highest = ", np.max(record))
image
从结果我们可以看到，最高的分数就是98.67%，很多种不同的k的选择都会有这一个结果。这个时候我们是不是应该用较为小的k值呢，去降低算法复杂度，加快预算时间。
参考：
李航博士《统计学习方法》
https://www.joinquant.com/view/community/detail/a98b7021e7391c62f6369207242700b2
https://www.joinquant.com/view/community/detail/c2c41c79657cebf8cd871b44ce4f5d97
https://www.joinquant.com/view/community/detail/bb850ee76d1cae16cc587f29c4439ebd
