统计学习方法-k近邻(KNN)笔记

k近邻(KNN)算法是一种简单易于实现的监督机器学习方法,可用于解决分类和回归问题(这里取决于KNN算法最后返回值的处理方法)

  • 分类问题:返回值为k个训练标签中占大多数的类
  • 回归问题:返回值为k个训练标签对应值的平均值

    k近邻算法没有进行数据的训练,直接使用实例数据与训练数据进行比较(首先确认输入实例点的k个邻训练实例点,然后利用这k个训练实例点的类的多数来预测输入实例点的类(通常会将k设为奇数,以便有一个决胜局),因此K-近邻算法不具有显式的学习过程

k近邻三要素:距离度量、k值的选择和分类决策规则,三者一旦决定,其KNN算法的结果也就是唯一的了:

  • 常用的距离度量是欧式距离(或者更一般的Lp距离,当p=1时则是曼哈顿距离)
  • k值的选择反映了偏差和方差的权衡:k值越小,则模型复杂,偏差小和方差大(训练误差小,测试误差大),容易出现过拟合;k值越大,则模型简单,偏差大和方差小(训练误差大,测试误差小),容易出现欠拟合;因此一般通过交叉验证来选取较小的最优k值
  • 常用的分类决策规则是多数表决,对应经验风险最小化(ERM,经验风险最小化模型认为经验风险最小的模型就是最优的模型)

有文章机器学习之KNN邻近算法总结了KNN算法的优劣:

  • KNN算法与人类日常思考模式很相近,无需估计参数,无需训练,也不会生成最终的分类器。 适合对稀有事件进行分类。较小数据量的快速分类常常使用KNN算法。特别适合于多分类问题(multi-modal,对象具有多个类别标签),在这一类问题上,KNN算法要优于很多其他的机器学习算法(如SVM)
  • KNN算法是一种消极算法(没有训练的过程,到了要决策的时候才会利用已有的数据进行决策),进行分类时由于要计算每个样本之间的距离,计算开销很大,运行比较慢。当数据量非常大时,不适合用KNN算法。当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。在极端情况下,如果某一类别的样本数目甚至小于K,那么最终的分类结果势必要收到很大的影响。分类结果完全以来于训练样本,不能给出分类规则(可解释性不强,相比决策树模型而言)。

按照<统计学习方法>KNN的3.1算法,也可以称为brute-force(暴力搜索),步骤如下:

  • 确定训练集和k值
  • 循环计算每个训练集中的点与实例点的距离,寻找出离实例点最近的k个点
  • 计算k个点所在类出现次数,根据多数表决的决策规则将实例点进行分类

Python代码如下(brute_force_knn函数是常规暴力搜索的KNN算法,knn_fd_cv函数则是KNN的K折交叉验证):

import numpy as np
import pandas as pd
from collections import Counter
from sklearn.model_selection import KFold

class KNN:
    def brute_force_knn(self, dat_X, label, input_x, k):
        # 计算欧式距离
        dist = ((input_x - dat_X)**2).sum(axis=1)**0.5
        dist_index = np.argsort(dist)
        # 分类决策:多数表决
        label_pre = []
        for i in dist_index[:k]:
            label_pre.append(label[i])
        target = Counter(label_pre).most_common(1)[0][0]
        return target

    def knn_fd_cv(self, dat_X, label, k, fd):
        kf = KFold(n_splits=fd)
        error_list = []
        for train_index, test_index in kf.split(dat_X):
            X_train, X_test = dat_X[train_index], dat_X[test_index]
            y_train, y_test = label[train_index], label[test_index]

            error = 0
            for i in range(len(y_test)):
                t = self.brute_force_knn(dat_X=X_train, label=y_train, input_x=X_test[i], k=k)
                # 计算测试误差
                if t != y_test[i]:
                    error += 1
            # print(error/len(y_test)*100)
            error_list.append(error/len(y_test)*100)
        return np.mean(error_list)

其实sklearn已有调用KNN算法的sklearn.neighbors.KNeighborsClassifier,类似于常用的R包,上面的代码只是为了理解下KNN算法和交叉验证而写着看看,sklearn的使用以后再看~

加权KNN(常用有高斯函数、反函数和减法函数等方式),即给更近的邻位点分配更大的权重(可消除孤立实例点的影响):

  • 对于离散型数据,将k个点对应的标记以权重区别对待,权重相加,那个类的值大就属于哪类
  • 对于数值型数据,将k个点求加权平均(累加值与权重相乘的结果,然后除以所有权重之和)

由于KNN是线性扫描的方式,当训练集很大的时候则会非常耗时;这时可以使用kd-树来找寻找最邻位点,其会将实例点储存到可以进行快速搜索的树形数据结构中,使得每次在局部空间中搜索,从而加快搜索速度,具体实现方式可参考<统计学习方法>以及kNN里面的两种优化的数据结构:kd-tree和ball-tree,在算法实现原理上有什么区别?

以一个Kaggle上的测试数据集MNIST为例(数字识别),用上述Python的简单KNN算法计算下不同k选值下的识别错误率,进而选择最优的K值:

# 读入测试数据集
dataset = pd.read_csv("train.csv")
dataset = np.array(dataset)
# 确定实例点和其对应标记
train_dat = dataset[:,1:]
train_label = dataset[:,0]

knn = KNN()
# 计算k取值在2-7下的测试误差,交叉验证为10折
for i in range(2,8):
    r = knn.knn_fd_cv(dat_X=train_dat, label=train_label, k=i, fd=10)
    print("k =",i,"error rate =",r)

最后发现k=4时测试误差最低(2.95%,即97.05%的准确率,效果有点差~相比其他用CNN卷积神经网络算法的99.9%的准确率来说)

参考资料:
K近邻算法(KNN)原理小结
《机器学习实战》学习笔记:K-近邻算法入门及实战|万字长文

本文出自于http://www.bioinfo-scrounger.com转载请注明出处

文章目录
|