KNN 分类算法
KNN是机器学习种最简单的分类算法，而图像分类也是图像识别种最简单的问题，所以这里使用 KNN来做图像分类，帮忙大家初步了解图像识别算法。
KNN（K-NearestNeighbor）,即K-最近邻算法，顾名思义，找到最近的k个邻居，在前k个最近样本(k近邻)中选择最近的占比最高的类别作为预测类别。
KNN算法的计算逻辑：
- 给定测试对象，计算它与训练集中每个对象的距离；
- 圈定距离最近的k个训练对象，作为测试对象的邻居；
- 根据这k个近邻对象所属的类别，找到占比最高的那个类别作为测试对象的预测类别。
在 KNN中，有两个方面的因素会影响 KNN算法的准确度： 一个是距离计算，另一个是k的选择。
一般使用两种比较常见的距离公式计算距离：
2. 欧式距离：
; KNN 算法实现
import numpy as np
import matplotlib.pyplot as plt
class KNNClassify:
@staticmethod
def create_data_set():
_group = np.array([[1.0, 2.0], [1.2, 0.1], [0.1, 1.4], [0.3, 3.5], [1.1, 1.0], [0.5, 1.5]])
_labels = np.array(['A', 'A', 'B', 'B', 'A', 'B'])
return _group, _labels
if __name__ == "__main__":
group, labels = KNNClassify.create_data_set()
plt.scatter(group[labels == 'A', 0], group[labels == 'A', 1], color='r', marker='*')
plt.scatter(group[labels == 'B', 0], group[labels == 'B', 1], color='g', marker='+')
plt.show()
我们先创建一个简单的数据集，然后使用 Matplotlib绘制图形，可以直观看到地查看数据分布情况。
接下来实现 KNN算法
import operator
class KNNClassify:
@staticmethod
def knn_classify(k, dis, x_train, y_train, x_test):
assert dis == 'E' or dis == 'M', 'dis must E or M, E代表欧式距离， M代表曼哈顿距离'
num_test = x_test.shape[0]
label_list = []
for i in range(num_test):
x_test_temp = np.tile(x_test[i], (x_train.shape[0], 1))
if dis == 'E':
result_temp = (x_train - x_test_temp) ** 2
result_sum_temp = result_temp.sum(axis=1)
distances = np.sqrt(result_sum_temp)
else:
result_temp = np.abs(x_train - x_test_temp)
distances = result_temp.sum(axis=1)
nearest_k = distances.argsort()
top_k = nearest_k[:k]
class_count = {}
for index in top_k:
class_count[y_train[index]] = class_count.get(y_train[index], 0) + 1
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
label_list.append(sorted_class_count[0][0])
return np.array(label_list)
最后测试下 KNN算法的效果：
y_test_pred = KNNClassify.knn_classify(1, 'E', group, labels, np.array([[1.0, 2.1], [0.4, 2.0]]))
print(y_test_pred)
注意，输入测试集的时候，需要将其转换为 Numpy矩阵，否则系统会提示传入的参数是list类型，没有shape的方法。
KNN 实现 MNIST 数据分类
下载和准备数据集
MNIST数据集是手写数字的图片数据集， MNIST可以直接通过 pytorch进行下载与读取（也可以自行下载，然后放到相关目录，使用 pytorch解析）
import torch
import numpy as np
from torch.utils.data import DataLoader
from torchvision import datasets
class MNIST:
def __init__(self):
self._batch_size = 100
self._train_data_set = None
self._test_data_set = None
self._train_loader = None
self._test_loader = None
def init_data(self):
self._train_data_set = datasets.MNIST(
root='/ml_dataset/pymnist',
train=True,
transform=None,
download=True
)
self._test_data_set = datasets.MNIST(
root='/ml_dataset/pymnist',
train=False,
transform=None,
download=True
)
self._train_loader = torch.utils.data.DataLoader(
dataset=self._train_data_set,
batch_size=self._batch_size,
shuffle=True
)
self._test_loader = torch.utils.data.DataLoader(
dataset=self._test_data_set,
batch_size=self._batch_size,
shuffle=True
)
print("train_data:", self._train_data_set.data.size())
print("train_labels:", self._train_data_set.targets.size())
print("test_data:", self._test_data_set.data.size())
print("test_labels:", self._test_data_set.targets.size())
if __name__ == "__main__":
mnist = MNIST()
mnist.init_data()
首次运行代码会自动下载数据到目录 /ml_dataset/pymnist，如果运行时速度过慢，可以上网查询 MNIST下载方式，将下载好的数据包，放置该目录，程序会自动解析。
train_dataset与test_dataset可以返回训练集数据、训练集标签、测试集数据以及测试集标签，训练集数据以及测试集数据都是n×m维的矩阵，这里的n是样本数（行数），m是特征数（列数）。训练数据集包含60 000个样本，测试数据集包含10 000个样本。
在 MNIST数据集中，每张图片均由28×28个像素点构成，每个像素点使用一个灰度值表示。在这里，我们将28×28的像素展开为一个一维的行向量，这些行向量就是图片数组里的行（每行784个值，或者说每行就代表了一张图片）。训练集标签以及测试标签包含了相应的目标变量，也就是手写数字的类标签（整数0～9）。
上面代码打印的结果为：
train_data: torch.Size([60000, 28, 28])
train_labels: torch.Size([60000])
test_data: torch.Size([10000, 28, 28])
test_labels: torch.Size([10000])
如果大家对这个数据集不是很了解，可以尝试多去显示几张图片看下，并查看相应的标签。
例如：
def show_data_example(self):
digit = self._train_loader.dataset.data[0]
plt.imshow(digit, cmap='gray')
plt.show()
print(self._train_loader.dataset.targets[0])
数字5：
原理剖析
在真正使用Python实现 KNN算法之前，我们先来剖析一下思想，这里我们以 MNIST的60 000张图片作为训练集，我们希望对测试数据集的10 000张图片全部打上标签。 KNN算法将会比较测试图片与训练集中每一张图片，然后将它认为最相似的那个训练集图片的标签赋给这张测试图片。
那么，具体应该如何比较这两张图片呢？在本例中，比较图片就是比较28×28的像素块。最简单的方法就是逐个像素进行比较，最后将差异值全部加起来
两张图片使用 L1距离(曼哈顿距离，相应的 L2距离是欧式距离)来进行比较。逐个像素求差值，然后将所有差值加起来得到一个数值。如果两张图片一模一样，那么 L1距离为0，但是如果两张图片差别很大，那么， L1的值将会非常大。
; 验证 KNN 在 MNIST 上的效果
我们直接利用上面实现的 KNN算法来测试：
from KNN import KNNClassify
class MNIST:
def predict(self):
x_train = self._train_loader.dataset.data.numpy()
x_train = x_train.reshape(x_train.shape[0], 28*28)
y_train = self._train_loader.dataset.targets.numpy()
x_test = self._test_loader.dataset.data[:1000].numpy()
x_test = x_test.reshape(x_test.shape[0], 28*28)
y_test = self._test_loader.dataset.targets[:1000].numpy()
num_test = y_test.shape[0]
y_test_pred = KNNClassify.knn_classify(5, 'M', x_train, y_train, x_test)
correct_arrays = np.array(y_test == y_test_pred)
num_correct = correct_arrays.sum()
accuracy = float(num_correct) / num_test
print(f'Got {num_correct}/{num_test} => accuracy: {accuracy}')
这里需要多说点，上面的 KNN算法实现，我是当作一个单独的脚本，这里的 MNIST数据分类，是另一个脚本，且位于同一文件夹下：
直接在 MNIST.py脚本中使用 from KNN import KNNClassify可能会出错，需要在 __init__.py中添加一行代码： from .KNN import KNNClassify。
最后运行代码，Got 368 / 1000 correct => accuracy: 0.368000！这说明1000张图片中有368张图片预测类别的结果是准确的。
先别气馁，我们之前不是刚说过可以使用数据预处理的技术吗？下面我们试一下如果在进行数据加载的时候尝试使用归一化，那么分类准确度是否会提高呢？
我们稍微修改下代码,主要是在将X_train和X_test放入 KNN分类器之前先调用centralized，进行归一化处理。
class MNIST:
@staticmethod
def get_x_mean(x_train):
x_train = x_train.reshape(x_train.shape[0], -1)
mean_image = x_train.mean(axis=0)
return mean_image
@staticmethod
def centralized(x_test, mean_image):
x_test = x_test.reshape(x_test.shape[0], -1)
x_test = x_test.astype(np.float64)
x_test -= mean_image
return x_test
def predict_centralized(self):
x_train = self._train_loader.dataset.data.numpy()
mean_image = self.get_x_mean(x_train)
x_train = self.centralized(x_train, mean_image=mean_image)
y_train = self._train_loader.dataset.targets.numpy()
x_test = self._test_loader.dataset.data[:1000].numpy()
x_test = self.centralized(x_test, mean_image)
y_test = self._test_loader.dataset.targets[:1000].numpy()
num_test = y_test.shape[0]
y_test_pred = KNNClassify.knn_classify(5, 'M', x_train, y_train, x_test)
correct_arrays = np.array(y_test == y_test_pred)
num_correct = correct_arrays.sum()
accuracy = float(num_correct) / num_test
print(f'Got {num_correct}/{num_test} => accuracy: {accuracy}')
下面再来看下输出结果的准确率：Got 951 / 1000 correct => accuracy: 0.951000，95%算是不错的结果。
现在我们来看一看归一化后的图像是什么样子的
class MNIST:
def show_data_centralized(self):
x_train = self._train_loader.dataset.data.numpy()
mean_image = self.get_x_mean(x_train)
x_test = self._test_loader.dataset.data[:1000].numpy()
c_data = self.centralized(x_test, mean_image)
c_data = c_data.reshape(c_data.shape[0], 28, 28)
plt.imshow(c_data[0], cmap='gray')
plt.show()
print(self._test_loader.dataset.targets[0])
if __name__ == "__main__":
mnist = MNIST()
mnist.init_data()
mnist.show_data_example()
mnist.show_data_centralized()
所以是否了解到数据预处理的重要性了？！未进行数据预处理的准确率只有36.8%,进行归一化数据预处理后，准确率提升至95%！
在开始使用算法进行图像识别之前， 良好的数据预处理能够很快达到事半功倍的效果。图像预处理不仅可以使得原始图像符合某种既定规则以便于进行后续的处理，而且可以帮助去除图像中的噪声。
在后续讲解神经网络的时候我们还会了解到， 数据预处理还可以帮助减少后续的运算量以及加速收敛。常用的图像预处理操作包括归一化、灰度变换、滤波变换以及各种形态学变换等。
归一化可用于保证所有维度上的数据都在一个变化幅度上。比如，在预测房价的例子中，假设房价由面积s和卧室数b决定，面积s在0～200之间，卧室数b在0～5之间，进行归一化的一个实例就是s=s/200，b=b/5。
KNN 实现 Cifar10 数据分类
Cifar10是一个由彩色图像组成的分类的数据集（ MNIST是黑白数据集），其中包含了飞机、汽车、鸟、猫、鹿、狗、青蛙、马、船、卡车10个类别，且每个类中包含了1000张图片。整个数据集中包含了60 000张32×32的彩***片。该数据集被分成50 000和10 000两部分，50 000是training set，用来做训练；10 000是test set，用来做验证。
下载和准备数据集
同样的你可以通过 Pytorch直接下载该数据集，或者自己从数据集官网下载，然后放置指定目录，程序会自动解析
import torch
import numpy as np
from torch.utils.data import DataLoader
import torchvision.datasets as datasets
import matplotlib.pyplot as plt
from KNN import KNNClassify
class Cifar10:
def __init__(self):
self._batch_size = 100
self._train_data_set = None
self._test_data_set = None
self._train_loader = None
self._test_loader = None
def init_data(self):
self._train_data_set = datasets.CIFAR10(
root='/ml_dataset/pycifar',
train=True,
download=True
)
self._test_data_set = datasets.CIFAR10(
root='/ml_dataset/pycifar',
train=False,
download=True
)
self._train_loader = torch.utils.data.DataLoader(
dataset=self._train_data_set,
batch_size=self._batch_size,
shuffle=True
)
self._test_loader = torch.utils.data.DataLoader(
dataset=self._test_data_set,
batch_size=self._batch_size,
shuffle=True
)
如果对数据集不了解，可以查看数据集的图片内容
class Cifar10
def show_data_example(self):
classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
digit = self._train_loader.dataset.data[0]
plt.imshow(digit)
plt.show()
print(classes[self._train_loader.dataset.targets[0]])
classes是我们定义的类别，其对应的是 Cifar中的10个类别。使用 PyTorch读取的类别是index，所以我们还需要额外定义一个classes来指向具体的类别。由于只有32×32个像素，因此图像比较模糊。
验证 KNN 在 Cifar10 上的效果
现在我们主要观察下 KNN对于 Cifar10数据集的分类效果，与之前 MNIST数据集不同的是， X_train = train_loader.dataset.train_data， X_train的 dtype是 uint8而不是 torch.uint8，所以不需要使用 numpy()这个方法进行转换。
class Cifar10:
def predict(self):
x_train = self._train_loader.dataset.data
mean_image = self.get_x_mean(x_train)
x_train = self.centralized(x_train, mean_image=mean_image)
y_train = self._train_loader.dataset.targets
x_test = self._test_loader.dataset.data[:100]
x_test = self.centralized(x_test, mean_image)
y_test = self._test_loader.dataset.targets[:100]
num_test = len(y_test)
y_test_pred = KNNClassify.knn_classify(8, 'E', x_train, y_train, x_test)
correct_arrays = np.array(y_test == y_test_pred)
num_correct = correct_arrays.sum()
accuracy = float(num_correct) / num_test
print(f'Got {num_correct}/{num_test} => accuracy: {accuracy}')
经过验证， KNN算法在 Cifar10数据集上的准确率不高，大概只有30%的准确率，而且是在归一化处理的基础上。
总结
前面我们讲了影响 KNN算法的两大因素分别为距离度量算法和K的取值，也就是算法的两个超参数，到底如何选取这两个值，就是一个模型调参的问题，这个过程一般就是需要你自己去测试，选取一个效果比较好的取值。
虽然 KNN在 MNIST数据集中的表现还算可以(主要原因可能是 MNIST是灰度图)，但是其在 Cifar10数据集上的分类准确度就差强人意了。另外，虽然 KNN算法的训练不需要花费时间（训练过程只是将训练集数据存储起来），但由于每个测试图像需要与所存储的全部训练图像进行比较，因此 测试需要花费大量时间，这显然是一个很大的缺点，因为在实际应用中，我们对测试效率的关注要远远高于训练效率。
在实际的图像分类中基本上是不会使用 KNN算法的。因为图像都是高维度数据（它们通常包含很多像素），这些高维数据想要表达的主要是语义信息，而不是某个具体像素间的距离差值（在图像中，具体某个像素的值和差值基本上并不会包含有用的信息），所以这就是我们为什么需要用深度学习和神经网络来训练模型提高准确率和检测速度。
我的gtihub博客地址：https://forchenxi.github.io/
另外，如果对投资理财感兴趣的同学，可以关注我的微信公众号：运气与实力。
Original: https://blog.csdn.net/qq_40691189/article/details/124439166
Author: 在路上的工程师
Title: KNN分类算法实践
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/663237/
转载文章受原作者版权保护。转载请注明原作者出处！