Py学习  »  机器学习算法

机器学习基础——简单易懂的K邻近算法,根据邻居“找自己”

承志 • 4 年前 • 361 次点击  
阅读 48

机器学习基础——简单易懂的K邻近算法,根据邻居“找自己”

本文始发于个人公众号:TechFlow,原创不易,求个关注


今天的文章给大家分享机器学习领域非常简单的模型——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个样本的结果来代表当前样本的结果。

整个算法的流程如下:

  1. 采集一批有标注结果的样本,设为s
  2. 遍历每一个未知结果的样本
  3. 遍历s,计算s中的每一个样本和的距离
  4. 根据距离进行排序,选出距离最小的k个样本
  5. 选出这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是非常基础的机器学习算法,相信对大家而言应该并不难。如果觉得有所收获,请顺手点个关注或者转发吧,你们的举手之劳对我来说很重要。

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/56048
 
361 次点击