曼哈顿距离（python计算曼哈顿距离）

【火炉炼AI】机器学习029-找到离你最近的邻居

(本文所使用的Python库和版本号: Python 3.6, Numpy 1.14, scikit-learn 0.19, matplotlib 2.2 )

最近邻算法的核心思想是：想要判断你属于哪一个类别，先找离你最近的K个邻居，看看这些邻居的大部分属于哪个类别，那么就可以认为你也属于这个类别。

所以，根据这种核心思想，有三个重要的因素：距离度量，K的大小和分类规则。在KNN中，当训练数据集和三要素确定后，相当于将特征空间划分为一些子空间。对于距离度量，有很多种方式，常用的是闵可夫斯基距离，其计算公式为：

其中P>=1, 当P=2时，是欧式距离，当p=1时，是曼哈顿距离。

对于K的大小选择是一个重要的考虑因素，其选择会对算法的结果有重大影响。如果Ｋ太小，就相当于用较小领域中的训练实例进行预测，这样会被噪声所影响，同时方差比较大，也就是模型的过拟合现象会比较严重。如果Ｋ太大，就相当于用很多的邻居来判断，此时会走向另一个极端，使得模型产生欠拟合现象。

在具体应用中，一般选择较小Ｋ并且Ｋ是奇数，通常使用交叉验证的方法来获取最合适的Ｋ值。

分类规则一般常用多数表决，即大多数实例所属的类别就认为是新样本的类别。这个很容易理解。

1. 查找最近的K个邻居

下面我们自己用代码寻找一个新样本的K个最近的邻居，看看这些邻居们都在哪儿。

# 1，寻找最近的K个邻居from sklearn.neighbors import NearestNeighbors# 自定义一些数据集X = np.array([[1, 1], [1, 3], [2, 2], [2.5, 5], [3, 1], [4, 2], [2, 3.5], [3, 3], [3.5, 4]])# 画出这些数据集在平面图上的分布情况plt.scatter(X[:,0],X[:,1],marker=’o’,color=’k’)# 一个新样本new_sample=np.array([[2.6,1.7]])plt.scatter(new_sample[:,0],new_sample[:,1],marker=’*’,color=’r’)复制代码

上面只是将原始数据集和新样本的分布绘制到二维平面上，但是没有计算其最近的距离和邻居。下面代码是计算过程。

# 构建KNN模型，计算最近的K个数据点K=3KNN=NearestNeighbors(n_neighbors=K,algorithm=’ball_tree’).fit(X)distances,indices=KNN.kneighbors(new_sample)# 打印最近的K个邻居for rank, (indices, distance) in \ enumerate(zip(indices[0][:K],distances[0][:K])): print(‘rank: {} –> {}, distance: {:.3f}’.format(rank, X[index],distance))复制代码

—————————-输———出——————————–

rank: 0 –> [2. 2.], distance: 0.671 rank: 1 –> [3. 1.], distance: 0.806 rank: 2 –> [3. 3.], distance: 1.360

———————————-完————————————-

可以看出距离新样本最近的三个邻居分别是【2,2】，【3,1】，【3,3】，而且各自的距离也打印出来了。实际上，KNN.kneighbors(new_sample)返回的indices数组是一个已经排序的数组，我们只需要从中获取下标即可。

下面为了方便观察，将最近的K个邻居用别的颜色重点标注出来。

########################小**********结###############################

1，想要寻找新样本最近的K个邻居，需要首先构建一个KNN模型，然后用数据集训练该模型。

2，然后使用函数KNN.kneighbors(new_sample)即可得到距离的排序，从这些排序中可以计算出最近的Ｋ个邻居。

#################################################################

注：本部分代码已经全部上传到（我的github）上，欢迎下载。

参考资料:

1, Python机器学习经典实例，Prateek Joshi著，陶俊杰，陈小莉译

曼哈顿距离（python计算曼哈顿距离）

相关推荐