k-近邻分类算法（k-Nearest Neighbor algorithm），是一种非常有效而且易于掌握的机器学习算法。k-近邻算法（简称kNN）采用测量不同特征值之间的距离方法进行分类。
优点：分类精度高、对异常值不敏感、无数据输入假定
缺点：算法时间复杂度和空间复杂度都很高
<!-- more -->
算法实现分类的步骤
- 计算已知类别数据集中的每个数据点到未知点的距离（如欧几里德距离，切比雪夫距离…）
- 按照距离递增持续排序
- 选择与未知点距离最近的前k个点
- 统计前k个点中出现次数最多的分类标签作为分类结果
关于数据的归一化
在进行距离计算时，使用欧式距离：
$dist= \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+…(a_n-b_n)^2}$
但其中某一项数值差值最大的属性将会对计算出的结果造成较大影响。
如： <table> <tr><td>房屋面积</td><td>房屋价格</td><td>房屋质量</td><td>分类结果</td></tr> <tr><td>300</td><td>1380000</td><td>99</td><td>别墅</td></tr> <tr><td>120</td><td>700000</td><td>87</td><td>公寓</td></tr> <tr><td>78</td><td>500000</td><td>50</td><td>公寓</td></tr> </table>
显然对于以上数据进行距离测算时，房屋价格一项对距离会产生较大影响。
在处理不同取值范围的特征值时，采用数值归一化。如把数值的取值范围处理为0-1之间或-1到1之间，有以下公式：
$new = (old-min)/(max-min)$
我的代码中实现了MLiA书中网站约会预测的kNN算法。
以数据集前900项作为练习数据，后101项作为测试数据。准确率为93.0%左右