1. k-近邻算法

1. 算法

k-近邻算法（k-nearest neighbors algorithm）是一个格外简单的算法，可用于分类和回归任务。

这里讨论的是用于分类任务，其采用测量不同特征值之间距离的方法进行分类。没有学习的过程，只是将新数据的每个特征与样本集中数据的对应特征进行比较（这里比较的方法采用欧式距离公式），然后选择其中前k个最相似的样本，统计k个样本中出现次数最多的分类作为新数据的类别。

下面为算法代码：

import numpy as np
import operator
# inX为新数据，inX.shape := (1,n) 或 inX.shape := (n,)，n个特征
# dataSet为样本集，dataSet.shape := (m,n)，有m个样本
# labels为样本集中样本对应的标签，这里labels.shape := (m,)
# k为k...
def classify0(inX, dataSet, labels, k):
    # 得到样本数量
    dataSetSize = dataSet.shape[0]
    # broadcast，与每一个样本对应特征相减
    diffMat = dataSet - inX
    # 各值平方
    sqDiffMat = np.square(diffMat)
    # 按列求和，keepdims为默认值False，所以sqDistances.shape := (m,)
    sqDistances = sqDiffMat.sum(axis=1)
    # 各个值开根号，这就得到了新数据与样本中各数据的欧式距离。
    distances = np.sqrt(sqDistances)
    # argsort()默认axis=-1，这里distances为1维
    # 返回的是由小到大排列的值的索引
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        # 索引对应的label，作为字典的key
        voteIlabel = labels[sortedDistIndicies[i]]
        # dict.get(key, value)的作用是如果key存在，则返回dict[key]
        # 如果key不存在，则返回value。也就是统计该key出现的次数。
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 通过dict.items()得到多个(key, value)元组，指定通过value
    #来排序，降序排序，得到的是通过value降序排列好的元组。
    sortedClassCount = sorted(classCount.items(),
                              key = operator.itemgetter(1), 
                              reverse=True)
    # 排序之后，第一个即为k个数据中出现次数最多的类别
    return sortedClassCount[0][0]

2. 一些函数的使用

operator.itemgetter()

"""
Return a callable object that fetches the given item(s) from its operand.
After f = itemgetter(2), the call f(r) returns r[2].
After g = itemgetter(2, 5, 3), the call g(r) returns (r[2], r[5], r[3])
"""

其源码如下：

class itemgetter:
    __slots__ = ('_items', '_call')

    def __init__(self, item, *items):
        if not items:
            self._items = (item,)
            def func(obj):
                return obj[item]
            self._call = func
        else:
            self._items = items = (item,) + items
            def func(obj):
                return tuple(obj[i] for i in items)
            self._call = func

    def __call__(self, obj):
        return self._call(obj)

    def __repr__(self):
        return '%s.%s(%s)' % (self.__class__.__module__,
                              self.__class__.__name__,
                              ', '.join(map(repr, self._items)))

    def __reduce__(self):
        return self.__class__, self._items

sorted(iterable, /, *, key=None, reverse=False)

"""
Return a new list containing all items from the iterable in ascending order.

A custom key function can be supplied to customize the sort order, and the
reverse flag can be set to request the result in descending order.
"""

参数：
iterable：待排序对象
key：根据key函数的返回值来排序。
reverse：默认False为升序。

dict.get()

"""
D.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None.
"""