KNN（K-Nearest Neighbor）是Cover&Hart于1968年提出的一种分类算法，算法思想就是：
>
1.为判断未知实例的类别，以所有已知类别的实例作为参考点；
2.选择参数K；
3.计算未知实例与所有已知实例的距离；
4.选择最近的K个已知实例；
5.根据投票法则，将未知实例归为K个最邻近样本中最多数的类别。

KNN就是这种“近朱者赤，近墨者黑”的思想，它由你的邻居来推断出你的类别。这里仅对以下一些细节进行补充说明。

距离

距离的衡量包括：欧式距离、余弦相似度、曼哈顿距离等。

欧式距离：
$$dist(X,Y)=\sqrt{\sum_{i=1}^{n} {(x_i-y_i)}^2}$$

余弦相似度（Cosine Similarity）：
$$sim(X,Y)=\cos\theta=\frac{\vec{x}\cdot \vec{y}}{||x||\cdot||y||}$$

曼哈顿距离：
$$dist(X,Y)=\sqrt{\sum_{i=1}^{n} {|x_i-y_i|}}$$
注：对于文本分类来说，使用余弦相似度来计算就比欧式距离更合适。

关于K

k值通常是采用交叉检验来确定（以k=1为基准），一般低于训练样本数的平方根。

优劣

1.优点：简单，易于理解，易于实现，无需估计参数，无需训练。适合对稀有事件进行分类，特别适合于多分类问题。
2.缺点：懒惰算法，对测试样本分类时的计算量大，内存开销大。可解释性较差，无法给出决策树那样的规则。

改进版本

对距离加权，距离越近，权重越大。例如：1/d。

本文完。