《余弦定理和新闻的分类》由会员分享,可在线阅读,更多相关《余弦定理和新闻的分类(15页珍藏版)》请在金锄头文库上搜索。
1、余弦定理和新闻的分类,数学之美系列十二 发表者:吴军,Google 研究员,介绍,新闻的分类无非是要把相似的新闻放到一类中;计算机其实读不懂新闻,它只能快速计算; 这就要求我们设计一个算法来算出任意两篇新闻的相似性; 为了做到这一点,我们需要想办法用一组数字或一个向量来描述一篇新闻。,如何确定网页和查询的相关性,例子:查找关于“原子能的应用”的网页 现在任何一个搜索引擎都包含几十万甚至是上百万个多少有点关系的网页。那么哪个应该排在前面呢? 显然我们应该根据网页和查询“原子能的应用”的相关性对这些网页进行排序。 因此,这里的关键问题是如何度量网页和查询的相关性。,如何确定网页和查询的相关性,短语
2、“原子能的应用”可以分成三个关键词:“原子能”、“的”、“应用”。 根据直觉,包含这三个词多的网页应该比包含它们少的网页相关。当然,这个办法有一个明显的漏洞。 因此我们需要根据网页的长度,对关键词的次数进行归一化,也就是用关键词的次数除以网页的总字 数。我们把这个商称为“关键词的频率”,或者“单文本词汇频率”(Term Frequency,TF),如何确定网页和查询的相关性,相关性的一个简单的度量:如果一个查询包含关键词 w1,w2,.,wn, 它们在一篇特定网页中的词频分别是: TF1, TF2, ., TFn。 (TF: term frequency)。 那么,这个查询和该网页的相关性就是
3、: TF1 + TF2 + . + TFn。,TF/IDF 介绍,在信息检索中,使用最多的权重是“逆文本频率指数” (Inverse document frequency 缩写为), 它的公式为()其中是全部网页数。比如,我们假定中文网页数是亿,词“的”在所有的网页中都出现,即亿,那么它的log(10亿/10亿)= log (1) = 。假如专用词“原子能”在两百万个网页中出现,即万,则它的权重log(500) =6.2。又假定通用词“应用”,出现在五亿个网页中,它的权重 = log(2),则只有 0.7。也就只说,在网页中找到一个“原子能”的比配相当于找到九个“应用”的匹配。 利用 IDF,
4、上述相关性计算公式就由词频的简单求和变成了加权求和,即 TF1*IDF1 + TF2*IDF2 . + TFN*IDFN。,新闻的分类,怎样找一组数字,或者说一个向量来描述一篇新闻?对于一篇新闻中的所有实词,我们可以计算出它们的单文本词汇频率/逆文本频率值(TF/IDF)。不难想象,和新闻主题有关的那些实词频率高,TF/IDF 值较大。,新闻的分类,比如,词汇表有六万四千个词,分别为 单词编号 汉字词 1 阿 2 啊 3 阿斗 4 阿姨 . 789 服装 64000 做作,新闻的分类,在一篇新闻中,这 64,000 个词的 TF/IDF 值分别为 单词编号 TF/IDF 值 1 0 2 0.0
5、034 3 0 4 0.00052 . 789 0.034 . 64000 0.075,新闻的分类,如果单词表中的某个词在新闻中没有出现,对应的值为零; 那么这 64,000 个数,组成一个64,000维的向量 我们就用这个向量来代表这篇新闻,并成为新闻的特征向量; 如果两篇新闻的特征向量相近,则对应的新闻内容相似,它们应当归在一类,反之亦然。,新闻的分类,向量实际上是多维空间中有方向的线段。如果两个向量的方向一致,即夹角接近零,那么这两个向量就相近。而要确定两个向量方向是否一致,这就要用到余弦定理计算向量的夹角了。,新闻的分类,三角形的余弦定理公式:将三角形的两边 b 和 c 看成是两个向量,那么上述公式等价于 其中分母表示两个向量 b 和 c 的长度,分子表示两个向量的内积,举一个具体的例子,假如新闻 X 和新闻 Y 对应向量分别是 x1,x2,.,x64000 和 y1,y2,.,y64000, 那么它们夹角的余弦等于:,新闻的分类,当两条新闻向量夹角的余弦等于一时,这两条新闻完全重复(用这个办法可以删除重复的网页); 当夹角的余弦接近于一时,两条新闻相似,从而可以归成一类; 夹角的余弦越小,两条新闻越不相关。,新闻的分类,X XY两天新闻相似 Y两天新闻无关,Thank you !,