week10 K-最近邻算法和最小错误概率的分类

近邻算法

有这样一个问题：有一堆红点、一堆绿点，我们怎么把它们分开？

绿肥红瘦

我们可以这样理解这个问题：有一堆已知的点，它们被分为两类：红与绿。它们在坐标纸上的分布如图，给我们一个新的点，我们能否通过这个点的坐标来判断它是红的还是绿的呢？这就是KNN研究的问题。

KNN（K-nearest neighbor）又称K-最近邻，它是通过新的点与已知点之间的坐标关系来进行分类。我们计算新的点与这堆已知的点的欧式距离（就是咱们理解的距离），将其排序得到距离的列表或字典。然后我们看这个列表或字典的前k个距离值，在这些距离里面，如果是红的（属于和红色点的距离）更多，那我们就认为这个新的点是红色，反之就认为是绿色。

听到这，我知道你要问了，如果两种点的数目一样呢？那么也很简单，就按照正常的思维，我们可以认为它既喜欢绿肥又喜欢红瘦（真是个泛滥的男人），从而给它随机划分，或者它既不喜欢绿肥又不喜欢红瘦（这人可能是个Gay 离他远点），从而不对它进行分类，把这个点丢掉，当然采取这种做法的话做大样本的数据可视化的时候也许会出现大面积的“白色”（不过这都不是问题啦~）

好了，进入正题

KNN题目

乍一看，这不就是个传统的KNN问题嘛，几句代码就解决啦

但是要注意的一点是这道题包含了数据的可视化，也就意味着我们需要自己生成样本点，自己对训练集验证集测试集进行划分 还包含了二维数据的一些处理 还是有一些细节值得一做的

思路也很简单：调用numpy库针对二维数据 调用matplotlib库来做可视化 自己写分类算法

对结果的处理：我想看到分界线 但是我不会画线 怎么办呢？简单粗暴 绘制大量的点 盖满整张坐标纸 这样线就出来啦

k=1 k=10 是不是就整齐很多 k=50 哇塞好齐 k=200 逐渐包围 k=300 吞掉！

基于后验概率的文档分类

问题来了

谁写的？

这两个人写作风格相近，我们要通过已有的文本来判断未知文本的作者。我们有很多txt，这些有一部分知道事hamilton写的，还有一部分知道是madison写的，还剩下几篇不知道作者是谁。我们需要判断这些文章的作者。

思路也很简单：对已知作者的txt进行特征提取，得到反映hamilton和madison两个人写作习惯和写作风格的特征向量，从而对新文本进行判断。简单来说，每篇txt里有很多词汇，每个人写了很多篇txt，我们要选取其中的几个词汇来代表这两位作家的写作差异，代入后验概率比公式，若大于一则认为是hamilton写的，反之则认为是madison写的。

里面有两个细节：一是文档需不需要合并（要反映两个人的差异嘛 可以合并 但是合并以后会出现另一个问题 那就是用不了tf-idf算法了） 二是验证集验证特征向量的正确率的时候，这个验证集能不能在训练集里 还是很考验细节的 当然这道题太费脑子啦不想做啊哈哈

判别 类对象 State government national State legislative national

不同关键词带来的正确率和判别结果的差异