July 31, 2006
相关度计算与信噪比::[Search Engine]
你知道google和百度两个关键词的相关度是多少么？
－－最后我将来回答这个问题
通常我们对于文本信息之间得相关性得计算都是采用向量的办法，我在以前的PPT里曾经提到过。然而对于文本信息更深层次的分析不能单纯从字面上分析一篇文章的关键词，更重要的是它隐含的扩展的意义。
传统的关于计算文本相关度和【网页和查询的相关性】的计算都是采用匹配的方式进行的，然而这只能是基于字面意义上的统计计算。这里介绍的做法是采用关键词相关性扩展的做法从而得到更加精确的相关度计算。
例子：
文章 A: 谈论的是大学教育，最高频的关键词是：学生[3]，学习[2]，大学[2]
文章 B: 谈论的是普通教育，最高频的关键词是：教育[5]，教师[1]，进修[1]
[]里是相对的权重，可以理解成 TF*IDF
根据传统的相关性计算，我们会得到如下的结果：
1. 文章A 与 文章B 不相关
2. 查询 学生，学习，大学只能返回文章A，不能返回文章B
3. 查询 教育，教师，进修只能返回文章B，不能返回文章A
分析：
这个显然是有一定的问题的，问题的出现在于我们通常将“字面”的意思做为分析的来源而且依靠和仅仅依靠这些“字面”的关键词做为文章相关性和查询相关性判断的唯一要素。
如何避免？
我在以前的文章中提到过【关键词相关度】的概念，举例说明：
当出现：｛学习｝这个词汇的时候，真实的表达的意义往往是这样的：
｛W1*学习，W2*教育，W3*教师，W4*大学。。。。。。｝
其中W1，W2...是学习和相关词汇的相关权重。
基于这样一个矩阵，我们就能够将一个词扩展成为一组词汇，因而也同时可以将文章所对应的向量扩展成一个更多词汇的集合。
这里的计算需要一个完整的相关度矩阵:M
M(i,j) = {关键词i,j的相关度}
而两篇文章的相关度的计算，也由简单的
R= Sigma Vi*Vi
变为
R= Sigma Vi*M(i,j)*Vj
查询关键词和文章的相关度也由简单的
R(i)=TF(i)*IDF(i)
变为
R(i)=Sigma TF(j)*IDF(j)*M(i,j)
下面碰到一个核心问题就是：关键词之间的相关度如何计算？
例如：学校和学生的相关度是多少？
计算方法：
假设一个文章集合 {C}，总文章数目为N，其中含有单词A的文章总数为Na，含有单词B的文章总数是Nb，含有｛A+B｝的文章总数是 Nab，那么相关性这么计算
CorrAB= Nab/(Na+Nb-Nab)-(Na*Nb)/(N*N)
本计算中可能会得到负相关，如果考虑到Na,Nb都是小量，可以忽略，那么
CorrAB= Nab/(Na+Nb-Nab)
至此，要计算相关度之间的全部要素都获得了。
思考，那么到底 学校 和学生 之间的相关度是多少呢？
我们利用google来回答这个问题吧：
约有91,700,000项符合学校的查询结果
约有88,200,000项符合学生的查询结果
约有48,900,000项符合学生 学校的查询结果
Corr{学校，学生}＝48,900,000/(91,700,000+88,200,000-48,900,000)=0.37
这个原理我以前应用在了计算【网页信噪比】上，和网页信噪比一起成为衡量一个网页的关键词的核心算法。
这也就是为什么6e的网页信噪比能够不依靠网页上现有的关键词而准确的判断网页的分类和相关度，是因为除了TF和IDF之外，我们能够从已有的文本集合里学到更多的“知识”。
那么百度和google的相关度应该不难计算了:
利用 google计算得到：2,950,000/(61,800,000+6,370,000-2,950,000)=0.03
利用 baidu计算得到：2,760,000/(21,700,000+12,200,000-2,760,000)=0.08
看来基本上相关度小于10%。
Posted at July 31, 2006 10:16 AM by Liang at 10:16 AM | Comments (46) | TrackBack(1) | Booso!| Niu.la收藏!Trackback
You can ping this entry by using http://www.wespoke.com/cgi-bin/mt/mt-tb.cgi/880
Trackbacked from http://joyfire.spaces.live.com/Blog/cns!502060A314B1A145!1160.entry with 本周收藏.2006.08.13 on joyfire.
Comments
根据传统的相关性计算，我们会得到如下的结果：
1. 文章A 与 文章B 不相关
2. 查询 学生，学习，大学只能返回文章A，不能返回文章B
3. 查询 教育，教师，进修只能返回文章B，不能返回文章A
如果采用相关反馈进行查询扩展,就有可能避免上述的情况,在学术界,特别是做检索评测的时候,基于相关反馈的查询扩展往往能够有效得提高检索的效果,但是不可避免地带来噪音.
Posted by: softlanding at August 1, 2006 01:33 PM from 218.106.181.28 目前流行的局部分析方法主要是伪相关反馈(pseudo
feedback),它是在相关反馈(relevance feedback)的基础上发展起来的.相关反馈机制由用户对检索出的文档进行相关性判定,系统根据这些判定生成新的查询,从而提高最终结果的准确率.伪相关反馈不需与用户交互,它将初次查询的前N篇文档自动认为是相关文档,以此为依据对查询进行扩展.
--摘自>
你这篇文章和Google黑板报上的一片文章的相关性很高
数学之美 系列 12 - 余弦定理和新闻的分类
哇。。你好强啊，你做我师傅吧，我也好想学这些啊，可是没人教我。
另外，我看到一个叫search的搜索引擎，很好用啊，国内没有这类的引擎呢，虽然它是一些引擎的杂交品种，但是真的很不错哦，它是用什么技术实现的啊，它搜索到的结果不会有冲突吗(好几个引擎的搜索结果)，这家公司是怎么盈利的呢？
还有，以后我有问题可以在这里来问你吧？？？
我会天天来这里拜你的
刚刚研究了一下XFN，然后我就想，如果能把6e信噪比用在朋友分类上，那将是一件很NB的事情。通过每个好友的个人Blog，还有基于XFN的好友之间的关系强度，可以把周围的朋友分成三六九等（我人品是不是有问题？:P）。期待阿。。。
Posted by: 王小虎 at August 7, 2006 08:55 AM from 130.113.68.167卢亮，你好。
你这里的blog好久没有更新了。^_^
最近我也在作一些中文信息结构化和信息相关度计算方面的思考。你这篇文章给了我一些启发，但是仍然有一个问题是没有办法解决的。
这也就是为什么6e的网页信噪比能够不依靠网页上现有的关键词而准确的判断网页的分类和相关度，是因为除了TF和IDF之外，我们能够从已有的文本集合里学到更多的“知识”。
这个结论实际上你包含了一个理性人的假设：提供服务的人总是喜欢简单的把它们的用户假设为纯理性的“好人”。这样公式提取全文中的关键字作匹配的百分比，但是不可避免地一定会有人能够利用这样的做法，在全文中堆砌关键词，（例如鬼文、阴文等伎俩），以此来提高自己的page的相关度。
这种检查信噪比方法的思路就如同金庸笔下公孙止的武功，难练易破。
不知道我说的是不是这么个道理，呵呵。 ：P
呵呵有意思,可以用Google的Search API来做一个任何两个词的相关度查询的服务试试看
http://www.niyue.com
倪跃
易观国际9月20日14：00~17：00有一场有关搜索引擎的沙龙，规模50人，有兴趣吗？
http://club.analysys.com.cn/huiyi_display_hyjj.php?id=65
活动联系人：Maggie 010-64666565*212
Posted by: analysys at September 7, 2006 03:52 PM from 220.231.7.212什么情况下两个词的相关度可以达到接近1？？
Co｛计算机，电脑｝≈0。74；
co｛搜索，检索｝<0.1,好像是，
什么情况下两个词的相关度可以达到接近1？？
能不能说说
“CorrAB= Nab/(Na+Nb-Nab)-(Na*Nb)/(N*N)”
这条式子的数学依据？
顺电一说，我在这里好像没办法留我的email,每次都提示xxx.com有问题。
Posted by: hzxdark at October 6, 2006 01:53 AM from 59.40.114.81我也对搜索引擎的技术很感兴趣，
还做了一个桌面搜索引擎，类似于google desktop search.查询速度比google的桌面搜索差不多，资源占用却能小很多。有兴趣，欢迎同道中人，试用交流一下。
www.18ie.com
我也对搜索引擎的技术很感兴趣，
还做了一个桌面搜索引擎，类似于google desktop search.查询速度比google的桌面搜索差不多，资源占用却能小很多。有兴趣，欢迎同道中人，试用交流一下。
www.18ie.com
我也对搜索引擎的技术很感兴趣，
还做了一个桌面搜索引擎，类似于google desktop search.查询速度比google的桌面搜索差不多，资源占用却能小很多。有兴趣，欢迎同道中人，试用交流一下。
www.18ie.com
抱歉，你的 post 脚本，可能有点问题，我刷了3次才写上。 你从后台把我的多余的2个留言去掉吧。多谢
Posted by: ftfind at October 21, 2006 07:43 PM from 220.114.65.234借宝地诚聘搜索引擎人才：
如果你羡慕百度的辉煌和大量百度人都是千万富翁的传奇，请不要再羡慕别人了，来加盟儒豹手机搜索引擎公司吧！中国有一亿PC用户，却有五亿手机用户！无线移动搜索将给五亿多手机用户带来随时随地，随身随手搜索的便利和乐趣，意义和影响比百度PC上的搜索还要巨大。中国十几亿人口为手机用户群提供了巨大的增长空间，前途不可估量。现在加盟儒豹，拥有大量近乎免费的早期原始股票期权，各种福利(医疗，住房，工伤，退休，失业，社保等)，快速扩张中大量提职高升的机会。想干一番事业的人，快来加盟儒豹!
儒豹手机搜索引擎公司注册在海外，架构和算法专家组在美国硅谷，拥有硅谷几个世界一流搜索引擎公司工作的经验。儒豹中国分公司位于美丽如画的人间天堂苏州工业园区，办公室座落在清澈绿荫的湖畔，街区环境是按照欧美国家工作生活标准而设计的现代化新区。公司创始人在清华大学无线电系获得学士，硕士，中国科学院自动化所模式识别国家重点实验室工作近三年，美国南加大(USC)获得计算机博士。博士生期间在IEEE和ACM国际一流刊物发表八篇论文，论文以创新引人瞩目而接受 LA Times(洛杉矶时报)采访拍照并见报，这在海外博士生中非常少见。博士毕业后在硅谷从事大型搜索引擎，海量数据挖掘等工作。公司核心团队的从业经验包括中国移动，中国联通，掌上万维，中国航天集团等。儒豹以美国硅谷世界一流搜索专家为架构，以技术和产品创新为特色，营造自由活泼和勤奋务实的企业文化。2006年8月面向全国寻觅人才，不限户口。
Posted by: 儒豹 at October 24, 2006 03:27 PM from 58.211.156.2http://www.htpbbs.com
科技园论坛 - [深圳-北京-上海-Silicon]
写得好,非常好！
两个词的相关度，我觉得还有主动和被动的问题。
比如最近比较热的 黄健翔 吴鸿飞
用google搜索：
约有508项符合黄健翔 吴鸿飞的查询结果，
约有3,150,000项符合黄健翔 的查询结果，
约有2,110项符合吴鸿飞 的查询结果
CorrAB= Nab/(Na+Nb-Nab)<0.001
但是，从结果可以看出吴鸿飞与黄健翔较“相关”
黄建翔与吴鸿飞的相关性则较差。
试着改一下公式：
CorrAB = Nab/(Na-Nab)
CorrBA = Nab/(Nb-Nab)
学习中,不太看得懂啊
HTTP://WWW.DX8888.CN
Posted by: kaivsun at December 19, 2006 10:27 PM from 60.187.72.227不知道我的网站http://www.9yxz.com的关键词相关度怎么样啊?
Posted by: sunny at December 21, 2006 08:20 AM from 61.175.244.58支持一下,如果可以请加下我的网站,免费杀毒软件http://www.9yxz.com/downlist/r_8_1.html
Posted by: 9yxz at December 23, 2006 12:02 AM from 60.187.72.227如前面一位兄弟所说,相关性还是较多地考虑用户的点击相关性更好,不知道这种自学习功能哪个搜索引擎做得最好.
Posted by: maxdigest at January 29, 2007 07:28 AM from 166.111.32.115注册香港网简介
http://www.008win.com/1/
这个相关度的计算应该来自聚类算法。不过这样做会引出一个新问题：如何定义相关词列表？或者计算所有词的term-to-term correlation matrix？第一种做法难免引入认为bias，第二种做法实践上很困难。
有些说到相关反馈，但是相关反馈要求搜索以向量为模型，而且如果不在客户端做一些工作如聚类，效果是没有什么提升的。
不过我个人是最看好相关反馈的，如果能对每一个用户建立唯一的profile的话。甚至可以对认知心理建立模型
本人初学,看了文章都不懂,问个很简单的问题,学习搜索技术应学习那些数学知识,有人愿意回答一下吗.谢谢
Posted by: lovergoogel at April 24, 2007 03:25 PM from 210.75.39.170外贸礼品网站有人愿意交换链接吗
www.cn-crystal.com
这个比较深，涉及到详细的算法了。
一般的SE方面的人还只是在掌握好与不好的规则而已
搜索引擎要求最高的其实还是数学了，你说的这些都是每本书上都会讲到的。
这个领域里面有个叫麦克林奇的ms很牛
