把经验提供给算法，它能够根据经验数据产生模型。在面对新的情况时，模型会为我们提供判断（预测）结果。
反映对象（事件）在某个方面的表现或者性质的事项，被称为属性或特征
具体的值，如反映身高的“188 cm”，就是特征值或属性值。
这组数据的集合称为数据集，其中每个数据称为一个样本。
从数据中学得模型的过程称为学习（learning）或者训练（training）。
在训练过程中所使用的数据称为训练数据，其中的每个样本称为训练样本，训练样本所组成的集合称为训练集。
如果希望获取一个模型，除了有数据，还需要给样本贴上对应的标签（label）。将拥有了标签的样本称为“样例”。
学得模型后，为了测试模型的效果，还要对其进行测试，被测试的样本称为测试样本。
输入测试样本时，并不提供测试样本的标签（目标类别），而是由模型决定样本的标签（属于哪个类别）。比较测试样本预测的标签与实际样本标签之间的差别，就可以计算出模型的精确度。
K近邻算法主要用于将对象划分到已知类中
理论基础
K近邻算法的本质是将指定对象根据已知特征值分类。
为了确定分类，需要定义特征。
为了提高算法的可靠性，在实施时会取k个近邻点，这k个点中属于哪一类的较多，然后将当前待识别点划分为哪一类。
为了方便判断，k值通常取奇数
计算
计算机的“感觉”是通过逻辑计算和数值计算来实现的。
在大多数的情况下，要对计算机要处理的对象进行数值化处理，将其量化为具体的值，以便后续处理。
比较典型的方法是取某几个固定的特征，然后将这些特征量化。
例如，在人脸识别的过程中，可以根据人脸部器官的形状描述以及它们之间的距离特性来获取有助于分类的特征数据。这些特征数据可能包括特征点间的距离、曲率和角度等。
K近邻算法在获取各个样本的特征值之后，计算待识别样本的特征值与各个已知分类的样本特征值之间的距离，然后找出k个最邻近的样本，根据k个最邻近样本中占比最高的样本所属的分类，来确定待识别样本的分类。
归一化
当有多个参数时，一般将这些参数构成列表（数组）进行综合判断。
在计算与特征值的距离时要充分考虑不同参数之间的权值。
通常情况下，由于各个参数的量纲不一致等原因，需要对参数进行处理，让所有参数具有相等的权值。
做归一化时，通常使用特征值除以所有特征值中的最大值（或者最大值与最小值的差）。
距离计算
- 通常会计算绝对值的和（曼哈顿距离）
- 平方和的方式
- 更普遍的形式是计算平方和的平方根（欧氏距离）
手写数字识别
手写数字识别的原理
识别的方式是，依次计算该数字图像（即写有数字的图像）与样本数字图像的距离，与哪个数字图像的距离最近（此时k=1），就认为它与哪幅图像最像，从而确定这幅图像中的数字是多少。
1. 特征值提取
- 步骤1把数字图像划分成很多小块，例如： 每个数字被分成5行4列，共计5×4=20个小块。每个小块是由很多个像素点构成的
待识别的数字“8”的图像可以理解为：
- 由5行4列，共计5×4=20个小块构成。
- 每个小块内其实是由M×N个像素（更小块）构成的。
- 步骤2计算每个小块内，有多少个黑色的像素点例如：
- 第1个小块B共有0个像素点（更小块）是黑色的，记为0。
- 第2个小块B共有28个像素点（更小块）是黑色的，记为28。
- 以此类推，计算出数字“8”的图像中每一个小块中有多少个像素点是黑色的
不同的数字图像中每个小块内黑色像素点的数量是不一样的。正是这种不同，使我们能用该数量（每个小块内黑色像素点的个数）作为特征来表示每一个数字。
- 步骤3
为了处理上的方便，把得到的特征值排成一行（写为数组形式） - 步骤4
与数字“8”的图像类似，每个数字图像的特征值都可以用一行数字来表示。
2. 数字识别
数字识别要做的就是比较待识别图像与图像集中的哪个图像最近。
这里指 二者之间的欧氏距离最短。
以上介绍的是K近邻算法只考虑最近的一个邻居的情况，相当于K近邻中k=1的情况。
3. 自定义函数手写数字识别
OpenCV提供了函数cv2.KNearest()用来实现K近邻算法，在OpenCV中可以直接调用该函数。
使用Python和OpenCV实现一个识别手写数字的实例。
- 数据初始化
对程序中要用到的数据进行初始化。涉及的数据主要有路径信息、图像大小、特征值数量、用来存储所有特征值的数据等。
s='image\\' # 图像所在的路径 # 用于判断分类的特征值有100个（对应100幅特征图像） num=100 # 共有特征值的数量 row=240 # 特征图像的行数 col=240 # 特征图像的列数 a=np.zeros((num, row, col)) # a用来存储所有特征的值
- 读取特征图像
将所有的特征图像读入到a中。
共有10个数字，每个数字有10个特征图像
n=0 # n用来存储当前图像的编号。 for i in range(0,10): for j in range(1,11): a[n, :, :]=cv2.imread(s+str(i)+'\\'+str(i)+'-'+str(j)+'.bmp',0) n=n+1
- 提取特征图像的特征值
在提取特征值时，可以计算每个子块内黑色像素点的个数，也可以计算每个子块内白色像素点的个数。
选择： 计算白色像素点（像素值为255）的个数。
- 如果原始图像内位于(row, col)位置的像素点是白色，则要把对应特征值内位于(row/5, col/5)处的值加1。
feature=np.zeros((num, round(row/5), round(col/5))) # feature存储所有样本的特征值 #print(feature.shape) # 在必要时查看feature的形状是什么样子 #print(num) # 在必要时查看num的值，有多少个特征值（100个） for ni in range(0, num): for nr in range(0, row): for nc in range(0, col): if a[ni, nr, nc]==255: feature[ni, int(nr/5), int(nc/5)]+=1 f=feature #简化变量名称
- 计算待识别图像的特征值
读取待识别图像，然后计算该图像的特征值。编写代码如下：
of=cv2.imread('image\\test\\9.bmp',0) # 读取待识别图像 # 读取图像的值 of=np.zeros((round(row/5), round(col/5))) # 用来存储待识别图像的特征值 for nr in range(0, row): for nc in range(0, col): if o[nr, nc]==255: of[int(nr/5), int(nc/5)]+=1
- 计算待识别图像与特征图像之间的距离
依次计算待识别图像与特征图像之间的距离
d=np.zeros(100) for i in range(0,100): d[i]=np.sum((of-f[i, :, :])*(of-f[i, :, :]))
- 数组d通过依次计算待识别图像特征值of与数据集f中各个特征值的欧氏距离得到。
数据集f中依次存储的是数字0~9的共计100个特征图像的特征值。
数组d中的索引号对应着各特征图像的编号,用d[mn]表示待识别图像与数字“m”的第n个特征图像的距离。
如果将索引号整除10，得到的值正好是其对应的特征图像上的数字。
例如：d[34]对应着待识别图像到数字“3”的第4个特征图像的欧式距离。而将34整除10，得到int(34/10)=3，正好是其对应的特征图像上的数字。 - 获取k个最短距离及其索引从计算得到的所有距离中，选取k个最短距离，并计算出这k个最短距离对应的索引。实现方法：
- 每次找出最短的距离（最小值）及其索引（下标），然后将该最小值替换为最大值。
- 重复上述过程k次，得到k个最短距离对应的索引。
d.tolist() temp=[] Inf = max(d) #print(Inf) k=7 for i in range(k): temp.append(d.index(min(d))) d[d.index(min(d))]=Inf
- 识别
根据计算出来的k个最小值的索引,确定索引所对应的数字。
temp=[i/10 for i in temp] # 数组r用来存储结果，r[0]表示K近邻中“0”的个数，r[n]表示K近邻中“n”的个数 r=np.zeros(10) for i in temp: r[int(i)]+=1 print('当前的数字可能为：' +str(np.argmax(r)))
完整程序
import cv2 import numpy as np import matplotlib.pyplot as plt # 读取样本（特征）图像的值 s='image\\' # 图像所在路径 num=100 # 样本总数 row=240 # 特征图像的行数 col=240 # 特征图像的列数 a=np.zeros((num, row, col)) # 存储所有样本的数值 #print(a.shape) n=0 # 存储当前图像的编号 for i in range(0,10): for j in range(1,11): a[n, :, :]=cv2.imread(s+str(i)+'\\'+str(i)+'-'+str(j)+'.bmp',0) n=n+1 #提采样本图像的特征 feature=np.zeros((num, round(row/5), round(col/5))) # 用来存储所有样本的特征值 #print(feature.shape) # 看看特征值的形状是什么样子 #print(num) # 看看num的值，有多少个特征值（100） for ni in range(0, num): for nr in range(0, row): for nc in range(0, col): if a[ni, nr, nc]==255: feature[ni, int(nr/5), int(nc/5)]+=1 f=feature # 简化变量名称 #####计算当前待识别图像的特征值 o=cv2.imread('image\\test\\5.bmp',0) # 读取待识别图像 ##读取图像值 of=np.zeros((round(row/5), round(col/5))) # 存储待识别图像的特征值 for nr in range(0, row): for nc in range(0, col): if o[nr, nc]==255: of[int(nr/5), int(nc/5)]+=1 ###开始计算，识别数字，计算最邻近的若干个数字是多少，判断结果 d=np.zeros(100) for i in range(0,100): d[i]=np.sum((of-f[i, :, :])*(of-f[i, :, :])) #print(d) d=d.tolist() temp=[] Inf = max(d) #print(Inf) k=7 for i in range(k): temp.append(d.index(min(d))) d[d.index(min(d))]=Inf #print(temp) #看看都被识别为哪些特征值 temp=[i/10 for i in temp] # 也可以返回去处理为array，使用函数处理 #temp=np.array(temp) #temp=np.trunc(temp/10) #print(temp) # 数组r用来存储结果，r[0]表示K近邻中“0”的个数，r[n]表示K近邻中“n”的个数 r=np.zeros(10) for i in temp: r[int(i)]+=1 #print(r) print('当前的数字可能为：'+str(np.argmax(r)))
K近邻模块的基本使用
使用OpenCV自带的K近邻模块
有两组位于不同位置的用于训练的数据集。两组数据集中，一组位于左下角；另一组位于右上角。随机生成一个数值，用OpenCV中的K近邻模块判断该随机数属于哪一个分组。
位于左下角的一组数据，其x、y坐标值都在(0, 30)范围内。位于右上角的数据，其x、y坐标值都在(70, 100)范围内。
- 根据上述分析，创建两组数据，每组包含20对随机数（20个随机数据点）：
rand1 = np.random.randint(0, 30, (20, 2)).astype(np.float32) rand2 = np.random.randint(70, 100, (20, 2)).astype(np.float32)
- 为两组随机数分配标签：
- 将第1组随机数对划分为类型0，标签为0。
- 将第2组随机数对划分为类型1，标签为1。
- 生成一对值在(0, 100)内的随机数对：
test = np.random.randint(0, 100, (1, 2)).astype(np.float32)
使用OpenCV自带的K近邻模块判断生成的随机数对test是属于rand1所在的类型0，还是属于rand2所在的类型1。
- 代码如下
import cv2 import numpy as np import matplotlib.pyplot as plt # 用于训练的数据 # rand1数据位于(0,30) rand1 = np.random.randint(0, 30, (20, 2)).astype(np.float32) # rand2数据位于(70,100) rand2 = np.random.randint(70, 100, (20, 2)).astype(np.float32) # 将rand1和rand2拼接为训练数据 trainData = np.vstack((rand1, rand2)) # 数据标签，共两类：0和1 # r1Label对应着rand1的标签，为类型0 r1Label=np.zeros((20,1)).astype(np.float32) # r2Label对应着rand2的标签，为类型1 r2Label=np.ones((20,1)).astype(np.float32) tdLable = np.vstack((r1Label, r2Label)) # 使用绿色标注类型0 g = trainData[tdLable.ravel() == 0] plt.scatter(g[:,0], g[:,1], 80, 'g', 'o') # 使用蓝色标注类型1 b = trainData[tdLable.ravel() == 1] plt.scatter(b[:,0], b[:,1], 80, 'b', 's') # plt.show() # test为用于测试的随机数，该数在0到100之间 test = np.random.randint(0, 100, (1, 2)).astype(np.float32) plt.scatter(test[:,0], test[:,1], 80, 'r', '*') # 调用OpenCV内的K近邻模块，并进行训练 knn = cv2.ml.KNearest_create() knn.train(trainData, cv2.ml.ROW_SAMPLE, tdLable) # 使用K近邻算法分类 ret, results, neighbours, dist = knn.findNearest(test, 5) # 显示处理结果 print("当前随机数可以判定为类型：", results) print("距离当前点最近的5个邻居是：", neighbours) print("5个最近邻居的距离： ", dist) # 可以观察一下显示，对比上述输出 plt.show()
输出数据的结构： [[n1,n2,n3, … ]]
K近邻手写数字识别
使用OpenCV自带的K近邻模块识别手写数字。
import cv2 import numpy as np import matplotlib.pyplot as plt # 读取样本（特征）图像的值 s='image\\' # 图像所在的路径 num=100 # 共有的样本数量 row=240 # 特征图像的行数 col=240 # 特征图像的列数 a=np.zeros((num, row, col)) # 用来存储所有样本的数值 #print(a.shape) n=0 # 用来存储当前图像的编号 for i in range(0,10): for j in range(1,11): a[n, :, :]=cv2.imread(s+str(i)+'\\'+str(i)+'-'+str(j)+'.bmp',0) n=n+1 # 提取样本图像的特征 feature=np.zeros((num, round(row/5), round(col/5))) # 用来存储所有样本的特征值 #print(feature.shape) # 看看特征值的形状是什么样子 #print(num) # 看看num的值，有多少个特征值（100） for ni in range(0, num): for nr in range(0, row): for nc in range(0, col): if a[ni, nr, nc]==255: feature[ni, int(nr/5), int(nc/5)]+=1 f=feature # 简化变量名称 # 将feature处理为单行形式 train = feature[:,:].reshape(-1, round(row/5)*round(col/5)).astype(np.float32) #print(train.shape) # 贴标签，要注意，是range(0,100)而非range(0,101) trainLabels = [int(i/10) for i in range(0,100)] trainLabels=np.asarray(trainLabels) #print(*trainLabels) # 打印测试看看标签值 ##读取图像值 o=cv2.imread('image\\test\\5.bmp',0) # 读取待识别图像 of=np.zeros((round(row/5), round(col/5))) # 用来存储待识别图像的特征值 for nr in range(0, row): for nc in range(0, col): if o[nr, nc]==255: of[int(nr/5), int(nc/5)]+=1 test=of.reshape(-1, round(row/5)*round(col/5)).astype(np.float32) # 调用函数识别图像 knn=cv2.ml.KNearest_create() knn.train(train, cv2.ml.ROW_SAMPLE, trainLabels) ret, result, neighbours, dist = knn.findNearest(test, k=5) print("当前随机数可以判定为类型：", result) print("距离当前点最近的5个邻居是：", neighbours) print("5个最近邻居的距离： ", dist)
