计算视觉——图像分类— K邻近分类法（KNN）
目录
K邻近分类法（KNN）
KNN算法介绍
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。KNN是通过测量不同特征值之间的距离进行分类。它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN算法的描述
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
由此也说明了KNN算法的结果很大程度取决于K的选择。
KNN算法三要素
1. k值的选择
k值的选择会对k近邻法的结果产生重大影响。
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。
如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这是与输入实例较远的训练实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单（欠拟合）。
在应用中，k值一般选取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
2.距离的度量
距离的度量描述了测试样本与训练样本的临近程度，这个临近程度就是K个样本选择的依据，在KNN算法中，如果特征是连续的，那么距离函数一般用曼哈顿距离（L1距离）或欧氏距离（L2距离），如果特征是离散的，一般选用汉明距离。
曼哈顿距离在KNN中其实就是样本特征每一个维度上的差值的和：
欧氏距离在KNN中其实就是样本特征每一个维度上的差值的平方和开根号：
汉明距离：
3.分类决策规则
通过上面提到的K与距离两个概念，我们就能选择出K个与测试样例最近的训练样本，如何根据这K个样本决定测试样例的类别就是KNN的分类决策规则，在KNN中最常用的就是多数表决规则。但是该规则严重依赖于训练样本的数目，我们后面会提到。
图像分类问题
那么KNN算法如何应用到图像分类问题中，其实问题也就是如何评价一张待分类的图像A与P个训练样本图像中间的距离呢？
其中关键的问题就是图像的特征选择成什么，把问题往更大的方面考虑下，对于图像而言，（传统）机器学习与深度学习的一个很大区别是后者的自动特征抽取，所以深度学习的问世在一定程度上改变了人们对图像处理问题的侧重点，从特征描述到网络结构。所以在下面我们可以不严格的分为两类考虑，直接使用图像与使用一种图像特征提取方法。
1.直接分类
所谓的直接分类本质上是将图像的每个像素点的像素值作为特征，那么此时两种图像的距离（假设使用L1）就是每个对应位置的像素点的像素值差值的绝对值的和。
那么两张图的L1距离为 371。
2.对特征分类
然后很多时候我们不会直接使用像素值作为图像的特征来使用，因为它并不能从本质上反映了人对图像的认知，比如我们将一张图稍稍向一个方向平移一段距离，在人眼看来他们应该是一类，甚至就是同一张，但是如果用像素值计算距离的话，距离确很大。
所以在更多的时候，要计算距离的对象是一些描述子生成的特征，举个例子，HOG+SVM的方法在行人检测中有很好的效果，而SVM的作用也是个分类器，如果换成KNN的话也是可行的（可行指的是原理上可行，效果如何并未考证），所以此时KNN计算的对象其实是HOG生成的描述子，而不再是图像的像素。
但是很不幸的是，KNN在图像问题中几乎不会使用，这个观点来源于斯坦福CS231n，它的原话是 K-Nearest Neighbor on images never used.
原因有两个：
1.很差的测试效率；
2.整个图像水平的距离度量可能非常不直观。
如说第二个原因可以靠着一些特征描述子来解决的话，那么第一个问题就是KNN算法的硬伤，在机器学习中其实我们对测试阶段的时间容忍要远远高于训练阶段，因为最终使用模型解决问题时足够快就可以了，CNN普遍是这样。但是这个问题在KNN中就会无限的暴露出来，“在线”学习的方式决定了样本量越大，分类过程就会越慢。
接下来对KNN算法的思想总结一下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
代码实现
KNN算法实现
实现最基本的KNN 算法：
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 13:42:10 2019
@author: Lenovo
"""
class KnnClassifier(object):
def __init__(self,labels,samples):
""" Initialize classifier with training data.使用训练数据初始化分类器 """
self.labels = labels
self.samples = samples
def classify(self,point,k=3):
""" Classify a point against k nearest
in the training data, return label.
在训练数据上采用 k 近邻分类，并返回标记
"""
# compute distance to all training points 计算所有训练数据点的距离
dist = array([L2dist(point,s) for s in self.samples])
# sort them 对它们进行排序
ndx = dist.argsort()
# use dictionary to store the k nearest 用字典存储 k 近邻
votes = {}
for i in range(k):
label = self.labels[ndx[i]]
votes.setdefault(label,0)
votes[label] += 1
return max(votes, key=lambda x: votes.get(x))
定义一个类并用训练数据初始化非常简单；每次想对某些东西进行分类时，用KNN方法，我们就没有必要存储并将训练数据作为参数来传递。用一个字典来存储邻近标记，我们便可以用文本字符串或数字来表示标记。在这例子中，我们用欧氏距离来进行度量。
我们首先建立一些简单的二维示例数据集来说明并可视化分类的工作原理，下面的脚本将创建两个不同的二维点集，每个点集有两类，用 Pickle 模块来保存创建的数据：
# -*- coding: utf-8 -*-
from numpy.random import randn
import pickle
from pylab import *
# create sample data of 2D points
n = 200
# two normal distributions
class_1 = 0.6 * randn(n,2)
class_2 = 1.2 * randn(n,2) + array([5,1])
labels = hstack((ones(n),-ones(n))) #标签
# save with Pickle
#with open('points_normal.pkl', 'wb') as f:
with open('points_normal_test.pkl', 'wb') as f:
pickle.dump(class_1,f) #数据存文件
pickle.dump(class_2,f)
pickle.dump(labels,f)
#正态分布，并使数据成环绕状分布
# normal distribution and ring around it
print ("save OK!")
class_1 = 0.6 * randn(n,2)
r = 0.8 * randn(n,1) + 5
angle = 2*pi * randn(n,1)
class_2 = hstack((r*cos(angle),r*sin(angle)))
labels = hstack((ones(n),-ones(n)))
# save with Pickle
#with open('points_ring.pkl', 'wb') as f:
with open('points_ring_test.pkl', 'wb') as f:
pickle.dump(class_1,f)
pickle.dump(class_2,f)
pickle.dump(labels,f)
print ("save OK!")
用不同的保存文件名运行该脚本两次，例如第一次用代码中的文件进行保存，第二次将代码中的 points_normal_t.pkl 和points_ring_ppkll 分别改为 points_normal_tst.pkl 和 points_ring_test.pkl 进行保存。这将得到四个二维数集文件，每个分布都有两个文件，我们可以将一个用来训练另一个用来测试。
创建一个脚本实现KNN分类器：
# -*- coding: utf-8 -*-
import pickle
from pylab import *
from PCV.classifiers import knn
from PCV.tools import imtools
pklist=['points_normal.pkl','points_ring.pkl']
figure()
# load 2D points using Pickle
for i, pklfile in enumerate(pklist):
with open(pklfile, 'rb') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)
# load test data using Pickle
with open(pklfile[:-4]+'_test.pkl', 'rb') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)
model = knn.KnnClassifier(labels,vstack((class_1,class_2)))
# test on the first point
print (model.classify(class_1[0]))
#define function for plotting
def classify(x,y,model=model):
return array([model.classify([xx,yy]) for (xx,yy) in zip(x,y)])
# lot the classification boundary
subplot(1,2,i+1)
#绘制分类边界
imtools.plot_2D_boundary([-6,6,-6,6],[class_1,class_2],classify,[1,-1])
titlename=pklfile[:-4]
title(titlename)
show()运行结果：
用稠密SIFT作为图像特征
要对图像进行分类，我们需要一个特征向量来表示一幅图像。这里用稠密SIFT特征向量来表示。
在整幅图像上用 一个规则的网格应用SIFT描述子可以得到稠密SIFT的表示形式。
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 14:37:48 2019
@author: Lenovo
"""
from PIL import Image
from numpy import *
import os
from PCV.localdescriptors import sift
def process_image_dsift(imagename,resultname,size=20,steps=10,force_orientation=False,resize=None):
""" Process an image with densely sampled SIFT descriptors
and save the results in a file. Optional input: size of features,
steps between locations, forcing computation of descriptor orientation
(False means all are oriented upwards), tuple for resizing the image."""
im = Image.open(imagename).convert('L')
if resize!=None:
im = im.resize(resize)
m,n = im.size
if imagename[-3:] != 'pgm':
#create a pgm file
im.save('tmp.pgm')
imagename = 'tmp.pgm'
# create frames and save to temporary file
scale = size/3.0
x,y = meshgrid(range(steps,m,steps),range(steps,n,steps))
xx,yy = x.flatten(),y.flatten()
frame = array([xx,yy,scale*ones(xx.shape[0]),zeros(xx.shape[0])])
savetxt('tmp.frame',frame.T,fmt='%03.3f')
path = os.path.abspath(os.path.join(os.path.dirname("__file__"),os.path.pardir))
path = path + "\\ch8\\win32vlfeat\\sift.exe "
print(path)
if force_orientation:
cmmd = str("sift " + imagename + " --output=" + resultname + " --read-frames=tmp.frame --orientations")
else:
cmmd = str("sift " + imagename + " --output=" + resultname + " --read-frames=tmp.frame")
os.system(cmmd)
os.system(cmmd)
print(cmmd)
print ('@ processed', imagename, 'to', resultname)
在这个函数中的最后一个参数可以在提取描述子之前对图像的大小进行调整，例如，传递参数 imsize=（100,100）会将图像调整为100*100像素的方形图像。最后如果fore_orientation为真，则提取出来的描述子会基于局部主梯度方向进行归一化；否则，则所有的描述子的方向只是简单的朝上。
利用下面代码可以计算稠密SIFT描述子，并可视化它们的位置：
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 14:03:50 2019
@author: Lenovo
"""
from PCV.localdescriptors import sift, dsift
from pylab import *
from PIL import Image
dsift.process_image_dsift('gesture/1.jpg','1.dsift',90,40,True)
l,d = sift.read_features_from_file('1.dsift')
im = array(Image.open('gesture/1.jpg'))
sift.plot_features(im,l,True)
title('dense SIFT')
show()使用用于定位描述子的局部梯度方向（force_orientation设置为真），该代码可以在整个图像中计算出稠密SIFT特征。
当 dsift.process_image_dsift('gesture/1.jpg','1.dsift',40,40,True)时：
图像分类：手势识别
用上面的SIFT函数对图像进行处理，可以得到所有图像的特征向量。这里再次假设列表imlist中包含了所有图像的文件名，可通过下面的代码得到每幅图像的稠密SIFT特征：
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 16:52:09 2019
@author: Lenovo
"""
# -*- coding: utf-8 -*-
import os
from PCV.localdescriptors import sift, dsift
from pylab import *
from PIL import Image
imlist=['gesture/test1/C-uniform01.jpg','gesture/test1/C-uniform02.jpg',
'gesture/test1/Five-uniform03.jpg','gesture/test1/V-uniform04.jpg',
'gesture/test1/A-uniform05.jpg','gesture/test1/Four-uniform06.jpg',
'gesture/test1/Point-uniform07.jpg','gesture/test1/Point-uniform08.jpg',
'gesture/test1/OK-uniform09.jpg','gesture/test1/Good-uniform10.jpg']
figure()
for i, im in enumerate(imlist):
print (im)
dsift.process_image_dsift(im,im[:-3]+'dsift',180,180,True)
l,d = sift.read_features_from_file(im[:-3]+'dsift')
dirpath, filename=os.path.split(im)
im = array(Image.open(im))
#显示手势含义title
titlename=filename[:-14]
subplot(2,5,i+1)
sift.plot_features(im,l,True)
title(titlename)
show()运行结果：
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 14:39:55 2019
@author: Lenovo
"""
from PCV.localdescriptors import dsift
import os
from PCV.localdescriptors import sift
from pylab import *
from PCV.classifiers import knn
def get_imagelist(path):
""" Returns a list of filenames for
all jpg images in a directory. """
return [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.jpg')]
def read_gesture_features_labels(path):
# 对所有以.dsift为后缀的文件创建一个列表
featlist = [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.dsift')]
# 读取特征
features = []
for featfile in featlist:
l,d = sift.read_features_from_file(featfile)
features.append(d.flatten())
features = array(features)
# 创建标记
labels = [featfile.split('/')[-1][0] for featfile in featlist]
return features,array(labels)
def print_confusion(res,labels,classnames):
n = len(classnames)
# confusion matrix
class_ind = dict([(classnames[i],i) for i in range(n)])
confuse = zeros((n,n))
for i in range(len(test_labels)):
confuse[class_ind[res[i]],class_ind[test_labels[i]]] += 1
print ('Confusion matrix for')
print (classnames)
print (confuse)
filelist_train = get_imagelist('gesture/train')
filelist_test = get_imagelist('gesture/test1')
imlist=filelist_train+filelist_test
# process images at fixed size (50,50)
for filename in imlist:
featfile = filename[:-3]+'dsift'
dsift.process_image_dsift(filename,featfile,10,5,resize=(50,50))
features,labels = read_gesture_features_labels('gesture/train/')
test_features,test_labels = read_gesture_features_labels('gesture/test/')
classnames = unique(labels)
# test kNN
k = 1
knn_classifier = knn.KnnClassifier(labels,features)
res = array([knn_classifier.classify(test_features[i],k) for i in
range(len(test_labels))])
# accuracy
acc = sum(1.0*(res==test_labels)) / len(test_labels)
print ('Accuracy:', acc)
print_confusion(res,test_labels,classnames)
结果分析
在上面的代码中，我们先是定义一个辅助函数 read_gesture_features_labels(path) 用于从文件中读取稠密SIFT描述子。用训练集及其标记作为输入，创建分类器对象；然后，我们在整个测试集上遍历并用classfy（）方法对每幅图像进行分类。将布尔数组和1相乘并求和，可以计算出分类的正确率。
会打印出如下结果：
Accuracy: 0.813471502591
这说明有81%的图像正确的。这个结果会随着K值及稠密SIFT图像描述子参数的变化而变化。
打印出来的正确率显示了对于一给定的测试集有多少图像是正确分类的，但是没有告诉我们那些手势难以分类，或会犯哪些错误。为此这里我们就引入了混淆矩阵。混淆矩阵是一个可以显示每类有多少个样本被分在每一类中的矩阵，它可以显示错误的分类情况，以及哪些类是经常相互“混淆”的。
当训练集与测试集相同时，准确率达到100%；
当训练集为自己拍的手势时：
Accuracy: 0.3
这是因为训练集和测试集不同，有些训练集的手势没有在训练集里，也就是没有被训练到，无法识别出来。
然而KNN作为一个简单的机器学习算法，同样存在很多不足：
1 首先，KNN算法是基于实例的，也就是说我们需要掌握接近实际数据的训练样本数据。
2 其次，训练样本的数目决定了存储空间的大小。以及由于必须对数据集中的每一个数据都计算距离，计算量很大。
3 由于只是采用距离来做度量，没有考虑到实际数据本身的结构信息，因此很难知道数据本身背后的含义。
4 kNN采用的是“majority-voting”的方法，在数据严重不对称时，也就是说如果某一类数据本身就出现的概率非常大，那么新来的样本就很有可能落入该类别中。这显然是不合理的。克服这个，可以给每一个邻居加上一个权重。也可以将其中的距离相近的点Merge成一个节点，作为一个整体，就不用管在原先数据集中的密度。再进行分类。
上一篇： Spring-AOP 流程切面