第八章 余弦定理和新闻的分类

第八章 余弦定理和新闻的分类

• 使用被分类文本在百万数量级

新闻的特征向量

• 所谓新闻的分类, 或者更广义地讲任何文本的分类, 无非是要把相似的新闻归人同一类中。但是计算机根本读不僅新闻, 计算机本质上只能做快速计算。为了让计算机能够 “算”新闻（而不是读新闻），就要求我们先把文字的新闻变成一组可计算的数字, 然后再设计一个算法来算出任意两篇新闻的相似性。

• “同一类新闻用词都是相似的, 不同类的新闻用词各不相同”。当然, 一篇新闻有很多泀, 有些词表达的语义重要, 有些词相对次要。那么如何确定哪些重要, 哪些次要呢? 不难想象, 和新闻主题有关的那些实词频率高, TF-IDF 值很大。

• 现在我们找到了一组来描述新闻主题的数字：对于一篇新闻中的所有实词, 计算出它们的 TF-IDF 值。把这些值按照对应的实词在词汇表的位置依次排列，就得到一个向量。比如，词汇表中有 64000 个词 ，那么$\log 64000\approx 16\text{Bit}=2\text{Byte}$,在某一篇特定的新阿中, 这 64000 个词的 TF-IDF 值分别如下表可视。

  单词编号	汉字词	TF-IDF 值
  1	阿	0
  2	啊	0.0034
  3	阿斗	0
  4	阿姨	0.00052
  $\dots$	$\dots$	$\dots$
  789	服装	0.034
  $\dots$	$\dots$	$\dots$
  64000	做作	0.075

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

---

向量距离的度量

• KaTeX parse error: Undefined control sequence: \ang at position 1: \̲a̲n̲g̲{A}余弦
  $$\cos A=\frac{b^2+c^2-a^2}{2bc}$$

  如果将三角形的两边 $b$ 和 $c$ 看成是两个以 $A$ 为起点的向量, 那么上述公式等价于
  $$\cos A=\frac{⟨b,c⟩}{|b|\cdot |c|}$$

  其中, 分母表示两个向量 $b$ 和 $c$ 的长度, 分子表示两个向量的内积。举一个具体的例子, 假如新闻 $X$ 和新闻 $Y$ 对应的向量分别是$x_1,x_2,\cdots ,x_{64000}$ 和 $y_1,y_2,\cdots ,y_{64000}$,

  那么它们夹角的余弦等于
  $$\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}}$$

• 具体算法

  1. 假定我们已知一些新闻类别的特征向量 $x_1,x_2,\cdots ,x_k$, 那么对于任何一个要被分类的新闻 $Y$, 很容易计算出它和各类新闻特征向量的余弦相似性 (距离), 并将其归人它该去的那一类中。至于这些新闻类别的特征向量, 既可以手工建立 (工作量非常大而且不准确), 也可以自动建立 (以后会介绍)。
  2. 第二种情形就比较麻烦了, 即如果事先没有这些新闻类别的特征向量怎么办。给出了一个自底向上不断合并的办法, 大致思想如下。
     1. 计算所有新闻之间两两的余弦相似性, 把相似性大于一个阈值的新闻合并成一个小类 (Subclass)。这样 $N$ 篇新闻就被合并成 $N_1$ 个小类, 当然 $N_1<N$ 。
     2. 把每个小类中所有的新闻作为一个整体, 计算小类的特征向量,再计算小类之间两两的余弦相似性, 然后合并成大一点的小类, 假如有 $N_2$ 个, 当然 $N_2<N_1$ 。

计算向量余弦的技巧

大数据量

• 利用下述公式计算余弦
  $$\cos A=\frac{⟨b,c⟩}{|b|\cdot |c|}$$
  计算两个向量夹角时, 计算量为 $O(|a|+|b|)$, 如果假定其中一个向量更长, 不失一般性 $|a|>|b|$, 这样复杂度为 $O(|a|)$ 。如果要比较一篇新闻和所有其他 $N$ 篇新闻的相关性, 那么计算复杂度为 $O(N\cdot |a|)$ 。如果要比较所有 $N$ 篇新闻之间两两的相关性, 计算复杂度为 $O\left(N^2\cdot |a|\right)$ 。注意，这还只是一次迭代。因此，这个计算量是很大的。我们假定词汇表的大小为 10 万, 那么向量的长度也是这么大，假定需要分类的新闻为 10 万篇, 总的计算量在 $10^{15}$ 这个数量级。如果用 100 台服务器, 每台服务器的计算能力是每秒 1 亿次, 那么每次迭代的计算时间在 10 万秒, 即大约 1 天。几十次迭代就需要两三个月，这个速度显然很慢。

• 简化方法

  1. 分母部分 (向量的长度) 不需要重复计算, 计算向量 $a$ 和向量 $b$ 的余弦时, 可以将它们的长度存起来, 等计算向量 $a$ 和向量 $c$ 的余弦时，直接取用 $a$ 的长度即可。这样，上面的计算量可以节省 $2/3$,当然这还没有从根本上降低算法的复杂度。
  2. 在计算分子即两个向量内积时, 只需考虑向量中的非零元素。计算的复杂度取决于两个向量中非零元素个数的最小值。如果一篇新闻的一般长度不超过 2000 词, 那么非零元素的个数一般也就是 1000 词左右, 这样计算的复杂度大约可以下降 100 倍, 计算时间从 “天”这个量级降至十几分钟这个量级。
  3. 可以删除虚词, 这里的虚词包括搜索中的非必留词, 诸如 “的” “是” “和” , 以及一些连词、副词和介词, 比如 “因为” “所以”“非常”, 等等。我们在上一节中分析过, 只有同一类新闻, 用词才有很大的重复性, 不同类的新闻用词不大相同。这样, 计算时间还可以缩短几倍。因此, 10 万篇新闻两两比较一下, 计算时间也就是几分钟而已。如果做几十次迭代, 可以在一天内计算完。

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

位置加权

• 和计算搜索相关性一样, 出现在文本不同位置的词在分类时的重要性也不相同。显然, 出现在标题中的词对主题的贡献远比出现在新闻正文中的重要。而即使在正文中, 出现在文章开头和结尾的词也比出现在中间的词重要。因此, 要对标题和重要位置的词进行额外的加权, 以提高文本分类的准确性。

原文地址：https://blog.csdn.net/hbkybkzw/article/details/145082566

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！