机器学习（二） K-近邻算法（kNN）

一.综述:

1.1 Cover和Hart在1968年提出了最初的邻近算法
1.2 分类(classification)算法
1.3 输入基于实例的学习(instance-based learning), 懒惰学习(lazy learning)
1.4 简单的说 K-近邻算法采用不同特征值之间的距离方法进行分类

二.工作原理:

存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据之后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们选取样本数据集中前K个最相似的数据，这就是k-近邻算法的出处。通常k是不大于20的整数（奇数较多）。最后选取K个最相似的数据中出现次数最多的分类，作为新数据的分类。

三.算法详述:

3.1 步骤：
为了判断未知实例的类别，以所有已知类别的实例作为参照
选择参数K
计算未知实例与所有已知实例的距离
选择最近K个已知实例
根据少数服从多数的投票法则(majority-voting)，让未知实例归类为K个最邻近样本中最多数的类别

3.2 细节:
关于K
关于距离的衡量方法:
3.2.1 Euclidean Distance 定义

其他距离衡量：余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）

四. 算法优缺点：

4.1 算法优点
简单
易于理解
容易实现
通过对K的选择可具备丢噪音数据的健壮性

4.2 算法缺点
[)](http://www.nczkevin.com/wp-content/uploads/2015/11/Image-4.png)
需要大量空间储存所有已知实例
算法复杂度高（需要比较所有已知实例与要分类的实例）
当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本

(改进方法：考虑距离，根据距离加上权重，比如: 1/d (d: 距离））

五.算法实战：

1.使用python 的机器学习库sklearn。具体介绍看sklearn官网

现在先写一个最简单的knn应用。

from sklearn import neighbors
from sklearn import datasets

knn = neighbors.KNeighborsClassifier()
iris = datasets.load_iris()

print iris

knn.fit(iris.data,iris.target)

predictedLabel = knn.predict([[0.1,0.2,0.3,0.4]])

print predictedLabel