概述

KNN算法(K最近邻算法)也是一种基本的机器学习算法,可以用于分类和回归任务中。即对于给定一个训练数据集,对新的实例在训练数据集中找到与该实例最邻近的k个实例。我们看一下可视化的KNN算法:

KNN 算法

如上图我们看到,给定一个新输入实例对于k的取值不同,对该算法的结果影响比较大,其次是当训练样本数大、特征向量维度很高时计算复杂度也高。因为我们在预测时需要计算预测样本和每一个训练样本的距离,并且对距离进行排序找到最近的k个样本并将结果返回。

    1. 使用高效的部分排序算法,只找出最小的k个数。
    1. k-d树实现快速的近邻查找。

KNN算法三要素

算法定义

分类算法定义

输入: 训练数据集

$$T={(x_1,y_1),(x_2,y_2)…(x_N,y_N)}$$

其中,$x_i \in X $的n维特征向量,$y_i \in Y={c_1,c_2….c_k}$为实例的类别

输出:实例x所属的类y

  1. 所以需要根据给定的距离度量来选择预测实例最邻近的k个点,记为$N_k(x)$。

  2. 在$N_k(x)$中根据分类决策规则决定x的类别y。

    $$ y=argmax \sum_{x_i \in N_k(x)}I(y_i=c_j),i=1,2,…N;j=1,2,3…K $$

回归算法定义

假设离测试样本最近的k个训练样本的标签值为$y_i$,则对样本的的回归预测值为:

$$ y=(\sum_{i=1}^k y_i)/k $$

即所有邻居的标签均值,我们认为最近的k个邻居贡献是相等的。我们也可以采用带权重的方式,

$$ y=(\sum_{i=1}^k w_i \cdot y_i)/k $$

knn算法没有显示的学习过程。

KNN模型

knn算法中,当训练数据集、距离度量、k值及分类决策规则确定后,对于任何一个新的实例,它所属的类唯一的确定。

距离定义

knn中的距离度量有很多种方式,我们这里只介绍其中两种距离度量方式曼哈顿距离和欧氏距离

曼哈顿距离

$$ L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}| $$

欧式距离

$$ L_2(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|)^{\frac{1}{2}} $$

k值的选择

不同的k值对算法结果产生重大的影响

  • 如果选择较小的k值,学习的近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用,但是学习的估计误差会增大,预测结果对于近邻的实例点非常敏感。k值的减小意味着整体模型边的复杂,容易发生过拟合。
  • 如果选择较大的k值,可以减少学习的估计误差,但是近似误差会增大,k值的增大意味着整体的模型变得简单。

所以我们一般将数据集划分为训练数据集、验证数据集和测试数据集,k值一般取一个比较小的数值,采用交叉验证的方法来选取最优的K值。

决策规则

knn算法中分类的决策规则往往是多数表决,即经验风险最小化。

KNN算法实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def classifyByKnn(k,x_train,y_labels,test):
  num_test = test.shape[0]
  labellist=[]
  for i in range(num_test):
    distances = np.sqrt(np.sum(((x_train-np.tile(test[i],(x_train.shape[0],1)))**2),axis=1))
    nearest_k = np.argsort(distances)
    topK = nearest_k[:k]
    classCount={}
    for i in topK:
      classCount[y_labels[i]]=classCount.get(y_labels[i],0)+1
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    labellist.append(sortedClassCount[0][0])
  return np.array(labellist)
                             

KNN 实战之图像分类

我们可以使用KNN算法来实现一个图像分类算法,我们选取的数据集为Cifar10(其中包含了飞机、汽车、鸟、猫、鹿、狗等10个类别),在进行图像分类之前我们需要对图像进行数据预处理。数据预处理可以帮助减少后续的运算量以及加速收敛,常用的图像预处理有:归一化、灰度变换、滤波变换、图像形态学变换等等。我们采用facebook开源的pytorch深度学习框架实现knn算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import torch
from torch.utils.data import DataLoader
import torchvision.datasets as dataset
import torchvision.transforms as transforms

#download dataset
batch_size=128
train_dataset = dataset.CIFAR10(root="./dataset",train=True,download=True)
test_dataset = dataset.CIFAR10(root="./dataset",train=False,download=True)

#load dataset
train_loader = torch.utils.data.DataLoader(dataset=train_dataset,batch_size=batch_size,shuffle=True)
test_loader = torch.utils.data.DataLoader(dataset=test_dataset,batch_size=batch_size,shuffle=False)

#labels
classes=('plane','car','bird','cat','deer','dog','frog','horse','ship','truck')

#process image data
def getXmean(x_train):
  x_train = np.reshape(x_train,(x_train.shape[0],-1))
  mean_image = np.mean(x_train,axis=0)
  return mean_image

def centralized(x_test,mean_image):
  x_test = np.reshape(x_test,(x_test.shape[0],-1))
  x_test = x_test.astype(np.float)
  x_test -= mean_image
  return x_test

#train model
train_x = train_loader.dataset.train_data
mean_image = getXmean(train_x)
train_x = centralized(trian_x,mean_image)
train_y = train_loader.dataset.train_labels
test_x = test_loader.dataset.test_data[:128]
test_x = centralized(test_x,mean_image)
test_y = test_loader.dataset.test_labels[:128]
num_test = len(test_y)
pred_y = classifyByKnn(k=6,train_x,trian_y,test_x)
num_correct = np.sum(pred_y==test_y)
accuracy = float(num_correct)/num_test

我们一般将数据集划分为训练集、验证集和测试集,其中对于k可以划分为多个数值,在验证集中选择合适的超参数即k。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
folds = 5
k_values=[3,5,8,10,12,15]
num_training=train_x.shape[0]
train_x_folds=[]
train_y_folds=[]
indices=np.array_split(np.arange(num_training),indices_or_sections=folds)
 accuracy_dict={}
for i in indices:
  train_x_folds.append(train_x[i])
train_y_folds.append(train_y[i])
for k in k_values:
  acc=[]
  for i in range(folds):
    x = train_x_folds[0:i]+train_x_folds[i+1:]
    x = np.concatenate(x,axis=0)
    y = train_y_folds[0:i]+train_y_folds[i+1:]
    y = np.concatenate(y,axis=0)
    test_x_valid = train_x_folds[i]
    test_y_valid = train_y_folds[i]
    #predict方法是对classifyByKnn面向对象的封装,自己可以实现下
    pred_y = knn.predict(k,test_x_valid)
    accuracy = np.mean(pred_y==test_y_valid)
    acc.append(accuracy)
 accuracy_dict[k] = acc
# sort accuracy and check
fok k in sorted(accuracy_dict):
  for accuracy in accuracy_dict[k]:
    print('k=%d,accuracy=%f' % (k,accuracy))

当然你可以将算法和处理流程按照OOP方式进行包装,也可以将k取值的准确率进行可视化出来。

参考链接

  1. 《统计机器学习》李航
  2. 《深度学习》