注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

数学之美系列12—余弦定理和新闻的分类【转】  

2010-11-15 21:30:56|  分类: Google黑板报 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

原文链接:http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html

2006年7月20日 上午 10:12:00
发表者:吴军,Google 研究员 

       余弦定理和新闻的分类似乎是两件八杆子打不着的事,但是它们确有紧密的联系。具体说,新闻的分类很大程度上依靠余弦定理。
Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻,它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点,我们需要想办法用一组数字来描述一篇新闻。
我们来看看怎样找一组数字,或者说一个向量来描述一篇新闻。回忆一下我们在“如何度量网页相关性”一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词,我们可以计算出它们的单文本词汇频率/逆文本频率值(TF/IDF)。不难想象,和新闻主题有关的那些实词频率高,TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如,词汇表有六万四千个词,分别为
单词编号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作
在一篇新闻中,这 64,000 个词的 TF/IDF 值分别为
单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075
       如果单词表中的某个次在新闻中没有出现,对应的值为零,那么这 64,000 个数,组成一个64,000维的向量。我们就用这个向量来代表这篇新闻,并成为新闻的特征向量。如果两篇新闻的特征向量相近,则对应的新闻内容相似,它们应当归在一类,反之亦然。
学过向量代数的人都知道,向量实际上是多维空间中有方向的线段。如果两个向量的方向一致,即夹角接近零,那么这两个向量就相近。而要确定两个向量方向是否一致,这就要用到余弦定理计算向量的夹角了。
余弦定理对我们每个人都不陌生,它描述了三角形中任何一个夹角和三个边的关系,换句话说,给定三角形的三条边,我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c,对应的三个角为 A, B 和 C,那么角 A 的余弦 --
数学之美系列 12 - 余弦定理和新闻的分类 - chhaj5236 - chhaj5236的博客
      如果我们将三角形的两边 b 和 c 看成是两个向量,那么上述公式等价于
数学之美系列 12 - 余弦定理和新闻的分类 - chhaj5236 - chhaj5236的博客
       其中分母表示两个向量 b 和 c 的长度,分子表示两个向量的内积。举一个具体的例子,假如新闻 X 和新闻 Y 对应向量分别是x1,x2,...,x64000 和y1,y2,...,y64000,那么它们夹角的余弦等于:

数学之美系列 12 - 余弦定理和新闻的分类 - chhaj5236 - chhaj5236的博客

       当两条新闻向量夹角的余弦等于一时,这两条新闻完全重复(用这个办法可以删除重复的网页);当夹角的余弦接近于一时,两条新闻相似,从而可以归成一类;夹角的余弦越小,两条新闻越不相关。


         我们在中学学习余弦定理时,恐怕很难想象它可以用来对新闻进行分类。在这里,我们再一次看到数学工具的用途。
Copyright ? 2010 Google Inc. All rights reserved.
  评论这张
 
阅读(213)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017