余弦定理和新闻的分类（TF-IDF+余弦相似度）

我就是我 2024-04-01 10:28 47阅读 0赞

#### 文章目录 ####

*   *  怎么把新闻向量化从而可计算呢？ TF-IDF
     *  怎么计算相似度呢？ 余弦相似度
     *  大数据量时的余弦计算
     *  来源

世界上有些事情常常超乎人们的想象。余弦定理和新闻的分类似乎是两件八杆子打不着的事，但是它们确有紧密的联系。具体地说，新闻的分类很大程度上依靠余弦定理。

2002年夏天，Google推出了自己的“新闻”服务。和传统媒体的做法不同，这些新闻不是记者写的，也不是人工编辑的，而是由计算机整理、分类和聚合各个新闻网站的内容，一切都是自动生成的。这里面的关键技术就是新闻的自动分类。

所谓新闻的分类，或者更广义地讲任何文本的分类，无非是要把相似的新闻放到同一类中。如果让编辑来对新闻分类，他一定 是先把新闻读懂,然后找到它的主题，最后根据主题的不同对新闻进行分类。但是计算机根本读不懂新闻，虽然一些商业人士和爱炫耀自己才学的计算机专家宣称计算机能读懂新闻。计算机本质上只能做快速计算。为了让计算机能够“算”新闻(而不是读新闻)，就要求我们首先要把文字的新闻变成可以计算的一组数字，然后再设计一个算法来算出任意两篇新闻的相似性。

### 怎么把新闻向量化从而可计算呢？ TF-IDF ###

首先让我们来看看怎样找一组数字(或者说一个向量)来描述一篇新闻。新闻是传递信息的，而词是信息的载体，新闻的信息和词的语义是联系在一起的。套用俄罗斯文豪托尔斯泰在《安娜●卡列尼娜》开篇的那句话来讲，“同一类新闻用词都是相似的,不同类的新闻用词各不相同”。

当然，一篇新闻有很多词，有些词表达的语义重要，有些相对次要。那么如何确定哪些重要，哪些次要呢?首先，直觉告诉我们含义丰富的实词一定比“的、地、得”这些助词，或者“之乎者也”这样的虚词重要，这点是肯定的。接下来，需要进一步对每个实词的重要性进行度量。回忆一下我们在“如何确定网页和查询的相关性”一章中介绍的单文本词汇频率/逆文本频率值TF-IDF的概念，在一篇文章中，重要的词TF-IDF值就高。不难想象，和新闻主题有关的那些实词频率高，TF-IDF值很大。

现在我们找到了一组来描述新闻主题的数字:对于一篇新闻中的所有实词，计算出它们的TF-IDF值。把这些值按照对应的实词在词汇表的位  
置依次排列，就得到一个向量。比如，词汇表中有64 000个词”，其编号和词如表14.1所示。

![image-20221025104912935][]

在某一篇特定的新闻中，这64 000个词的TF-IDF值分别如表14.2所示:

![image-20221025104948112][]

如果单词表中的某个词在新闻中没有出现，对应的值为零，那么这.64000个数，组成一个64000维的向量。我们就用这个向量来代表这篇  
新闻，并成为新闻的特征向量( Feature Vector)。每一篇新闻都可以对应这样一个特征向量，向量中每一个维度的大小代表每个词对这篇新闻主题的贡献。当新闻从文字变成了数字后，计算机就有可能算一算新闻之间是否相似了。

![image-20221025105031648][]

### 怎么计算相似度呢？ 余弦相似度 ###

世界各国无论是哪门语言的“语文课”( Language Art)，老师教授写作时都会强调特定的主题用特定的描述词。几千年来，人类已经形成了  
这样的写作习惯。因此，同一类新闻一定是某些主题词用得较多，另外一些词则用得少。比如金融类的新闻，这些词出现的频率就很高:股票，利息，债券,基金，银行,物价，上涨。而这些词出现的就少:二氧化碳，宇宙，诗歌，木匠，诺贝尔，包子。反映在每一篇新闻的特征上，如果两篇新闻属于同一类，它们的特征向量在某几个维度的值都比较大，而在其他维度的值都比较小。反过来看，如果两篇新闻不属于同一类，由于用词的不同，它们的特征向量中，值较大的维度应该没有什么交集。这样就定性地认识到两篇新闻的主题是否接近，取决于它们的特征向量“长得像不像”。当然，我们还需要定量地衡量两个特征向量之间的相似性。

学过向量代数的人都知道，向量实际上是多维空间中从原点出发的有向线段。

不同的新闻，因为文本长度的不同，它们的特征向量各个维度的数值也不同。一篇10000字的文本，各个维度的数值都比一篇500字的文本来得大，因此单纯比较各个维度的大小并没有太大意义。但是，向量的方向却有很大的意义。如果两个向量的方向一致，说明相应的新闻用词的比例基本一致。因此，可以通过计算两个向量的夹角来判断对应的新闻主题的接近程度。而要计算两个向量的夹角，就要用到余弦定理了。比如图14.2中，左边两个向量的夹角小，距离就较“近”，相反，右边两个向量的夹角大，距离就“远”。

![image-20221025105242132][]

我们对余弦定理都不陌生，它描述了三角形中任何-一个夹角和三个边的关系，换句话说，给定三角形的三条边，可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为a ,b和c,对应的三个角为A, B和C。

![image-20221025105408165][]

那么∠A的余弦  
 cos ⁡ ( A ) = b 2 + c 2 − a 2 2 b c \\cos (A)=\\frac\{b^2+c^2-a^2\}\{2 b c\} cos(A)=2bcb2\+c2−a2  
如果将三角形的两边b和c看成是两个以A为起点的向量，那么上述公式等价于  
 cos ⁡ ( A ) = ⟨ b , c ⟩ ∣ b ∣ ⋅ ∣ c ∣ \\cos (A)=\\frac\{\\langle b, c\\rangle\}\{|b| \\cdot|c|\} cos(A)=∣b∣⋅∣c∣⟨b,c⟩  
其中，分母表示两个向量b和c的长度，分子表示两个向量的内积。举一个具体的例子，假如新闻X和新闻Y对应的向量分别是  
 x 1 , x 2 , … , x 64000 和 y 1 , y 2 , … , y 64000 ， \\mathrm\{x\}\_1, \\mathrm\{x\}\_2, \\ldots, \\mathrm\{x\}\_\{64000\} \\text \{ 和 \} \\mathrm\{y\}\_1, \\mathrm\{y\}\_2, \\ldots, \\mathrm\{y\}\_\{64000\} \\text \{ ， \} x1,x2,…,x64000和y1,y2,…,y64000，  
那么它们夹角的余弦等于  
 cos ⁡ θ = x 1 y 1 + x 2 y 2 + ⋯ + x 64000 y 64000 x 1 2 + x 2 2 + ⋯ x 64000 2 ⋅ y 1 2 + y 2 2 + ⋯ y 64000 2 \\cos \\theta=\\frac\{x\_1 y\_1+x\_2 y\_2+\\cdots+x\_\{64000\} y\_\{64000\}\}\{\\sqrt\{x\_1^2+x\_2^2+\\cdots x\_\{64000\}^2\} \\cdot \\sqrt\{y\_1^2+y\_2^2+\\cdots y\_\{64000\}^2\}\} cosθ=x12\+x22\+⋯x640002⋅y12\+y22\+⋯y640002x1y1\+x2y2\+⋯\+x64000y64000  
由于向量中的每一个变量都是正数,因此余弦的取值在0和1之间，也就是说夹角在0度到90度之间。当两条新闻向量夹角的余弦等于1时，这两个向量的夹角为零，两条新闻完全相同;当夹角的余弦接近于1时，两条新闻相似，从而可以归成一类;夹角的余弦越小，夹角越大，两条新闻越不相关。当两个向量正交时(90度)，夹角的余弦为零，说明两篇新闻根本没有相同的主题词，它们毫不相关。

现在把一篇篇文字的新闻变成了按词典顺序组织起来的数字(特征向量),又有了计算相似性的公式，就可以在此基础\_上讨论新闻分类的算法了。具体的算法分为两种情形。第一种比较简单，假定我们已知一些新闻类别的特征向量 x 1 , x 2 , . . . . , x k x\_1,x\_2,....,x\_k x1,x2,....,xk,那么对于任何一个要被分类的新闻Y,很容易计算出它和各类新闻特征向量的余弦相似性(距离)，并且分到它该去的那一类中。至于这些新闻类别的特征向量，既可以手工建立(工作量非常大而且不准确)，也可以自动建立(以后会介绍)。第二种情形就比较麻烦了，即如果事先没有这些新闻类别的特征向量怎么办。弗洛里安(Radu Florian)和教授雅让斯基给了一个自底向上不断合并的办法,大致思想如下:

1.  计算所有新闻之间两两的余弦相似性，把相似性大于一个阈值的新闻合并成一个小类( Subclass)。这样N篇新闻就被合并成N1个小类，当然N1 < N。
2.  把每个小类中所有的新闻作为一个整体,计算小类的特征向量，再计算小类之间两两的余弦相似性，然后合并成大一点的小类，假如有N2个，当然N2 < N1。

这样不断做下去,类别越来越少，而每个类越来越大。当某一类太大时，这一类里一些新闻之间的相似性就很小了，这时就要停止上述迭代的过程了。至此，自动分类完成。下图是弗洛里安给出的一个真实的文本分类迭代和聚合的过程，图中左边的每-一个点都代表一篇文章， 因为数量太多，因此密密麻麻地连成了一片。每一次迭代，子类数量就不断减少, 当子类的数量比较少时，就会看清楚这些子类了。

![image-20221025110052537][]

当然,这里面有很多的技术细节,有兴趣和基础的读者可以读他们的论文。

弗洛里安和雅让斯基1998年做这项工作的动机很有意思。当时雅让斯基是某个国际会议的程序委员会主席，需要把提交上来的几百篇论文发给各个专家去评审决定是否录用。为了保证评审的权威性，需要把每个研究方向的论文交给这个方向最有权威的专家。虽然论文的作者自己给论文定了方向，但是范围太广，没有什么指导意义。雅让斯基当然没有时间浏览这近千篇论文，然后再去分发，于是就想了这个将论文自动分类的方法，由他的学生弗洛里安很快实现了。接下来几年的会议都是这么选择评审专家的。从这件事我们可以看出美国人做事的一个习惯:美国人总是倾向于用机器(计算机)代替人工来完成任务。虽然在短期需要做一些额外的工作，但是从长远看可以节省很多时间和成本。

余弦定理就这样通过新闻的特征向量和新闻分类联系在一起。我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类。在这里，我们再一次看到数学工具的用途。

### 大数据量时的余弦计算 ###

利用公式计算两个向量夹角时，计算量为 O ( ∣ a ∣ + ∣ b ∣ ) O(|a|+ |b|) O(∣a∣\+∣b∣)，如果假定其中一个向量更长，不失一般性 ∣ a ∣ > ∣ b ∣ |a|> |b| ∣a∣>∣b∣,这样复杂度为 O ( ∣ a ∣ ) O(|a|) O(∣a∣)。如  
果要比较一篇新闻和所有其他N篇新闻的相关性，那么计算复杂度为 O ( N ∗ ∣ a ∣ ) O(N\*|a|) O(N∗∣a∣)。如果要比较所有N篇新闻之间两两的相关性，计算复杂度为 O ( N 2 ∗ ∣ a ∣ ) O(N^2\*|a|) O(N2∗∣a∣)。注意，这还只是一次迭代。因此，这个计算量是很大的。我们假定词汇表的大小为10万，那么向量的长度也是这么大，假定需要分类的新闻为10万篇,总的计算量在1015这个数量级。如果用100台服务器,每台服务器的计算能力是每秒1亿次，那么每次迭代的计算时间在10万秒，即大约1天。几十次迭代就需要两三个月，这个速度显然很慢。这里面可简化的地方非常多。

**首先**分母部分(向量的长度)不需要重复计算，计算向量a和向量b的余弦时，它们的长度可以存起来，等计算向量a和向量c的余弦时，将a的长度直接调出来使用即可。这样, 上面的计算量可以节省2/3，也就是只有公式中分子的部分需要两两计算。当然这还没有从根本上降低算法的复杂度。

**第二个**可以简化的地方就是在计算中的分子，即两个向量内积的时候，只需考虑向量中的非零元素即可。那么计算的复杂度取决于两个向量中，非零元素个数的最小值。如果一篇新闻的一般长度不超过2000词，那么非零元素的个数一般也就是1000词左右，这样计算的复杂度大约可以下降100倍,计算时间从“天”这个量级降到十几分钟这个量级。

**第三个**简化是删除虚词,这里的虚词包括搜索中的非必留词，诸如“的”、“是”、“和”，以及一些连词、副词和介词，比如“因为”、“所以”、“非常”等等。我们在上一节中分析过,只有同一类新闻，用词才有很大的重复性，不同类的新闻用词不大相同。因此，去掉这些虚词后，不同类的新闻，即使它们的向量中还有不少非零元素，但是共同的非零元素并不多，因此要做的乘法并不多。大多数情况下，都可以跳过去(因为非零元素乘以零，结果还是零)。这样，计算时间还可以缩短几倍。因此，10万篇新闻两两比较一下，计算时间也就是几分钟而已。如果做几十次迭代，可以在一天内计算完。

特别需要指出的是，删除虚词后，不仅可以提高计算速度，对新闻分类的准确性也大有好处，因为虚词的权重其实是一种干扰分类正常进行的噪音。这一点，和通信中过滤掉低频噪音是同样的原理。通过这件事，我们也可以看出自然语言处理和通信的很多道理是相通的。

还有一个准确率优化手段是进行位置的加权。和计算搜索相关性一样，出现在文本不同位置的词在分类时的重要性也不相同。显然，出现在标题中的词对主题的贡献远比出现在新闻正文中的重要。而即使在正文中，出现在文章开头和结尾的词比出现在中间的词重要。在中学学习语文和大学学习英语文学时，老师都会强调这一点——阅读时要特别关注第一段和最后一段，以及每个段落的第一个句子。在自然语言处理中这个规律依然有用。因此，要对**标题和重要位置的词进行额外的加权**，以提高文本分类的准确性。

### 来源 ###

吴军. 数学之美 : Beauty of mathematics\[M\]. 人民邮电出版社, 2014.

[image-20221025104912935]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/789282d15a124e8988472e2323cab555.png
[image-20221025104948112]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/00cdd57f7dfc4289bd53eaafa7303a58.png
[image-20221025105031648]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a3cf5d8c01f24e76880549547a1c5b66.png
[image-20221025105242132]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/85c87147f8e146b7bc512f8e848625ff.png
[image-20221025105408165]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/332ec4c678074c899bebb7b963ffd094.png
[image-20221025110052537]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/07481fcb9b16433397fcba3b16751537.png