k近邻算法(kNN)

---

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 算法描述

1. 计算分类未知数据 x_new 与训练样本集数据 x 的欧氏距离 distance
2. 将 distance 递增排序
3. 选取 distance 的前 k 个点
4. 选取前 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
转载请告知作者，感谢！