k-近邻算法

算法简介

k-近邻算法可以说是我接触过的最简单的机器学习算法了，其思路非常直白：给定一个训练集，输入一个实例，在训练集中找到和输入实例最近的k个点，这k个点中数量最多的类就是输入实例的类。可以看出来，k邻近算法的关键就是怎么样找到这最近的k个点。通过遍历训练集挨个计算与输入实例的距离肯定是可以做的，那就先用这种方法来实现一次。

python实现

• 首先，创建一个模拟训练集

from numpy import *
import operator

def create_data_set():
    """
    创建数据集
    :return group: 数据集
    :return labels: 分类标签
    """
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 1.0]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

模拟训练集忠有4条数据，用数组表示，数组的每个元素代表训练实例的一个属性值。这里先不关注它的实际意义，把它当做二维坐标中的点即可。

• 然后，求K近邻

def classify0(in_x, data_set, labels, k):
    """
    kNN算法，分类器
    :param in_x: 测试集
    :param data_set: 训练集
    :param labels: 分类标签
    :param k: kNN算法参数，选择距离最小的k个点
    :return:
    """
    data_set_size = data_set.shape[0]  # numpy函数shape返回array每一维的长度,shape[0]即第一维的长度
    diff_mat = tile(in_x, (data_set_size, 1)) - data_set  # numpy函数tile将数组in_x在行方向上重复data_set_size次，列方向上一次
    sq_diff_mat = diff_mat ** 2
    sq_distance = sq_diff_mat.sum(axis=1)  # 在第二维上进行求和（即每一列相加,axis只能是0或1
    distance = sq_distance ** 0.5  # 算出欧氏距离
    sorted_dist_indices = distance.argsort()  # 返回排序后的索引

    class_count = {}  # 记录标签出现的次数
    for i in range(k):
        vote_i_label = labels[sorted_dist_indices[i]]
        class_count[vote_i_label] = class_count.get(vote_i_label, 0) + 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1),
                                reverse=True)  # 字典排序itemgetter(0)根据key排序，itemgetter(1)根据value排序
    return sorted_class_count[0][0]

注意的问题：

• 样本不平衡
  例如某个类样本容量很大，这样测试样本的K个邻居中，大容量的类可能占多数（但是并不是最靠近测试样本的），测试样本就会被归为大容量的类。针对这个问题，可以采用距离权值的方法（可以和距离成反比）。
• 归一化
  使用 kNN 时需要根据特征数据的取值区间来调整特征矩阵

def auto_norm(data_set):
    """
    数据归一化
    :param data_set:原特征矩阵
    :return norm_data_set: 归一化后的特征矩阵
    :return ranges: 每一列的数据最大值最小值之差
    :return min_vals: 每一列的最小值
    """
    min_vals = data_set.min(0)  # min(0)以行为维度，即计算每一列的最小值
    max_vals = data_set.max(0)
    ranges = max_vals - min_vals
    m = data_set.shape[0]
    norm_data_set = data_set - tile(min_vals, (m, 1))
    norm_data_set = norm_data_set / tile(ranges, (m, 1))  # numpy 的"/"表示矩阵的每一个元素相除，矩阵的除法用linalg.solve(matA,matB)
    return norm_data_set, ranges, min_vals

• 计算量大
  对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

• 多分类
  有时候我们并不想知道测试实例的一个具体分类，而是想知道它属于每个分类的概率是多少。这时我们可以取测试实例的K个邻居中任意分类的数量除以K，作为此分类的概率。

完整代码

https://github.com/yshhuang/practice-code/tree/master/ml-in-action/02-kNN

参考文章：

【量化课堂】一只兔子帮你理解 kNN
Python3《机器学习实战》学习笔记（一）：k-近邻算法(史诗级干货长文)
一文搞懂k近邻（k-NN）算法（一）