K最近邻算法

  • 橙子还是柚子
  • 创建推荐系统
  • 特征抽取
  • 回归
  • 挑选合适的特征
  • 机器学习简介

橙子还是柚子

假设你看到一种水果，个头很大、颜色偏红，它是橙子还是柚子？判断方法是看它最像哪种水果。如果它最像的 3 个邻居（K=3）中有 2 个是柚子，那它很可能是柚子。

这就是 K 最近邻（KNN）算法——对东西进行分类时，先看它最近的 K 个邻居。

创建推荐系统

假设你是 Netflix，要为用户创建电影推荐系统。可以将所有用户都放入一个图表中，位置取决于其喜好，喜好相似的用户距离较近。要向 Priyanka 推荐电影，找出与她最接近的 5 位用户，他们喜欢的电影 Priyanka 很可能也喜欢。

特征抽取

如何确定两位用户的相似程度？需要将每位用户转换为一组数字（坐标），然后计算距离。

在前面的水果示例中，比较的特征是个头和颜色（2 个数字）。对 Netflix 用户，可以让他们指出对各类电影（喜剧、动作、爱情、恐怖、科幻）的喜好程度，每位用户就用 5 个数字表示。

计算距离：使用毕达哥拉斯公式（欧几里得距离），即便涉及很多个数字（多维空间），公式依然适用：

distance = sqrt((x1-x2)² + (y1-y2)² + (z1-z2)² + ...)

这个距离指出了两组数字之间的相似程度——距离越小，越相似。

回归

KNN 不仅可以做分类（编组），还可以做回归（预测结果如一个数字）。

假设要预测 Priyanka 会给电影打多少分，找出与她最近的 5 个人，取他们评分的平均值。如果 5 个人的评分分别是 5、4、4、5、3，平均值为 4.2，这就是预测的评分。

分类与回归：

  • 分类就是编组（这个水果是橙子还是柚子）
  • 回归就是预测结果（预测一个数字）

面包店示例：预测每天该烤多少面包，特征包括天气指数（1-5）、是否周末（0/1）、是否有活动（0/1）。找出与今天特征最接近的 4 天（K=4），取这些天售出面包数的平均值作为预测。

挑选合适的特征

使用 KNN 时，挑选合适的特征至关重要。所谓合适的特征：

  • 与要预测的内容紧密相关的特征
  • 不偏不倚的特征（例如，如果只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）

余弦相似度：在实际工作中，经常使用余弦相似度代替距离公式。如果一位用户打分更保守（总是给 4 星而不是 5 星），距离公式可能把他们判为不相似，但余弦相似度比较两个矢量的角度，更适合处理这种情况。

机器学习简介

KNN 是进入机器学习领域的领路人。机器学习旨在让计算机更聪明。

OCR（光学字符识别）：

  1. 浏览大量的数字图像，提取特征（线段、点、曲线等），这被称为训练
  2. 遇到新图像时，提取其特征，用 KNN 找出最近的邻居

创建垃圾邮件过滤器：使用朴素贝叶斯分类器（Naive Bayes classifier），先训练分类器，让它学习垃圾邮件中各单词出现的概率，然后计算新邮件为垃圾邮件的概率。

预测股票市场：使用机器学习预测股市涨跌很难，因为涉及的变数太多，挑选合适的特征几乎是不可能完成的任务。未来很难预测。

小结

  • KNN 用于分类和回归，需要考虑最近的邻居
  • 分类就是编组，回归就是预测结果（如数字）
  • 特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字
  • 能否挑选合适的特征事关 KNN 算法的成败
  • 机器学习算法大多包含训练的步骤：先训练计算机，再让它完成任务
  • 朴素贝叶斯分类器也是一种简单而极其有效的算法，应用领域与 KNN 相似

接下来可以探索的方向

本书最后一章还简要介绍了以下主题：

  • 树：二叉查找树，对于其中的每个节点，左子节点的值比它小，右子节点的值比它大。查找、插入、删除的时间复杂度均为 O(log n)
  • 反向索引：搜索引擎用来建立单词到包含该单词的文档的映射
  • 傅里叶变换：将信号从时域转换到频域，用于音频处理、图像压缩等
  • 并行算法：利用多核处理器并行计算以加速
  • MapReduce：分布式算法，映射函数对数据进行处理，归并函数合并结果
  • 布隆过滤器和 HyperLogLog：概率型数据结构，用很少的内存判断元素是否在集合中
  • SHA 算法：散列函数，用于比较文件、检查密码
  • 局部敏感的散列算法：与 SHA 不同，相似的输入会得到相似的散列值
  • Diffie-Hellman 密钥交换：双方无需会面即可商定密钥的加密算法
  • 线性规划：在给定约束条件下最大化或最小化某个目标，是最宽泛的图算法