4.2 KNN算法的核心知识

KNN算法虽然简单，但有几个核心知识点需要特别注意。首先是关于“远近”概念的度量方法；其次是K值，即近邻数量的选择；第三是K个近邻的选择，即参数K的选择。

4.2.1 距离或相似度的衡量

在KNN算法中常使用欧氏距离、曼哈顿距离和夹角余弦来计算距离，从而衡量各个对象之间的非相似度。在实际应用中，使用哪一种衡量方法需要具体情况具体分析。对于关系型数据，常使用欧氏距离；对于文本分类来说，使用夹角余弦（cosine）来计算相似度比欧式（Euclidean）距离更合适。

• 欧式距离为： d（ x，y） =， MATLAB 代码为： d = pdist （[ x;y ] ,'euclidean'）。

• 曼哈顿距离为： d（ x，y） =， MATLAB 代码为： d=pdist （ [ x; y] ,'cityblock'）。

• 夹角余弦为： cos < x， y > =， MATLAB 代码为： d =1 - pdist （[ x;y ] ,'cosine'）。

4.2.2 K值的选取

在KNN算法中K值的选取非常重要，一般来说，我们只选择样本数据集中前K个最相似的数据，这就是K近邻算法中K值的出处（通常K<20）。

如果K值选大了，求出来的K最近邻集合可能包含了太多隶属于其他类别的样本点，不具有代表性；如果K值选小了，结果对噪声样本点很敏感。根据实际经验，K值一般为奇数，并且一般低于训练样本数的平方根。

4.2.3 K个邻近样本的选取

在KNN算法中，整个样本集中的每一个样本都要与待测样本进行距离计算，然后在其中取K个最近邻。但是会带来巨大的距离计算量，这也是懒惰算法所带来的计算成本。改进方案有两个：一是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算，例如KD树方法；另一个是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果，例如压缩近邻算法。