KNN

K邻近学习

k近邻学习是一种监督学习算法，lazy-learning算法。训练复杂度为0。在给定的训练样本集中，基于某种距离度量，找出与训练集最靠近的k个训练样本，然后基于这k个邻居信息来进行预测。
投票法：通常在分类任务中使用，判别方法是选择这k个样本中出现最多的雷冰标记作为预测结果。（所以k值取值一般为奇数，以便可以得到有偏向的投票结果）
平均法：通常在回归任务中使用，判别方法是将这k个样本的实值输出标记的平均值最为预测结果。
加权平均或加权投票：根据距离远近来决定权重，距离越近，权重越大。

增加权重后，就可以避免由于密集的样本造成的影响。

KNN算法主要过程

1. 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
2. 对上面所有的距离值进行排序；
3. 选前k个最小距离的样本；
4. 根据这k个样本的标签进行投票，得到最后的分类类别；

如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取，比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。
近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。

距离衡量方法

Euclidean Distance

$D=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

余弦（cos）

相关度(correlation)

$$cos(θ)=\frac{A·B}{||A||×||B||}$$

曼哈顿距离(Manhattan distance)

走过的街区数。

KNN算法的优缺点

优点：

1. 思想简单，理论成熟，既可以用来做分类也可以用来做回归；
2. 可用于非线性分类；
3. 训练时间复杂度为O(n)；
4. 准确度高，对数据没有假设，对outlier不敏感；

缺点：

1. 计算量大；
2. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
3. 需要大量的内存；

import numpy as np
from sklearn import neighbors,datasets
knn=neighbors.KNeighborsClassifier()
iris=datasets.load_iris()
knn.fit(iris.data,iris.target)
predictedLabel=knn.predict([[0.1,0.2,0.3,0.4]])
print(predictedLabel)