k-近邻算法

k-近邻算法概述

在模式识别领域中，K-近邻算法（KNN算法）是一种用于分类和回归的非参数统计方法。在这两种情况下，输入包含特征空间中的k个最接近的训练样本。

• 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。
• 在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。

k-近邻算法的一般流程

1. 收集数据：可以使用任何方法。
2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式。
3. 分析数据：可以使用任何方法。
4. 测试算法：计算错误率。
5. 使用算法： 首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

Python实现

import operator
from euclidean_distance import point_data_set_distance


def classify(in_x, data_set, labels, k):
    distance = point_data_set_distance(in_x, data_set)
    sorted_distance_indicies = distance.argsort()
    class_count = {}
    for i in range(k):
        vote_label = labels[sorted_distance_indicies[i]]
        class_count[vote_label] = class_count.get(vote_label, 0) + 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]

如图1中有四个点[[1.0,1.1],[1.0,1.0],[0.0,0.1],[0.0,0.0]]对应的值为['A','A','B','B']，现有一个点[1.0,1.2]，计算这个点可能的值。

>>> from numpy import array
>>> group = array([[1.0,1.1],[1.0,1.0],[0.0,0.1],[0.0,0.0]])
>>> labels = array(['A','A','B','B'])
>>> from knn import classify
>>> classify([1.0,1.2],group,labels,3)
'A'

classify函数有4个输入参数，用于分类的输入向量in_x，输入的训练样本集data_set，标签向量labels，最后的参数k表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵data_set的行数相同。
程序使用欧式距离公式计算两个向量点x_A和x_B之间的距离，关于欧式距离的原理及算法实现请参见欧几里得距离。