机器学习的敲门砖kNN算法下

共计 7387 个字符，预计需要花费 19 分钟才能阅读完成。

作者 | Japson
来源 | 木东居士

在上一篇文章《机器学习的敲门砖：kNN 算法（中）》中，我们借助 kNN 分类算法，学习了如下知识点：

将数据集划分为训练数据集和测试数据集，以此验证模型好坏。
在我们得到了分类结果之后，计算出 accuracy 分类精准度。
了解了超参数对模型的影响，并使用网格搜索算法搜索出最佳超参数组。

但是在前面的实验中，我们都忽略了相当关键的一步，数据归一化。本篇文章，我们可以学习数据归一化对算法的影响及其实现。最后，作为 kNN 算法的收尾，我们会总结算法的优缺点以及优化思路。

在实际应用中，样本的不同特征的单位不同，会在求距离时造成很大的影响。比如：在两个样本中肿瘤大小的分别为 1cm 和 5cm，发现时间分别为 100 天和 200 天，那么在求距离时，时间差为 100、大小差为 4，那么其结果会被时间所主导，因为肿瘤大小的差距太小了。但是如果我们把时间用年做单位，0.27 年与 0.55 年的差距又远小于肿瘤大小的差距，结果又会被大小主导了。

我们发现，在量纲不同的情况下，以上的情况，不能反映样本中每一个特征的重要程度。这就需要数据归一化了。

一般来说，我们的解决方案是：把所有的数据都映射到同一个尺度（量纲）上。

一般来说，常用的数据归一化有两种：

最值归一化 (normalization)： 把所有数据映射到 0 - 1 之间。
最值归一化的使用范围是 特征的分布具有明显边界的 (分数 0～100 分、灰度 0～255)， 受 outlier 的影响比较大

x_{scale} = \frac {x - x_{min}} {x_{max} - x_{min}}

均值方差归一化 (standardization)： 把所有数据归一到均值为 0 方差为 1 的分布中。
适用于数据中没有明显的边界，有可能存在极端数据值的情况.

x_{scale} = \frac {x - x_{mean}} {S}

为了了解最值归一化的代码实现，我们可以创建 100 个随机数，然后对其进行最值归一化。

import numpy as np# 创建 100 个随机数 x = np.random.randint(0,100,size=100)# 最值归一化（向量）# 最值归一化公式，映射到 0，1 之间 (x - np.min(x)) / (np.max(x) -  np.min(x))# 最值归一化（矩阵）# 0～100 范围内的 50* 2 的矩阵 X = np.random.randint(0,100,(50,2))# 将矩阵改为浮点型 X = np.array(X, dtype=float)# 最值归一化公式，对于每一个维度（列方向）进行归一化。# X[:,0] 第一列，第一个特征 X[:,0] = (X[:,0] - np.min(X[:,0])) / (np.max(X[:,0]) - np.min(X[:,0]))# X[:,1]第二列，第二个特征 X[:,1] = (X[:,1] - np.min(X[:,1])) / (np.max(X[:,1]) - np.min(X[:,1]))# 如果有 n 个特征，可以写个循环：for i in range(0,2):
    X[:,i] = (X[:,i]-np.min(X[:,i])) / (np.max(X[:,i] - np.min(X[:,i])))

下面我们可以简单地绘制样本，并使用 np.mean()/np.std() 来计算其均值和方差

import matplotlib.pyplot as plt# 简单绘制样本，看横纵坐标 plt.scatter(X[:,0],X[:,1])
plt.show()

同样地，为了了解均值方差归一化的代码实现，我们可以创建 100 个随机数，然后对其进行均值方差归一化。

X2 = np.array(np.random.randint(0,100,(50,2)),dtype=float)# 套用公式，对每一列做均值方差归一化 for i in range(0,2):
    X2[:,i]=(X2[:,i]-np.mean(X2[:,i])) / np.std(X2[:,i])

下面我们可以简单地绘制样本

plt.scatter(X2[:,0],X2[:,1])
plt.show()

计算其均值 / 方差

np.mean(X2[:,0])
np.std(X2[:,1])

首先我们来看一个在实际使用归一化时的一个小陷阱。

我们在建模时要将数据集划分为训练数据集 & 测试数据集。

训练数据集进行归一化处理，需要计算出训练数据集的均值 mean_train 和方差 std_train。

问题是：我们在对测试数据集进行归一化时，要计算测试数据的均值和方差么？

答案是否定的。在对测试数据集进行归一化时，仍然要使用训练数据集的均值 train_mean 和方差 std_train。这是因为测试数据是模拟的真实环境，真实环境中可能无法得到均值和方差，对数据进行归一化。只能够使用公式 (x_test - mean_train) / std_train
并且，数据归一化也是算法的一部分，针对后面所有的数据，也应该做同样的处理.

因此我们要保存训练数据集中得到的均值和方差。

在 sklearn 中专门的用来数据归一化的方法：StandardScaler。

下面我们加载鸢尾花数据集

import numpy as npfrom sklearn import datasetsfrom sklearn.model_selection import train_test_split

iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train,X_test,y_train,y_test = train_test_split(iris.data,iris.target,test_size=0.2,random_state=666)

使用数据归一化的方法：

from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()# 归一化的过程跟训练模型一样 standardScaler.fit(X_train)
standardScaler.mean_
standardScaler.scale_   # 表述数据分布范围的变量，替代 std_# 使用 transformX_train_standard = standardScaler.transform(X_train)
X_test_standard = standardScaler.transform(X_test)

如此就能输出归一化后的数据了。

同样地，我们仿照 sklearn 的风格，可以自己实现一下均值方差归一化的方法。

我们在之前的工程中创建 processing.py：

import numpy as npclass StandardScaler:

    def __init__(self):
        self.mean_ = None
        self.scale_ = None

    def fit(self, X):
        """根据训练数据集 X 获得数据的均值和方差"""
        assert X.ndim == 2, "The dimension of X must be 2"

        # 求出每个列的均值
        self.mean_ = np.array([np.mean(X[:,i] for i in range(X.shape[1]))])
        self.scale_ = np.array([np.std(X[:, i] for i in range(X.shape[1]))])        return self    def tranform(self, X):
        """将 X 根据 StandardScaler 进行均值方差归一化处理"""
        assert X.ndim == 2, "The dimension of X must be 2"
        assert self.mean_ is not None and self.scale_ is not None, \        "must fit before transform"
        assert X.shape[1] == len(self.mean_), \        "the feature number of X must be equal to mean_ and std_"
        # 创建一个空的浮点型矩阵，大小和 X 相同
        resX = np.empty(shape=X.shape, dtype=float)        # 对于每一列（维度）都计算
        for col in range(X.shape[1]):
            resX[:,col] = (X[:,col] - self.mean_[col]) / self.scale_[col]        return resX

KNN 的主要优点有：

理论成熟，思想简单，既可以用来做分类也可以用来做回归
天然解决多分类问题，也可用于回归问题
和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
由于 KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN 方法较其他方法更为适合

KNN 的主要缺点有：

计算量大，效率低。
即使优化算法，效率也不高。
高度数据相关，样本不平衡的时候，对稀有类别的预测准确率低
相比决策树模型，KNN 模型可解释性不强
维数灾难：
随着维度的增加，“看似相近”的两个点之间的距离越来越大，而 knn 非常依赖距离

大家感觉一万维貌似很多，但实际上就是 100*100 像素的黑白灰图片。

以上就是关于 kNN 算法的总结。

你是不是以为这一篇就两节内容就结束了？没想到吧！下面还有一波干货：kNN 优化之 KD 树。

K 近邻法的重要步骤是对所有的实例点进行快速 k 近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询操作是，使用 kd 树。

kd 树是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，且 kd 树是一种二叉树，表示对 k 维空间的一个划分。

k-d tree 是每个节点均为 k 维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为 d，其左子树上所有点在 d 维的坐标值均小于当前值，右子树上所有点在 d 维的坐标值均大于等于当前值，本定义对其任意子节点均成立。

常规的 k -d tree 的构建过程为：

循环依序取数据点的各维度来作为切分维度，
取数据点在该维度的中值作为切分超平面，
将中值左侧的数据点挂在其左子树，将中值右侧的数据点挂在其右子树，
递归处理其子树，直至所有数据点挂载完毕。

对于构建过程，有两个优化点：

选择切分维度：根据数据点在各维度上的分布情况，方差越大，分布越分散，从方差大的维度开始切分，有较好的切分效果和平衡性。
确定中值点：预先对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。也可以从原始数据点中随机选择固定数目的点，然后对其进行排序，每次从这些样本点中取中值，来作为分割超平面。该方式在实践中被证明可以取得很好性能及很好的平衡性。

例子：
采用常规的构建方式，以二维平面点 (x,y) 的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明 k -d tree 的构建过程：

构建根节点时，此时的切分维度为 x，如上点集合在 x 维从小到大排序为 (2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)；
其中值为(7,2)。
（注：
2,4,5,7,8,9 在数学中的中值为(5 + 7)/2=6，但因该算法的中值需在点集合之内，所以本文中值计算用的是 len(points)//2=3, points[3]=(7,2)）
(2,3)，(4,7)，(5,4)挂在 (7,2) 节点的左子树，(8,1)，(9,6)挂在 (7,2) 节点的右子树。
构建 (7,2) 节点的左子树时，点集合 (2,3)，(4,7)，(5,4) 此时的切分维度为 y，中值为 (5,4) 作为分割平面，(2,3)挂在其左子树，(4,7)挂在其右子树。
构建 (7,2) 节点的右子树时，点集合 (8,1)，(9,6) 此时的切分维度也为 y，中值为 (9,6) 作为分割平面，(8,1)挂在其左子树。
至此 k -d tree 构建完成。

上述的构建过程结合下图可以看出，构建一个 k -d tree 即是将一个二维平面逐步划分的过程。

需要注意的是，对于每次切分，都是循环顺序选择维度的，二维是：x->y->x…；三维则是：x->y->z->x…。

下面从三维空间来看一下 k -d tree 的构建及空间划分过程。首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此 4 个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为 8 个子空间，此 8 个子空间即为叶子节点。

# points 为实例点集合，depth 深度，为用来确定取维度的参数 def kd_tree(points, depth):    
    if 0 == len(points):        return None
    # 指定切分维度，len(points[0])是数据的实际维度，这样计算可以保证循环
    cutting_dim = depth % len(points[0])    # 切分点初始化
    medium_index = len(points)    # 对所有的实例点按照指定维度进行排序，itemgetter 用于获取对象哪些维度上的数据，参数为需要获取的数据在对象中的序号
    points.sort(key=itemgetter(cutting_dim))
    # 将该维度的中值点作为根节点
    node = Node(points[medium_index])
    # 对于左子树，重复构建（depth+1）node.left = kd_tree(points[:medium_index], depth + 1)
    # 对于右子树，重复构建（depth+1）node.right = kd_tree(points[medium_index + 1:], depth + 1)
    return node

kd 树的检索是 KNN 算法至关重要的一步，给定点 p，查询数据集中与其距离最近点的过程即为最近邻搜索。

如在构建好的 k -d tree 上搜索 (3,5) 的最近邻时，对二维空间的最近邻搜索过程作分析。首先从根节点 (7,2) 出发，将当前最近邻设为 (7,2)，对该 k -d tree 作深度优先遍历。以(3,5) 为圆心，其到 (7,2) 的距离为半径画圆（多维空间为超球面），可以看出 (8,1) 右侧的区域与该圆不相交，所以 (8,1) 的右子树全部忽略。接着走到 (7,2) 左子树根节点 (5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。以(3,5) 为圆心，其到 (5,4) 的距离为半径画圆，发现 (7,2) 右侧的区域与该圆不相交，忽略该侧所有节点，这样 (7,2) 的整个右子树被标记为已忽略。遍历完 (5,4) 的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以 (3,5) 的最近邻为(5,4)。

Sklearn 中有 KDTree 的实现，仅构建了一个二维空间的 k -d tree，然后对其作 k 近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。

import numpy as npfrom matplotlib import pyplot as pltfrom matplotlib.patches import Circlefrom sklearn.neighbors import KDTree
np.random.seed(0)
points = np.random.random((100, 2))
tree = KDTree(points)
point = points[0]# kNNdists, indices = tree.query([point], k=3)
print(dists, indices)# query radiusindices = tree.query_radius([point], r=0.2)
print(indices)
fig = plt.figure()
ax = fig.add_subplot(111, aspect='equal')
ax.add_patch(Circle(point, 0.2, color='r', fill=False))
X, Y = [p[0] for p in points], [p[1] for p in points]
plt.scatter(X, Y)
plt.scatter([point[0]], [point[1]], c='r')
plt.show()

图像化展示：

到这里，我们 kNN 算法就算告一段落了。我们回顾一下：

在《机器学习的敲门砖：kNN 算法（上）》中，我们了解了非常适合入门机器学习的算法：k 近邻算法。

我们学习了 kNN 算法的流程，并且在 jupyter notebook 上手动实现了代码，并且在外部也进行了封装。最后我们学习了 sklearn 中的 kNN 算法。

由此我们引出了疑问：即如何评价模型的好坏。

在《机器学习的敲门砖：kNN 算法（中）》中，我们使用训练数据集和测试数据集来判断模型的好坏，给出并实现 accurcay 这一分类问题常用指标，计算出 accuracy 分类精准度。最后我们再探寻超参数的选择对模型的影响。并使用网格搜索算法搜索出最佳超参数组。

在本篇中，我们学习了数据归一化对算法的影响及其实现。作为 kNN 算法系列的收尾，我们总结算法的优缺点。并在最后详细阐述了 kNN 优化算法之一的“KDTree”。

相信大家通过这三篇的学习，已经初步了解了机器学习中最简单朴素的算法。现在有很多机器学习的文章笔记，开篇都是玄之又玄的损失函数、梯度下降、L1 正则 L2 正则云云，实属劝退最佳法宝。但是我们也发现，其实机器学习并没有想象中的那么抽象，我们也可以通过代码的方式来对其中的概念进行理解。

当然，此三篇文章，包括以后的系列文章，为本人的学习笔记，或称之为“集注”，是在各位老师前辈基础上总结归纳而来，拾人牙慧矣。因参考甚多，故不能一一标注出处，还请见谅。

搜索进入小程序，可解锁更多精彩资讯和优质内容，不要错过哟！

0x00 前言

0x01 数据归一化

1.1 为什么要数据归一化

1.2 最值归一化实现

1.3 均值方差归一化实现

1.4 Sklearn 中的归一化

1.5 自己实现均值方差归一化

0x02 kNN 优缺点

0x03 KD 树

3.1 kd 树的原理

3.2 kd 树的构建

3.3 kd 树的检索

3.4 sklearn 中的 KDTree

0xFF 总结

Just My Socks（注册教程内含优惠码）