今天的文章给大家分享机器学习领域非常简单的模型 --KNN, 也就是 K Nearest Neighbours 算法, 翻译过来很简单, 就是 K 最近邻居算法. 这是一个经典的无监督学习的算法, 原理非常直观, 易于理解.
监督与无监督
简单介绍一下监督这个概念, 监督是 supervised 的直译, 我个人觉得不太准确, 翻译成有标注和无标注可能更加准确. 也就是说如果模型在学习的时候, 既能够看到样本的特征又可以看到样本的结果, 那么就是有监督学习, 如果只能看到特征, 但是并不能知道这些特征对应的结果, 那么就是无监督学习.
之前我们介绍的线性回归和逻辑回归模型就是典型的有监督模型, 因为模型在训练的时候知道样本的结果, 并且根据我们设计的损失函数朝着贴近样本真实结果的方向 "努力". 而今天介绍的 KNN 算法则是一个经典的无监督学习模型, 算法在训练的时候并不知道正确的结果是什么, 也因此模型根本没有损失函数这个概念, 那么自然整个算法的运行原理也很监督模型大相径庭.
算法概述
其实 KNN 算法的原理非常简单, 简单到只有一句话, 就是找到样本的 K 个邻居, 然后这 K 个邻居出现次数最多的结果就是答案.
但是我们怎么定义邻居, 又怎么找到这些邻居呢?
在回答这个问题之前, 我们先来看一个例子.
假设现在有这么一个问题, 我需要知道全城的用户有哪些用户有车, 但是我们只知道用户的家庭地址, 那么该怎么办呢?
很显然, 我需要在全城做一个调查, 也就是对全城市民做一个抽样, 抽取一部分做个是否有车的调研. 对于剩下的用户呢, 我去寻找离他最近的几个邻居, 看看他的这几个邻居是否有车. 如果离他近的邻居大多数都有车, 那么, 我可以认为, 该用户可能住在富人区, 他有车的概率比较大. 如果他的邻居都没有车, 可能他住在穷人区, 他很有可能也没有车.
你可能会说中国不像美国可以划分成穷人区和富人区, 往往在一个区域内穷富是杂居的, 用这种方法得出的结果准确率肯定不高.
的确存在这个问题, 所以我们可以在此基础上做一点优化, 很简单, 我们只知道用户住在哪里是不够的, 我们可能还需要了解用户的收入情况. 在寻找他最近的邻居的过程当中, 除了要考虑距离上的远近之外, 还需要保证收入尽可能接近.
如果能知道和他距离和收入都接近的邻居是否有车, 那么大概率可以判断这个用户是否有车. 重复这个算法, 我就可以通过少量的样本, 算出全体样本是否有车的情况.
说到这里, 想必你应该能明白, 在 KNN 算法的范畴当中,"邻居" 指的不是地理上的邻近关系, 而指的是样本空间的接近.
我们都知道, 对于向量 A(a1,a2,a3...an),B(b1,b2,b3...bn)
在机器学习当中, 我们通常会把一条样本数据当做向量空间中的一条向量. 比如在刚刚的问题当中, 用户 A, 他的样本可能是 (120.3213, 30.1312, 10.5), 指的是居住地点的经纬度和年收入. 也可能是(城东, 泾河花园, 10.5), 或者是(城东, 沿河西路, 泾河花园, 10.5) 等等.
同样的一条样本, 表示成向量就有多种形式. 对于不同的问题而言, 不同的表示方法拥有不同的效果. 在当前问题当中, 我们需要计算向量和向量之间的距离, 显然, 使用第一种经纬度的表示方式更好.
算法原理
通过上面这个例子, 其实我们已经把算法的整个运行过程讲解清楚了. 所谓的 k - 邻近算法, 其实就是使用距离样本最近的 k 个样本的结果来代表当前样本的结果.
整个算法的流程如下:
采集一批有标注结果的样本, 设为 s
遍历每一个未知结果的样本
遍历 s, 计算 s 中的每一个样本和 的距离
根据距离进行排序, 选出距离最小的 k 个样本
选出这 k 个样本中出现频次最多的类别作为 的结果
算法流程不难理解, 但是其中有几个注意点:
首先, 每一个样本其实指的是样本空间里的一个向量. 既然是向量, 并且要计算样本之间的距离, 那么向量的每一个维度都必须是实数. 一般情况下, 字符串是无法作为特征计算距离的.
其次, 向量距离的计算方法. 常规来说, 向量之间的距离可以理解成空间中两个点的距离, 关于这个距离常规上有几种计算的公式.
第一种叫做欧式公式, 就是我们刚才列的也是最常见的欧几里得距离公式:
第二种叫做曼哈顿距离, 曼哈顿是纽约的 CBD, 既然是街区, 从一个路口到另一个路口的距离显然是不能从街区中跨越的. 所以两个路口的距离, 其实是两点的直角连线距离.
假设一个点坐标是(3, 4) , 另一个点的坐标是(5, 1), 这两点的距离 d = | 3 - 5| + | 4 - 1| = 5
公式为:
在距离计算的方法当中, 欧氏距离和曼哈顿距离最常用, 除了这两种之外还有切比雪夫距离和闵可夫斯基距离等, 一般不太常用, 我们不多做赘述, 感兴趣的可以自行谷歌.
代码实现
下面就到了我们紧张刺激的代码实现环节, KNN 的原理不算难, 只要能理解, 稍微思考一下我想大部分同学应该都能写出来. 所以之前阿里的校招经常用 KNN 作为笔试题, 考察一下同学的代码能力以及对基础模型的理解情况. 所以实现是一方面, 将代码写漂亮, 实现完美又是另一方面.
仔细想一下当我们的数据有了之后, KNN 主体就只有一个函数, 我们先来看一下不使用任何库函数进行实现的代码:
- def classify(vector, dataSet, labels, k):
- dis = []
- for i in range(len(dataSet)):
- data = dataSet[i]
- d = calculate_distance(vector, data)
- dis.append(d)
- dis_index = sorted(enumerate(dis), key=lambda x: x[1])
- label_map = {}
- for i in range(k):
- label = labels[dis_index[i][0]]
- if label in label_map:
- label_map[label] += 1
- else:
- label_map[label] = 1
- maxi = 0
- label = None
- for i in label_map:
- if label_map[i]> maxi:
- maxi = label_map[i]
- label = i
- return label
其中 calculate_distance 是计算两个向量距离的函数, 实现也很简单, 就是套用一下上面刚才提到的距离公式, 基本没有难度:
- def calculate_distance(vectorA, vectorB):
- d = 0
- for i in range(len(vectorA)):
- d += (vectorA[i] - vectorB[i]) * (vectorA[i] - vectorB[i])
- return math.sqrt(d)
但是显然这是没有必要的, 我们多做了很多无用功. 灵活地使用库函数, 可以将代码缩减到不可思议的地步:
- import random
- import numpy as np
- from collections import Counter
- def classify(x, dataset, labels, K):
- x, dataset = np.array(x), np.array(dataset)
- # 通过 numpy 计算距离, numpy 有广播机制
- # 会自动将 x 和 dataset 当中的每一行计算距离
- dis = np.sqrt(np.sum((x - dataset) ** 2, axis=1))
- # 按照距离排序, 返回结果对应的下标
- topKIdices = np.argsort(dis)[:K]
- labels = np.array(labels)
- # 使用 Counter 进行计数, 返回数量最多的
- counter = Counter(labels[topKIdices])
- return counter.most_common(1)[0][0]
不知道大家看到有没有觉得有点不可思议, 我们一个 for 循环都没有用到就实现了 KNN 算法, 只有短短 5 行. 其中 Numpy 是我们做机器学习非常常用的包, 由于 Numpy 有非常多的 API 可以非常方便地进行计算, 所以我们会在之后单独开一个 Numpy 专题. 关于 Counter 等库函数的用法, 在之前介绍 collections 的文章当中介绍过, 如果有遗忘的同学可以在公众号回复 collections 获取文章.
最后, 我们创造一个简单的 sample 来验证一下:
- def create_data_set():
- dataset = np.array([[0.5, 0], [0, 0.5], [1.5, 1], [1, 1.5]])
- labels = ['A', 'A', 'B', 'B']
- return dataset, labels
运行程序得到的结果是 A.
优化
到这里我们还没有结束, 还有一个问题值得讨论. 在我们刚才叙述算法流程的过程当中, 有一个关键点被我们忽略了.
我们的样本由特征构成, 我们对特征向量计算距离. 问题是这些特征并不是一个维度的, 还用上面的例子. 我们为了判断一个用户是否有车, 用到了三个特征, 分别是他家的经度, 纬度和年收入. 注意, 经纬度和年收入并不是一个量纲下的变量, 从数学上我们当然可以对它们当做是一个量纲来计算, 但是这样显然是不准确的. 最主要的问题是, 不同量纲的特征波动的幅度可能完全不同.
这一点应该不难理解, 对于经纬度而言, 取值范围假设是[0, 360], 但是年收入的浮动范围可能是上千万. 显然如果我们直接来计算距离的话, 那么主要的权重就落在了年收入上, 这个模型就发生了倾斜, 这显然是我们不想看到的, 因为会影响模型最终的效果. 为了解决这个问题, 我们需要将这些量纲归一化, 消除量纲带来的影响. 这也是 KNN 关键的优化.
归一化的方式很多, 比较常用的有两种. 一种是 Standardization, 又称为 Z-score normalization, 归一化之后的数据服从正态分布, 它的公式如下:
这里的 和分别对应样本的均值和方差, 归一化之后的结果在 [-1, 1] 之间.
另一种归一化的方法叫做 Min-max Scaling, 它是根据样本的最大最小值进行的缩放. 公式如下:
这样缩放之后的结果在 [0, 1] 之间, 最大值时取 1, 最小值时取 0, 这也是最常用的归一化的方法之一. 通过归一化之后, 我们可以将不同量纲下的变量缩放到同一个取值范围当中, 从而将特征拉到平等的维度, 这样模型学习的效果更佳均匀, 不容易被其中某一个或者某几个特征带偏.
今天的文章就是这些, KNN 是非常基础的机器学习算法, 相信对大家而言应该并不难. 如果觉得有所收获, 请顺手点个关注或者转发吧, 你们的举手之劳对我来说很重要.
来源: https://www.cnblogs.com/techflow/p/12460255.html