第八章 余弦定理和消息的分类
第八章 余弦定理和消息的分类[*]使用被分类文本在百万数量级
消息的特征向量
[*] 所谓消息的分类, 或者更广义地讲任何文本的分类, 无非是要把相似的消息归人同一类中。但是计算机根本读不僅消息, 计算机本质上只能做快速计算。为了让计算机可以或许 “算”消息（而不是读消息），就要求我们先把笔墨的消息变成一组可计算的数字, 然后再计划一个算法来算出任意两篇消息的相似性。
[*] “同一类消息用词都是相似的, 不同类的消息用词各不雷同”。当然, 一篇消息有很多泀, 有些词表达的语义重要, 有些词相对次要。那么如何确定哪些重要, 哪些次要呢? 不难想象, 和消息主题有关的那些实词频率高, TF-IDF 值很大。
[*] 如今我们找到了一组来描述消息主题的数字：对于一篇消息中的所有实词, 计算出它们的 TF-IDF 值。把这些值按照对应的实词在词汇表的位置依次分列，就得到一个向量。好比，词汇表中有 64000 个词 ，那么 log 64000 ≈ 16 Bit = 2 Byte \log 64000 \approx 16~\text{Bit}=2~\text{Byte} log64000≈16 Bit=2 Byte,在某一篇特定的新阿中, 这 64000 个词的 TF-IDF 值分别如下表可视。
单词编号汉字词TF-IDF 值1阿02啊0.00343阿斗04阿姨0.00052 … \ldots … … \ldots … … \ldots …789服装0.034 … \ldots … … \ldots … … \ldots …64000做作0.075如果单词表中的某个词在消息中没有出现, 对应的值为零, 那么这 64000 个数, 构成一个 64000 维的向量。我们就用这个向量来代表这篇消息,并称为消息的特征向量 (Feature Vector)。每一篇消息都可以对应如许一个特征向量, 向量中每一个维度的大小代表每个词对这篇消息主题的贡献。当消息从笔墨变成了数字后，计算机就有大概 “算一算” 消息之间是否相似了。
向量距离的度量
https://i-blog.csdnimg.cn/img_convert/26a113aaa27d94db7a721fe99626ccea.png
[*] KaTeX parse error: Undefined control sequence: \ang at position 1: \̲a̲n̲g̲{A}余弦
cos A = b 2 + c 2 − a 2 2 b c \cos A=\frac{b^2+c^2-a^2}{2 b c} cosA=2bcb2+c2−a2
如果将三角形的两边 b b b 和 c c c 当作是两个以 A A A 为起点的向量, 那么上述公式等价于
cos A = ⟨ b , c ⟩ ∣ b ∣ ⋅ ∣ c ∣ \cos A=\frac{\langle b, c\rangle}{|b| \cdot|c|} cosA=∣b∣⋅∣c∣⟨b,c⟩
其中, 分母表现两个向量 b b b 和 c c c 的长度, 分子表现两个向量的内积。举一个具体的例子, 假如消息 X X X 和消息 Y Y Y 对应的向量分别是 x 1 , x 2 , ⋯ , x 64000 x_1, x_2, \cdots, x_{64000} x1,x2,⋯,x64000 和 y 1 , y 2 , ⋯ , y 64000 y_1, y_2, \cdots, y_{64000} 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+⋯+y640002 x1y1+x2y2+⋯+x64000y64000
[*] 具体算法
[*]假定我们已知一些消息类别的特征向量 x 1 , x 2 , ⋯ , x k x_1, x_2, \cdots, x_k x1,x2,⋯,xk, 那么对于任何一个要被分类的消息 Y Y Y, 很容易计算出它和各类消息特征向量的余弦相似性 (距离), 并将其归人它该去的那一类中。至于这些消息类别的特征向量, 既可以手工创建 (工作量非常大而且不正确), 也可以主动创建 (以后会介绍)。
[*]第二种情况就比力贫苦了, 即如果事先没有这些消息类别的特征向量怎么办。给出了一个自底向上不停合并的办法, 大致思想如下。
[*]计算所有消息之间两两的余弦相似性, 把相似性大于一个阈值的消息合并成一个小类 (Subclass)。如许 N N N 篇消息就被合并成 N 1 N_1 N1 个小类, 当然 N 1 < N N_1<N N1<N 。
[*]把每个小类中所有的消息作为一个整体, 计算小类的特征向量,再计算小类之间两两的余弦相似性, 然后合并成大一点的小类, 假如有 N 2 N_2 N2 个, 当然 N 2 < N 1 N_2<N_1 N2<N1 。
计算向量余弦的技巧
大数据量
[*] 使用下述公式计算余弦
cos A = ⟨ b , c ⟩ ∣ b ∣ ⋅ ∣ c ∣ \cos A=\frac{\langle b, c\rangle}{|b| \cdot|c|} cosA=∣b∣⋅∣c∣⟨b,c⟩
计算两个向量夹角时, 计算量为 O ( ∣ a ∣ + ∣ b ∣ ) O(|a|+|b|) O(∣a∣+∣b∣), 如果假定其中一个向量更长, 不失一样平常性 ∣ a ∣ > ∣ b ∣ |a|>|b| ∣a∣>∣b∣, 如许复杂度为 O ( ∣ a ∣ ) O(|a|) O(∣a∣) 。如果要比力一篇消息和所有其他 N N N 篇消息的相干性, 那么计算复杂度为 O ( N ⋅ ∣ a ∣ ) O(N \cdot|a|) O(N⋅∣a∣) 。如果要比力所有 N N N 篇消息之间两两的相干性, 计算复杂度为 O ( N 2 ⋅ ∣ a ∣ ) O\left(N^2 \cdot|a|\right) O(N2⋅∣a∣) 。注意，这还只是一次迭代。因此，这个计算量是很大的。我们假定词汇表的大小为 10 万, 那么向量的长度也是这么大，假定必要分类的消息为 10 万篇, 总的计算量在 1 0 15 10^{15} 1015 这个数量级。如果用 100 台服务器, 每台服务器的计算能力是每秒 1 亿次, 那么每次迭代的计算时间在 10 万秒, 即约莫 1 天。几十次迭代就必要两三个月，这个速度显然很慢。
[*] 简化方法
[*]分母部门 (向量的长度) 不必要重复计算, 计算向量 a a a 和向量 b b b 的余弦时, 可以将它们的长度存起来, 等计算向量 a a a 和向量 c c c 的余弦时，直接取用 a a a 的长度即可。如许，上面的计算量可以节省 2 / 3 2 / 3 2/3,当然这还没有从根本上降低算法的复杂度。
[*]在计算分子即两个向量内积时, 只需思量向量中的非零元素。计算的复杂度取决于两个向量中非零元素个数的最小值。如果一篇消息的一样平常长度不超过 2000 词, 那么非零元素的个数一样平常也就是 1000 词左右, 如许计算的复杂度约莫可以下降 100 倍, 计算时间从 “天”这个量级降至十几分钟这个量级。
[*]可以删除虚词, 这里的虚词包罗搜索中的非必留词, 诸如 “的” “是” “和” , 以及一些连词、副词和介词, 好比 “因为” “以是”“非常”, 等等。我们在上一节中分析过, 只有同一类消息, 用词才有很大的重复性, 不同类的消息用词不大雷同。如许, 计算时间还可以收缩几倍。因此, 10 万篇消息两两比力一下, 计算时间也就是几分钟而已。如果做几十次迭代, 可以在一天内计算完。
备注：必要特别指出的是, 删除虚词, 不仅可以进步计算速度, 对消息分类的正确性也大有好处, 因为虚词的权重其实是一种噪声, 干扰分类的正常进行。这一点与通讯中过滤掉低频噪声是同样的原理。通过这件事, 我们也可以看出自然语言处理和通讯的很多原理是相通的。
位置加权
[*]和计算搜索相干性一样, 出如今文本不同位置的词在分类时的重要性也不雷同。显然, 出如今标题中的词对主题的贡献远比出如今消息正文中的重要。而即使在正文中, 出如今文章开头和结尾的词也比出如今中心的词重要。因此, 要对标题和重要位置的词进行额外的加权, 以进步文本分类的正确性。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]