[人工智能] 【机器学习4】KNN算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 【机器学习4】KNN算法 -> 正文阅读

[人工智能]【机器学习4】KNN算法

四、KNN算法

4.1算法流程：

1）给定测试对象，计算它与训练集中每个对象的距离。
2）圈定距离最近的k个训练对象，作为测试对象的邻居。
3）根据这k个近邻对象所属的类别，找到占比最高的那个类别作为测试对象的预测类别。

4.2 影响KNN算法的准确度的两个因素：

计算测试对象与训练集中各个对象的距离
k的选择

4.3 KNN代码

4.3.1 无框架代码

import numpy as np
import matplotlib.pyplot as plt
import operator

##给出训练数据以及对应的类别
def createDataSet():
    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

'''
    k : 选取的最近k个目标
    dis : 'E' 欧拉 ; 'M' 曼哈顿
    X_train : 训练测试的特征数据
    x_train : 训练测试的标签数据
    Y_test : 测试的特征数据
'''
def kNN_classify(k,dis,X_train,x_train,Y_test):
    assert dis == 'E' or dis == 'M', 'dis must E or M，E代表欧拉距离，M代表曼哈顿距离'
    num_test = Y_test.shape[0]  #测试样本的数量
    labellist = []
    # 使用欧拉公式作为距离度量
    if (dis == 'E'):
        for i in range(num_test):
            # 实现欧拉距离公式
            distances = np.sqrt(np.sum(((X_train - np.tile(Y_test[i], (X_train.shape[0], 1))) ** 2), axis=1))
            nearest_k = np.argsort(distances)#距离由小到大进行排序，并返回index值
            topK = nearest_k[:k]#选取前k个距离
            classCount = {}
            for i in topK: #统计每个类别的个数
                classCount[x_train[i]] = classCount.get(x_train[i],0) + 1   # 查找该类别的个数，如果没找到就返回0， 最终都要+1
            # classCount.iteritems()将classCount字典分解为元组列表，
            # operator.itemgetter(1)按照第二个元素的次序对元组进行排序，
            # reverse=True是逆序，即按照从大到小的顺序排列
            sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
            print(i, sortedClassCount)
            labellist.append(sortedClassCount[0][0])    # 取出排序好的第一个元组的第一个值也就是键[('A', 3), ('B', 2)]，取出'A'
        return np.array(labellist)
    # 使用曼哈顿公式作为距离度量
    if (dis == 'M'):
        for i in range(num_test):
            # 按照列的方向相加，其实就是行相加
            distances = np.sum(np.abs(X_train - np.tile(Y_test[i], (X_train.shape[0], 1))), axis=1)
            nearest_k = np.argsort(distances)
            topK = nearest_k[:k]
            classCount = {}
            for i in topK:
                classCount[x_train[i]] = classCount.get(x_train[i], 0) + 1
            sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
            print(i, sortedClassCount)
            labellist.append(sortedClassCount[0][0])
        return np.array(labellist)

if __name__=='__main__':
    group,labels = createDataSet()
    X_test = kNN_classify(5, 'M', group, labels, np.array([[0.8, 1.2]]))
    print(X_test)
    # plt.scatter(group[labels=='A',0],group[labels=='A',1],color = 'r', marker='*')#对于类别为A的数据集我们使用红色六角形表示
    # plt.scatter(group[labels=='B',0],group[labels=='B',1],color = 'g', marker='+')#对于类别为B的数据集我们使用绿色十字形表示
    # plt.show()

4.3.2 pytorch代码

import torch
from torch.utils.data import DataLoader
import torchvision.datasets as dsets
import torchvision.transforms as transforms
import numpy as np
import operator

batch_size = 100
import warnings
warnings.filterwarnings('ignore') 

def kNN_classify(k,dis,X_train,x_train,Y_test):
    assert dis == 'E' or dis == 'M', 'dis must E or M，E代表欧拉距离，M代表曼哈顿距离'
    num_test = Y_test.shape[0]  #测试样本的数量
    labellist = []
    '''
    使用欧拉公式作为距离度量
    '''
    if (dis == 'E'):
        for i in range(num_test):
            # 实现欧拉距离公式
            distances = np.sqrt(np.sum(((X_train - np.tile(Y_test[i], (X_train.shape[0], 1))) ** 2), axis=1))
            nearest_k = np.argsort(distances)#距离由小到大进行排序，并返回index值
            topK = nearest_k[:k]#选取前k个距离
            classCount = {}
            for i in topK: #统计每个类别的个数
                classCount[x_train[i]] = classCount.get(x_train[i],0) + 1
            sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
            labellist.append(sortedClassCount[0][0])
        return np.array(labellist)
    # 使用曼哈顿公式作为距离度量
    if (dis == 'M'):
        for i in range(num_test):
            # 按照列的方向相加，其实就是行相加
            distances = np.sum(np.abs(X_train - np.tile(Y_test[i], (X_train.shape[0], 1))), axis=1)
            nearest_k = np.argsort(distances)
            topK = nearest_k[:k]
            classCount = {}
            for i in topK:
                classCount[x_train[i]] = classCount.get(x_train[i], 0) + 1
            sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
#             print(i, sortedClassCount)
            labellist.append(sortedClassCount[0][0])
        return np.array(labellist)

# 使用曼哈顿公式作为距离度量
# 读者自行补充完成

def main():
    # MNIST dataset
    train_dataset = dsets.MNIST(root = '/ml/pymnist', #选择数据的根目录
                               train = True, # 选择训练集
                               transform = None, #不考虑使用任何数据预处理
                               download = True) # 从网络上download图片
    test_dataset = dsets.MNIST(root = '/ml/pymnist', #选择数据的根目录
                               train = False, # 选择测试集
                               transform = None, #不考虑使用任何数据预处理
                               download = True) # 从网络上download图片
    #加载数据
    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 = True)
    X_train = train_loader.dataset.train_data.numpy() #需要转为numpy矩阵
    X_train = X_train.reshape(X_train.shape[0],28*28)#需要reshape之后才能放入knn分类器
    y_train = train_loader.dataset.train_labels.numpy()
    X_test = test_loader.dataset.test_data[:1000].numpy()
    X_test = X_test.reshape(X_test.shape[0],28*28)
    y_test = test_loader.dataset.test_labels[:1000].numpy()
    num_test = y_test.shape[0]
    y_test_pred = kNN_classify(5, 'M', X_train, y_train, X_test)
    num_correct = np.sum(y_test_pred == y_test)
    accuracy = float(num_correct) / num_test
    print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))
main()

4.5 交叉验证

第一步，使用之前所写的KNN分类器，代码如下：

sortedClassCount =
sorted(classCount.items(), key=operator.itemgetter(1),
reverse=True)
labellist.append(sortedClassCount[0][0])
return np.array(labellist)
#使用曼哈顿公式作为距离度量
if (dis == 'M'):
for i in range(num_test):
#按照列的方向相加，其实就是行相加
distances = np.sum(np.abs(self.Xtr -
np.tile(X_test[i], (self.Xtr.shape[0], 1))), axis=1)
nearest_k = np.argsort(distances)
topK = nearest_k[:k]
classCount = {}
for i in topK:
classCount[self.ytr[i]] =
classCount.get(self.ytr[i], 0) + 1
sortedClassCount =
sorted(classCount.items(), key=operator.itemgetter(1),
reverse=True)
labellist.append(sortedClassCount[0][0])
return np.array(labellist)

第二步，准备测试数据与验证数据，值得注意的是，如果使用方法四，则在选择超参数阶段不需要使用到X_test和y_test的输出，代码如下：

X_train = train_loader.dataset.train_data
X_train = X_train.reshape(X_train.shape[0],-1)
mean_image = getXmean(X_train)
X_train = centralized(X_train,mean_image)
y_train = train_loader.dataset.train_labels
y_train = np.array(y_train)
X_test = test_loader.dataset.test_data
X_test = X_test.reshape(X_test.shape[0],-1)
X_test = centralized(X_test,mean_image)
y_test = test_loader.dataset.test_labels
y_test = np.array(y_test)
print(X_train.shape)
print(y_train.shape)
print(X_test.shape)
print(y_test.shape)

第三步，将训练数据分成5个部分，每个部分轮流作为验证集，代码如下：

k_to_accuracies = {}
for k in k_choices:
#进行交叉验证
acc = []
for i in range(num_folds):
x = X_train_folds[0:i] + X_train_folds[i+1:]
#训练集不包括验证集
x = np.concatenate(x, axis=0)
#使用concatenate将4个
训练集拼在一起
y = y_train_folds[0:i] + y_train_folds[i+1:]
y = np.concatenate(y)
#对label进行同样的操作
test_x = X_train_folds[i]
 (k, accuracy))

4.4 KNN的图像分类

1.简介

图像分类问题就是将已有的固定的分类标签集合中最合适的标签分配给输入的图像
$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h3nxbeu5-1648606691801)(C:\Users\Jun\AppData\Roaming\Typora\typora-user-images\image-20220330101316304.png)]$

如图，机器识别的图像大小248*400像素，有红绿蓝RGB3个颜色通道，计算机需要处理的总数据有248×400×3=297600，每个数据在0 -255之间，0代表黑色，255为白色
标签集合为{cat，dog，hat，mug}
图像分类的任务就是预测一个给定的图像包含了哪个分类标签（或者给出属于一系列不同标签的可能性）。

2.预处理

1）目的：

使得原始图像符合某种既定规则以便于进行后续的处理，
去除图像中的噪声。
减少后续的运算量以及加速收敛。

2）常用的图像预处理操作：

归一化（重点）
灰度变换
滤波变换以及
各种形态学变换

3.归一化

归一化可用于保证所有维度上的数据都在一个变化幅度

例如：在预测房价的例子中，假设房价由面积s和卧室数b决定，面积s在0～200之间，卧室数b在0～5之间，进行归一化的一个实例就是s=s/200，b=b/5。
两种方法来实现归一化
最值归一化，比如将最大值归一化成1，最小值归一化成-1；或者将最大值归一化成1，最小值归一化成0
均值方差归一化，一般是将均值归一化成0，方差归一化成1。

代码链接1_knn.ipynb