KNN 算法的背景

KNN（Nearest Neighbors）算法或称K近邻算法的思想最早来自于伯克利统计学家 Fix 和 Joseph (1961)¹ 给美国空军写的一份关于非参数分类方法的报告。
- 他们从1944年开始参与美国空军第二十空军的统计问题项目。可能是因为工作的性质，他们从未正式发表该论文。1989年International Statistical Review首次印发了他们的工作。
  - 基本思路若一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的，大多数属于某一个类别(投票器)，则该样本也属于这个类别。

Fix, Evelyn(1904-1965)

Joseph L. Hodges (1922-2000)

$~$

Thomas 和 peter （1968）²给出理论上比较成熟的KNN算法。
随后，为解决样本间距离精确度量、k值选择、高效计算等问题，相继出现了WAKNN、AkNN、KNN-Kmeans等改进KNN算法。
KNN 算法的应用场景：产品推荐（如，淘宝的有好货）、医疗诊断（如，心脏病复发诊断）、信用评价（如，蚂蚁信用）等

$~$

KNN算法的基本原理

KNN 基本原理

例：现有7组红蓝颜色饱和度和亮度的样本，试预测新样本(40,35)可能的颜色。

亮度	饱和度	颜色类型
40	20	红色
50	50	蓝色
60	90	蓝色
10	25	红色
70	70	蓝色
20	10	红色
25	50	蓝色
40	35	?

注：常用的颜色格式有rgb， hsb(H(hues)表示色相，S(saturation)表示饱和度，B（brightness）表示亮度) ，名称有十六进制和字符

mycolors <- colorRampPalette(c("blue", "Red"))(1e3);#mycolors[1:3]
barplot(rep(1, times = 1e3), col = mycolors, border = mycolors, axes = FALSE)
# to rgb
#mycolorsRgb <- farver::decode_colour(mycolors, to = "rgb"); dim(mycolorsRgb); head(mycolorsRgb, 3)
# to hsl
#mycolorsHsl <- farver::decode_colour(mycolors, to = "hsl"); dim(mycolorsHsl); head(mycolorsHsl, 3)

绘图散点图，查看样本的亮度和饱和度的分布情况。

vc1 = c(40, 50, 60, 10, 70, 20, 25, 40)
vc2 = c(20, 50, 90, 25, 70, 10, 50, 35)
typ = c('红色','蓝色','蓝色','红色','蓝色','红色','蓝色','黑色')
cols = sapply(typ, function(x){
  switch(x,
  '红色' = 'red',
  '蓝色' = 'blue',
  '黑色' = 'black'
  )
}) 
plot(vc1, vc2, type='p', pch=16, cex=4, col=typ, 
     xlim = c(0,80),
     ylim = c(-10, 100)
       )

思考：新样本（黑色实心圆）属于红色还是蓝色？

KNN算法的基本原理

直观的做法：以新样本为中心画圆，统计指定半径下圆内部不同颜色实心圆的个数。

library(plotrix)
op = par(mar=c(4,4,3,1))
plot(vc1, vc2, type='p', pch=16, cex=4, col=cols, 
     xlim = c(0,80),
     ylim = c(-10, 100),
     main = '红蓝颜色的饱和度和亮度分布图'
       )
draw.circle(40, 35, seq(10, 30, by=5), 
            border = 'gray50')
par(op)

KNN中K的含义：距离目标样本最近的样本个数。
思考：
1. 数据量大时，上述绘制同心圆的方式会出现什么问题？
2. 当某个同心圆内各颜色数据均等时，该如何判断？
3. K该取多大？

$~$

KNN算法的距离度量

距离度量

基于距离的做法，量化目标样本同其他样本之间的距离

library(plotrix)
op = par(mar=c(4,4,3,1))
plot(vc1, vc2, type='p', pch=16, cex=4, col=cols, 
     xlim = c(0,80),
     ylim = c(-10, 100),
     main = '红蓝颜色的饱和度和亮度分布图'
       )
draw.circle(40, 35, seq(10, 30, by=5), 
            border = 'gray50')
segments(40, 35, 50, 35, col='red', lwd=4)
segments(50, 35, 50, 50, col='red', lwd=4)
segments(40, 35, 50, 50, col='red', lty=2, lwd=4)
text(40, 32, 'A (40, 35)', col='blue', font=2)
text(50, 53, 'B (50, 50)', col='blue', font=2)
text(50, 32, 'C (50, 35)', col='blue', font=2)       
par(op)

根据勾股定理计算中心点A到样本点B之间的距离。
- 计算直角边 AC 和 BC 的长度，然后计算 \[AB = \sqrt{AC^2+BC^2}\]

# 计算AC 和 BC 的距离
lAC = 50 - 40; lBC = 50 - 35

# 计算 AB
AB = sqrt(lAC^2 + lBC^2); AB

## [1] 18.02776

欧式（欧几里得）距离：已知坐标点 $(x_1,y_1)$ 和 $(x_2, y_2)$，则它们之间的欧氏距离为 \[ \begin{equation}\tag{1} d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}. \end{equation} \]
- 当每个样本存在3个特征（如颜色的饱和度、亮度、色相），设坐标点为 $(x_1,y_1,z_1)$ 和 $(x_2, y_2, z_2)$，此时基于式(1)有它们之间的欧氏距离 \[ \begin{equation}\tag{2} d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2 + (z_1-z_2)^2}. \end{equation} \]
- 依次类推，当每个样本存在$p$个特征，坐标点 $\boldsymbol{X} = (X_1,\dots, X_p)$ 和 $\boldsymbol{Y} = (Y_1,\dots, Y_p)$之间的欧式距离为 \[ \begin{equation}\tag{3} d = \sqrt{(X_1-Y_1)^2+\dots + (X_p-Y_p)^2}=\sqrt{\sum_{i=1}^{p}(X_i-Y_i)^2} . \end{equation} \]
  - 其他距离测度有：闵可夫斯基距离、绝对距离、切比雪夫距离以及夹角余弦距离，它们分别表示为： \[ \begin{align} &\sqrt[\leftroot{10} \uproot{5} k]{\sum_{i=1}^{p}|X_i-Y_i|^{k}}, &\sum_{i=1}^{p}|X_i-Y_i|, \\ & max(|X_i-Y_i|, i=1,\dots,p), &\frac{\sum_{i=1}^{p}(X_iYi)}{\sqrt{\sum_{i=1}^p}X_i^2\cdot \sqrt{\sum_{i=1}^p}Y_i^2} \end{align} \]

距离度量

计算目标样本到所有样本的欧式距离，步骤包含：
1. 构建计算欧式距离的函数；
2. 将样本依次循环应用到该函数；
3. 把计算结果按从小到达的顺序排列。

# 1. 构建计算欧式距离的函数
f.Euclid = function(a, b=c(40, 35)){
  # b默认为本例中目标样本的坐标
  l1 = b[1] - a[1]
  l2 = b[2] - a[2]
  d = sqrt(l1^2 + l2^2)
  d
}

# 2. 将样本依次循环应用到该函数
## for method
vc1s = c(40, 50, 60, 10, 70, 20, 25)
vc2s = c(20, 50, 90, 25, 70, 10, 50)
typ = c('红色','蓝色','蓝色','红色','蓝色','红色','蓝色','黑色')
res = numeric(length(vc1s)); 
for(i in 1:length(vc1s)){
  ai = c(vc1s[i], vc2s[i])
  res[i] = f.Euclid(ai)
}
res

## [1] 15.00000 18.02776 58.52350 31.62278 46.09772 32.01562 21.21320

## apply method
vcs = cbind(vc1s, vc2s)
res = apply(vcs, 1, function(x) f.Euclid(x))
res

## [1] 15.00000 18.02776 58.52350 31.62278 46.09772 32.01562 21.21320

# 3. 把计算结果按从小到达的顺序排列
sort(res) # 给出排序

## [1] 15.00000 18.02776 21.21320 31.62278 32.01562 46.09772 58.52350

order(res) # 给出索引

## [1] 1 2 7 4 6 5 3

# 4. 整合结果
knitr::kable(
  data.frame(vc1s, vc2s, 
           `颜色种类` = typ[-length(typ)],
           `欧式距离` = res)[order(res),],
  align='c',
  row.names = FALSE,
  caption = "红蓝颜色样本距离目标样本点的欧式距离",
  format="html"
)

红蓝颜色样本距离目标样本点的欧式距离
vc1s	vc2s	颜色种类	欧式距离
40	20	红色	15.00000
50	50	蓝色	18.02776
25	50	蓝色	21.21320
10	25	红色	31.62278
20	10	红色	32.01562
70	70	蓝色	46.09772
60	90	蓝色	58.52350

为便于后续应用，现将上面循环计算欧式距离和最近近邻判断的程序整合为统一的函数f.myknn

f.myknn = function(trainData, trainlabel, testPoint, k=1){
  ntr = nrow(trainData)
  res = numeric(ntr); 
  for(i in 1:ntr){
    ai = trainData[i,]
    res[i] = f.Euclid(ai, testPoint)
}
res = table((trainlabel[order(res)])[1:k])
# 判断结果是不是只包含一类
ifelse(length(res)==1, names(res),
       names(res)[max(res)])
}

f.myknn(trainData =vcs, 
        trainlabel = typ[-length(typ)], 
        testPoint = c(40, 35),
        k = 3
        )

## [1] "蓝色"

$~$

KNN算法的k值选择

K值选择

KNN 算法中最紧邻个数 K 直接影响分类的结果，因此K值的选择对KNN分类的精度至关重要。
两种常用的K值选择方法是：留一法，旁置法。
- 留一法：
  1. 从$n$个观测集中，依次抽取一个样本作为测试样本；
  2. 计算该样本同其他样本之间的距离；
  3. 找出距离该测试样本最近的K样本，统计各类比例，设置测试样本的类型为比例最大的类型；
  4. 重复上面过程，便利所有样本。
  - 该算法涉及几个循环？
- 旁置法：
  1. 把数据结合进行分割，$2/3$的样本用做训练集，其余样本作为测试集合。
  2. 对指定的近邻个数 K，在训练集上按留一法：给出样本类别的预测值。
  3. 然后，基于留一法：，在具有新标签的训练样本下，依次判断预测集样本的类别。
  - 该算法涉及几个循环？
如何度量预测的精度呢？：
- MSE（均方误差）:设y_i$和$_i$分别是样本的实际类别和预测类别,$i=12,,n$，则有 \[ \begin{align} MSE = \frac{1}{n}\sum_{i=1}^{n}(y_i - \hat{y}_i)^2 \end{align}, \] 留一法：直接计算所有类别的MSE，而旁置法：计算预测集上的MSE
- 判错率:，对于下面分类的混淆阵,其判错率为 \[ \begin{align} \frac{n_2+n_3}{n_1+n_2+n_3+n_4} \end{align} \]
  
  预测值
  
  1
  
  0
  
  实际值
  
  1
  
  $n_1$
  
  $n_2$
  
  0
  
  $n_3$
  
  $n_4$

	预测值
实际值	1	\(n_1\)	\(n_2\)
0	\(n_3\)	\(n_4\)

$~$

KNN算法的实施

下面以一组模拟数据集说KNN算法的计算过程
- 模拟数据

set.seed(12) ## 设置随机种子，保证可重复

# 设置两组模拟变量
simulatedDataGroup1 <- cbind(X = rnorm(100), Y = rnorm(100)) 
simulatedDataGroup2 <- cbind(X = rnorm(100, mean = 2), Y = rnorm(100, mean = 2)) 

#组合数据
combinedData <- matrix(nrow = 200, ncol = 2)                                                                   
combinedData[1:100, ] <- simulatedDataGroup1
combinedData[101:200, ] <- simulatedDataGroup2 

#设置标签
groupMembership <- c(rep("red", 100), rep("blue", 100)) 

plot(combinedData, col = groupMembership, main = "原始数据")

在留一法下，计算K=1是的分类情况

ns1 = nrow(combinedData) 

labelPrect = NULL
for (i in 1:ns1) {
  trainData = combinedData[-i,]
  trainlabel = groupMembership[-i]
  testPoint = combinedData[i,]
  labelPrect = c(labelPrect, f.myknn(trainData, trainlabel, testPoint,k=3))
}

# 判断预测和真实值之间的相似性
tp = table(groupMembership, labelPrect);tp

##                labelPrect
## groupMembership blue red
##            blue   81  19
##            red     2  98

tpr = (1 - sum(diag(tp))/sum(tp))*100 # 计算判错率的百分比
tpr

## [1] 10.5

扩展到k=1、3、5、7、9

tprs = NULL
kv = c(1, 3, 5, 7, 9, 11, 13, 17, 19)
for(k in kv){
  ns1 = nrow(combinedData) 
  labelPrect = NULL
  for (i in 1:ns1) {
  trainData = combinedData[-i,]
  trainlabel = groupMembership[-i]
  testPoint = combinedData[i,]
  labelPrect = c(labelPrect, f.myknn(trainData, trainlabel, testPoint, k=k))
  }
  # 判断预测和真实值之间的相似性
  tp = table(groupMembership, labelPrect);#tp
  tprs = c(tprs, (1 - sum(diag(tp))/sum(tp))*100) #   计算判错率的百分比
}
tprs

## [1] 12.0000000 10.5000000  2.7027027  2.2222222  1.6129032  1.7241379  0.9345794
## [8]  1.0309278  1.0638298

plot(kv, tprs, type = 'o')
grid()

使用class::knn函数实现该过程

k-nearest neighbour classification for test set from training set. For each row of the test set, the k nearest (in Euclidean distance) training set vectors are found, and the classification is decided by majority vote , with ties broken at random. If there are ties for the kth nearest vector, all candidates are included in the vote.

knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)
- train test：训练集和测试集，可以为矩阵、数据框以及向量；
- cl：训练集真实类别；
- k：K近邻数；
- prob：返回概率值；
- use.all：等类别时，扩大K

library(class)

tprs1 = NULL
kv = c(1, 3, 5, 7, 9, 11, 13, 17, 19)
for(k in kv){
  ns1 = nrow(combinedData) 
  labelPrect = NULL
  for (i in 1:ns1) {
  trainData = combinedData[-i,]
  trainlabel = groupMembership[-i]
  testPoint = combinedData[i,]
  labelPrect = c(labelPrect, knn(trainData,  testPoint, trainlabel, k=k))
  }
  # 判断预测和真实值之间的相似性
  tp = table(groupMembership, labelPrect);#tp
  tprs1 = c(tprs1, (1 - sum(diag(tp))/sum(tp))*100) #   计算判错率的百分比
}
tprs1

## [1] 12.0  9.5  8.5  8.0  7.5  7.0  8.0  7.0  7.0

plot(kv, tprs1, type = 'o', ylim=c(0,12))
points(kv, tprs, col='red')
lines(kv, tprs, col='red')
legend('topright', c('f.myknn', 'knn'), 
       lty=1, col = c('red', 'black'),
       pch =1
       )
grid()

思考，两种方法都使用了欧式距离和多数投票法，为什么出现不同的结果？

KNN算法的实施

使用旁置法拟合上述模拟数据
划分训练集和测试集合

op = par(mfrow=c(1,2),mar=c(4,6,4,4))
SampleId<-sample(x=1:200,size=50)
groupMembershipNu = ifelse(groupMembership=='red',0,1)
Data <- data.frame(combinedData,groupMembershipNu)
DataTest<-Data[SampleId,]   
DataTrain<-Data[-SampleId,]  
plot(Data[,1:2],pch=Data[,3]+1,cex=0.8,xlab="x1",ylab="x2",main="全部样本")
plot(DataTrain[,1:2],pch=DataTrain[,3]+1,cex=0.8,xlab="x1",ylab="x2",main="训练样本和测试样本")
points(DataTest[,1:2],pch=DataTest[,3]+16,col=2,cex=0.8)

par(op)

不同方法比较

library("class")
errRatio<-vector()   
for(i in 1:30){    
 KnnFit<-knn(train=Data[,1:2],test=Data[,1:2],cl=as.factor(Data[,3]),k=i)
 CT<-table(Data[,3],KnnFit)  
 errRatio<-c(errRatio,(1-sum(diag(CT))/sum(CT))*100)     
}
plot(errRatio,type="l",xlab="近邻个数K",ylab="错判率(%)",main="近邻数K与错判率",ylim=c(0,12))

errRatio1<-vector()   
for(i in 1:30){
 KnnFit<-knn(train=DataTrain[,1:2],test=DataTest[,1:2],cl=as.factor(DataTrain[,3]),k=i) 
 CT<-table(DataTest[,3],KnnFit) 
 errRatio1<-c(errRatio1,(1-sum(diag(CT))/sum(CT))*100)    
}
lines(1:30,errRatio1,lty=2,col=2)

set.seed(12345)
errRatio2<-vector()   
for(i in 1:30){   
 KnnFit<-knn.cv(train=Data[,1:2],cl=as.factor(Data[,3]),k=i) 
 CT<-table(Data[,3],KnnFit)  
 errRatio2<-c(errRatio2,(1-sum(diag(CT))/sum(CT))*100)     
}
lines(1:30,errRatio2,col=2)
legend('bottomright', c('全部','置旁法','留一法'),
       col = c('black', 'red', 'red'), 
       lty = c(1, 2, 1)
       )

KNN算法的实施

KNN 做回归时，再投票法的基础上，计算多数类的均值。

set.seed(12345)
x1<-runif(60,-1,1)  
x2<-runif(60,-1,1)  
y<-runif(60,10,20)   
Data<-data.frame(Fx1=x1,Fx2=x2,Fy=y)
SampleId<-sample(x=1:60,size=18)  
DataTest<-Data[SampleId,]  
DataTrain<-Data[-SampleId,]  
mseVector<-vector()    
for(i in 1:30){
 KnnFit<-knn(train=DataTrain[,1:2],test=DataTest[,1:2],cl=DataTrain[,3],k=i,prob=FALSE) 
 KnnFit<-as.double(as.vector(KnnFit))   
 mse<-sum((DataTest[,3]-KnnFit)^2)/length(DataTest[,3])   
 mseVector<-c(mseVector,mse)
}
plot(mseVector,type="l",xlab="近邻个数K",ylab="均方误差",main="近邻数K与均方误差",ylim=c(0,80))

KNN算法的实施

绘制KNN分类边界
1. 根据坐标值，绘制网格图；
2. 然后把网格点作为测试集合，原数据作为训练集，预测网格点的类型；
3. 根据网格顶类别不同绘制点图，即构建KNN算法的边界。


# 设置网格
XInt <- seq(-2.5, 4.5, by = 0.1) 
YInt <- seq(-3, 6, by = 0.1)

colMatrix5 <- matrix(nrow = length(YInt), ncol = length(XInt))

# 计算每个网格点的类别
for (j in 1:length(XInt)) { 
  for (i in 1:length(YInt)) {
    NN5 <- knn(combinedData, 
               c(XInt[j], YInt[i]),
               groupMembership, 
               k = 5)
    colMatrix5[i, j] <- as.character(NN5)
  }
}

# 设置网格点的位置
rm(NN5, i, j)

Xwhich <- rep(NA, length(colMatrix5))

for (i in ((1:length(XInt))-1)) {
  Xwhich[(1+i*length(YInt)):(length(YInt)+i*length(YInt))] <- (i+1)
}

pointLocations <- data.frame(X = XInt[Xwhich], Y = rep(YInt, length(XInt)))

# 设置点的颜色
coloursPoints5 <- c(colMatrix5)
plot(pointLocations, col = coloursPoints5, cex = 0.1, main = "基于5NN的分类边界")
points(combinedData[,1], combinedData[,2], 
       col=groupMembership,pch=1)

colMatrix1 <- matrix(nrow = length(YInt), ncol = length(XInt))

for (j in 1:length(XInt)) { 
  for (i in 1:length(YInt)) {
    NN1 <- knn(combinedData, 
               c(XInt[j], YInt[i]), 
               groupMembership, 
               k = 1)
    colMatrix1[i, j] <- as.character(NN1)
  }
}

rm(NN1, i, j)

coloursPoints1 <- c(colMatrix1)

plot(pointLocations, col = coloursPoints1, cex = 0.3, main = "基于 1NN 的分类边界")
points(combinedData[,1], combinedData[,2], 
       col=groupMembership,pch=1)

$~$

KNN算法的适用性和特征选择

KNN算法的适用性

前面结果表明K值对KNN边界的影响有：
- KNN可以用于边界不规则的分类问题；
- K值越大，分类边界越平滑。
当空间维度较高时： KNN的局部性可能会消失，导致预测偏差越来越大。

KNN算法的特征选择

1. 从自变量自身考察：重要的变量是取值离散（差异）较大的变量，筛选方法有
- 标准差或变异系数小于某个阈值；
- 分类变量中，类别最大个数或比例大于某个阈值；
- 缺失值大于某个阈值。
1. 从输入变量和输出变量相关性角度考察：相关性越高越重要，变量间相关性的度量方法有
- (数值型,数值型)：相关系数、t检验统计量；
- (数值型/分类型,分类型/数值型)：方差分析,检查不同类别下的均值是否存在显著差异；
- (分类型,数值型)：卡方检验，构建列联表，计算卡方统计量。
1. 从训练误差角度考察：依据训练误差给变量打分，基本思想
- 控制某-变量，计算计算其他变量在KNN下的判错率或均方误差，两种训练方法：逐次加或减变量。

Fix Evelyn and Joseph L. Hodges. “Discriminatory Analysis - Nonparametric Discrimination: Consistency Properties (1961).” International Statistical Review 57 (1989): 238.↩︎
Thomas Cover and Hart Peter. “Nearest neighbor pattern classification.” IEEE transactions on information theory 13.1 (1967): 21-27.↩︎

数据挖掘（1）

R的近邻分析：数据预测

Overview

\(~\)

KNN 算法的背景

\(~\)

KNN 基本原理

KNN算法的基本原理

\(~\)

距离度量

距离度量

\(~\)

K值选择

\(~\)

KNN算法的实施

KNN算法的实施

KNN算法的实施

KNN算法的实施

\(~\)

KNN算法的适用性

KNN算法的特征选择