KNN

KNN算法

1 简介


  KNN算法即K近邻分类算法,可以说其是最简单的一种算法。用一句话来说,其就是把未标记的案例归类为与它们最相似的带有标记的案例所在的类中。

  kNN算法的核心思想是:如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。

2 优缺点


无论是基础算法还是高级算法,它们都有各自的优缺点,下面给大家展示一下我们本节要介绍的KNN算法的主要优缺点:

优点 缺点
简单且有效 不产生模型,在发现特征之间关系上的能力有限
对数据分布没有要求 分类阶段很慢
训练阶段很快 需要大量内存(尤其针对于大数据)
名义变量(特征)和缺失数据需要额外处理

3 算法流程


因为该算法的原理浅显易懂,那么其所对应的流程也是及其简单的:

  1. 选K值 :选择合适的K值,即被预测样本的邻居个数
  2. 算距离:给定测试样本,计算它与训练集中的每个样本的距离
  3. 找邻居:圈定距离最近的k个训练样本,作为测试样本的邻居
  4. 做分类:找到这个k个邻居所归属的大多数类别,作为测试样本的分类

如果大家感觉流程比较抽象,那么下面我给大家用一张图去展示算法的流程:

  假设上图蓝色矩形框中的三角形、正方形和红色的小圆圈是我们的所有的样本点,那么如果我想对红色的小圆圈进行分类,该怎么做?

  很简单,按照上面的流程,我们先选择K值,比如我们选择的k是3,那么其近邻就是一个小三角和两个小正方形,最后根据小正方形是占据了3个邻居中的大多数,所以说小红圆圈最后的分类是正方形。怎么样,这样一讲大家就清楚了吧。

  但是呢,细心的同学会发现:当k取11的时候,小红圆圈的分类就是三角形了(11个样本中,有6个三角形,所以最后分类必定是三角形)。这也就说明了,k的取值很重要,其大小决定了测试样本的类别。下面我们也会讲到选择k值的几种常用方法。

4 常见问题


4.1 计算距离

计算距离的公式有很多,比如欧氏距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离。不过一般采用的是欧式距离。

欧式距离计算公式: \[dis(p,q) = \sqrt{(p_1-q_1)^2+(p_2-q_2)^2+…+(p_n-q_n)^2}\] \(p\)\(q\)代表的是需要比较的样本,它们都有n个特征,项\(p1\)代表案例\(p\)的第一个特征,\(q1\)代表案例\(q\)的第一个特征,\(p2、q2\)等以此类推。

4.2 k值的选择

实际中,K值的选取取决于要学习概念的难度和训练数据中案例的数量,通常K为3~10。

  1. 设置K等于训练集中案例数量的平方根。(常见做法)
  2. 循环的方式设定K值,选出一个最好的K值。(比较常见)
  3. 选择一个较大的K值同时应用一个权重投票。(不太常见)

4.3 数据的整理

在应用KNN算法之前通常将特征值度量范围过大的或过小的重新缩放以使每个特征对距离公式的贡献相对平均,传统的方法是min-max标准化,该过程将特征转化使所有值都落在0-1的范围内。

标准化公式: \[X_{max} = \frac{X-min(X)}{max(X)-min(X)}\]

另一种常见的变换称为z-score标准化它的公式是:减去特征X的均值后,再除以X的标准差。

z-score标准化公式: \[X_{new}=\frac{X-Mean(X)}{StdDev(X)}\]

5 knn与kknn的区别


实现KNN算法有两种常见的函数:knn()、kknn()

  knn()是class程序包中的函数,kknn()是kknn程序包中的函数。虽然函数名不同,但是其算法相同,所以思路是一样的。其主要思路是:如果一个样本在空间中的k个最相似的样本大多数属于某一个类别,则该样本也属于这个类别。他们都是k近邻算法的其中一种,但他们也有很多不同的地方。下面就让我们来简单的谈一谈他们的不同:

  首先距离公式不一样。knn()中的距离公式使用的是欧氏距离,而kknn()中的距离公式是闵可夫斯基距离。闵可夫斯基距离是衡量数值点之间距离的一种很常见的方法,假设数值点A和B坐标如下: \[A(x_1,x_2,x_3…x_n)\] \[B(y_1,y_2,y_3…y_n)\]

闵可夫斯基距离:

\[(\sum_{i=1}^{n}|x_i-y_i|^p)^\frac 1p\]

  该距离最常用的p是2和1,前者是欧式距离,后者是曼哈顿距离。当p趋近于无穷大时,闵可夫斯基距离转化成切比雪夫距离。

其次kknn是加权的knn,那么kknn是怎么加权的呢?接下来让我们一起来研究研究:

  kknn()使用内核函数来根据每个点与当前点的距离来对每个点进行加权。也就是说为每个点的距离增加一个权重,使得距离近的点可以得到更大的权重。比如内核函数是反函数。反函数最简单的形式是返回距离的倒数,比如a点到当前点的距离为d,则a点权重为\(1/d\)。常用的核函数有:矩形、Epanechnikov曲线、高斯曲线等。

  kknn()的计算过程:加权knn首先获得经过排序的距离值,再取距离最近的k个元素。在处理离散型数据时,将这k个数据用权重区别对待,预测结果与第n个数据的所属类相同的概率:

\[P_n=\frac {Wn} {\sum_{i=1}^{k}W_i}\]

6 案例解读


上面我们讲了一些有关算法的理论知识,下面使用knn()kknn()两个函数对经典的iris数据集进行分类,顺便做一下比较。

6.1 收集数据

iris数据也称鸢尾花数据是R语言自带的数据集,接下来我们将用这个数据进行一系列的探索:

# install.packages("DT") # 下载DT程序包
library(DT)              # 加载DT程序包,使用datatable()函数

datatable(iris)          # 展示数据
summary(iris[1:4, ]) # 统计前四个变量的主要描述性统计量
##   Sepal.Length    Sepal.Width     Petal.Length    Petal.Width 
##  Min.   :4.600   Min.   :3.000   Min.   :1.300   Min.   :0.2  
##  1st Qu.:4.675   1st Qu.:3.075   1st Qu.:1.375   1st Qu.:0.2  
##  Median :4.800   Median :3.150   Median :1.400   Median :0.2  
##  Mean   :4.825   Mean   :3.200   Mean   :1.400   Mean   :0.2  
##  3rd Qu.:4.950   3rd Qu.:3.275   3rd Qu.:1.425   3rd Qu.:0.2  
##  Max.   :5.100   Max.   :3.500   Max.   :1.500   Max.   :0.2  
##        Species 
##  setosa    :4  
##  versicolor:0  
##  virginica :0  
##                
##                
## 

来看一下Sepal.Length这个变量,它的值域为[4.3,7.9],而Petal.Width的值域为[0.1,2.5]。knn算法在计算距离上很大程度上依赖于特征的测量尺度,也就是说当两个变量的值相差较大时,对于knn算法的预测是有很大影响的,所以我们要对数据进行归一化处理。

6.2 数据归一化

  我们在特征工程部分已经讲过了无量纲化的操作,那么我们就使用preProcess()函数对数据进行归一化。

# install.packages("caret")
library(caret)

standard <- preProcess(iris, method = 'range') # 针对数据设定归一化方法
iris.s <- predict(standard, iris)              # 对数据进行归一化

6.3 函数对比


6.3.1 knn

我们将iris.s数据分为两份,一份为训练集,用于建模。另一份为测试集,用于预测我们建模的好坏。这里我们将训练集和测试集的比例分为2:1,也就是训练集有100个数据,而测试集有50个数据。

set.seed(111) #设置随机种子,保证随机抽样的一致性

# 按照因变量Species进行分层抽样,设置训练集恶占比为2/3
index <- createDataPartition(iris.s$Species, p = 2/3, list = F)
train1 <- iris[index, ] # 抽取2/3的数据作为训练集
test1 <- iris[-index, ] # 抽取1/3的数据作为测试集

train <- train1[-5]     # 踢除第5列,即因变量Species列
test <- test1[-5]       # 踢除第5列,即因变量Species列

以上训练集和测试集我们除去了Species(种类)变量,所以我们还要建立一个只包含 Species变量的训练集和测试集,以便我们后期用knn建模和预测:

train.Species <- iris.s[index, 5]  # 只包含Species变量的训练集
test.Species <- iris.s[-index, 5]  # 只包含Species变量的测试集

对于knn算法测试数据中的每一个实例,该函数将使用欧氏距离标识k个近邻,其中k是指我们自己指定的一个数。然后在这k个近邻中选出类数最多的那个类。

接下来来看看knn()函数的参数,对它创建分类器并进行预测:

p <- knn(train, test, class, k)

  • train: 矩阵或数据集的训练集案例
  • test: 矩阵或数据集的测试集案例
  • class: 包含训练数据每一行的分类
  • k: 邻居的数量

训练数据集有120个数据实例,因为11的平方接近于120,所以我们将k设为11。

library(class)
iris.knn <- knn(train = train,      # 指定训练集
                test = test,        # 指定测试集
                cl = train.Species, # 练数据每一行的分类
                k = 11)             # 设k值为11

上面我们建立了模型,接下来欧式对模型进行评估。下面我们使用table()函数去构建混淆矩阵,统计模型的精确度。

table(test.Species, iris.knn) # 建立混淆矩阵
##             iris.knn
## test.Species setosa versicolor virginica
##   setosa         16          0         0
##   versicolor      0         16         0
##   virginica       0          1        15

从返回的结果中可以看出,一共有1个数据被错误分类(把virginica类的鸢尾花误分为了versicolor的鸢尾花),其他均分类正确,即模型的正确率为98%。

6.3.2 kknn

对于kknn算法测试数据中的每一个实例,该函数将使用闵可夫斯基距离标识k个近邻,其中k是指我们自己指定的一个数。然后再给k个近邻使用内函数来根据距离对k个点进行加权。然后计算出这k个近邻中所属类别概率最高的那个类。

让我们来看看kknn()函数的参数。创建分类器并进行预测:

p <- kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = “optimal”)

  • formula: 一个回归模型。具体为:分类变量~特征变量。
  • train: 训练集
  • test: 测试集
  • na.action: 缺失值处理,默认为去掉缺失值。
  • k: k值选择,默认为7。
  • kernel:内核使用。可能的选择是“矩形”(这是标准的未加权KNN)、“三角形”、“EpnEnnimikOv”(或β(2,2))“高斯”。
  • distance: diatance为闵科夫斯基距离,默认为2时,该距离为欧式距离。
#install.packages("kknn")
library(kknn)

## 使用kknn函数进行预测
iris.kknn <- kknn(formula = Species ~ ., # 指定分类变量和特征变量
                  train = train1,        # 指定训练集
                  test = test1,          # 指定测试集
                  distance = 11,         # 设p值为11
                  k = 11,                # 设邻居的个数为11
                  kernel = "triangular") # 内核函数使用三角形

fit <- iris.kknn$fitted.values           # 提取fit列,即预测分类的结果
table(test.Species, fit)                 # 建立混淆矩阵
##             fit
## test.Species setosa versicolor virginica
##   setosa         15          1         0
##   versicolor      0         16         0
##   virginica       0          1        15

从返回的结果中可以看出,一共有2个数据被错误分类,其他均分类正确,即模型的正确率为96%。

7 参考文献


[1] Brett Lantz. 机器学习与R语言[M]. 机械工业出版社, 2015.
[2] 用R语言做数据分析——有权重的K最近邻算法. http://baijiahao.baidu.com/s?id=1576910210335627064&wfr=spider&for=pc. 2017.
[3] 张良均 谢佳标 杨坦 肖刚等. R语言与数据挖掘. 机械工业出版社. 2016.

滚动至顶部