K Nearest Neighbor 算法
openkk 12年前
<p> K Nearest Neighbor 算法又叫 KNN 算法，这个算法是机器学习里面一个比较经典的算法， 总体来说 KNN 算法是相对比较容易理解的算法。其中的K表示最接近自己的K个数据样本。KNN 算法和<a title="K-Means 算法" href="/misc/goto?guid=4958522354654426340" target="_blank">K-Means 算法</a>不同的是，K-Means 算法用来聚类，用来判断哪些东西是一个比较相近的类型，而 KNN 算法是用来做归类的，也就是说，有一个样本空间里的样本分成很几个类型，然后，给定一个待分类的数据，通过计算接近自己最近的K个样本来判断这个待分类数据属于哪个分类。<strong>你可以简单的理解为由那离自己最近的K个点来投票决定待分类数据归为哪一类</strong>。</p> <p> Wikipedia 上的 <a href="/misc/goto?guid=4958522354761861246" target="_blank">KNN 词条</a>中有一个比较经典的图如下：</p> <p style="text-align:center;"><img title="KNN Classification" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/cb4c67e16369e32a785ad8481150352e.jpg" width="220" height="199" /></p> <p> 从上图中我们可以看到，图中的有两个类型的样本数据，一类是蓝色的正方形，另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。</p> <ul> <li>如果K=3，那么离绿色点最近的有 2 个红色三角形和 1 个蓝色的正方形，这 3 个点投票，于是绿色的这个待分类点属于红色的三角形。</li> </ul> <ul> <li>如果K=5，那么离绿色点最近的有 2 个红色三角形和 3 个蓝色的正方形，这 5 个点投票，于是绿色的这个待分类点属于蓝色的正方形。</li> </ul> <p> 我们可以看到，机器学习的本质——<strong>是基于一种数据统计的方法</strong>！那么，这个算法有什么用呢？我们来看几个示例。</p> <p> <strong>产品质量判断</strong></p> <p> 假设我们需要判断毛巾的品质好坏，毛巾的品质好坏可以抽像出两个向量，一个是“酸腐蚀的时间”，一个是“能承受的压强”。如果我们的样本空间如下：（所谓样本空间，又叫 Training Data，也就是用于机器学习的数据）</p> <table border="1" cellspacing="3" cellpadding="3"> <tbody> <tr> <td valign="top" width="33%"> <p align="center"><strong>向量 X1</strong></p> <p align="center"><strong>耐酸时间（秒）</strong></p> </td> <td valign="top" width="33%"> <p align="center"><strong>向量 X2</strong></p> <p align="center"><strong>圧强(公斤/平方米)</strong></p> </td> <td valign="top" width="33%"> <p align="center"><strong>品质Y</strong></p> </td> </tr> <tr> <td valign="top" width="33%"> <p align="center">7</p> </td> <td valign="top" width="33%"> <p align="center">7</p> </td> <td valign="top" width="33%"> <p align="center">坏</p> </td> </tr> <tr> <td valign="top" width="33%"> <p align="center">7</p> </td> <td valign="top" width="33%"> <p align="center">4</p> </td> <td valign="top" width="33%"> <p align="center">坏</p> </td> </tr> <tr> <td valign="top" width="33%"> <p align="center">3</p> </td> <td valign="top" width="33%"> <p align="center">4</p> </td> <td valign="top" width="33%"> <p align="center">好</p> </td> </tr> <tr> <td valign="top" width="33%"> <p align="center">1</p> </td> <td valign="top" width="33%"> <p align="center">4</p> </td> <td valign="top" width="33%"> <p align="center">好</p> </td> </tr> </tbody> </table> <p> 那么，如果 X1 = 3 和 X2 = 7， 这个毛巾的品质是什么呢？这里就可以用到 KNN 算法来判断了。</p> <p> 假设K=3，K应该是一个奇数，这样可以保证不会有平票，下面是我们计算（3，7）到所有点的距离。（关于那些距离公式，可以参看<a title="K-Means 算法" href="/misc/goto?guid=4958522354872039737" target="_blank">K-Means 算法中的距离公式</a>）</p> <table border="1" cellspacing="3" cellpadding="3"> <tbody> <tr> <td valign="top" width="25%"> <p align="center"><strong>向量 X1</strong></p> <p align="center"><strong>耐酸时间（秒）</strong></p> </td> <td valign="top" width="25%"> <p align="center"><strong>向量 X2</strong></p> <p align="center"><strong>圧强(公斤/平方米)</strong></p> </td> <td valign="top" width="25%"> <p align="center"><strong>计算到 (3, 7)的距离</strong></p> </td> <td valign="top" width="25%"> <p align="center"><strong>向量Y</strong></p> </td> </tr> <tr> <td valign="top" width="25%"> <p align="center">7</p> </td> <td valign="top" width="25%"> <p align="center">7</p> </td> <td valign="top" width="25%"> <p align="center"><strong><img alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/7acc46c857051570a7a87bdf0b919921.gif" width="138" height="17" /></strong></p> </td> <td style="text-align:center;" valign="top" width="25%"> 坏</td> </tr> <tr> <td valign="top" width="25%"> <p align="center">7</p> </td> <td valign="top" width="25%"> <p align="center">4</p> </td> <td valign="top" width="25%"> <p align="center"><strong><img alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/3c7b9c00e21ee86d105d5a1b5fb8c2ff.gif" width="139" height="17" /></strong></p> </td> <td valign="top" width="25%"> N/A</td> </tr> <tr> <td valign="top" width="25%"> <p align="center">3</p> </td> <td valign="top" width="25%"> <p align="center">4</p> </td> <td valign="top" width="25%"> <p align="center"><strong><img alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/dad78b38ef650a1c3db55e8475883cfb.gif" width="130" height="17" /></strong></p> </td> <td style="text-align:center;" valign="top" width="25%"> 好</td> </tr> <tr> <td valign="top" width="25%"> <p align="center">1</p> </td> <td valign="top" width="25%"> <p align="center">4</p> </td> <td valign="top" width="25%"> <p align="center"><strong><img alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/7b95e6118f1a39db5df748694c203f85.gif" width="135" height="17" /></strong></p> </td> <td valign="top" width="25%"> 好</td> </tr> </tbody> </table> <p> 所以，最后的投票，好的有 2 票，坏的有 1 票，最终需要测试的（3，7）是合格品。（当然，你还可以使用权重——可以把距离值做为权重，越近的权重越大，这样可能会更准确一些）</p> <p> <strong>注：<a href="/misc/goto?guid=4958522354959350875" target="_blank">示例来自这里</a>，<a href="/misc/goto?guid=4958522355055699584">K-NearestNeighbors Excel 表格下载</a></strong></p> <p> <strong>预测</strong></p> <p> 假设我们有下面一组数据，假设X是流逝的秒数，Y值是随时间变换的一个数值（你可以想像是股票值）</p> <p style="text-align:center;"><img title="KNN_TimeSeries_clip_image004" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/887576f568d3a7b500c9bf42837c3a69.jpg" width="191" height="187" /></p> <p> 那么，当时间是6.5秒的时候，Y值会是多少呢？我们可以用 KNN 算法来预测之。</p> <p> 这里，让我们假设K=2，于是我们可以计算所有X点到6.5的距离，如：X=5.1，距离是 6.5 – 5.1 = 1.4， X = 1.2 那么距离是 6.5 – 1.2 = 5.3 。于是我们得到下面的表：</p> <p style="text-align:center;"><img title="KNN_TimeSeries_clip_image006" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/7f7ac88642e03462848930673b4179c8.jpg" width="312" height="120" /></p> <p> 注意，上图中因为K=2，所以得到X=4 和 X =5.1的点最近，得到的Y的值分别为 27 和8，在这种情况下，我们可以简单的使用平均值来计算：<img title="KNN_TimeSeries_clip_image008" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/d6d821eadd5cc2f1dfacd60f972de892.gif" width="81" height="34" /></p> <p> 于是，最终预测的数值为：17.5</p> <p style="text-align:center;"><img title="KNN_TimeSeries_clip_image010" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/7a46c0967a1a8e93e44a32847cee4510.jpg" width="402" height="305" /></p> <p> <strong>注：<a href="/misc/goto?guid=4958522355142382381" target="_blank">示例来自这里</a>，<a href="/misc/goto?guid=4958522355235316152">KNN_TimeSeries Excel 表格下载</a></strong></p> <p> <strong>插值，平滑曲线</strong></p> <p> KNN 算法还可以用来做平滑曲线用，这个用法比较另类。假如我们的样本数据如下（和上面的一样）：</p> <p style="text-align:center;"><img title="KNN_TimeSeries_clip_image012" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/df785efd1bf1a419fc95489cc21d7af2.jpg" width="335" height="35" /></p> <p> 要平滑这些点，我们需要在其中插入一些值，比如我们用步长为0.1开始插值，从 0 到 6 开始，计算到所有X点的距离（绝对值），下图给出了从 0 到0.5 的数据：</p> <p style="text-align:center;"><img title="KNN_TimeSeries_clip_image014" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/11d571225ff359760e1c12593091ad58.jpg" width="334" height="152" /></p> <p> 下图给出了从2.5到3.5插入的 11 个值，然后计算他们到各个X的距离，假值K=4，那么我们就用最近 4 个X的Y值，然后求平均值，得到下面的表：</p> <p style="text-align:center;"><img title="KNN_TimeSeries_clip_image016" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/cdb08852ec6383b18554b237da55b824.jpg" width="576" height="206" /></p> <p> 于是可以从0.0, 0.1, 0.2, 0.3 …. 1.1, 1.2, 1.3…..3.1, 3.2…..5.8, 5.9, 6.0 一个大表，跟据K的取值不同，得到下面的图：</p> <table style="border-bottom:black 1px dashed;border-left:black 1px dashed;border-top:black 1px dashed;border-right:black 1px dashed;" class="ke-zeroborder"> <tbody> <tr> <td><img title="KNN_TimeSeries_clip_image026" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/720f2469dc083db1d746b57cbe748b2b.jpg" width="262" height="246" /></td> <td><img title="KNN_TimeSeries_clip_image024" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/cde5a0f21e7db1cb0326537c69ea5a08.jpg" width="270" height="249" /></td> </tr> <tr> <td><img title="KNN_TimeSeries_clip_image022" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/fbc05f274a99162caad32170be9339f5.jpg" width="262" height="244" /></td> <td><img title="KNN_TimeSeries_clip_image020" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/325d6675e95f70bdbc64ac4235d74023.jpg" width="251" height="234" /></td> </tr> <tr> <td><img title="KNN_TimeSeries_clip_image018" alt="K Nearest Neighbor 算法" src="https://simg.open-open.com/show/91a7c0dc9e8fa9aca194be4bf54a2832.jpg" width="246" height="228" /></td> </tr> </tbody> </table> <p> <strong>注：<a href="/misc/goto?guid=4958522355142382381" target="_blank">示例来自这里</a>，<a href="/misc/goto?guid=4958522355338926124">KNN_Smoothing Excel 表格下载</a></strong></p> <p> <strong>后记</strong></p> <p> 最后，我想再多说两个事，</p> <p> 1） 一个是机器学习，算法基本上都比较简单，最难的是数学建模，把那些业务中的特性抽象成向量的过程，另一个是选取适合模型的数据样本。这两个事都不是简单的事。算法反而是比较简单的事。</p> <p> 2）对于 KNN 算法中找到离自己最近的K个点，是一个很经典的算法面试题，需要使用到的数据结构是“<a href="/misc/goto?guid=4958522355429332899" target="_blank">最大堆——Max Heap</a>”，一种二叉树。你可以看看相关的算法。</p> <div id="come_from"> 来自: <a id="link_source2" href="/misc/goto?guid=4958522355535028428" target="_blank">coolshell.cn</a> </div>