Love Thy neighbours — Photo by Christian Stahl on Unsplash

本文是一篇k-NN学习笔记，内容如下：

一. k-NN简介
二. k-NN原理
三. 关于 k-NN的进一步讨论
- 3.1 K的大小怎么选择?
- 3.2 怎么计算最近“邻居”?
- 3.3 既然是监督学习，怎么训练？
- 3.4 k-NN怎么用于回归？
- 3.5 最后，为什么选择k-NN?
四. k-NN应用-提高约会对象匹配(python)
- 4.1 读文件，解析特征向量和类别标签
- 4.2 特征标准化
- 4.3 画散点图，观察特征
- 4.4 利用k-NN算法进行分类
- 4.5 验证算法

一. k-NN简介

k-NN，即k-nearest neighbors algorithm ，是一种非常简单且应用广泛的机器学习算法，属于监督学习大家庭中的一员，多用于分类问题，也可以用于回归问题，本文主要讲述分类问题。虽然k-NN简单，但应用很广泛，且常被用作更复杂分类器的测试基准，对k-NN应用的研究有很多，例如：

二. k-NN原理

分类问题中，训练集（training set）中的每个样本已知类别，而测试集（test set）中的样本未知类别，分类问题的目标是对测试集中每个样本标记类别标签（label）。k-NN(k-nearest neighbors algorithm)，即对每一个测试集样本 $x$ ，在训练集中选取 $k$ 个最近的“邻居”，由这些“邻居”的大多数来决定 $x$ 所属的类别标签，如下图所示：

绿圆应该标记成红三角还是蓝方块？well, it depends !
计算绿圆和所有红三角、蓝方块的距离；
当时（实心圆圈），选取绿圆的个最近“邻居”，即个红三角和个蓝方块，红三角占多数，那么绿圆标记成红三角；
当时（虚线圆圈），选取绿圆的个最近“邻居”，即个红三角和个蓝方块，蓝方块占多数，那么绿圆标记成蓝方块；

下面给出k-NN的定义：

k-NN is a non parametric, instance based, lazy supervised algorithm

三. 关于 k-NN的进一步讨论

上文讲述了k-NN的核心思想，但仍然有很多疑问等待我们继续挖掘，(ง •̀_•́)ง

3.1. $K$ 的大小怎么选择?

首先我们来看下 $K$ 的取值有什么影响，我们刚才已经看到 $K$ 越大，参与标记决策的最近“邻居”越多，意味着正确标记的可能性越大，但是k越大越好么？
来看一个训练集，其中共有2个类别，红点-Class 1和蓝点-Class 2，每个类别100个点，画出散点图如下，我们可以大致看出左上部分主要是红点，右下部分主要是蓝点：

如果我们为两个类别划分边界：

$K$ = 1 时，边界准确地划分了训练集；而当
$K$ = 5 时，训练误差变大了。

过度的追求训练集的准确性并没有什么用，因为过高的训练集的准确性会导致较低的测试集准确性，很容易导致过拟合（overfitting）。机器学习中过拟合（overfitting）指当算法在训练集上表现非常好，而对测试集上新的数据表现很差。简单来说，算法推广性较差。

随着 $K$ 增大，边界越来越平滑。

最后，蓝色和红色区域大致分开了，同时，蓝色和红色两类中都有落到对方区域的点，这使训练误集准确性降低，不过不是坏事，因为算法的推广性更好了，对新数据标记的准确性增加，如图所示：

为了选取 $K$ 的值，我们将一部分数据作为测试集，尝试不同的 $K$ 值，观察验证误差。

测试误差/验证误差 = (预测错误数/验证集总数T) * 100%

验证误差最小时 $K$ 的取值就是我们要找的 $K$ 值， $K$ 值与训练集误差，K值与测试集误差之间的关系如下图所示，可以看出，当 $K$ = 8时，测试集误差最小。

左 : 随着K增大，训练集误差增大 | 右 :K = 8时，测试集误差最小 | Source: AnalyticsVidhya)

3.2. 怎么计算最近“邻居”

给定 $K$ 值，怎么找出最近的 $K$ 个“邻居”呢？计算 $x-y$ 平面上两点 $p (x_1, y_1)$ 和 $q (x_2, y_2)$ 有很多种方法，这里主要简单介绍三种。
欧式距离（Euclidean distance），即两点之间的直线距离，也是最常用的一种计算距离的方法：
$distance = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

切比雪夫距离:
$distance = max(|x_1 - x_2| , |y_1 - y_2|)$

曼哈顿距离，也称为 $L1$ 距离:
$distance = |x_1 - x_2| + |y_1 - y_2|$

3.3 既然是监督学习，怎么训练？

k-NN没有显示的训练这一步骤，我们需要知道的所有内容就是最近“邻居”的标签-本身已知。也就是k-NN的训练过程就是准备好训练集中样本的特征向量和样本的标签。不过需要注意的是，我们上面距离都是 $x-y$ 平面上点 $(x, y)$ ，两个特征值组成的特征向量，实际上一个样本可能有多个特征组成一个特征向量，别急，后面有例子(＾-＾)

3.4. 定义中的lazy, non-parametric怎么理解?

非参数（Non-parametric）
Non-parametric意味着算法不依赖样本数据的分布，模型只适应样本数据本身。这对于现实世界中不适合任何一个分布的数据集非常有用。除了k-NN，两个非常流行的非参数机器学习算法是：

决策树(Decision Trees )，例如像CART和C4.5
支持向量机（Support Vector Machines）

懒惰（lazy）

An eager learner has a model fitting or training step. A lazy learner does not have a training phase.

逻辑回归算法通过训练学习得到假设(hypothesis)的参数，进而在预测阶段使用这个假设。而K-NN则不同，它没有这一训练学习过程，而是像记住了所有训练集样本数据一样，在预测阶段全部拿来计算，看来lazy这个词还是挺恰当的(＾-＾)。

3.5. k-NN怎么用于回归?

k-NN 用来解决回归问题需要预测连续值，可以使用最近 $K$ 个“邻居”的加权平均值，权重与和“邻居”之间的距离成反比。和解决分类问题不同，不再是看“邻居”的大多数来决定分类标签了。

3.6. 最后, 为什么选择k-NN?

k-NN是监督学习算法的一种，虽然没有训练学习的过程，但是选择最近“邻居”的过程成本较高，如果没有其他优化手段，需要计算和所有训练集样本之间的距离，然后再排序，选出 $K$ 个最近的。随着特征向量维度增加或者是训练集样本的增加，计算成本将会是指数级的增长。不过k-NN也有优点：

可以快速实现 : 这也是为什么k-NN广泛作为其他算法的测试基准；
训练学习时间少；
预测准确性高: 很多研究论文中指出，k-NN在很多应用中预测的准确性都很高。

四. k-NN应用-提高约会对象匹配(python)

（参考数据集与源代码见 machine learning in action Source Code Ch02）
场景：Hellen最近在用一个在线约会app，app经常给她推荐一些她可能感兴趣的人，Hellen可以和这些人去约会，可是渐渐的Hellen发现，和她约会的这些人大致分为三种：

不喜欢(People she didn't like)
魅力一般(People she liked in small doses)
极具魅力(People she liked in large doses)

Hellen收集了一些app上没有的特征数据，希望我们帮忙将app推荐的人自动分类：

每年获取的飞行常客里程数
玩视频游戏的耗时百分比
每周吃掉的冰激凌（单位：升）

数据集文本格式如下：

40920   8.326976    0.953952    largeDoses
14488   7.153469    1.673904    smallDoses
26052   1.441871    0.805124    didntLike
75136   13.147394   0.428964    didntLike
35948   6.830792    1.213192    largeDoses
42666   13.276369   0.543880    largeDoses
67497   8.631577    0.749278    didntLike

4.1 读文件，解析特征向量和类别标签

"""
    读取数据集文件，输出特征矩阵和类别标签
"""
def file2matrix(filename):
    # get number of lines in file
    fr = open(filename)
    numberOfLines = len(fr.readlines())

    # create NumPy matrix to return
    fr = open(filename)
    datingDataMat = zeros((numberOfLines, 3))
    datingLabelDescs = []
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        # 3 features 
        datingDataMat[index, 0:3] = listFromLine[0:3]
        # label description
        datingLabelDescs.append(listFromLine[-1])
        index += 1

    # 类别数据转数值数据  [didntLike, smallDoses, largeDoses] -> [0, 1, 2]
    datingLabelDataFrame = pd.DataFrame(datingLabelDescs)
    datingLabelDict = {label: idx for idx, label in enumerate(unique(datingLabelDataFrame))}
    datingLabels = datingLabelDataFrame[0].map(datingLabelDict)

    return datingDataMat, datingLabels

很多机器学习算法不能处理类别数据，例如电影类型中有科幻、爱情、恐怖、乡村等，本节例子中不喜欢(didntLike)，魅力一般（smallDoses）和极具魅力（largeDoses），因此数据预处理阶段会涉及类别数据转换成数值数据的问题。关于
有序类别特征：电影评星
无序的类别特征，如电影类型，科幻->0、爱情->1、恐怖->2、乡村->3，但这样直接编码可能存在问题，因为计算机会认为3>2>2>0，如果算法中存在数值大小有关的计算影响了结果，就需要用到独热(one-hot)技术去解决，关于这块就不细说了，感兴趣可以自己去了解。

4.2 特征标准化(normalizing numeric values)

3.2小节介绍了计算最近“邻居”的三种方法，这里我们使用常用的欧式距离（Euclidean distance），这里有3个特征，设特征向量为 $(x, y, z)$ ，则距离计算方法如下：
$distance = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$
取两个样本的特征向量进行计算
$\sqrt{(40920 - 14488)^2 + (8.326976 - 7.153469)^2 + (0.953952 - 1.673904)^2}$
我们会发现每年的累计飞行里程数这个特征数值比较大，对距离的计算起到了决定性作用，这对其他两个特征不公平，因为在Hellen眼里，这些特征都是平等的，因此我们需要对数值进行标准化，即将处在不同数值范围的特征数据标准化到一个数值范围，比如[0,1]或者[-1,1]，我们选用[0,1]，标准化的计算方式如下：
$newValue = (oldValue - min)/(max - min)$
代码如下所示：

"""
    数值特征标准化
"""
def autoNorm(dataSet):
    # numpy中的array的min
    # arrayTest = array([[1,6,3],[4,2,5]])
    # arrayTest.min(0) -> array([1, 2, 3]) # 每一列的最小值
    # arrayTest.min(1) -> array([1, 2])  # 每一行的最小值
    minVal = dataSet.min(0)
    maxVal = dataSet.max(0)
    ranges = maxVal - minVal
    # shape：This is a tuple of integers indicating the size of the array in each dimension.
    # b = np.array([[1,2,3],[3,4,5]])
    # print(b.shape)
    # 输出(2,3)
    dataSetShape = shape(dataSet)
    normMat = zeros(dataSetShape)
    m = dataSet.shape[0]
    normMat = dataSet - tile(minVal, (m, 1))
    normMat = normMat/tile(ranges, (m, 1))
    return normMat, ranges, minVal

4.3 画散点图，观察特征

在处理好特征数据之后，通常先画出散点图观察一下，可以检验下前面两步没有问题，比如输出个空，也可以看出是否有明显的规律，还可以观察是否有明显离谱的点，我们的特征向量是三维的，有三个类别标签，我们挑两个特征来看下：

"""
    画出散点图，观察特征数据
"""
def plotDataSet3d(datingDataMat, classLabels):
    dating_x1 = []
    dating_y1 = []
    dating_x2 = []
    dating_y2 = []
    dating_x3 = []
    dating_y3 = []
    fig = plt.figure()
    ax = fig.add_subplot(111)
    i = 0
    for labels in datingLabels:
        if labels == 0:
            dating_x1.append(datingDataMat[i, 0])
            dating_y1.append(datingDataMat[i, 1])
            i = i + 1
        if labels == 1:
            dating_x2.append(datingDataMat[i, 0])
            dating_y2.append(datingDataMat[i, 1])
            i = i + 1
        if labels == 2:
            dating_x3.append(datingDataMat[i, 0])
            dating_y3.append(datingDataMat[i, 1])
            i = i + 1

    ax.scatter(dating_x1, dating_y1, s=5, label='不喜欢')
    ax.scatter(dating_x2, dating_y2, s=10, label='魅力一般')
    ax.scatter(dating_x3, dating_y3, s=15, label='极具魅力')
    plt.legend(loc='best')
    plt.xlabel('每年获取的飞行常客里程数（经标准化）')
    plt.ylabel('玩视频游戏所耗时间百分比（经标准化）')
    plt.show()

4.4 利用k-NN算法进行分类

终于来到了k-NN算法的核心部分～

"""
    对输入样本inX使用k-NN算法进行分类
"""
def kNNClassify(inX, dataSet, labels, start, k):
    dataSetSize = dataSet.shape[0]

    # Distance calculation
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistance = sqDiffMat.sum(axis=1)              # axis=0，按列相加； axis=1，按行相加；
    distance = sqDistance**0.5

    # Voting with lowest k distances
    sortedDistIndices = distance.argsort()          # argsort函数返回数组值从小到大索引值
    classCount = {}
    for i in range(k):
        labelIndex = sortedDistIndices[i]
        voteIlabel = labels[labelIndex + start]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # Sort dictionary
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

4.5 验证算法

"""
    对测试集进行预测，k-NN算法性能
"""
def datingClassTest():
    hoRatio = 0.10
    filename = "Ch02/datingTestSet.txt"
    datingDataMat, datingLabels = file2matrix(filename)

    normMat, ranges, minVal = autoNorm(datingDataMat)

    # plotDataSet(normMat, datingLabels)

    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = kNNClassify(normMat[i, :], normMat[numTestVecs:m, ], datingLabels[numTestVecs:m], numTestVecs,  3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print("the total error rate is: %f" % (errorCount / float(numTestVecs)))
    print(errorCount)

运行程序得到最终结果如下：