k邻近算法Python实现

目录

一、什么是k邻近学习二、k邻近算法如何实现2.1 伪代码2.2 距离度量 三、Python实现

一、什么是k邻近学习

  k邻近 (k-Nearest Neighbor, kNN) 学习是一种常用的监督学习方法。不同于其他机器学习算法，例如线性回归、SVM等，k邻近学习的原理十分简单易懂：

  对于给定的测试样本，可以从训练集中寻找到和测试样本最接近的k个样本，根据这k个训练样本的标签可以对测试样本作出合理的预测。例如回归任务可以取k个训练样本的均值，分类任务可以进行投票。

二、k邻近算法如何实现

2.1 伪代码

  根据上面给出的k邻近算法的原理，能够轻松构思出k邻近算法的伪代码。   首先，由于k邻近算法的预测计算过程需要测试样本数据，所以考虑使用懒惰学习的方式进行训练。

训练：存储训练集预测： 遍历每一个测试样本xi 遍历每一个训练样本fit_xi 计算xi到fit_xi的距离并保存 选择出到xi距离最小的k个fit_xi如果是分类任务，以k个fit_xi中样本数最多的标签作为测试样本标签如果是回归任务，将k个fit_xi标签的均值作为样本标签

2.2 距离度量

  两个样本的距离度量方式通常有以下几种：

欧几里得距离 $$d(x,y)=\sqrt{(x_1-y_1{)}^2+(x_2-y_2{)}^2+...}$$余弦距离 $$d(x,y)=1-\frac{x^{T}y}{\Vert x{\Vert }^2\Vert y{\Vert }^2}$$曼哈顿距离 $$d(x,y)=|x_1-y_1|+|x_2-y_2|+...$$

下面的实现将以欧几里得距离为例。

三、Python实现

  k邻近分类器：

import numpy as np from scipy import stats class KNNClassifier: def __init__(self, k=1): self.k = k self.fit_X = None self.fit_y = None # 欧几里得距离 def _d(self, x, y): return np.sqrt(np.sum((x - y)**2)) # 惰性学习 def fit(self, X, y): self.fit_X = X self.fit_y = y return self # 开销主要集中在预测 def _predict(self, x): d = [] indexs = [] for fit_x in self.fit_X: d.append(self._d(fit_x, x)) for i in range(self.k): index = np.argmin(d) indexs.append(index) d.pop(index) return stats.mode(self.fit_y[indexs])[0][0] def predict(self, X): y = [] for x in X: y.append(self._predict(x)) return np.array(y)

  k邻近回归：

import numpy as np class KNNRegression: def __init__(self, k=1): self.k = k self.fit_X = None self.fit_y = None # 欧几里得距离 def _d(self, x, y): return np.sqrt(np.sum((x - y)**2)) # 惰性学习 def fit(self, X, y): self.fit_X = X self.fit_y = y return self # 开销主要集中在预测 def _predict(self, x): d = [] indexs = [] for fit_x in self.fit_X: d.append(self._d(fit_x, x)) for i in range(self.k): index = np.argmin(d) indexs.append(index) d.pop(index) return np.mean(self.fit_y[indexs]) def predict(self, X): y = [] for x in X: y.append(self._predict(x)) return np.array(y)