Python机器学习-k近邻–一个懒惰学习算法 - 书目录

Python机器学习-k近邻–一个懒惰学习算法

k近邻–一个懒惰学习算法

本章我们要讨论的最后一个监督学习算法是k紧邻算法(k-nearest neighbor classifier, KNN), 这个算法很有意思,因为他背后的思想和本章其他算法完全不同。

KNN是懒惰学习的一个典型示例。之所以称为“懒惰”并不是由于此类算法看起来很简单,而是在训练模型过程中这类算法并不去学习一个判别式函数(损失函数)而是要记住整个训练集。

Note 参数模型VS变参模型

机器学习算法可以被分为两大类:参数模型和变参模型。对于参数模型,在训练过程中我们要学习一个函数,重点是估计函数的参数,然后对于新数据集,我们直接用学习到的函数对齐分类。典型的参数模型包括感知机、逻辑斯蒂回归和线性SVM。与之相对的,变参模型中的参数个数不是固定的,它的参数个数随着训练集增大而增多!很多书中变参(nonparametric)被翻译为无参模型,一定要记住,不是没有参数,而是参数个数是变量!变参模型的两个典型示例是决策树/随机森林和核SVM。

KNN属于变参模型的一个子类:基于实例的学习(instance-based learning)。基于实例的学习的模型在训练过程中要做的是记住整个训练集,而懒惰学习是基于实例的学习的特例,在整个学习过程中不涉及损失函数的概念。

KNN算法本身非常简单,步骤如下:

  • 1 确定k大小和距离度量。
  • 2 对于测试集中的一个样本,找到训练集中和它最近的k个样本。
  • 3 将这k个样本的投票结果作为测试样本的类别。

一图胜千言,请看下图:

对每一个测试样本,基于事先选择的距离度量,KNN算法在训练集中找到距离最近(最相似)的k个样本,然后将k个样本的类别的投票结果作为测试样本的类别。

像KNN这种基于内存的方法一大优点是:一旦训练集增加了新数据,模型能立刻改变。另一方面,缺点是分类时的最坏计算复杂度随着训练集增大而线性增加,除非特征维度非常低并且算法用诸如KD-树等数据结构实现。此外,我们要一直保存着训练集,不像参数模型训练好模型后,可以丢弃训练集。因此,存储空间也成为了KNN处理大数据的一个瓶颈。

下面我们调用sklearn训练一个KNN模型:

我们设置k=5,得到了相对平滑的决策界:

k的选择对于KNN模型来说至关重要,除此之外,距离度量也是很有用的。通常,欧氏距离用于实数域的数据集,此时一定要对特征进行标准化,这样每一维度特征的重要性等同。我们在上面的代码中使用的距离度量是'minkowski',它是欧氏距离和曼哈顿距离的一般化:

如果p=2,则退化为欧氏距离,p=1,则退化为曼哈顿距离。使用metric参数可以选择不同的距离度量。

Note 维度诅咒

注意,如果特征维度过大,KNN算法很容易过拟合。我们可以想象,对于一个固定大小的训练集,如果特征空间维度非常高,空间中最相似的两个点也可能距离很远(差别很大)。虽然我们在逻辑回归中讨论了正则项来防止过拟合,但是正则项却不适用于KNN和决策树模型,我们只能通过特征选择和降维手段来避免维度诅咒。下一章我们会讲到。

results matching “

    No results matching “

    133940

     

    转载链接:https://ljalphabeta.gitbooks.io/python-/content/knn.html