第八章-搜索引擎技术.ppt

北京大学软件与微电子学院2009年度课程,1,第八章 搜索引擎技术,2010年11月,最后更新日期：2019-2-7,北京大学软件与微电子学院2009年度课程,2,主要内容,信息采集技术(information gathering) 信息的组织和索引(information organization&indexing) 相似度计算信息检索模型(ir models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(evaluation),北京大学软件与微电子学院2009年度课程,3,主要内容,信息采集技术(information gathering) 信息的组织和索引(information organization&indexing) 相似度计算信息检索模型(ir models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(evaluation),北京大学软件与微电子学院2009年度课程,4,信息的采集技术,北京大学软件与微电子学院2009年度课程,5,信息采集的概念,主要是指通过web页面之间的链接关系从web上自动获取页面信息,并且随着链接不断向所需要的web页面扩展的过程，信息采集系统也常常称为robot, spider, crawler等等 信息采集是搜索引擎获得数据来源的过程，地位相当重要 信息采集的目标：快速获得高质量的网页 信息采集是一项十分繁杂和庞大的工程 不同的协议 不同的网络情况 时效性的要求 网页质量的要求 实际上是图的遍历过程 通过种子页面或站点(seed)，获取更多的链接，将它们作为下一步种子，循环 这个过程一般永远不会结束！,北京大学软件与微电子学院2009年度课程,6,web图结构,北京大学软件与微电子学院2009年度课程,7,web图中的一些概念,节点(node)：指每个网页，当图中每个连接的单位是网站时，每个网站看成一个node。 入度(in degree)：每个node的入度指的是指向该node的node数目。 出度(out degree)：每个node的出度指的是该node指向的node数目。,北京大学软件与微电子学院2009年度课程,8,web的相关特性(1),power law(幂分布定律)：web的很多属性满足f(x)=x-， 1,北京大学软件与微电子学院2009年度课程,9,web的相关特性(2),small world(小世界)理论：整个web虽然庞大，但是任意两点之间的平均距离却不大。有人做过实验，计算出整个web的平均距离约为19。 人类社会的六度分离理论，人类社会至多通过6人可以实现两人的互通。,北京大学软件与微电子学院2009年度课程,10,web的相关特性(3),web的结构：蝴蝶结型(bow-tie) scc为连通部分 in中网页指向scc scc指向out中网页 非连通部分(tendrils),北京大学软件与微电子学院2009年度课程,11,信息采集的基本结构,北京大学软件与微电子学院2009年度课程,12,采集的遍历算法,宽度优先 vs. 深度优先 宽度优先：先采集完同一层的网页，再采集下一层网页 深度优先：先沿一条路径采到叶节点，再从同层其他路径进行采集 有研究表明：宽度优先的方法得到的网页集合的重要性更好 网站采集 vs. 全局url采集 网站采集：一个网站一个网站采集 全局url采集：将所有url放入一个url池，从中使用某种方法进行选择 网站采集在支持应用方面灵活性大一些，但是采集效率可能不如全局url采集，通常的搜索引擎采用全局url采集的方法。,北京大学软件与微电子学院2009年度课程,13,采集网页的更新策略,定期重采：一段时间以后重新采集所有网页，全部采完以后替换原来的网页 增量采集：只按照某种策略采集那些可能新增、变化的网页，并删除那些已经不存在的网页 定期重采非常简单，但是浪费带宽，周期也长；增量采集可以节省带宽，网页更新周期相对较短，但是系统的复杂性增大。,北京大学软件与微电子学院2009年度课程,14,采集网页的速度保证措施,本地dns解析 多机分布式并行 局域网联接多机进行采集并行 广域网分布式采集 单机多程序并行 多进程并行 多线程并行,北京大学软件与微电子学院2009年度课程,15,采集网页的质量保证措施,减少重复页面的采集 url重复的检测和排除 内容重复的检测和排除 保证重要页面的高优先级 入度高的网页相对重要 url浅的网页相对重要 含有被别人广泛映像的内容的网页重要,北京大学软件与微电子学院2009年度课程,16,采集中的“礼貌”问题,遵守网站上发布的robot.txt 采集限制协议 采集时尽量不要太过密集地采集某个网站，这种密集访问类似于dos攻击，导致普通用户正常浏览网站产生困难。有些网站会严密控制这种密集访问行为。,北京大学软件与微电子学院2009年度课程,17,信息采集的研究趋势,高速、高质量信息采集 个性化信息采集 只采集符合用户的兴趣的数据 基于主题的信息采集 采集某个领域的数据 信息采集及抽取 采集后提取结构化信息,北京大学软件与微电子学院2009年度课程,18,主要内容,信息采集技术(information gathering) 信息的组织和索引(information organization&indexing) 相似度计算信息检索模型(ir models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(evaluation),北京大学软件与微电子学院2009年度课程,19,信息的组织和索引(information organization&indexing),北京大学软件与微电子学院2009年度课程,20,提纲,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2009年度课程,21,课前思考题,google号称80亿网页，baidu也有10亿网页，数量可谓巨大，但是当我们输入一个查询时，返回时间往往不到1秒，为什么这么快？奥秘在哪里？ 什么情况下使用字符串匹配？ 什么情况下使用前向索引？ 什么情况下使用倒排索引？倒排索引的生成过程如何？,北京大学软件与微电子学院2009年度课程,22,引言,检索面对的搜索基本问题：给定一个查询串，在文档集合里面搜索出现这些查询串的文档。 解决该问题的效率将影响检索的效率。,北京大学软件与微电子学院2009年度课程,23,提纲,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2009年度课程,24,基于字符串匹配的搜索,定义：给定一个子串q,在字符串d中查找q所有出现的位置(有时只要判断是否出现即可)。q的长度假设为m，d的长度假设为n。 搜索问题转化为对每个查询q，在文档集合中搜索出现查询q的文档。 当文档集合规模不大时，通过字符串定位可以实现检索。如小型网站的全文检索。 优点： 方法简单易行 很方便地支持文档更新(增加和删除) 缺点： 效率不高。,北京大学软件与微电子学院2009年度课程,25,brute force方法,假设文档长度为n，子串长度为m，用子串逐一试探，一旦不能匹配则往后移动一位继续匹配，相当于一个窗口不断滑动。 例子： 查询：中国 文档：那一位同行来自中国北京。 算法复杂度：(不考虑分词)最坏情况下时间复杂度o(mn)，最好情况下o(n+m),北京大学软件与微电子学院2009年度课程,26,kmp方法,knuth & morris & pratt发现，简称kmp方法。数据结构中的经典算法。 通过重用先前的匹配信息，减少滑动的次数，从而提高效率。 具体地：先预先求出模式串每个位置的next函数。匹配过程中一旦匹配失败则利用next函数滑动窗口进行匹配。 算法复杂度：最坏情况下仍然是o(mn)，但是在一般情况下的实际执行时间是o(m+n)。特别适合于模式串和文本串之间存在许多“部分匹配”的情况。整个匹配过程中，指向文本串的指针不需要回溯。,北京大学软件与微电子学院2009年度课程,27,其他方法及其他匹配方式,aho-corasick (ac) boyer-moore(bm) shift-or 多模式匹配 正则表达式匹配 模糊匹配、容错近似匹配,北京大学软件与微电子学院2009年度课程,28,提纲,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2009年度课程,29,前向索引(1),直接对一篇篇文本扫描费时费力，能不能预先将文本处理一下进行匹配？答案是肯定的！ 前向索引(forward index) ：将每篇文档表示成 docid 及其文本内容组成的类向量模式。,北京大学软件与微电子学院2009年度课程,30,前向索引(2),文档1：b d a b b c b a d c 文档2：a b c d a c d b d a b (注意：例子中为简化起见，用每个字母代表一个字符串索引单位),文档1,文档2,a,3,8,b,1,4,c,6,10,d,2,9,a,1,5,b,2,8,c,3,6,d,4,7,5,7,10,11,9,北京大学软件与微电子学院2009年度课程,31,前向索引(3),仍然是依次扫描每个文档，但是对于一个字符串的多次出现不需要一一扫描，而且对同一文档内的字符串查找可以采用二分查找的方式，加快匹配过程。也就是说通过预处理的方式加快对每篇文档的匹配速度。,北京大学软件与微电子学院2009年度课程,32,倒排索引(1),使用前向索引，仍然需要一篇篇扫描每个文档，如果文档数目较多，那么就非常费时费力。 能不能有一种方法能够直接从查询词定位到文档？答案是当然有了，这就是倒排索引(inverted index)。,北京大学软件与微电子学院2009年度课程,33,倒排索引(2),文档1：b d a b b c b a d c 文档2：a b c d a c d b d a b,文档id号,偏移位置,dictionary,posting list,北京大学软件与微电子学院2009年度课程,34,倒排索引(3),一本书中倒排索引的例子,北京大学软件与微电子学院2009年度课程,35,倒排索引(4),对于单个查询词，搜索就是词典查找的过程，不需要扫描所有文档，只需要访问这个词对应的posting list，速度相当快。,北京大学软件与微电子学院2009年度课程,36,建立倒排索引的大致过程,索引源,预处理,分词,排序,写临时索引文件,合并临时索引文件,索引压缩,写索引文件,北京大学软件与微电子学院2009年度课程,37,中文分词(chinese word segmentation),对于中文，分词的作用实际上是要找出一个个的索引单位 例子：李明天天都准时上班 索引单位 字：李 明 天 天 都 准 时 上 班 索引量太大，查全率百分百，但是查准率低，比如查“明天” 这句话也会出来 词：李明 天天 都 准时 上班 索引量大大降低，查准率较高，查全率不是百分百，而且还会受分词错误的影响，比如上面可能会切分成：李 明天 天都 准时 上班 字词混合方式,北京大学软件与微电子学院2009年度课程,38,英文词根还原(stemming),进行词根还原：stop/stops/stopping/stoppedstop 好处：减少词典量；坏处：按词形查不到，词根还原还可能出现错误 不进行词根还原： stoppedsto+ppe+d 好处：支持词形查询；坏处：增加词典量,北京大学软件与微电子学院2009年度课程,39,停用词消除,停用词(stop words)是指那些出现频率高但是无重要意义，通常不会作为查询词出现的词，如“的”、“地”、“得”、“都”、“是”等等 消除：通常是通过查表的方式去除，去除的好处-大大较少索引量，坏处-有些平时的停用词在某些上下文可能有意义 保留：索引空间很大,北京大学软件与微电子学院2009年度课程,40,排序,排序就是扫描每篇文档产生的（文档号，单词号，出现位置）三元组按照单词号重新排序，单词号相同的项再按照文档号排序，单词号和文档号都相同的再按照出现位置排序。 排序的过程正好是实现“倒排”的过程 排序以后的结果写入临时索引文件。,北京大学软件与微电子学院2009年度课程,41,排序举例(1),文档1 b d a b b c b a d c 文档2 a b c d a c d b d a b,北京大学软件与微电子学院2009年度课程,42,排序举例(2),对文档1分析产生的三元组如下 b d a b b c b a d c (文档号，单词号，位置） (1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10),北京大学软件与微电子学院2009年度课程,43,排序举例(3),对文档2分析产生的三元组如下 a b c d a c d b d a b (文档号，单词号，位置） (2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5) (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b,11),北京大学软件与微电子学院2009年度课程,44,排序举例(4),(1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10),(2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5) (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b,11),(1,a,3) (1,a,8) (2,a,1) (2,a,5) (2,a,10) (1,b,1) (1,b,4) (1,b,5) (1,b,7) (2,b,2),(2,b,8) (2,b,11) (1,c,6) (1,c,10) (2,c,6) (1,d,2) (1,d,9) (2,d,4) (2,d,7) (2,d,9),北京大学软件与微电子学院2009年度课程,45,写入临时索引文件,(1,a,3) (1,a,8) (2,a,1) (2,a,5) (2,a,10) (1,b,1) (1,b,4) (1,b,5) (1,b,7) (2,b,2),(2,b,8) (2,b,11) (1,c,6) (1,c,10) (2,c,6) (1,d,2) (1,d,9) (2,d,4) (2,d,7) (2,d,9),北京大学软件与微电子学院2009年度课程,46,合并多个临时索引文件,一批文档(例如：50mb)产生一个索引文件 多批之间通过合并产生一个大的临时文件 如果不合并，可以建立通过文档进行分割的分布式索引 也可以合并以后，按照词典进行分割,文档1，2，m,文档m+1，m+2，2m,词1，2，n,词n+1，n+2，2n,北京大学软件与微电子学院2009年度课程,47,索引压缩,理论上，(全文)索引的大小和原始文件相当，因为每个词的每次出现都必须在posting list中记录。 需不需要压缩？ 要压缩：索引大小通常和原始文本大小相当，不压缩可能会耗费大量存储开销 不压缩：硬盘很便宜，数据量不是特别大，而且不需要解压缩的消耗,北京大学软件与微电子学院2009年度课程,48,倒排索引的更新,情况一：出现了新的词，则需要修改词典结构，在词典中增加词条。 情况二：出现了新的文档，则在相应的词条下增加posting list。 情况三：某些文档不复存在，则在相应的位置进行标记，等积累到一定时期进行一次性操作。,北京大学软件与微电子学院2009年度课程,49,词典的组织,顺序排序数组：采用字典序，查找采用二分法。空间消耗小，查找较快，但是插入删除麻烦。 二叉搜索树、b树、trie树等。 hash表：通过hash函数直接把词映射到地址，空间消耗和hash函数设计有关。较快，插入删除容易。,北京大学软件与微电子学院2009年度课程,50,布尔查询的处理,and 关系：a and b，取出a、b的posting list进行交叉合并。 or 关系：a or b，取出a、b的posting list进行叠加。 not 关系：a and not b，取出a、b的posting list进行减操作。,北京大学软件与微电子学院2009年度课程,51,短语查询的处理,比如查ab，取出a、b的posting list，然后进行交叉合并，并且合并时要满足位置相邻的关系。,北京大学软件与微电子学院2009年度课程,52,小结,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2009年度课程,53,主要内容,信息采集技术(information gathering) 信息的组织和索引(information organization&indexing) 相似度计算信息检索模型(ir models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(evaluation),北京大学软件与微电子学院2009年度课程,54,相似度计算-信息检索模型,北京大学软件与微电子学院2009年度课程,55,提纲,模型定义及分类 布尔模型 向量空间模型 概率模型 统计语言建模ir模型,北京大学软件与微电子学院2009年度课程,56,信息检索模型,信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。 本质上是对相关度建模。 信息检索模型是ir中的核心内容之一。,查询表示,文档表示,相关度计算,原始文档,原始查询,北京大学软件与微电子学院2009年度课程,57,相关概念,标引项(index term) 文档表示成多个term的集合 通常用词来表示，但是也可以用其他语言单位来表示 关键词 (key words) 可以看成term的一种 标引项的权重(weight) 不同标引项作用是不同的 通过权重加以区分,北京大学软件与微电子学院2009年度课程,58,信息检索模型分类,从所使用的数学方法上分： 基于集合论的ir模型(set theoretic models) 布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4) 基于代数论的ir模型(algebraic models) 向量空间模型(2) 潜性语义索引模型 (5) 基于概率统计的ir模型(probabilistic models) 回归模型(6) 二值独立概率模型(7) 语言模型建模ir模型(8),北京大学软件与微电子学院2009年度课程,59,信息检索模型分类,从所使用的数学方法上分： 基于集合论的ir模型(set theoretic models) 布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4) 基于代数论的ir模型(algebraic models) 向量空间模型(2) 潜性语义索引模型 (5) 基于概率统计的ir模型(probabilistic models) 回归模型(6) 二值独立概率模型(7) 语言模型建模ir模型(8),北京大学软件与微电子学院2009年度课程,60,集合(直观描述),具有某种属性的对象总体(通常用大写字母表示，如a,b等)，这些对象称为其元素 (通常用小写字母表示，如x,y等). x是a的元素记为: xa (读作x属于a) x不是a的元素记为: xa (读作x不属于a) 集合的基本特性是，对于给定的集合a，任何对象x, xa与xa中有且只有一个成立.,北京大学软件与微电子学院2009年度课程,61,集合的并运算和交运算,集合a和b的并是由a或b的所有元素组成的集合, 记为ab, 也就是 ab=x | xa或xb 集合a和b的交是由所有a和b的公共元素组成的集合, 记为a b, 也就是 a b=x | xa且xb,北京大学软件与微电子学院2009年度课程,62,集合的差运算和余(补)运算,集合的差运算：由集合a中不在集合b中的元素所组成的集合叫做集合a与集合b的差，记作ab(有时也记作a-b), 也就是 ab=xa | xb 设集合ae, ea叫做a关于e的余集，当e是公认的时候，简称为a的余集(补集)，记为 。,北京大学软件与微电子学院2009年度课程,63,布尔代数,布尔变量：只有“真”、“假”取值的变量 如：命题 一篇文档中存在“世界杯”这个词 的结果变量就是一个布尔变量(存在 则取真，否则 取假)。 计算机中常常用1表示“真”true，0表示“假”false 布尔操作(关系)： 与(and)：(a and b) = true iff a=true and b=true 或(or) ： (a or b) = true iff a=true or b=true 非(not) ：(not a) = true iff a=false 布尔表达式：多个布尔变量之间通过布尔操作组成的表达式 如： a and (b or c) and not d 蕴含：两个布尔表达式p、q，如果a为true，那么q为true，则称p蕴含q，记为pq,北京大学软件与微电子学院2009年度课程,64,布尔模型,布尔模型：查询和文档均表示为term(“是否存在”)的布尔表达式，其中文档表示成所有term(存在)的“与”关系布尔表达式。 例子(因不会产生歧义，以下例子直接用term进行布尔操作)： 查询： 2006 and 世界杯 and not 小组赛 文档1： 2006年世界杯在德国举行。 文档2： 2006年世界杯小组赛已经结束。 相似度计算：查询布尔表达式和所有文档的布尔表达式进行匹配，匹配成功的文档的得分为1，否则为0。 类似于传统数据库检索，是精确匹配,北京大学软件与微电子学院2009年度课程,65,布尔模型匹配的集合表示,2006,世界杯,小组赛,2006 and 世界杯 and not 小组赛,北京大学软件与微电子学院2009年度课程,66,布尔模型(续),形式化表示： 任一布尔查询都可以写成析取范式(dnf)：如 q=a(bc)=abcab ca b c 任一文本可以写成所有term的交，如 doc=a b c d e 因为doc(蕴含)q，所以相似度为1,北京大学软件与微电子学院2009年度课程,67,课堂思考题,想查关于2006年超女 6进5 比赛的新闻，用布尔模型怎么构造查询？,北京大学软件与微电子学院2009年度课程,68,我的解答,(2006 or 今年) and (超级女声 or 超女 or 超级女生) and (6进5 or 六进五 or 六 and 进 and 五) 表达式相当复杂，构造困难！ 不严格的话结果过多，而且很多不相关；非常严格的话结果会很少，漏掉很多结果。,北京大学软件与微电子学院2009年度课程,69,google检索结果,北京大学软件与微电子学院2009年度课程,70,布尔模型的优缺点,优缺点 优点： 简单：现代很多搜索引擎中仍然包含布尔模型的思想，如google的高级检索 自我保护功能：暗暗地降低用户对搜索系统的期望，使自己不在责任方，检索结果不好的原因在于用户构造查询不好 缺点： 只能严格匹配(得分不是0就是1)，不能近似或者部分匹配，多个结果无法排序 一般用户构造查询不是很容易，构造不利可能造成结果过多或者过少,北京大学软件与微电子学院2009年度课程,71,信息检索模型分类,从所使用的数学方法上分： 基于集合论的ir模型(set theoretic models) 布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4) 基于代数论的ir模型(algebraic models) 向量空间模型(2) 潜性语义索引模型 (5) 基于概率统计的ir模型(probabilistic models) 回归模型(6) 二值独立概率模型(7) 语言模型建模ir模型(8),北京大学软件与微电子学院2009年度课程,72,向量,向量(矢量，vector)：既有大小又有方向的量，通常用有向线段表示，记作 或者 考虑从空间坐标系原点出发(其他向量可以平移到原点出发)的向量 ，终点坐标为，我们称之为一个n维向量 向量的运算：加、减、倍数、内积,北京大学软件与微电子学院2009年度课程,73,向量的模、距离和夹角,向量的模(大小)： 向量的(欧氏)距离 夹角,北京大学软件与微电子学院2009年度课程,74,向量空间模型,向量空间模型(vector space model，vsm)是康奈尔大学 salton等人上世纪70年代提出并倡导，原型系统smart* term独立性假设：term在文档中的出现是独立、互不影响的。 查询和文档都可转化成term及其权重组成的向量表示，都可以看成空间中的点。向量之间通过距离计算得到查询和每个文档的相似度。,*可从/pub/smart/下载全部源码和相关语料,北京大学软件与微电子学院2009年度课程,75,文档-标引项矩阵(doc-term matrix),n篇文档，m个标引项构成的矩阵am*n，每列可以看成每篇文档的向量表示，同时，每行也可以可以看成标引项的向量表示。,北京大学软件与微电子学院2009年度课程,76,一个例子,查询q：(,) 文档d1：(,) 文档d2：(,),北京大学软件与微电子学院2009年度课程,77,一个例子(续),查询和文档进行向量的相似度计算： 采用内积： 文档d1与q的内积：1*1+3*2=7 文档d2与q的内积：2*2=4 夹角余弦： 文档d1与q的夹角余弦： 文档d2与q的夹角余弦：,北京大学软件与微电子学院2009年度课程,78,vsm中三个关键问题,标引项term的选择 权重计算(term weighting)：即计算每篇文档中每个term的权重 查询和文档的相似度计算(similarity computation),北京大学软件与微电子学院2009年度课程,79,term的选择,term是能代表文档内容的特征 term粒度：term可以是字、词、短语、n-gram或者某种语义单元(比如：所有同义词作为1维)，最简单的是采用全文标引(full text indexing)，即用文档中出现的所有的字或者词作为标引词。 降维：vsm中向量的维数很大(以中文词索引为例，向量维数会上10万)时，往往也同时引入了很多噪音。因此，实际应用中，会采用一些降维策略(如：去停用词、对英文进行词干还原、只选择名词作为term、将term聚成的不同类作为一个个term、选择出现次数较多的词作为term等等),北京大学软件与微电子学院2009年度课程,80,权重计算,布尔权重：term i在文档j中的权重aij=0 or 1 (出现则取1，否则取0) tf权重：tf (term frequency)是term在文档中出现的次数。权重aij=tfij 或者归一化后的tf值 tf的归一化(normalization) ：将一篇文档中所有term的tf值归一化到0,1之间。通常可以采用以下三种方式之一： maximum normalization 1,2,1,0,40.25,0.5,0.25,0,1 augmented maximum normalization 1,2,1,0,40.625,0.75,0.625,0.5,1 cosine normalization 1,2,1,0,40.213,0.426,0.213,0.0.852,北京大学软件与微电子学院2009年度课程,81,权重计算(续),idf权重： term的文档频率df(document frequency)：term 在整个文档集合中出现的文档篇数。df反映了term的区分度，df越高表示term越普遍，因此其区分度越低，因此权重也越低。 逆文档频率(inverse df，idf)：df的倒数，通常采用如下公式进行计算(n是文档集合中所有文档的数目)： 向量空间模型中通常采用tf*idf的方式计算权重。即term i在文档dj中的权重aij=tfij *idfi,北京大学软件与微电子学院2009年度课程,82,权重计算(续),对tf或idf的缓冲 对tf进行缓冲：1+log(tf), 1+log(1+log(tf) 对idf进行缓冲：1+log(n/df) log的作用：将值域拉平，使得函数的变化更平缓(常常以e为底，即ln) 加1的作用：平滑,北京大学软件与微电子学院2009年度课程,83,权重计算(续),文档长度因素 文档长度大小不一 某个term第二次出现不如第一次出现信息量大 关于文档长度的两个观点： 长文档具有更多的词 长文档具有更多的信息 因此常常需要对长文档进行惩罚，对短文档进行补偿。(不同的相似度计算方法下得到的结论不尽如此，也会采用不同的归一化方法) pivoted normalization*：1-b+b*doclen/avgdoclen (b在01之间),*singhal, a., buckley, c., mitra, m. (1996): pivoted document length normalization, in proceedings of sigir96,北京大学软件与微电子学院2009年度课程,84,权重计算模式-tf,注：smart系统中定义,北京大学软件与微电子学院2009年度课程,85,权重计算模式-idf,北京大学软件与微电子学院2009年度课程,86,权重计算模式-length,北京大学软件与微电子学院2009年度课程,87,权重计算模式,lnc表示 tf采用l、idf采用n、长度归一化采用c模式 查询和文档的表示可以采用不同的模式，而且一些实验表明这些模式更优，如lnc-ltc表示文档采用lnc，查询采用ltc,北京大学软件与微电子学院2009年度课程,88,相似度计算,北京大学软件与微电子学院2009年度课程,89,vsm的发展,向量空间模型经过不断发展，也提出了很多公式，下面是一个最常用的公式：,tfdoc,idf,tfq,长度规整,公式(1),北京大学软件与微电子学院2009年度课程,90,vsm的优缺点,优点： 简洁直观，可以应用到很多其他领域(文本分类、生物信息学)。 支持部分匹配和近似匹配，结果可以排序 检索效果不错 缺点： 理论上不够：基于直觉的经验性公式 标引项之间的独立性假设与实际不符：实际上，term的出现之间是有关系的，不是完全独立的。如：“王励勤” “乒乓球”的出现不是独立的。,北京大学软件与微电子学院2009年度课程,91,课堂思考题,判断两段程序之间是否存在抄袭？,北京大学软件与微电子学院2009年度课程,92,我的解答,比如对每段程序建立一个向量，然后进行向量相似度计算。如果相似度大于某个阈值，则认为可能抄袭。,北京大学软件与微电子学院2009年度课程,93,课后练习(暂停),对于下列例子，分别用夹角余弦方式(向量的分量采用tf表示)和公式(1)进行计算 (s=0.2，文档长度以字节数表示，1个汉字以2个字节计算，不含标点和空格)，写出计算过程，并判断哪篇文档和查询q更相关(不去除停用词)。 查询q：2006 世界杯 举办地 文档d1：2006 世界杯 在 德国 举行，本届 世界杯 的 冠军 是 意大利 队。 文档d2：2002 世界杯 在 韩国 和 日本 举行，最后 的 冠军 得主 是 巴西 队。,北京大学软件与微电子学院2009年度课程,94,信息检索模型分类,从所使用的数学方法上分： 基于集合论的ir模型(set theoretic models) 布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4) 基于代数论的ir模型(algebraic models) 向量空间模型(2) 潜性语义索引模型 (5) 基于概率统计的ir模型(probabilistic models) 回归模型(6) 二值独立概率模型(7) 语言模型建模ir模型(8),北京大学软件与微电子学院2009年度课程,95,布尔模型回顾,查询为布尔表达式，每个文档也是布尔表达式，相似度计算的过程实际是布尔表达式的匹配过程，结果要么是1要么是0。 缺点：不能对结果进行排序，不支持部分匹配和模糊匹配。 以下讲到的基于模糊集的ir模型和扩展布尔模型都是针对上述缺点对原始布尔模型进行改进。,北京大学软件与微电子学院2009年度课程,96,普通集合,对于论域u上的一个子集a，可以定义函数： 该函数刻画了论域u上的元素x到a的隶属度，当隶属度为1时， x属于a，当隶属度为0时，x不属于a，该函数是二值函数 例子：“大于1的实数”用集合表示为 a=x|x1, xr,北京大学软件与微电子学院2009年度课程,97,模糊集合,模糊集合论对于论域u上的一个“模糊子集” a，可以定义函数： 该函数刻画了论域u上的元素x到a的隶属度，函数值域为0,1 。 例子：“所有比1大得多的实数” 用模糊集a可以定义为：,北京大学软件与微电子学院2009年度课程,98,模糊集隶属函数的性质,模糊集合也存在非、并、交等运算，它们满足：,北京大学软件与微电子学院2009年度课程,99,基于模糊集的ir模型,对于文档集合d1,d2,dn，term集合t1,t2,tm 第一步，定义term之间的关系：建立一部相关性词典，定义所有term和term之间的相关性。ti和tl的相关性ci,l可以通过下式计算(下式实际计算的是共现频率，ci,l取值范围为0,1)：,北京大学软件与微电子学院2009年度课程,100,基于模糊集的ir模型(续),第二步，定义term和文档之间的关系：对于一个ti建立一个模糊集合ai，其元素是所有文档集合，其中每个文档dj对该模糊集ai的隶属度通过下式计算(dj中和ti越相关的term越多，函数值越大)：,北京大学软件与微电子学院2009年度课程,101,基于模糊集的ir模型(续),最后，定义查询q和文档dj之间的关系，查询q对应一个模糊集合，求每个文档dj的隶属度。 例子：对于布尔查询 q=a (b c)，可以求得其dnf范式 q=abcab ca b c，则dj的隶属度函数可以用下式计算(计算时使用代数和与积取代max和min),北京大学软件与微电子学院2009年度课程,102,基于模糊集的ir模型的优缺点,优点： 克服原始布尔模型不能部分匹配的缺点 缺点： 通常在模糊集研究领域涉及，在ir领域不流行 缺乏大规模语料上的实验证实其有效性,北京大学软件与微电子学院2009年度课程,103,信息检索模型分类,从所使用的数学方法上分： 基于集合论的ir模型(set theoretic models) 布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4) 基于代数论的ir模型(algebraic models) 向量空间模型(2) 潜性语义索引模型 (5) 基于概率统计的ir模型(probabilistic models) 回归模型(6) 二值独立概率模型(7) 语言模型建模ir模型(8),北京大学软件与微电子学院2009年度课程,104,扩展布尔模型,基本想法：在布尔模型的基础上加入向量空间模型的一些思想。 和vsm一样，首先将每篇文档表示成n维空间上的一个点，比如：文档dj中term x 对应的分量可以这样计算：,北京大学软件与微电子学院2009年度课程,105,扩展布尔模型(续),or情况处理：对于布尔查询q=kx or ky情况的处理，由于(0,0)是尽量避免的点，因此可以定义(0,0) 到(wx,wy)(简单计为(x,y)的距离并归一化来计算文档和查询的相似度,北京大学软件与微电子学院2009年度课程,106,扩展布尔模型(续),and情况处理：对于布尔查询q=kx and ky情况的处理，(1,1)是最希望达到的点，因此可以定义1减去(1,1) 到(wx,wy)(简单计为(x,y)的距离并归一化来计算相似度,北京大学软件与微电子学院2009年度课程,107,扩展布尔模型(续),在多维空间上可以通过计算欧式距离归一化对二维平面的情况进行扩展,北京大学软件与微电子学院2009年度课程,108,扩展布尔模型(续),p-norm 模型不使用欧氏距离，而是使用p-距离(p是引入的参数，p=1,也可以是无穷大) 查询分别为： 这样，相似度计算公式为：,北京大学软件与微电子学院2009年度课程,109,扩展布尔模型(续),对于p-norm模型，p=1时，相似度计算公式类似于向量模型，p=时，类似于基于模糊集的ir模型。,北京大学软件与微电子学院2009年度课程,110,扩展布尔模型的优缺点,优点：提供了一个统一的框架，将向量空间模型、基于模糊集的模型都包括在一个框架内。 缺点：不够自然简洁，目前在ir领域使用较少。,北京大学软件与微电子学院2009年度课程,111,信息检索模型分类,从所使用的数学方法上分： 基于集合论的ir模型(set theoretic models) 布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4) 基于代数论的ir模型(algebraic models) 向量空间模型(2) 潜性语义索引模型 (5) 基于概率统计的ir模型(probabilistic models) 回归模型(6) 二值独立概率模型(7) 语言模型建模ir模型(8),北京大学软件与微电子学院2009年度课程,112,向量空间模型回顾,vsm中将每篇文档看成多个term为坐标轴的空间上的点 vsm假设多个term之间的出现是互相独立的，这与实际情况显然不符 隐性语义索引(latent semantic indexing)就是这方面的一个尝试。,北京大学软件与微电子学院2009年度课程,113,文档-标引项矩阵(doc-term matrix),n篇文档，m个标引项构成的矩阵am*n，每列可以看成每篇文档的向量表示，每行可以看成标引项的向量表示。ata是n*n对称矩阵，其中每个元素表示文档两两之间的相似度，aat是m*m对称矩阵，其中每个元素表示term两两之间的相似度。,北京大学软件与微电子学院2009年度课程,114,隐性语义索引(lsi),向量空间模型中向量表示中的其他问题： 一词多义polysemy: java (language/island) 一义多词synonymy: 电脑 计算机 词并不等价于概念或者语义 lsi susan dumais 等人提出* 利用数学中的svd分解，重新表征标引项 去掉噪音,*dumais, s. t., furnas, g. w., landauer, t. k. and deerwester, s. (1988), “using latent semantic analysis to improve information retrieval.“ in proceedings of chi88: conference on human factors in computing, new york: acm, 281-285.,北京大学软件与微电子学院2009年度课程,115,奇异值分解(singular value decomposition，svd),am*n=usvt ，u为m*r矩阵，s为r*r对角且从左上到右下降序排列的方阵，对角线上的值称为singular value。v为n*r矩阵。r是a的秩。uut=im*m，vvt=in*n。svd分解结果唯一。,t1 tm,d1 dn,北京大学软件与微电子学院2009年度课程,116,去掉噪音,s中从左上角到右下角只选择较大的k个singular value，得到方阵s。同样u取前k列，v取前k列分别得到u和v，令a=usvt，a是a的近似 ata表示文档两两之间的相似度，将查询q看成一个虚拟文本向量放入，经过lsa得到a，将q向量和其他文档向量进行向量计算，则可以得到该查询和所有文档的相似度。,t1 tm,d1 dn,北京大学软件与微电子学院2009年度课程,117,新矩阵a,新矩阵a是a的一个k-秩近似矩阵，它在最小平方意义下最接近原始矩阵，即最优的近似矩阵。 a包含了a的主要结构信息，可以理解为对a的重构，它忽略了词项使用上的噪音数据，由于维数的降低，近似的词项被合并。如：同义词在k维空间中有相似的表示。 并且在这个k维空间中，出现在相似文档中的词项也将是近似的，即使它们从未出现在同一个文档中。lsi构造了新的语义空间，具备“概念检索”的特征。,北京大学软件与微电子学院2009年度课程,118,新空间下的表示,北京大学软件与微电子学院2009年度课程,119,svd更新策略,svd更新策略：对已经进行了奇异值分解的词频矩阵，若有新的文档或词项加入，主要有两种方法进行svd更新：重新计算svd或者直接加入。 直接加入是一种简单的更新策略，如图分别为直接加入p个文档或q个词项。,北京大学软件与微电子学院2009年度课程,120,svd更新策略,北京大学软件与微电子学院2009年度课程,121,k值的选取,北京大学软件与微电子学院2009年度课程,122,一个例子,label course title c1 parallel programming languages systems c2 parallel processing for noncommercial applications c3 algorithm design for parallel computers c4 networks and algorithms for parallel computation c5 application of computer graphics c6 database theory c7 distributed database systems c8 topics in database management systems c9 data organization and management c10 network theory c11 computer organization,注：该例子取自jianyun nie老师的ppt,北京大学软件与微电子学院2009年度课程,123,结果,a,t1= parallel t2=algorithm t3=system t4=compute t5=network t6=application t7=database t8=theory t9=manage t10=organization,北京大学软件与微电子学院2009年度课程,124,有关lsi的实验结论,svd非常耗时，目前还没有特别快的方法 k通常取经验值(2001000) 在一些小规模语料(如ca