[分享] 《机器学习算法与实现 —— Python编程与应用实例》-- 第二贴 K最邻近算法

引言：

本书第四章讲解了K最近邻算法，本算法在之前的ACM等算法设计大赛中也是比较常见的算法。

什么是K最近邻算法？

kNN(k-Nearest Neighbor)算法，是机器学习中最基础的算法之一，既能用于分类，又可用于回归。核心思想：通过度量给定样本到训练数据集中所有样本的特征距离，将与给定样本特征距离最近的k个样本中出现次数最多的类别指定为该样本最优估计的类别；

K最近邻原理：

分类问题中，对于一个新样本，可以根据距离最近的样本的类别来判断其所属的类别。因为k近邻算法主要依靠周围邻近的有限样本而非判别类别的方法来确定所属类别，所以对类别交叉或重叠较多的待分样本集，较其他方法来说更合适。

存在的问题：

样本不平衡时，会产生误判，可以通过加权（与样本距离短的邻居权重大）来改进。

仅适用于数据量少的情况，否则计算复杂度会过高。

特征距离计算：

机器学习中常见的距离度量有：曼哈顿距离，欧氏距离等。kNN算法中通常使用的欧氏距离

曼哈顿距离，也称为城市街区距离或出租车距离，是一种计算在标准坐标系上两点之间距离的方法，它表示两个点在南北方向上的距离加上在东西方向上的距离。这种距离的计算方式得名于规划为方形建筑区块的城市，如曼哈顿，其中最短的行车路径（忽略单向车道和特定大道的斜向车道）是通过南北方向和东西方向上的直线距离之和来确定的。

曼哈顿距离的计算公式为：http://www.w3.org/1998/Math/MathML">𝑑(𝑖,𝑗)=∣𝑋1−𝑋2∣+∣𝑌1−𝑌2∣d(i,j)=∣X1−X2∣+∣Y1−Y2∣，其中http://www.w3.org/1998/Math/MathML">(𝑋1,𝑌1)(X1,Y1)和(𝑋2,𝑌2)(X2,Y2)是二维平面上的两个点。这个公式直接反映了曼哈顿距离的定义，即两点在南北方向上的距离加上在东西方向上的距离。