1. 前言
k-邻近算法(kNN)是机器学习中非常简洁并且易于掌握的算法，是一种用于分类和回归的非参数统计算法。
本文首先介绍k-邻近算法思想及过程，随后介绍了kNN的Python实现。全文基于机器学习实战，着重阐述作者自己的理解。此外，还参考了Scipy Lecture Notes、维基百科以及许多博客。
2. 描述
2.1 工作原理
存在一个训练样本集 (x,y)，每个样本 x^(i)都有对应的标签 y^(i)，也就是说，对于每个训练样本，我们都知道该样本的所属分类。此后，输入一个不带标签的测试样本数据 x_new，选取训练样本集中与 x_new 欧氏距离(*)最近的 $k$ 个点，获取这k个样本的标签，其中出现次数最多的标签即作为 x_new的标签 y_new ，即：将 x_new 归为 y_new 类。其中，k <=20，y_new属于y。
- 欧氏距离：即几何距离。如：$(0, 0, 0)$ 与 $(1, 2, 3)$ 的欧氏距离为$d = \sqrt{(1-0)^2 + (2-0)^2 + (3-0)^2}$
2.2 算法描述
- 计算分类未知数据 x_new 与训练样本集数据 x 的欧氏距离 distance
- 将 distance 递增排序
- 选取 distance 的前 k 个点
- 选取前 k 个点中，出现频率最高的类别 y 作为 x_new的分类
3. Python实现
import numpy as np
import os
from collections import Counter
3.1 数据导入
3.1.1 使用NumPy导入数据
使用np.loadtxt()可以读取被空格隔开的数据。
def read_file(file_path):
file = np.loadtxt(file_path) # 读取txt文件
feature = file[:, :-1] # 前n-1列构成特征矩阵
label = file[:, -1] # 最后一列构成标签向量
return feature, label
3.1.2 将32*32的文本格式照片转换为向量
def img_to_vector(file_path):
lines = 32 # 像素大小
with open(file_path) as f: # 用这种形式，将自动执行f.close()
data = list() # 生成一个空的list
# 使用f.readline()逐行遍历文本，添加到data后
for i in range(lines):
data.append(list(f.readline())[:lines])
# 循环结束后，生成一个32*32矩阵
return_vector = np.array(data).ravel() # 将矩阵扁平化为一个向量
return return_vector
3.1.3 读取文件夹，生成训练样本矩阵
def read_digits(file_path):
file_lists = os.listdir(file_path) # 读取文件夹下所有文件名，生成list
file_num = file_lists.__len__() # 文件数m
matrix = np.zeros((file_num, 1024), dtype=np.int) # 生成矩阵(m*2014)
for i in range(file_lists.__len__()):
abs_file_path = file_path + file_lists[i] # 文件绝对路径
vector = img_to_vector(abs_file_path) # 获取文件生成的向量
matrix[i] = vector # 为矩阵(m*2014)赋值
return matrix
3.2 归一化数据
样本归一化的作用，是将任意取值范围的特征值转换为0到１区间内的值。
new_value = (old_value - min) / (max - min)
def auto_norm(data_mat):
min_column = np.min(data_mat, axis=0) # 获取每一列的最小值
max_column = np.max(data_mat, axis=0) # 获取每一列的最大值
range_column = max_column - min_column # 获取每一列的取值范围(max - min)
data_mat = data_mat - min_column # (old_value - min)
norm_feature_mat = np.true_divide(data_mat, range_column)
return norm_feature_mat
3.3 计算距离
# x为待测试点，point为训练样本集中的点
# NumPy数组可以进行许多便捷的操作
def cal_distance(x, point):
temp = (point - x)**2
return temp.sum(axis=1)
3.4 分类
# in_x 测试数据，可以不止一组
# data_set, labels 分别为训练集和训练集标签
# k 不必赘述
def classify(in_x, data_set, labels , k):
result_labels = np.zeros((in_x.shape[0], ), dtype=np.int) # 分类结果向量
for i in range(in_x.shape[0]):
distance = cal_distance(in_x[i], data_set) # 计算距离
mask = distance.argsort()[:k] # 选取前k个点
k_array = labels[mask] # 利用掩码获取k个点的标签
result_labels[i] = Counter(k_array).most_common(1)[0][0] # 获取出现频率最高的标签
return result_labels
作者邮箱： mr.yxj@foxmail.com
转载请告知作者，感谢！
