<div id="article_content" class="article_content clearfix">
<link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-1a85854398.css">
<div id="content_views" class="htmledit_views">
<h1><a name="t0"></a>k近邻算法</h1>
<p>k近邻算法通过测量不同特征值之间的距离来分类，具有如下优缺点</p>
<p>优点：精度高，对异常值不敏感，无数据输入假定</p>
<p>缺点：计算复杂度高，空间复杂度高</p>
<p>K 近邻算法的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。</p>
<p>输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前 k个最相似的数据，这就是 K 近邻算法中 k的出处，通常 k 是不大于 20 的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。</p>
<h3><a name="t1"></a>k近邻算法的一般流程</h3>
<p>1. 收集数据：可以使用任何方法。 <br> 2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式。 <br> 3. 分析数据：可以使用任何方法。 <br> 4. 训练算法：此步骤不适用于 K 近邻算法。 <br> 5. 测试算法：计算错误率。<br> 6. 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K 近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。</p>
<p>首先，导入数据</p>
<pre class="has" name="code"><code class="language-python hljs"><ol class="hljs-ln" style="width:100%"><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="1"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-keyword">import</span> numpy <span class="hljs-keyword">as</span> np</div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="2"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"> </div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="3"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-keyword">def</span> <span class="hljs-title function_">create_dataset</span>():</div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="4"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"> group=np.array([[<span class="hljs-number">1.0</span>, <span class="hljs-number">1.1</span>], [<span class="hljs-number">1.0</span>, <span class="hljs-number">1.0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">0.1</span>]])</div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="5"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"> labels=[<span class="hljs-string">'A'</span>, <span class="hljs-string">'A'</span>, <span class="hljs-string">'B'</span>, <span class="hljs-string">'B'</span>]</div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="6"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"> <span class="hljs-keyword">return</span> group, labels</div></div></li></ol></code><div class="hljs-button {2}" data-title="复制（为作者贡献原力分）" data-report-click="{"spm":"1001.2101.3001.4259"}" onclick="hljs.copyCode(event)"></div></pre>
<p>这里有 4 组数据，每组数据有两个我们已知的属性或者特征值。上面的 `group` 矩阵每行包含一个不同的数据，我们可以把它想象为某个日志文件中不同的测量点或者入口。由于人类大脑的限制，我们通常只能可视化处理三维以下的事务。因此为了简单地实现数据可视化，对于每个数据点我们通常只使用两个特征。</p>
<p>向量 `labels` 包含了每个数据点的标签信息，`labels` 包含的元素个数等于 `group` 矩阵行数。这里我们将数据点 `(1, 1.1)` 定义为类 A，数据点 `(0, 0.1)` 定义为类 B。为了说明方便，例子中的数值是任意选择的，并没有给出轴标签。</p>
<h3><a name="t2"></a>如何测试分类器</h3>
<p>在上文中我们提到使用 K 近邻 算法能够判断出一个电影是动作片还是爱情片，即我们使用 K 近邻 算法能够实现一个分类器。我们需要检验分类器给出的答案是否符合我们的预期。读者可能会问：「分类器何种情况下会出错？」或者「答案是否总是正确的？」</p>
<p>答案是否定的，分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。此外分类器的性能也会受到多种因素的影响，如分类器设置和数据集等。不同的算法在不同数据集上的表现可能完全不同，这也是本部分的 6 章都在讨论分类算法的原因所在。</p>
<p>为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率：分类器给出错误结果的次数除以测试执行的总数。</p>
<p>错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为 0，最差分类器的错误率是 1.0，在这种情况下，分类器根本就无法找到一个正确答案。读者可以在后面章节看到实际的数据例子。</p>
<h2><a name="t3"></a>开始正文</h2>
<pre class="has" name="code"><code class="language-python hljs"><ol class="hljs-ln" style="width:100%"><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="1"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-comment"># 在 Jupyter Notebook 单元格中执行，下载并解压数据。</span></div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="2"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line">!wget <span class="hljs-string">"http://labfile.oss.aliyuncs.com/courses/777/digits.zip"</span></div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="3"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-comment"># 解压缩</span></div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="4"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line">!unzip digits.<span class="hljs-built_in">zip</span></div></div></li></ol></code><div class="hljs-button {2}" data-title="复制（为作者贡献原力分）" data-report-click="{"spm":"1001.2101.3001.4259"}" onclick="hljs.copyCode(event)"></div></pre>
<h3><a name="t4"></a>步骤一：将图像转化为测试向量</h3>
<p>为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个 `32x32` 的二进制图像矩阵转换为 `1x1024` 的向量，这样前两节使用的分类器就可以处理数字图像信息了。</p>
<p>我们首先编写一段函数 `img2vector`，将图像转换为向量：该函数创建 `1x1024` 的 NumPy 数组，然后打开给定的文件，循环读出文件的前 `32` 行，并将每行的头 `32` 个字符值存储在 NumPy 数组中，最后返回
