惰性学习算法 ---- k 近邻算法

KNN 是惰性学习算法的典型例子。说它具有惰性不是因为它看起来简单，而是因为它仅仅对训练数据集有记忆功能，而不会从训练集中通过学习得到一个函数。

这种基于记忆的学习算法的优点：分类器可以快速地适应新的训练数据

缺点：在最坏的情况下，计算复杂度随着样本数量的增多而呈线性增长，除非数据集中的样本维度（特征数量）有限，而且使用了高效的数据结构（如 KD 树等）。

此外，我们还不能忽视训练样本，因为此模型没有训练步骤

参数化模型与非参数化模型

机器学习算法可以划分为

参数化模型

当使用参数化模型时，需要我们通过训练数据估计参数，并得到一个模式，一边在无需原始训练数据信息的情况下对新的数据点进行分类操作。

典型的参数化模型包括
- 感知器
- 逻辑回归
- 线性支持向量
- …
非参数化模型

非参数化模型无法通过一组固定的参数来进行表征，而参数的数量也会随着训练数据的增加而递增
- 决策树
- 核 SVM
- KNN
- …

KNN 属于非参数化模型的一个子类，它可以被描述为基于 实例的学习。此类模型的特点：对训练数据进行记忆；而惰性学习则是基于 实例学习 的一个特例，他在学习阶段的计算成本为 0。

k 近邻算法：

输入：训练数码集 $D = {(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)}$

其中， $x_i \in x \subseteq R$ 为实例的特征向量，$y_i \in Y = (c_1, c_2, …, c_n) $ 为实例的类别， $i = 1, 2, ..., n$ ；实例特征向量 $x$ ；

输出：实例 $x$ 所属的类 $y$

根据给定的距离度量，在训练集 $D$ 中找出与 $x$ 最近邻的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的邻域记作： $N_k(x)$
在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别：

$y = argmax_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_j), i=1,2,...,n; j=1,2,...,k$ $(1)$

在 $(1)$ 式中， $I$ 为指示函数，即当 $y_i = c_j$ 时 $I$ 为 1 ，否则 $I$ 为 0。

k 近邻法特殊情况是 $k=1$ 的情形，称为 最近邻算法。对于输入的实例点（特征向量） $x$ ，最近邻法将训练数据集中与 $x$ 最近邻点的类作为 $x$ 的类。

k 近邻法使用的模型实际上对应于特征空间的划分。模型由三个基本要素决定：

距离度量
k 值的选择
分类决策规则

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。k 近邻模型的特征空间一般是 $n$ 维实数向量空间 $R$ 。使用的距离是 欧氏距离，但也可以是其他距离，如更一般的 闽可夫斯基距离（Minkowski distance ）

闵可夫斯基距离时对欧几里得距离和曼哈顿距离的一种泛化

minkowski distance:

$(\sum_{i=1}^{n}|X_i^{(a)} - X_i^{(b)}|^p)^{\frac{1}{p}}$

曼哈顿距离：当 p = 1 时

$(\sum_{i=1}^{n}|X_i^{(a)} - X_i^{(b)}|)^{\frac{1}{1}}$

欧几里得距离：当 p = 2 时

$(\sum_{i=1}^{n}|X_i^{(a)} - X_i^{(b)}|^2)^{\frac{1}{2}}$

k 值的选择

k值的选择会对k近邻法的结果产生重大影响。

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的 k 值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k 值的增大就意味着整体的模型变得简单。

如果 k＝n，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。

在应用中，k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。

分类决策规则

k 近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

KNN 算法可以归纳为一下几步：

选择近邻的数量 $k$ 和距离度量方法
找到代分类样本的 $k$ 个最近邻居
根据最近邻的类标进行多数投票

惰性学习算法 ---- k 近邻算法

代码：

class KNN_classify:
	def __init__(self, k):
		self.k = k
		self._X_train = None
		self._y_train = None
	def fit(self, X_train, y_train):
		self._X_train = X_train
		self._y_train = y_train
		return self
	def predict(self, X_predict):
		y_predict = [self._predict(x) for x in X_predict]
		return np.array(y_predict)
	def _predict(self, x):
		distance = [np.sqrt(np.sum((x_train - x) ** 2)) for x_train in self._X_train]
		n = np.argsort(distance)
		k_y = [self._y_train[i] for i in n[:self.k]]
		votes = Counter(k_y)
		return votes.most_common(1)[0][0]

实例：数字分类

import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

digits = datasets.load_digits()
X = digits.data
y = digits.target

some_digits_image = X[1].reshape(8, 8)
plt.imshow(some_digits_image, cmap=matplotlib.cm.binary)
plt.show()

x_train, x_test, y_train, y_test = train_test_split(X, y, random_state=42)
knn_clf = KNeighborsClassifier(n_neighbors=3)
# knn_clf = KNeighborsClassifier(n_neighbors=k, p=2)  # 
knn_clf.fit(x_train, y_train)
y_predict = knn_clf.predict(x_test)

accuracy_score(y_test, y_predict)

维度灾难

由于维度灾难（curse of dimensionality）的原因，使得 KNN 算法易于过拟合。

维度灾难：对于一个样本数量大小稳定的训练数据集，随着其特征数量的增加，样本中有具体值的特征数量变得极其稀疏（大多数特征为空）。直观的说，可以认为即使是最近的邻居，它们在高维空间中的实际距离也是非常远的，因此难以给出一个合适的类标判断。

参考：

李航-统计学习方法
imooc python3入门机器学习 https://coding.imooc.com/class/chapter/169.html#Anchor

惰性学习算法 ---- k 近邻算法

惰性学习算法 ---- k 近邻算法

相关推荐