参考：
1. KNN算法介绍，Python程序和一个简单算例
2. k-nearest neighbor algorithm
基本想法：
在距离空间里，如果一个样本的最接近的k个邻居里，绝大多数属于某个类别，则该样本也属于这个类别。俗话叫，“随大流”。
算法描述：
1. 依公式计算 Item 与 D1、D2 … …、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)。2. 将Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)排序，若是超过相似度阈值t则放入邻居案例集合NN。3. 自邻居案例集合NN中取出前k名，依多数决，得到Item可能类别。
参数K的选取：
如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。比如下图，
待测样本（绿色圆圈）既可能分到红色三角形类，也可能分到蓝色正方形类。如果k取3，从图可见，待测样本的3个邻居在实线的内圆里，按多数投票结果，它属于红色三角形类，票数1:2.但是如果k取5，那么待测样本的最邻近的5个样本在虚线的圆里，按表决法，它又属于蓝色正方形类，票数2（红色三角形）:3（蓝色正方形）。
其它问题：
计算两者间距离，用哪种距离会更好呢？计算量太大怎么办？假设样本中，类型分布非常不均，该怎么办呢？
例子（电影分类）：
| 电影名称 | 打斗次数 | 接吻次数 | 电影类型 |
California Man | 3 | 104 | Romance |
He’s Not Really into Dudes | 2 | 100 | Romance |
Beautiful Woman | 1 | 81 | Romance |
Kevin Longblade | 101 | 10 | Action |
Robo Slayer 3000 | 99 | 5 | Action |
Amped II | 98 | 2 | Action |
| 未知 | 18 | 90 | Unknown |
这个数据用打斗次数和接吻次数来界定电影类型，接吻多的是Romance类型的，而打斗多的是动作电影。现在有一部名字未知的电影，打斗次数为18次，接吻次数为90次的电影（这里名字未知是为了防止能从名字中猜出电影类型），它到底属于哪种类型的电影呢？
下面调用Python的sklearn模块求解：(转自KNN算法介绍)
import numpy as npfrom sklearn import neighborsknn = neighbors.KNeighborsClassifier() #取得knn分类器data = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]) # data对应着打斗次数和接吻次数labels = np.array([1,1,1,2,2,2]) #labels则是对应Romance和Actionknn.fit(data,labels) #导入数据进行训练'''knn.predict([18,90])
首先，用labels数组中的1和2代表Romance和Aciton，因为sklearn不接受字符数组作为标志，只能用1,2这样的int型数据来表示，后面处理可以将1和2映射到Romance和Action上来。fit则是用data和labels进行训练，data对应的是打斗次数和接吻次数构成的向量，称之为特征向量。labels则是这个数据所代表的电影所属的类型。调用predict 进行预测，将未知电影的特征向量代入，则能分析出该未知电影所属的类型。此处计算结果为1,也就是该未知电影属于Romance，和直觉相符。
问题是：在这个例子中，k是多少呢？
