knn 算法简介和三种实现方式

文章目錄

1. knn 算法介绍
2. 使用自己编写的代码实现 knn 算法
3. 使用 class 包实现 knn 算法
4. 使用 caret 包实现 knn 算法
1. 4.1. 使用 createDataPartition 函数划分训练集和测试集
2. 4.2. 使用 knn3 函数进行分类预测

knn 算法介绍

knn 是 k-nearest neighbour 的缩写，又名 k 邻近。knn 算法的核心思想是“近朱者赤，近墨者黑”。拿一个电子商务系统举例来说，该系统在为你做商品推荐的时候，需要根据和你具有相似特征的人群的购买记录来为你推荐。它的理由就是：如果他们和你是类似的人的话，那么他们想要购买的东西，想必你也是需要买的，所以推荐给你。那么如何定义和你具有相似特征的人呢？这些特征可能是性别、年龄、地域、浏览记录、购买记录、收藏记录等各种数据。对于这些不同类别的数据，无论是分类数据，还是数值型数据，我们都有若干种方法来定义两个样本点之间的距离，比如最常见的欧氏距离，曼哈顿距离等。通过利用合适的方法来度量距离，我们可以得到谁和你是类似的人。那么他们喜欢的东西，系统经过排序，将会将结果展现给你。

除了使用哪种距离以外，我们还需要关注的是，需要综合你周围的几个人的意见来为你做推荐？是需要少数几个人就够，还是需要很多人的综合意见？这就是 knn 算法中的参数 k 的含义。通常情况下，选择不同的 k 会使得我们的算法的表现有好有坏，我们需要对 k 经过多种尝试，来决定到底使用多大的 k 来作为最终参数。

对于 knn 算法的实现， R 语言中已经有了很多种方式。以下我们介绍其中三种。第一种是通过自己编写代码来实现 knn 算法，其代码来自于 <机器学习:实用案例解析> 一书。另外两种分别借助 R 语言中的两个包，分别是 class 包和 caret 包。

使用自己编写的代码实现 knn 算法

数据集介绍

首先我们使用的是来自于 <机器学习:实用案例解析> 自带的数据，可以点击这里下载

首先我们读取数据集，并进行查看

1 2	data <- read.csv("example_data.csv") str(data)

## 'data.frame':	100 obs. of  3 variables:
##  $ X    : num  2.37 3.18 2.16 4.6 3.33 ...
##  $ Y    : num  5.4 4.39 5.34 3.87 6.43 ...
##  $ Label: int  0 0 0 0 0 0 0 0 0 0 ...

1	summary(data)

##        X                Y             Label    
##  Min.   :0.7853   Min.   :3.195   Min.   :0.0  
##  1st Qu.:3.0829   1st Qu.:5.134   1st Qu.:0.0  
##  Median :3.9015   Median :6.067   Median :0.5  
##  Mean   :3.9740   Mean   :6.097   Mean   :0.5  
##  3rd Qu.:4.7370   3rd Qu.:7.013   3rd Qu.:1.0  
##  Max.   :7.0872   Max.   :9.308   Max.   :1.0

可以看到该数据集有100个样本点，每个样本点有两个数值型特征，并且其数据分布范围相差不大。第三列是这些样本所归属的类，但是该列现在仍然是 int 类型

1	table(data$Label)

1
2
3

## 
##  0  1 
## 50 50

归属于 0 和 1 这两类的样本各为 50 个。由于只有两个特征，我们可以使用 ggplot2 包来对这些样本点进行可视化。很显然，X 和 Y 用来确定样本点的位置，而 Label 用来给点上色。

1
2
3

library(ggplot2)
visual <- ggplot(data, aes(X,Y,colour = factor(Label)))
visual + geom_point() + scale_colour_brewer(palette = "Set1")

可以看到，不同 Label 的点相对较为分离，不过仍有一些交叉。我们使用 knn 算法，可能会得到相对不错的效果。

距离矩阵定义

由于数据在二维平面上作图得到良好的感官效果，我们可以顺理成章的使用二维的欧氏距离来定义两个样本点之间的距离。在下面的代码中，我们给 distance.matrix 函数传入一个数据框 df。该函数会先创建一个 nrow(df) 行 nrow(df) 列的方阵，并使用循环遍历方阵中的每一个元素，将其赋值为对应位置两个样本点的欧氏距离。该函数最后返回距离矩阵。矩阵的第 (i,j) 位置的值，就是第 i 个样本点和第 j 个样本点的欧式距离。

distance.matrix <- function(df)
{
  distance <- matrix(rep(NA, nrow(df) ^ 2), nrow = nrow(df))
  
  for (i in 1:nrow(df))
  {
    for (j in 1:nrow(df))
    {
      distance[i, j] <- sqrt((df[i, 'X'] - df[j, 'X']) ^ 2 + (df[i, 'Y'] - df[j, 'Y']) ^ 2)
    }
  }

  return(distance)
}

knn 函数的定义

有了距离矩阵，我们对任意的一个样本点，比如说第 i 个样本点，就能知道其余所有点和它的距离了。那么我们自然也可以对这些距离排个序，并找出离 i 最近的 k 个样本点来。这里需要注意的是，由于样本点 i 和自身的距离永远为零，那么我们在使用最近的 k 个邻居来对其进行预测时，当然不能把它自己给算进去了。所以距离最小的这个自身的点，我们用不上。那么有了以上的思路以后，我们就有了下面的函数，该函数用来对样本点 i 找出和其最近的 k 个样本来(不包括它自己)，并返回这些样本点的位置。

k.nearest.neighbors <- function(i, distance, k = 5)
{
  return(order(distance[i, ])[2:(k + 1)])
}

有了以上两个函数做铺垫，我们可以定义最后的 knn 函数了。该函数有两个参数，第一个是数据框，第二个是选择的最近邻居个数 k。当数据框进入 knn 函数后，我们先使用 distance.matrix 函数计算出其距离矩阵。然后我们使用 k.nearest.neighbors 函数，对数据框中的每一个样本，找出和其最近的 k 个样本点，然后计算这 k 个样本点的 Label 均值。由于 Label 只有 1 和 0 两个值，那么近邻中取哪个值的样本点占得比例高，Label 的均值就应该在 0.5 的基础上向着相应值靠拢，这就是下面利用 ifelse 函数对样本点的 Label 进行预测的依据这种决策方法也叫做 majority vote，或者叫草根民主。最后，knn 函数返回所有样本点的一个 Label 预测。我们可以用该预测和所有点的 Label 真实值作比较，看看我们的算法的正确率如何。

knn <- function(df, k = 5)
{
  distance <- distance.matrix(df)
  
  predictions <- rep(NA, nrow(df))
  
  for (i in 1:nrow(df))
  {
    indices <- k.nearest.neighbors(i, distance, k = k)
    predictions[i] <- ifelse(mean(df[indices, "Label"]) > 0.5, 1, 0)
  }
  
  return(predictions)
}

正确率的计算

将 knn 函数返回的 Label 预测向量利用 transform 函数添加到原数据框中

1	data <- transform(data, kNNPredictions = knn(data))

预测错误了多少条？

1	sum(with(data, Label != kNNPredictions))

## [1] 7

knn 算法的正确率多少？

1	sum(with(data, Label == kNNPredictions))/nrow(data)

1	## [1] 0.93

可以看到，我们的正确率还是不错的，不过仍然有一些点是预测错误的。具体是哪些点呢？

1	with(data,which(Label != kNNPredictions))

1	## [1] 5 11 18 20 84 93 95

我们可以将这些点在图中标注出来，用三角形来表示预测错误的点

index <- with(data,which(Label != kNNPredictions))
data$differ <- "right"
data$differ[index] <- "wrong"
visual + geom_point(aes(shape = factor(data$differ))) + scale_shape_manual(values = c(21,24)) + scale_colour_brewer(palette = "Set1")

可以看到，预测错误的点都是“深入敌后”的样本点。

使用 class 包实现 knn 算法

class 包中有三个和 knn 算法相关的函数，分别是

knn k-Nearest Neighbour Classification
knn1 1-nearest neighbour classification
knn.cv k-Nearest Neighbour Cross-Validatory Classification

关于三个函数的参数说明和使用方法，请见class 包中的 knn 系列函数一文

数据准备

我们仍然采用前面的数据集 data

1	head(data)

##          X        Y Label kNNPredictions differ
## 1 2.373546 5.398106     0              0  right
## 2 3.183643 4.387974     0              0  right
## 3 2.164371 5.341120     0              0  right
## 4 4.595281 3.870637     0              0  right
## 5 3.329508 6.433024     0              1  wrong
## 6 2.179532 6.980400     0              0  right

我们只保留原始数据，因此去掉 data 数据集的后两列

1 2	data <- data[c("X","Y","Label")] head(data)

##          X        Y Label
## 1 2.373546 5.398106     0
## 2 3.183643 4.387974     0
## 3 2.164371 5.341120     0
## 4 4.595281 3.870637     0
## 5 3.329508 6.433024     0
## 6 2.179532 6.980400     0

由于我们在上文中已经定义了 knn 函数，这与即将要加载的 class 包中 knn 函数同名，因此我们需要先删除之前定义的 knn 函数，以免引起混淆

1 2	rm(knn) library(class)

接下来，我们为 class 包中的 knn 函数和 knn1 函数准备训练集和测试集

1
2
3

trainset <- data[c(1:25,51:75),1:2]
testset <- data[c(26:50,76:100),1:2]
trainlabel <- data[c(1:25,51:75),3]

使用 class::knn 和 class::knn1 进行分类

针对上述测试集，我们对其分类进行预测

1 2	pred.knn <- knn(train = trainset,test = testset,cl = trainlabel, k = 3) pred.knn1 <- knn1(train = trainset,test = testset,cl = trainlabel)

我们来看一下使用 knn 和 knn1 的各自分类效果如何

testlabel <- data[c(26:50,76:100),3]
accuracy.knn <- sum(pred.knn == testlabel)/length(testlabel)
accuracy.knn1 <- sum(pred.knn1 == testlabel)/length(testlabel)
accuracy.knn

1	## [1] 0.86

1	accuracy.knn1

1	## [1] 0.86

使用 class::knn.cv 进行分类

对于 knn.cv 函数，我们把所有的数据都放到训练集中去

1 2	trainset <- data[1:100,1:2] trainlabel <- data[1:100,3]

使用 knn.cv 进行预测，并计算其准确率

1	sum(knn.cv(trainset,trainlabel,k = 3) == trainlabel)/length(trainlabel)

1	## [1] 0.91

可以看到，同样使用 k = 3 的参数，knn.cv 比 knn 的表现要好一些

使用 caret 包实现 knn 算法

仍然使用上述数据集 data, 我们使用 caret 包中的 createDataPartition 函数将数据集划分为训练集和测试集，然后使用 caret 包中的 knn3 函数和 predict.knn3 函数进行分类预测，并最终计算分类准确率

使用 createDataPartition 函数划分训练集和测试集

1	library(caret)

1	## Loading required package: lattice

1 2	set.seed(2014) createDataPartition(y = data$Label, times = 1, p = 0.5)

## $Resample1
##  [1]   2   3   4   5   7   9  15  17  20  22  23  24  26  31  32  35  36
## [18]  38  40  41  43  44  46  47  50  52  57  58  61  62  65  67  69  70
## [35]  72  74  76  77  78  79  83  87  88  89  90  93  96  98  99 100

在 createDataPartition 函数中，主要有三个参数(其他参数请查阅帮助文档)

y 真实分类数据
times 从 y 中创建的 partition 的个数，除非重复实验，否则需要一个就行
p 训练集占数据集的比重

使用 createDataPartition 的好处在于，它能将低熵数据集随机抽取出我们需要的训练集来。比如我们的数据集共有 100 个样本点，前 50 个是一类，后 50 个是一类。我们为了让训练集里两类样本都各有一些，必然希望从前 50 个样本点随机抽取一定比例，后 50 个里也随机抽取相应比例的样本点来组成训练集。这个手动过程因为涉及到人的主观意识，从而不能保证完全随机化。而 createDataPartition 会自动从 y 的各个 level 随机取出等比例的数据来，组成训练集，给我们省了很多事。

createDataPartition 函数默认返回的是列表，我们将其中的训练集对应坐标提取出来，并用其去划分训练集

1 2	set.seed(2014) index.caret <- createDataPartition(y = data$Label, times = 1, p = 0.5)[[1]]

使用 knn3 函数进行分类预测

这一步要使用 caret 包的两个函数

knn3 用来建模，有好几种实现形式，我们选用公式形式，返回的是一个 knn3 类型
predict.knn3，也可以写成 predict，针对 knn3 类型的模型，提供测试数据集，可以预测

1
2
3

data.fit <- knn3(factor(Label) ~ ., data, index.caret, k = 3)
predict.caret <- predict(data.fit,newdata = data[-index.caret,1:2],type = "class")
predict.caret

1
2
3

##  [1] 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
## [36] 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1
## Levels: 0 1

我们再把预测的结果和测试集的真实分类作比较，计算预测准确率

1	sum(predict.caret == data[-index.caret,3])/length(index.caret)

1	## [1] 0.88

准确率也不错。

综上所述，在本篇文章中的数据集下，用自己编写代码的方式、class包、caret包都能取得较好的预测准确率。