机器学习入门笔记05

K近邻算法

系列文章

K近邻算法

基本原理

K近邻算法(K-Nearest Neighbor, KNN)算法的原理为：对于一个新样本，在已有数据中找出与它最相似的 \\( K \\) 个数据，或与它“距离最近”的 \\( K \\) 个数据，如果其中大部分属于某一类别，那么样本也属于该类别。

考虑以下有两个特征变量的数据，将其在坐标轴上绘制成散点图，点的颜色代表其分类（因变量）：

对于新增的一个样本，取其最近的 K 个数据，发现大多数属于蓝色类别，那么新样本也能归结到蓝色类别上。从直观上也可以看到每个类别中的数据确实挨得较近。

实际应用中，数据的特征通常有 n 个，那么可以利用 \\( n \\) 维空间的欧氏距离公式计算：

\\[ |AB| = \sqrt{ (X_1 - Y_1)^2 + (X_2 - Y_2)^2 + \dots + (X_n - Y_n)^2} \\]

计算出距离后，按照由近及远的顺序排序，取前 K 个数据，判断包含个体较多的类别，即为样本代表的类别。

数据标准化

当一个变量的量纲导致该变量的数据普遍很大时，其重要度将会变得很大，会变成距离计算的主导因素。

此时就要对数据进行预处理，该手段称为数据标准化或数据归一化。数据标准化的常用方法有min-max标准化（离差标准化）和Z-score标准化（均值归一化），将在以后介绍。

代码实现：图像数字识别

K近邻算法模型分为分类模型与回归模型，分别使用 sklearn.neighbors 模块内的 KNeighborsClassifier 和 KNeighborsRegressor 类，具体使用方法等与前几个模型类似，主要通过 n_neighbors 参数调整模型。

以下以图像数字识别模型为例，介绍K近邻算法的运用与图像处理基本方法。

图像预处理

图像识别的必要步骤就是将图片转换为计算机能处理的数字形式。

一些图像数字的示例如下：

使用 pillow 库对其进行处理。该库的笔记。

首先，打开一张图片，并对其进行灰度处理：

from PIL import Image
img = Image.open('4.png')
img = img.convert('L')

灰度处理的目的是将其转化为黑白图像，便于分离数字与背景部分。接下来对图片二值化处理：

img_arr = np.array(img.point(lambda x: 1 if x < 128 else 0))

将二值化后的图片以二维数组的形式打印，可以看到 0 和 1 中浮现出了一个数字“4”：

接下来还需要对该图像进行简单的处理：将 32×32 的二维数组变成一个 1×1024 的一位数组：

img_arr.reshape(1, -1)
array([[0, 0, 0, ..., 0, 0, 0]], dtype=uint8)

处理后得到的一位数组可以看成一个行向量，两张图片对应行向量间的欧氏距离可以反应两张图片的相似度。

可以这样认为：将待识别数字与标准数字的图像重叠，比较两张图片点的不重合度，认为不重合度低的为识别结果。

识别模型搭建

将待训练的图片集整理到一起，使用以下函数加载一个图像：

def load_image(filename, number):
    img = Image.open(filename)
    # img = img.resize((155, 135))
    img = img.convert('L')
    img_arr = np.array(img.point(lambda x: 1 if x < 128 else 0))
    img_df = pd.DataFrame(img_arr.flatten()).T
    img_df['number'] = number
    return img_df

由于待识别的图像必须保证尺寸相同才能正确对比，因此如果图像大小不一致，可以将第三行代码取消注释来规范图像尺寸。

将图片放在 font-numbers 目录下，相同数字的图像统一放在相同的子目录中。以下是部分用于训练的图像：

通过以下代码加载所有图像：

import os
imgs = pd.DataFrame()
for dir in range(10):
    for file in os.listdir(os.join('font-numbers', str(dir))):
        imgs = imgs.append(
            load_image(os.join('font-numbers', str(dir), file), dir),
            verify_integrity=False)

使用K近邻算法生成训练模型并使用网格搜索调优的核心代码如下：

from sklearn.neighbors import KNeighborsClassifier as KNN
from sklearn.model_selection import GridSearchCV
model = KNN()
grid_search = GridSearchCV(model, {'n_neighbors': range(1, 9)}, cv=5)
grid_search.fit(X_train, Y_train)
model = KNN(**grid_search.best_params_)
model.fit(X_train, Y_train)
KNeighborsClassifier()

检验训练的结果如下：

print(grid_search.best_params_, grid_search.best_score_)
print(model.predict(load_image('handwriting-number.png', 5).drop(columns='number')))
{'n_neighbors': 1} 0.7968944099378883 [5]

其中 handwriting-number.png 是手写的数字图像。打开它检查一下：

确实是 5 。模型的预测正确。

K近邻算法作为一种经典的机器学习算法，原理非常简单，但计算量较大，拟合速度慢。本次使用K近邻算法进行图像识别，尽管有着预处理要求较高、灵活度不够等许多缺点，但对于以上提供的形态各异的数字识别成功率依旧能达到 80% 左右，效果相当不错。