【量化课堂】一只兔子帮你理解 kNN

r囧r小猫 2021-12-10 16:55 236阅读 0赞

**导语**：商业哲学家 Jim Rohn 说过一句话，“你，就是你最常接触的五个人的平均。”那么，在分析一个人时，我们不妨观察和他最亲密的几个人。同理的，在判定一个未知事物时，可以观察离它最近的几个样本，这就是 kNN（k最近邻）的方法。

作者：肖睿
    编辑：宏观经济算命师
    
    本文由JoinQuant量化课堂推出，本文的难度属于进阶（上），深度为 level-1

**简介**

kNN（k-Nearest Neighbours）是机器学习中最简单易懂的算法，它的适用面很广，并且在样本量足够大的情况下准确度很高，多年来得到了很多的关注和研究。kNN 可以用来进行分类或者回归，大致方法基本相同，本篇文章将主要介绍使用 kNN 进行分类。

**举个例子跟你讲**

kNN还真是直接讲例子最好懂。大家都喜欢兔子，所以就来说一说兔子的事情吧。

有一种兔子叫作***悲伤（Grief）***，它们的平均身高是 505050 厘米，平均体重 555 公斤。我们拿来一百个悲伤，分别测量它们的身高和体重，画在坐标图上，用绿色方块表示。  
![图1.png][1.png]

还有一种兔子呢，叫作***痛苦（Agony）***。它们体型比较小，平均身高是 303030 厘米，平均体重是 444 公斤。我们将一百个痛苦的身高和体重画在同一个坐标图上，用蓝色三角表示。  
![图2.png][2.png]

最后一种兔子叫***绝望（Despair）***。它们的平均身高45厘米，但体重较轻，平均只有2.5公斤。一百只绝望的数据用黄色圆圈表示。  
![图3.png][3.png]

在这些数据中，(身高,体重)(身高,体重)(身高,体重) 的二元组叫做*特征（features）*，兔子的品种则是分类*标签（class label）*。我们想解决的问题是，给定一个未知分类的新样本的所有特征，通过已知数据来判断它的类别。

北京十八环外有一个小树林里经常出现这三种兔子。为了了解它们的生态环境，某研究团队想知道三种兔子的数量比例；可是这些兔子又太过危险，不能让人亲自去做，所以要设计一个全自动的机器人，让它自己去树林里识别它遇到的每一个兔子的种类。啊，为了把故事讲圆，还要假设他们经费不足，所以机器只有测量兔子的身高和体重的能力。

那么现在有一迷之兔子，我们想判断它的类别，要怎么做呢？按照最普通的直觉，应该在已知数据里找出几个和我们想探究的兔子最相似的几个点，然后看看那些兔子都是什么个情况；如果它们当中大多数都属于某一类别，那么迷之兔子大概率也就是那个类别了。

于是乎，我们给机器人预设一个整数 kkk，让它去寻找距离最近的k个数据样本进行分析。好，机器发现了一只兔子，它长着八条腿，三十二只眼睛，毛茸茸的小尾巴，齐刷刷的八十六颗獠牙，面相狰狞，散发着噩梦般的腐臭，发出来自地狱底处的咆哮… 差不多就是这个样子（作者手绘）：  
![未知的凶猛兔子.png][.png]

可我们的机器才识别不了那么多，它只测量出这只兔子身长 404040 厘米，体重 2.72.72.7 公斤，就是下面图中那颗闪闪发亮的红星  
![图4.png][4.png]

kNN 算法如何对这次观测进行分类要取决于k的大小。直觉告诉我们迷之兔像是一只绝望，因为除了最近的蓝色三角外，附近其他都是黄色圆圈。的确，如果设 k=15k=15k=15，算法会判断这只兔子是一只绝望。但是如果设 k=1k=1k=1，那么由于距离最近的是蓝色三角，会判断迷之兔子是一只痛苦。

如果按照15NN和1NN的方法对这个二维空间上的每一个点进行分类，会形成以下的分割  
![15NN分类有星.png][15NN_.png]  
![1NN分类有星.png][1NN_.png]

在两组分类中，1NN 的分类边界明显更“崎岖”，但是对历史样本没有误判；而 15NN 的分类边界更平滑，但是对历史样本有发生误判的现象。选择k的大小取决于对偏差和方差之间的权衡，本篇不进行更深探讨，读者在使用 kNN 时凭感觉选一个 kkk 就好。

**距离函数**

我们在上面的例子中把一个很重要的概念隐藏了起来，在  
选择一个数量k还只是小问题，更重要的是距离的计算方法。毕竟，当我们说“最近的k个点”时，这个“近”是怎么衡量的？

在数学中，一个空间上距离的严格定义如下：  
设 MMM 为一个空间，MMM 上的一个距离函数是一个函数 d:M×M→Rd:M×M→Rd:M×M→R，满足

∙ d(x,y)≥0 ∀x,y∈M∙ d(x,y)≥0 ∀x,y∈M∙ d(x,y)≥0 ∀x,y∈M  
∙ d(x,y)=0⟺x=y∙ d(x,y)=0⟺x=y∙ d(x,y)=0⟺x=y  
∙ d(x,y)=d(y,x) ∀x,y∈M∙ d(x,y)=d(y,x) ∀x,y∈M∙ d(x,y)=d(y,x) ∀x,y∈M  
∙ d(x,z)≤d(x,y)+d(y,z) ∀x,y,z∈M∙ d(x,z)≤d(x,y)+d(y,z) ∀x,y,z∈M∙ d(x,z)≤d(x,y)+d(y,z) ∀x,y,z∈M  
两个点 x,yx,yx,y 之间的距离就是 d(x,y)d(x,y)d(x,y)。

我们一般最常用的距离函数是欧氏距离，也称作 L2L2L2 距离。如果 x=(x1,x2,…,xn)x=(x1,x2,…,xn)x=(x1,x2,…,xn) 和 y=(y1,y2,…,yn)y=(y1,y2,…,yn)y=(y1,y2,…,yn)是 nnn 维欧式空间 RnRnRn 上的两个点，那它们之间的 L2L2L2 距离是

d2(x,y)=∑i=1n(xi−yi)2−−−−−−−−−−√.

d2(x,y)=∑i=1n(xi−yi)2−−−−−−−−−−√.d2(x,y)=∑i=1n(xi−yi)2.

L2L2L2 是更普遍的 LpLpLp 距离在 p=2p=2p=2 时的特列。LpLpLp 距离的函数 dpdpdp 定义如下：对于 1≤p<∞1≤p<∞1≤p<∞，有

dp(x,y)=(∑i=1n|xi−yi|p)1/p.

dp(x,y)=(∑i=1n|xi−yi|p)1/p.dp(x,y)=(∑i=1n|xi−yi|p)1/p.

还有 L∞L∞L∞ 距离

d∞(x,y)=maxi=1,…,n|xi−yi|.

d∞(x,y)=maxi=1,…,n|xi−yi|.d∞(x,y)=maxi=1,…,n|xi−yi|.

在实际应用中，距离函数的选择应该根据数据的特性和分析的需要而定，本篇就不进行更深入的探讨，一般情况下使用最常用的 L2L2L2 函数即可。

但是！注意！使用 kNN 时需要根据特征数据的取值区间来调整坐标轴的比例，这个做法叫作标准化或者归一化。为什么要这么做呢？拿上面的例子来说，一只兔子的身长（cm）数值平均是它的体重（kg）的 101010 倍左右，如果我们在这组数值上直接使用 L2L2L2 距离函数的话就会导致横轴的距离比重明显放大，分类结果也不合理，如下图所示  
![15NN 距离未归一.png][15NN _.png]

如果把坐标轴成其他的单位，比如毫米和吨，并用相应的新数值来计算距离，又会得到完全不同的分类标准。甚至，在极端情况下，如果身高用纳米并且体重用吨计量，那么相比之下身高的数值会奇高无比，以至于两点之间的距离是完全由身高决定的，体重则没有任何权重。为了解决这个问题，我们应该在计算距离时把所有坐标轴进行归一化。

在之前的例子中，由于横轴数值大约是竖轴的 101010 倍左右，所以我们将横轴（身高）的数值压缩 101010 倍，即计算距离时使用

d((x1,x2),(y1,y2))=(x110−y110)2+(x2−y2)2−−−−−−−−−−−−−−−−−−−−√

d((x1,x2),(y1,y2))=(x110−y110)2+(x2−y2)2−−−−−−−−−−−−−−−−−−−−√d((x1,x2),(y1,y2))=(x110−y110)2+(x2−y2)2

就可以得出合理的 kNN 分类。

一般来说，假设进行 kNN 分类使用的样本的特征是 \{(xi1,xi2,…,xin)\}mi=1\{(xi1,xi2,…,xin)\}mi=1\{(xi1,xi2,…,xin)\}i=1m，取每一轴上的最大值减最小值

Mj=maxi=1,…,mxij−mini=1,…,mxij,

Mj=maxi=1,…,mxij−mini=1,…,mxij,Mj=maxi=1,…,mxij−mini=1,…,mxij,

并且在计算距离时将每一个坐标轴除以相应的 MjMjMj 以进行归一化，即

d((y1,…,yn),(z1,…,zn))=∑j=1n(yjMj−zjMj)2−−−−−−−−−−−−−−−⎷

d((y1,…,yn),(z1,…,zn))=∑j=1n(yjMj−zjMj)2−−−−−−−−−−−−−−−⎷d((y1,…,yn),(z1,…,zn))=∑j=1n(yjMj−zjMj)2

便可以规避坐标轴比例失衡的问题。

**概率 KNN**

上面的kNN算法返回的是对一组特征的绝对分类，告诉我们这只兔子被判断为哪一个类别。可有时我们并不想知道一个确切地分类，而想知道它属于某个分类的概率是多大。比如我们发现一只身长 373737 体重 4.84.84.8 的小兔兔，在下图五角星的位置。  
![图5.png][5.png]

这只兔子的特征数据在悲伤和痛苦的分界处，机器不论判断它属于哪个类别都很有可能是错的。这时，类似“它有一半可能性是痛苦，一半可能性是悲伤”的反馈会更有意义。

为了这个目的，我们同样找找出距离问题特征最近的 kkk 个样本，但与其寻找数量最多的分类，我们统计其中每个类别的分别有多少个，再除以 kkk 得到一个属于每一个类别概率值。比如在上面的图里，距离五角星最近的 151515 个样本中，有 888 只悲伤和 777 只痛苦，由此判断：它有 53%53%53% 的可能性是悲伤，47%47%47% 的可能性是痛苦，0%0%0% 的可能性是绝望。

在整个二维空间中的每一个点上进行概率 kNN 算法，可以得到每个特征点是属于某个类别的概率热力图，图中颜色越深代表概率越大。

![绿的.png][.png 1]  
![蓝的.png][.png 2]  
![黄的.png][.png 3]

相比于绝对的分类，这些概率的计算会给我们更有效的表述以及更多的应用空间。比如说，我们知道悲伤兔子喜欢向我们的机器人上喷洒奇怪的粘液，毫无作用毫无意义的绿色的粘液，就像这样（作者手绘）：  
![粘液兔子.png][.png 4]

倒不是因为别的，我们就是觉得这种粘液很恶心，清洗起来也很麻烦，所以我们想让机器人在测量并发现是悲伤之后马上掉头逃跑。但是如果机器发现了一只体型接近痛苦的悲伤，并且普通的 kNN 算法发生误判，没有马上逃跑，那么最后就会被喷了。所以我们使用概率 kNN 的算法并且使用以下风控原则：只要发现兔子有 30%30%30% 以上的概率是悲伤，就马上逃跑。从此之后，机器人就再也没被喷过。

**结语**

不知你有没有发现，我跟你讲了这么多关于兔子的事，却丝毫没有提及如何用代码计算 kNN。这是因为 kNN 虽然思路简单，但实现起来有一个问题，那就是计算量很大；当数据量很多时，拿一组特征来和所有样本依次计算距离并选取最近的 kkk 个，是非常耗费时间的。所以，在量化课堂接下来的文章中，我们将讲解 kNN 的一个高效算法—kd树。

[1.png]: /images/20211210/c740e373f228478a9b652ca8ea1df8e9.png
[2.png]: /images/20211210/b2375d2847bb460aa7f46fed85f6a0ec.png
[3.png]: /images/20211210/910b55c928de4d23858d629912e59a8f.png
[.png]: /images/20211210/965a70d9f6a24ee894b8e01c6ef7c5b4.png
[4.png]: /images/20211210/3d499d26a455417896a60a4c0efd38a6.png
[15NN_.png]: /images/20211210/537e264707c746de892ed9751b16a560.png
[1NN_.png]: /images/20211210/f6b9f4c83b5a4e569d567632e80a70c1.png
[15NN _.png]: /images/20211210/21f34269e1e6443185132d69b4051a0e.png
[5.png]: /images/20211210/9823fc168167468a8fe872097c6ba761.png
[.png 1]: /images/20211210/98171410e4454a9aabc8defac0f078dc.png
[.png 2]: /images/20211210/41d9fd1c139f442d874963aff11085d5.png
[.png 3]: /images/20211210/ec81b86985bd4c3a94b150d2bc960928.png
[.png 4]: /images/20211210/beb8431c3a304b3c8691472fa8130bfb.png