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

2019/04/10 10:10
阅读数 13

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

<br>

<section id="nice" data-tool="mdnice编辑器" data-website="https://www.mdnice.com" style="font-size: 16px; color: black; padding: 10px; line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; word-break: break-word; word-wrap: break-word; text-align: left; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, 'PingFang SC', Cambria, Cochin, Georgia, Times, 'Times New Roman', serif;"><p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">今天的文章给大家分享机器学习领域非常简单的模型——KNN,也就是K Nearest Neighbours算法,翻译过来很简单,就是K最近邻居算法。这是一个经典的<strong style="font-weight: bold; color: rgb(71, 193, 168);">无监督学习</strong>的算法,原理非常直观,易于理解。</p> <h2 data-tool="mdnice编辑器" style="margin-top: 40px; font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 30px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">监督与无监督</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">简单介绍一下监督这个概念,监督是supervised的直译,我个人觉得不太准确,翻译成<strong style="font-weight: bold; color: rgb(71, 193, 168);">有标注和无标注</strong>可能更加准确。也就是说如果模型在学习的时候,既能够看到样本的特征又可以看到样本的结果,那么就是有监督学习,如果只能看到特征,但是并不能知道这些特征对应的结果,那么就是无监督学习。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">之前我们介绍的线性回归和逻辑回归模型就是典型的有监督模型,因为模型在训练的时候知道样本的结果,并且根据我们设计的损失函数朝着贴近样本真实结果的方向“努力”。而今天介绍的KNN算法则是一个经典的无监督学习模型,算法在训练的时候并不知道正确的结果是什么,也因此模型根本没有损失函数这个概念,那么自然整个算法的运行原理也很监督模型大相径庭。</p> <h2 data-tool="mdnice编辑器" style="margin-top: 40px; font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 30px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">算法概述</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">其实KNN算法的原理非常简单,简单到只有一句话,就是<strong style="font-weight: bold; color: rgb(71, 193, 168);">找到样本的K个邻居</strong>,然后这K个邻居出现次数最多的结果就是答案。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">但是我们怎么定义邻居,又怎么找到这些邻居呢?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">在回答这个问题之前,我们先来看一个例子。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">假设现在有这么一个问题,我需要知道全城的用户有哪些用户有车,但是我们只知道用户的家庭地址,那么该怎么办呢?</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">很显然,我需要在全城做一个调查,也就是对全城市民做一个抽样,抽取一部分做个是否有车的调研。对于剩下的用户呢,我去寻找离他最近的几个邻居,看看他的这几个邻居是否有车。如果离他近的邻居大多数都有车,那么,我可以认为,该用户可能住在富人区,他有车的概率比较大。如果他的邻居都没有车,可能他住在穷人区,他很有可能也没有车。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">你可能会说中国不像美国可以划分成穷人区和富人区,往往在一个区域内穷富是杂居的,用这种方法得出的结果准确率肯定不高。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">的确存在这个问题,所以我们可以在此基础上做一点优化,很简单,我们只知道用户住在哪里是不够的,我们可能还需要了解用户的收入情况。在寻找他最近的邻居的过程当中,除了要考虑距离上的远近之外,还需要保证收入尽可能接近。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">如果能知道和他距离和收入都接近的邻居是否有车,那么大概率可以判断这个用户是否有车。重复这个算法,我就可以通过少量的样本,算出全体样本是否有车的情况。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">说到这里,想必你应该能明白,在KNN算法的范畴当中,<strong style="font-weight: bold; color: rgb(71, 193, 168);">“邻居”指的不是地理上的邻近关系,而指的是样本空间的接近</strong>。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">我们都知道,对于向量A(a1,a2,a3...an),B(b1,b2,b3...bn)</p> <figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px;"><img class="equation" src="https://juejin.im/equation?tex=dis = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2 + \cdots + (a_n - b_n)^2} " alt style="display: block; margin: 0 auto; width: auto; max-width: 100%;"></figure> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">在机器学习当中,我们通常会把一条样本数据当做向量空间中的一条向量。比如在刚刚的问题当中,用户A,他的样本可能是(120.3213, 30.1312, 10.5),指的是居住地点的经纬度和年收入。也可能是(城东, 泾河花园, 10.5),或者是(城东, 沿河西路, 泾河花园, 10.5)等等。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">同样的一条样本,表示成向量就有多种形式。对于不同的问题而言,不同的表示方法拥有不同的效果。在当前问题当中,我们需要计算向量和向量之间的距离,显然,使用第一种经纬度的表示方式更好。</p> <h2 data-tool="mdnice编辑器" style="margin-top: 40px; font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 30px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">算法原理</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">通过上面这个例子,其实我们已经把算法的整个运行过程讲解清楚了。所谓的k-邻近算法,其实就是使用距离样本最近的k个样本的结果来代表当前样本的结果。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">整个算法的流程如下:</p> <ol data-tool="mdnice编辑器" style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">采集一批有标注结果的样本,设为s</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">遍历每一个未知结果的样本<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=x_i" alt></span></section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">遍历s,计算s中的每一个样本和<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=x_i" alt></span>的距离</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">根据距离进行排序,选出距离最小的k个样本</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">选出这k个样本中出现频次最多的类别作为<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=x_i" alt></span>的结果</section></li></ol> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">算法流程不难理解,但是其中有几个注意点:</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">首先,每一个样本其实指的是样本空间里的一个向量。既然是向量,并且要计算样本之间的距离,那么<strong style="font-weight: bold; color: rgb(71, 193, 168);">向量的每一个维度都必须是实数</strong>。一般情况下,字符串是无法作为特征计算距离的。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">其次,向量距离的计算方法。常规来说,向量之间的距离可以理解成空间中两个点的距离,关于这个距离常规上有几种计算的公式。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">第一种叫做欧式公式,就是我们刚才列的也是最常见的欧几里得距离公式:</p> <figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px;"><img class="equation" src="https://juejin.im/equation?tex=d = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2 + \cdots + (a_n - b_n)^2} " alt style="display: block; margin: 0 auto; width: auto; max-width: 100%;"></figure> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">第二种叫做曼哈顿距离,曼哈顿是纽约的CBD,既然是街区,从一个路口到另一个路口的距离显然是不能从街区中跨越的。所以两个路口的距离,其实是两点的直角连线距离。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">假设一个点坐标是(3, 4) ,另一个点的坐标是(5, 1),这两点的距离d = | 3 - 5| + | 4 - 1| = 5</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">公式为:</p> <figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px;"><img class="equation" src="https://juejin.im/equation?tex=\displaystyle d = \sum_{i=1}^n|x_{1i}-x_{2i}| " alt style="display: block; margin: 0 auto; width: auto; max-width: 100%;"></figure> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">在距离计算的方法当中,欧氏距离和曼哈顿距离最常用,除了这两种之外还有切比雪夫距离和闵可夫斯基距离等,一般不太常用,我们不多做赘述,感兴趣的可以自行谷歌。</p> <h2 data-tool="mdnice编辑器" style="margin-top: 40px; font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 30px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">代码实现</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">下面就到了我们紧张刺激的代码实现环节,KNN的原理不算难,只要能理解,稍微思考一下我想大部分同学应该都能写出来。所以之前阿里的校招经常用KNN作为<strong style="font-weight: bold; color: rgb(71, 193, 168);">笔试题</strong>,考察一下同学的代码能力以及对基础模型的理解情况。所以实现是一方面,将代码写漂亮,实现完美又是另一方面。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">仔细想一下当我们的数据有了之后,KNN主体就只有一个函数,我们先来看一下不使用任何库函数进行实现的代码:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span> <span class="hljs-title" style="color: #61aeee; line-height: 26px;">classify</span><span class="hljs-params" style="line-height: 26px;">(vector, dataSet, labels, k)</span>:</span><br> dis = []<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span> range(len(dataSet)):<br> data = dataSet[i]<br> d = calculate_distance(vector, data)<br> dis.append(d)<br> dis_index = sorted(enumerate(dis), key=<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">lambda</span> x: x[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>])<br> label_map = {}<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span> range(k):<br> label = labels[dis_index[i][<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>]]<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">if</span> label <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span> label_map:<br> label_map[label] += <span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">else</span>:<br> label_map[label] = <span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br> maxi = <span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span><br> label = <span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">None</span><br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span> label_map:<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">if</span> label_map[i] &gt; maxi:<br> maxi = label_map[i]<br> label = i<br><br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span> label<br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">其中calculate_distance是计算两个向量距离的函数,实现也很简单,就是套用一下上面刚才提到的距离公式,基本没有难度:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span> <span class="hljs-title" style="color: #61aeee; line-height: 26px;">calculate_distance</span><span class="hljs-params" style="line-height: 26px;">(vectorA, vectorB)</span>:</span><br> d = <span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span><br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span> range(len(vectorA)):<br> d += (vectorA[i] - vectorB[i]) * (vectorA[i] - vectorB[i])<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span> math.sqrt(d)<br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">但是显然这是没有必要的,我们多做了很多无用功。灵活地使用库函数,可以将代码缩减到不可思议的地步:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">import</span> random<br><br><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">import</span> numpy <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">as</span> np<br><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">from</span> collections <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">import</span> Counter<br><br><br><span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span> <span class="hljs-title" style="color: #61aeee; line-height: 26px;">classify</span><span class="hljs-params" style="line-height: 26px;">(x, dataset, labels, K)</span>:</span><br> x, dataset = np.array(x), np.array(dataset)<br> <span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;"># 通过numpy计算距离,numpy有广播机制</span><br> <span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;"># 会自动将x和dataset当中的每一行计算距离</span><br> dis = np.sqrt(np.sum((x - dataset) ** <span class="hljs-number" style="color: #d19a66; line-height: 26px;">2</span>, axis=<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>))<br> <span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;"># 按照距离排序,返回结果对应的下标</span><br> topKIdices = np.argsort(dis)[:K]<br> labels = np.array(labels)<br> <span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;"># 使用Counter进行计数,返回数量最多的</span><br> counter = Counter(labels[topKIdices])<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span> counter.most_common(<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>)[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>][<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>]<br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">不知道大家看到有没有觉得有点不可思议,我们一个for循环都没有用到就实现了KNN算法,只有<strong style="font-weight: bold; color: rgb(71, 193, 168);">短短5行</strong>。其中Numpy是我们做机器学习非常常用的包,由于Numpy有非常多的API可以非常方便地进行计算,所以我们会在之后单独开一个Numpy专题。关于Counter等库函数的用法,在之前介绍collections的文章当中介绍过,如果有遗忘的同学可以在公众号回复collections获取文章。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">最后,我们创造一个简单的sample来验证一下:</p> <pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px;"><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span> <span class="hljs-title" style="color: #61aeee; line-height: 26px;">create_data_set</span><span class="hljs-params" style="line-height: 26px;">()</span>:</span><br> dataset = np.array([[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0.5</span>, <span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>], [<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>, <span class="hljs-number" style="color: #d19a66; line-height: 26px;">0.5</span>], [<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1.5</span>, <span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>], [<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>, <span class="hljs-number" style="color: #d19a66; line-height: 26px;">1.5</span>]])<br> labels = [<span class="hljs-string" style="color: #98c379; line-height: 26px;">'A'</span>, <span class="hljs-string" style="color: #98c379; line-height: 26px;">'A'</span>, <span class="hljs-string" style="color: #98c379; line-height: 26px;">'B'</span>, <span class="hljs-string" style="color: #98c379; line-height: 26px;">'B'</span>]<br> <span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span> dataset, labels<br></code></pre> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">运行程序得到的结果是A。</p> <h2 data-tool="mdnice编辑器" style="margin-top: 40px; font-weight: bold; font-size: 24px; border-bottom: 2px solid rgb(89,89,89); margin-bottom: 30px; color: rgb(89,89,89);"><span style="font-size: 22px; display: inline-block; border-bottom: 2px solid rgb(89,89,89);">优化</span></h2> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">到这里我们还没有结束,还有一个问题值得讨论。在我们刚才叙述算法流程的过程当中,有一个关键点被我们忽略了。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">我们的样本由特征构成,我们对特征向量计算距离。问题是这些<strong style="font-weight: bold; color: rgb(71, 193, 168);">特征并不是一个维度的</strong>,还用上面的例子。我们为了判断一个用户是否有车,用到了三个特征,分别是他家的经度、纬度和年收入。注意,经纬度和年收入并不是一个量纲下的变量,从数学上我们当然可以对它们当做是一个量纲来计算,但是这样显然是不准确的。最主要的问题是,不同量纲的特征波动的幅度可能完全不同。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">这一点应该不难理解,对于经纬度而言,取值范围假设是[0, 360],但是年收入的浮动范围可能是上千万。显然如果我们直接来计算距离的话,那么主要的权重就落在了年收入上,这个<strong style="font-weight: bold; color: rgb(71, 193, 168);">模型就发生了倾斜</strong>,这显然是我们不想看到的,因为会影响模型最终的效果。为了解决这个问题,我们需要将这些量纲归一化,消除量纲带来的影响。这也是KNN关键的优化。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">归一化的方式很多,比较常用的有两种。<strong style="font-weight: bold; color: rgb(71, 193, 168);">一种是Standardization</strong>,又称为Z-score normalization,归一化之后的数据服从正态分布,它的公式如下:</p> <figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px;"><img class="equation" src="https://juejin.im/equation?tex=z_i = \frac{x_i-\mu}{\delta} " alt style="display: block; margin: 0 auto; width: auto; max-width: 100%;"></figure> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">这里的<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=\mu" alt></span>和<span><img style="margin: 0 auto; width: auto; max-width: 100%; display: inline;" class="equation" src="https://juejin.im/equation?tex=\delta" alt></span>分别对应样本的均值和方差,归一化之后的结果在[-1, 1]之间。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">另一种归一化的方法叫做<strong style="font-weight: bold; color: rgb(71, 193, 168);">Min-max Scaling</strong>,它是根据样本的最大最小值进行的缩放。公式如下:</p> <figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px;"><img class="equation" src="https://juejin.im/equation?tex=z_i=\frac{x_i - min(x_i)}{max(x_i)-min(x_i)} " alt style="display: block; margin: 0 auto; width: auto; max-width: 100%;"></figure> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">这样缩放之后的结果在[0, 1]之间,最大值时取1,最小值时取0,这也是最常用的归一化的方法之一。通过归一化之后,我们可以将不同量纲下的变量缩放到同一个取值范围当中,从而将特征拉到平等的维度,这样模型学习的效果更佳均匀,不容易被其中某一个或者某几个特征带偏。</p> <p data-tool="mdnice编辑器" style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: rgb(89,89,89);">今天的文章就是这些,KNN是非常基础的机器学习算法,相信对大家而言应该并不难。如果觉得有所收获,请顺手点个<strong style="font-weight: bold; color: rgb(71, 193, 168);">关注或者转发</strong>吧,你们的举手之劳对我来说很重要。</p>

原文出处:https://www.cnblogs.com/techflow/p/12460255.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部