knn基本概念

knn把每个样例看做是空间上的一个点，给定一个测试样例，

使用适当的邻近性度量算法，计算出该点与训练集中其他点的邻近度。选择K个最相近的点。

在选择出的K个样例中，比例最好的类就是测试样例的类。

从以上描述中可以看出，如果k选择的太小，该算法容易受到噪声的影响，而产生过度拟合的影响，然而如果选择的过大，可能造成误分类。

算法描述：

k是最近邻数目，D是训练样例的集合，z是测试样例
for 样例 in 训练样例集合：
     z和每个样例的相似度
找到k个最相近的样例集合
k个样例中类标号最多的类，就是测试样例的类标号。

Orange中的knn

以iris数据为例：

import Orange
#加载数据
iris = Orange.data.Table('iris')
knn = Orange.classification.knn.kNNLearner(iris, k=10)

for i in iris:
     #将预测结果和实际结果不同的部分输出
     if i.getclass()!=knn(i):
         print i.getclass(),knn(i)

输出结果如下：

Iris-versicolor Iris-virginica
Iris-versicolor Iris-virginica
Iris-virginica Iris-versicolor
Iris-virginica Iris-versicolor
Iris-virginica Iris-versicolor

该数据集共有150个实例，从结果看有5个预测结果是错误的。

下面以图形化的方式来比较朴素贝叶斯分类、KNN分类、s。

下图展现了用orange图形界面的方法：

下图给出了这一比较结果:

从上面的结果中可以看出knn和其他几个方法基本相当。

参考资料

 数据挖掘导论 http://book.douban.com/subject/5377669/