专栏首页一名叫大蕉的程序员机器学习的敲门砖:kNN算法(下)

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

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

本文为数据茶水间群友原创,经授权在本公众号发表。

关于作者:Japson。某人工智能公司AI平台研发工程师,专注于AI工程化及场景落地。持续学习中,期望与大家多多交流技术以及职业规划。

0x00 前言

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

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

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

0x01 数据归一化

1.1 为什么要数据归一化

在实际应用中,样本的不同特征的单位不同,会在求距离时造成很大的影响。比如:在两个样本中肿瘤大小的分别为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}

1.2 最值归一化实现

为了了解最值归一化的代码实现,我们可以创建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()

1.3 均值方差归一化实现

同样地,为了了解均值方差归一化的代码实现,我们可以创建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])

1.4 Sklearn中的归一化

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

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

训练数据集进行归一化处理,需要计算出训练数据集的均值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)

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

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

同样地,我们仿照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

0x02 kNN优缺点

KNN的主要优点有:

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

KNN的主要缺点有:

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

维数

点到点

距离

1维

0到1的距离

1

2维

(0,0)到(1,1)的距离

1.414

3维

(0,0,0)到(1,1,1)的距离

1.73

64维

(0,0,…0)到(1,1,…1)

8

10000维

(0,0,…0)到(1,1,…1)

100

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

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

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

3 KD树

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

3.1 kd树的原理

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

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

3.2 kd树的构建

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

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

对于构建过程,有两个优化点:

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

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

  1. 构建根节点时,此时的切分维度为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. (2,3),(4,7),(5,4)挂在(7,2)节点的左子树,(8,1),(9,6)挂在(7,2)节点的右子树。
  3. 构建(7,2)节点的左子树时,点集合(2,3),(4,7),(5,4)此时的切分维度为y,中值为(5,4)作为分割平面,(2,3)挂在其左子树,(4,7)挂在其右子树。
  4. 构建(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

3.3 kd树的检索

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)。

3.4 sklearn中的KDTree

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()

图像化展示:

0xFF 总结

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

在《机器学习的敲门砖:kNN算法(上)》中,我们了解了非常适合入门机器学习的算法:k近邻算法。

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

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

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

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

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

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

下期预告:线性回归系列…

本文分享自微信公众号 - 一名叫大蕉的程序员(DaBananaTalk)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 手把脚看看密码学No.72

    咳咳,不可否认,有时候总会出现,请证明你爸是你爸的这种事情,所以会有了身份认证的密码。但是这个密码不是你们想的那个登录密码,银行卡密码,QQ密码,IQ密码,更不...

    大蕉
  • 分布式架构的套路No.74

    今天小蕉跟大伙一起聊聊分布式系统的架构的套路。在开始说套路之前,大家先思考一个问题,为什么要进行分布式架构? 大多数的开发者大多数的系统可能从来没接触过分布式...

    大蕉
  • 《七天数据可视化之旅》第一天 数据可视化过程

    Destiny,某物流公司数据产品经理,目前从事数据平台搭建和可视化相关的工作。持续学习中,期望与大家多多交流数据相关的技术和实际应用,共同成长。

    大蕉
  • 机器学习的敲门砖:kNN算法(下)

    关于作者:Japson。某人工智能公司AI平台研发工程师,专注于AI工程化及场景落地。持续学习中,期望与大家多多交流技术以及职业规划。

    木东居士
  • Numpy入门

    NumPy(Numerical Python) 是 Python 语言的一个扩展程序库,支持大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。

    俺也想起舞
  • 100个Numpy练习【2】

    Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

    YingJoy_
  • 100个Numpy练习【3】

    Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

    YingJoy_
  • 100个Numpy练习【5】

    Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

    YingJoy_
  • 100个Numpy练习【2】

    翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

    YingJoy_
  • 100个Numpy练习【3】

    翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

    YingJoy_

扫码关注云+社区

领取腾讯云代金券