k-近邻算法(kNN)

kNN简介

简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

它的工作原理是：存在一个样本数据集合，也称做训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

优缺点

优点

简单，易于理解，易于实现，无需估计参数，无需训练；
适合对稀有事件进行分类；
特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。

缺点

该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

Python实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np 
import operator

# kNN算法实现
# inX:用于分类的输入向量
# dataSet:输入的训练样本集
# labels:标签向量
# k:用于选择最近邻居的数目
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]      # shape[0]表示行的数量
    diffMat = np.tile(inX,(dataSetSize, 1)) - dataSet       # tile()此处以数组形式重复元素
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis = 1)       # axis = 1 将矩阵的每一行相加
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()    # argsort()返回数组值从小到大的索引值
    classCount = {}

    # 选择距离最小的k个点    
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # 按照第二个元素的次序对元组进行排序
    sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
    return sortedClassCount[0][0]

参考文献

[1][机器学习实战]

[2]维基百科：最近邻居法

[3]百度百科：邻近算法