架构师课程第十三周总结

关注
发布于: 2020 年 09 月 09 日
做软件不能满足只会使用，应该深入内部了解背后的机制，必要的时候，自己也能实现出一个。
否则，吃*也吃不上热乎的。 
        ——李智慧
﻿
连接大数据与机器学习的纽带是算法。
﻿
本周的议题通过各种算法的讲解串联到了一起。
﻿
首当其冲的是 PageRank 算法，其次是 KNN 分类算法，提取文本特征值的 TF-IDF 算法，贝叶斯分类算法、K-means 聚类算法、推进引擎算法。本文介绍一些关键的算法。
﻿
机器学习系统的架构如下图：
﻿
﻿
在人类的学习中，有的人可能有高人指点，有的人则是无师自通。在机器学习中也有类似的分类。根据训练数据是否具有标签信息，可以将机器学习的任务分成以下三类。
监督学习：基于已知类别的训练数据进行学习；
无监督学习：基于未知类别的训练数据进行学习；
半监督学习：同时使用已知类别和未知类别的训练数据进行学习。
受学习方式的影响，效果较好的学习算法执行的都是监督学习的任务。即使号称自学成才、完全脱离了对棋谱依赖的 AlphaGo Zero，其训练过程也要受围棋胜负规则的限制，因而也脱不开监督学习的范畴。
﻿
KNNKNN 的英文叫 K-Nearest Neighbor，应该算是数据挖掘算法中最简单的一种。
﻿
﻿
可以把打斗次数看成 X 轴，接吻次数看成 Y 轴，然后在二维的坐标轴上，对这几部电影进行标记，如下图所示。对于未知的电影 A，坐标为 (x,y)，我们需要看下离电影 A 最近的都有哪些电影，这些电影中的大多数属于哪个分类，那么电影 A 就属于哪个分类。实际操作中，我们还需要确定一个 K 值，也就是我们要观察离电影 A 最近的电影有多少个。
﻿
﻿
KNN 的工作原理
“近朱者赤，近墨者黑”可以说是 KNN 的工作原理。整个计算过程分为三步：
计算待分类物体与其他物体之间的距离；
统计距离最近的 K 个邻居；
对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。
你能看出整个 KNN 的分类过程，K 值的选择还是很重要的。那么问题来了，K 值选择多少是适合的呢？
﻿
如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。这样产生的一个问题就是，如果邻居点是个噪声点，那么未分类物体的分类也会产生误差，这样 KNN 分类就会产生过拟合。
﻿
如果 K 值比较大，相当于距离过远的点也会对未知物体的分类产生影响，虽然这种情况的好处是鲁棒性强，但是不足也很明显，会产生欠拟合情况，也就是没有把未分类物体真正分类出来。
﻿
所以 K 值应该是个实践出来的结果，并不是我们事先而定的。在工程上，我们一般采用交叉验证的方式选取 K 值。
﻿
交叉验证的思路就是，把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在 KNN 算法中，我们一般会把 K 值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为 K 值。
﻿
在 KNN 算法中，还有一个重要的计算就是关于距离的度量。两个样本点之间的距离代表了这两个样本之间的相似度。距离越大，差异性越大；距离越小，相似度越大。关于距离的计算方式有下面五种方式：欧氏距离；曼哈顿距离；闵可夫斯基距离；切比雪夫距离；余弦距离。
﻿
其实从上文你也能看出来，KNN 的计算过程是大量计算样本点之间的距离。为了减少计算距离次数，提升 KNN 的搜索效率，人们提出了 KD 树（K-Dimensional 的缩写）。KD 树是对数据点在 K 维空间中划分的一种数据结构。在 KD 树的构造中，每个节点都是 k 维数值点的二叉树。既然是二叉树，就可以采用二叉树的增删改查操作，这样就大大提升了搜索效率。
在这里，我们不需要对 KD 树的数学原理了解太多，你只需要知道它是一个二叉树的数据结构，方便存储 K 维空间的数据就可以了。而且在 sklearn 中，我们直接可以调用 KD 树，很方便。
﻿
 TF-IDF在信息检索（Information Retrieval）、文本挖掘（Text Mining）以及自然语言处理（Natural Language Processing）领域，TF-IDF 算法都可以说是鼎鼎有名。虽然在这些领域中，目前也出现了不少以深度学习为基础的新的文本表达和算分（Weighting）方法，但是 TF-IDF 作为一个最基础的方法，依然在很多应用中发挥着不可替代的作用。
﻿
了解和掌握 TF-IDF 算法对初学者大有裨益，能够帮助初学者更快地理解其它更加深入、复杂的文本挖掘算法和模型。
﻿
要理解 TF-IDF 算法，第一个步骤是理解 TF-IDF 的应用背景。TF-IDF 来源于一个最经典、也是最古老的信息检索模型，即“向量空间模型”（Vector Space Model）。
简单来说，向量空间模型就是希望把查询关键字和文档都表达成向量，然后利用向量之间的运算来进一步表达向量间的关系。比如，一个比较常用的运算就是计算查询关键字所对应的向量和文档所对应的向量之间的“相关度”。
因为有了向量的表达，相关度往往可以用向量在某种意义上的“相似度”来进行近似，比如余弦相似性（Cosine Similarity）或者是点积（Dot Product）。这样，相关度就可以用一个值来进行表达。不管是余弦相似度还是点积都能够从线性代数或者几何的角度来解释计算的合理性。
﻿
在最基本的向量空间模型的表达中，查询关键字或是文档的向量都有 V 维度。这里的 V 是整个词汇表（Vocabulary）的总长度。比如，我们如果有 1 万个常用的英文单词，那么这个 V 的取值就是 1 万，而查询关键字和每个文档的向量都是一个 1 万维的向量。 对于这个向量中的每一个维度，都表示英文中的一个单词，没有重复。
可以看到，在这样的情况下，如果当前的词出现在这个向量所对应的文档或者关键字里，就用 1 来表达；如果这个词没出现，就用 0 来表达。这就是给每个维度赋值（Weighting）的最简单的方法。
TF-IDF 就是在向量空间模型的假设下的一种更加复杂的赋值方式。TF-IDF 最基础的模式，顾名思义，就是 TF 和 IDF 的乘积。
TF 其实是“单词频率”（Term Frequency）的简称。意思就是说，我们计算一个查询关键字中某一个单词在目标文档中出现的次数。举例说来，如果我们要查询“Car Insurance”，那么对于每一个文档，我们都计算“Car”这个单词在其中出现了多少次，“Insurance”这个单词在其中出现了多少次。这个就是 TF 的计算方法。
TF 背后的隐含的假设是，查询关键字中的单词应该相对于其他单词更加重要，而文档的重要程度，也就是相关度，与单词在文档中出现的次数成正比。比如，“Car”这个单词在文档 A 里出现了 5 次，而在文档 B 里出现了 20 次，那么 TF 计算就认为文档 B 可能更相关。
然而，信息检索工作者很快就发现，仅有 TF 不能比较完整地描述文档的相关度。因为语言的因素，有一些单词可能会比较自然地在很多文档中反复出现，比如英语中的“The”、“An”、“But”等等。这些词大多起到了链接语句的作用，是保持语言连贯不可或缺的部分。然而，如果我们要搜索“How to Build A Car”这个关键词，其中的“How”、“To”以及“A”都极可能在绝大多数的文档中出现，这个时候 TF 就无法帮助我们区分文档的相关度了。
IDF，也就是“逆文档频率”（Inverse Document Frequency），就在这样的情况下应运而生。这里面的思路其实很简单，那就是我们需要去“惩罚”（Penalize）那些出现在太多文档中的单词。也就是说，真正携带“相关”信息的单词仅仅出现在相对比较少，有时候可能是极少数的文档里。这个信息，很容易用“文档频率”来计算，也就是，有多少文档涵盖了这个单词。
很明显，如果有太多文档都涵盖了某个单词，这个单词也就越不重要，或者说是这个单词就越没有信息量。因此，我们需要对 TF 的值进行修正，而 IDF 的想法是用 DF 的倒数来进行修正。倒数的应用正好表达了这样的思想，DF 值越大越不重要。
在了解了 TF 和 IDF 的基本计算方法后，我们就可以用这两个概念的乘积来表达某个查询单词在一个目标文档中的重要性了。值得一提的是，虽然我们在介绍 TF-IDF 这个概念的时候，并没有提及怎么把查询关键字和文档分别表达成向量，其实 TF-IDF 算法隐含了这个步骤。
具体来说，对于查询关键字，向量的长度是 V，也就是我们刚才说过的词汇表的大小。然后其中关键字的单词出现过的维度是 1，其他维度是 0。对于目标文档而言，关键词出现过的维度是 TF-IDF 的数值，而其他维度是 0。在这样的表达下，如果我们对两个文档进行“点积”操作，则得到的相关度打分（Scoring）就是 TF-IDF 作为相关度的打分结果。
参考https://time.geekbang.org/column/article/822
https://time.geekbang.org/column/article/80983
﻿