K-近邻算法及实践

K-近邻算法概念

K-近邻算法（K-Nearest Neighbor）即K个最近的邻居。通俗地讲，要评价你是什么样的人，只需要看看你周围的朋友都是什么样的人便知道了。这与“鱼找鱼，虾找虾，乌龟找王八”都是想通的，相近似的事物总会聚在一起。将这种判断模式抽象为数学模型，就转化为一个距离计算问题。KNN是最简单的机器学习算法之一，属于有监督算法，用于分类任务。

k-近邻算法的原理

给定一个训练样本数据集，其中每条数据记录都存在标签。输入没有标签都一条数据记录，计算该条记录于训练样本中每一条记录的特征距离，然后提取前K条距离最小的训练样本的分类标签。这K条训练样本分类标签最多的类，就作为新数据所属的分类。（K通常不大于20）

如图所示，K=1时，New example属于哪一类，只要看与它第1近的邻居是哪一类。图中显示第1近的邻居是蓝色的方块，该邻居是属于Class 1的。所以K=1时，New example我们认为它也是属于Class 1的。

K=3时，New example的类别取决于与它第3近的邻居都是哪些类。图中显示前3近的邻居中，有两个是红色的三角形，这两位邻居是属于Class 2的，有一个是蓝色的方块，该邻居是属于Class 1的。总结三位邻居中比较多的是属于Class 2的，所以K=3时，我们认为New example是属于Class 2的。

显然，K的取值直接决定了New example所归属的分类，K不同有时会导致计算出的分类结果完全不同。K的选取还是有学问的。

K-近邻算法的特点

优点：分类精度高，异常值不敏感，没有假设条件

缺点：

计算时间复杂度高、空间复杂度高
分类结果受到学习样本分布均衡性影响较大

适用于数值型、分类型数据

K-近邻算法的实现

如何使用python开发一个基于KNN算法的分类器呢？

KNN算法的伪代码：

对于待分类的新数据，

计算待分类新数据在多维空间中与训练样本中每个点之间的距离；
按照距离递增排序；
选取距离增序后的前K个点；
统计前K个点类别频率分布；
返回前K个点中频率最高点类别，作为当前点的预测分类结果。

KNN代码：

import numpy as np
import operator as op


def create_dataset():
    group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']


    return group, labels


def classify0(inX, dataset, labels, k):


    dataset_size = dataset.shape[0]
    diff = np.tile(inX, (dataset_size, 1)) - dataset
    sqrt_diff = diff ** 2
    dist = (sqrt_diff.sum(axis = 1)) ** 0.5
    sort_dist = dist.argsort()


    class_count = {}
    for i in range(k):
        vote_label = labels[sort_dist[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]

知识点学习：

dict.get( )方法：
Python字典(Dictionary) get( )函数返回指定键的值，如果值不在字典中返回默认值。所以以上代码中，在统计分类的频率分布时，借助了get( )方法实现：class_count.get(vote_label,0) + 1，如果直接写class_count[vote_label] += 1就会报错，因为刚开始字典里可能没有存有vote_label这个key值。
dataset.shape返回dataset的大小，结果为一个元组，dataset.shape为(4,2)。
numpy.tile(inX,(dataset_size,1))，其中的变量dataset_size=4构造一个新的数组，通过拷贝inX，变换为4行1列的数组，从而直接与dataset进行减法计算。