陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org 现代信息检索 陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org.

Presentation on theme: "陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org 现代信息检索 陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org."— Presentation transcript:

1 陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org
现代信息检索 陆铭 mingler.ccshu.org

2 课程总结1 课程概况(About the course)
本课程的教学目标是培养学生了解信息检索工具的基本原理和技术，使学生能够进行较深层的研究或应用开发 本课程不是一门讲授使用信息检索方法的课程，本课程是研究信息检索的技术实现的一门基础课程

3 课程总结2 课程核心内容 检索理论 文本检索 网络检索 信息自动处理和系统评价 多媒体检索 数字图书馆 IR模型的形式化表示和类型，经典模型
检索语言，互操作，自然语言、本体论 文本检索 经典、现代文本处理和全文文本处理，分类和聚合 网络检索 网络检索、 PageRank和HITS算法 信息自动处理和系统评价 可视化、自动文摘、评价 多媒体检索 模型与语言，标引与检索，并行于分布式检索 数字图书馆 OPAC，文献模型、表达与存取，元数据，查新及数据库检索技能

4 课程总结3 授课方式 考核方式 成绩构成 自学与课堂讨论相结合 课堂讲述和课后练习相结合 课程论文 平时成绩：课堂讨论与1篇小论文，30%
课后练习主要是阅读文献和进行文献综述 考核方式 课程论文 按发表要求写作，课程结束，论文录用 成绩构成 平时成绩：课堂讨论与1篇小论文，30% 考试：1篇课程论文（约4000字），70%

5 课程总结4 研究历史和现状 1948年C. N. Mooers在其MIT硕士论文中第一次使用了“Information Retrieval”这个术语 1960－70年代在建立文摘检索系统中，产生了布尔模型(Boolean Model)、向量空间模型(Vector Space Model)和概率检索模型(Probabilistic Model) 1980年代出现商用数据库检索系统：Dialog，ORBIT, MEDLINE 1990’s第一个网络搜索工具：1990年加拿大蒙特利尔大学开发的FTP搜索工具Archie

6 课程总结5 研究历史和现状 第一个WEB搜索引擎： 1990年代推荐系统的出现：Ringo，Amazon，NetPerceptions
1994年美国CMU开发的Lycos 1995斯坦福大学博士生开发Yahoo 1998斯坦福大学博士生开发的Google，提出PageRank计算公式 1998年基于语言模型的IR模型提出 1990年代推荐系统的出现：Ringo，Amazon，NetPerceptions 文本分类和聚类的使用、信息抽取：Whizbang

7 课程总结6 研究历史和现状 2000’s的重要事件 2000’s以来的其他重要事件
文本检索会议TREC(Text Retrieval Conference )的发展 问答系统评测专项Q/A track(Question Answering Track) 2001年，百度成立 2000’s以来的其他重要事件 多媒体IR，Image，Video，Audio and music 跨语言IR，DARPA Tides，文本摘要，DUC评测

8 国际著名研究机构和代表人物 美国康奈尔大学Salton(1927-1995) 英国剑桥大学SparckJones (1935-2007)
现代信息检索的奠基人 SMART的完成人 第一任Salton奖得主，ACM Fellow 英国剑桥大学SparckJones ( ) 概率检索模型的提出者之一 NLP和IR中的先辈 曾获ACL终身成就奖和Salton奖

9 国际著名研究机构和代表人物 美国UMassCIIR W. B. Croft，ACM Fellow
和CMU共同开发了Lemur工具 Salton奖得主 英国Glasgow大学Rijsbergen，ACM Fellow 信息检索逻辑推理学派的提出者和倡导者 现在试图用量子物理的方法解决IR问题 英国微软剑桥研究院、伦敦城市大学Robertson 概率检索模型的倡导者 开发了OKAPI 美国卡耐基-梅隆大学（简称CMU） TRECVID是影视检索领域中的国际性权威评测，由美国国家标准技术研究所组织实施。美国国家标准技术研究所向世界各国的大学和公司的参评. 在前三届所有子任务的评测中，前三名都被IBM Watson研究中心和卡耐基·梅隆大学(CMU)等著名大学和研究机构所垄断 2006年4月26日 ，微软亚洲研究院共有17篇高质量的论文分别入选三大国际顶级学术会议——2006国际图形学年会（ACM SIGGRAPH 2006）、2006国际信息检索年会（ACM SIGIR 2006）

10 国际著名研究机构和代表人物 美国CMU 美国UIUC 微软研究院 IBM研究院 Google研究院

11 一些活跃的华裔学者 加拿大蒙特利尔大学聂建云教授 美国UIUC ChengxiangZhai博士 美国CMU YimingYang教授
跨语言检索 IR模型 美国UIUC ChengxiangZhai博士 美国CMU YimingYang教授 文本分类 台湾中研院简立峰 号称“中文搜索”第一人 加入Google研究院 聂建云博士是加拿大蒙特利尔大学计算机系教授。他毕业于东南大学，随后赴法国留学。博士毕业后，自1991年起在蒙特利尔大学任教至今。聂建云教授一直从事信息检索及相关领域的研究，其中包括信息检索理论模型，推理式智能检索系统，跨语言和多语言信息个人主页： Chengxiang Zhai 伊大计算机系、基因生物学学院、图情学院教授. 曾获2004科学与工程总统奖（美国国家科学基金会提名），2004计算机机器协会. 最佳论文奖，美国国家科学基金会职业奖，伊大2006春季最佳教

12 国内活跃的研究机构 软件端 应用端 武汉大学信息管理学院 中山大学信息管理系 南京大学信息管理系 清华大学计算机科学与技术系
北京大学，复旦大学，清华大学，哈尔滨工业大学，中科院计算所，中科院软件所，中科院自动化所 应用端 武汉大学，南京大学，北京大学 武汉大学信息管理学院 网络信息检索、情报检索模型理论、信息过滤、 文本知识的自动分类 中山大学信息管理系 网络信息过滤 南京大学信息管理系 文本信息检索 清华大学计算机科学与技术系 文本自动分类，自动文摘 复旦大学计算机系 文本过滤、音频视频检索 中国科学院计算技术研究所 文本自动分类、文本检索、知识网格 北京大学信息管理系 图像检索、文本检索 南京农业大学信息管理系 中文信息自动分类

13 一些重要的会议 国际会议： 国内会议： SIGIR、ACL、WWW、SIGKDD CIKM、ICML TREC AIRS
全国信息检索及内容安全学术会议(2年一届) 全国计算语言学联合会议(2年一届) ACM SIGIR Special Interest Group on Information Retrieval the Association for Computational Linguistics Conference on Information and Knowledge Management (CIKM ICML 2006: 23rd International Conference on Machine Learning

14 检索模型 布尔模型 向量空间模型 概率模型 以上模型在实践中，常常混合使用，以达到最佳效果
基于集合论和布尔代数，适用于普通用户，核心是二值相关，不能进行相关性排序 向量空间模型 以向量表示提问和文档，向量计算在后台进行，与用户无关，优点是可以进行相关性排序，也可产生文档文摘 概率模型 基于贝叶斯概率论，更具有普遍性，适应多媒体、语义文档的检索，具有逻辑推理能力 以上模型在实践中，常常混合使用，以达到最佳效果

15 信息处理与组织 自动标引 自动分类与聚类 自动摘要 视频音频信息索引

16 课程总结7 信息检索技术与方法 布尔检索 加权检索 全文检索 超文本检索 信息检索技术与方法 多媒体检索 智能检索 跨语言检索 跨平台检索

17 信息检索的相关概念(IR concepts)
用户接口(User Interface)：用户和IR系统的人机接口 输入查询(Query)，返回排序后的结果文档(Ranked Docs)并对其进行可视化(Visualization)，支持用户进行相关反馈(Feedback) 用户的两种任务：retrieval 或者browsing IR的两种模式：pull (ad hoc) 和push (filtering)。 Pull: 用户是主动的发起请求，在一个相对稳定的数据集合上进行查询。 Push:用户事先定义自己的兴趣，系统在不断到来的流动数据上进行操作，将满足用户兴趣的数据推送给用户

18 信息检索的相关概念(IR concepts)
相关(relevant)、相关度(relevance) 相关取决于用户的判断，是一个主观概念，不同用户做出的判断很难保证一致，即使是同一用户在不同时期、不同环境下做出的判断也不尽相同。

19 信息检索的相关概念(IR concepts)
形式上说，信息检索中的相关度是一个函数R，输入是查询Q、文档D和文档集合C，返回的是一个实数值 R=f(Q,D,C) 信息检索就是给定一个查询Q，从文档集合C中计算每篇文档D与Q的相关度并排序(Ranking)。 相关度通常只有相对意义，对一个Q，不同文档的相关度可以比较，而对于不同的Q的相关度不便比较相关度的输入信息可以更多，比如用户的背景信息、用户的查询历史等等

20 检索模型的基本概念——相关概念 标引项(Index Term) 标引项的权重(Weight) 文档表示成多个Term的集合
通常用词来表示，但是也可以用其他语言单位来表示 关键词(key words) 可以看成Term的一种 标引项的权重(Weight) 不同标引项作用是不同的 通过权重加以区分

21 检索模型的基本概念——模型要素 F是一个框架,用以构建文档,查询以及它们之间关系的模型
D是一个文档集合，通常由文档逻辑视图来表示。可以是一组索引词或关键词。既可以自动提取，也可以是由人主观指定。 Q是一个查询集合，是用户任务的表达，由查询需求的逻辑视图来表示。 R(qi,dj) 是一个排序函数，它给查询qi和文档 dj 之间的相关度赋予一个排序值 即: IR模型由上述三个要素组成 R(qi,dj) = F( D, Q )

22 检索模型的基本概念——模型分类 三类 基于内容的信息检索模型有 基于内容的信息检索模型 结构化模型 浏览型数学模型 集合论模型 代数模型
布尔模型、模糊集合模型、扩展布尔模型 代数模型 向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型 概率模型 经典概率论模型、推理网络模型、置信（信念）网络模型

23 检索模型分类 信息检索模型 检索模型 浏览模型 内容模型 结构模型 布尔 模型 向量 概率 非重叠 链表模型 邻近节 点模型 平坦 结构导
向模型 超文本

24 布尔模型 一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上 基本原理 系统索引词集合中的每一个索引词在一篇文档中只有两个状态
出现 不出现 检索提问式q由三种布尔运算符 “and”、“or”、“not”连接索引词来构成

25 布尔模型 集合的几种表示 具有某种属性的事物的全体就构成一个集合，以 A, B, C,…表示构成集合的事物，以 a,b,c,…表示该集合的元
某个图书馆现存的所有图书——有限集 以 S1＝ {a,b,c,d}表示 所有的正整数——无限集 以 S2＝ {1,2,3,4,…}表示 P(x)表示与元x有关的一个属性 S3＝ {x|x是正偶数} S4＝ {x|1<x<10 } 为空集

26 布尔模型——集合的表示 集合间的关系 集合的图形表示 x是A中的一个元，记作x ∈ A x不是A中的一个元，记作x ∉ A 集合A 元x
空间E 集合A 元x

27 布尔模型——集合的运算 并运算 设A，B是两个集合，集合A与B的并运算是由A的一切元素和B的一切元素所组成的集合，记做 A∪B，数学表示为：
设 A={a,b,c,d,e}，B={c,d,x,y,z} 则 A∪B={a,b,c,d,e,x,y,z} 即 A∪B={x|x∈A∨x∈B } A B 空间E

28 布尔模型——集合的运算 交运算 设A，B是两个集合，包含A和B的所有公共元素的集合叫做A与B的交集，记做 A∩B，数学表示为：
设 A={a,b,c,d,e}，B={c,d,x,y,z} 则 A∩B={c,d} 即 A∩B={x|x∈A∧x∈B }

29 布尔模型——集合的运算 差运算 设A，B是两个集合，A-B是由一切属于A但不属于B的元素所组成的集合，称为B在A中的余集，或者A与B的差，即
设 A={a,b,c,d,e}， B={c,d,x,y,z} 则 A-B={a,b,e}， B-A={x,y,z} 数学表示为 A-B={x|x∈A﹁x∈B }

30 布尔模型——布尔代数 与运算 真值表 A B Y 1 A B Y 只有输入全为1时，输出才为1
1 只有输入全为1时，输出才为1 决定事件的全部条件都满足时，事件才发生——这就是与逻辑关系。 在函数式中，用表示与运算，记做 Y=AB 或Y=AB

31 布尔模型——布尔代数 或运算 真值表 A B Y 1 输入全部为0时，输出为0 A B Y
1 决定事件的全部条件至少有一个满足时，事件就发生——这就是或逻辑关系。 在函数式中，用＋ 表示或运算，记做 Y=A＋B

32 布尔模型——布尔代数 非运算 真值表 A Y 1 A R Y 该图代表的逻辑关系是：决定事件的条件满足时，事件不发生——这就是非逻辑关系。
1 该图代表的逻辑关系是：决定事件的条件满足时，事件不发生——这就是非逻辑关系。 在函数式中，用_ 表示非运算，记做 Y=A

33 布尔模型——布尔代数 布尔运算的性质和定理 交换律 AB=BA A+B=B+A
结合律 A+(B+C)=(A+B)+C A(BC)=(AB)C 分配律 A(B+C)=AB+AC A+(BC)=(A+B)(A+C)

34 布尔模型 布尔模型 查询和文档均表示为Term(“是否存在”)的布尔表达式，其中文档表示成所有Term(存在)的“与”关系布尔表达式。 例子(因不会产生歧义，以下例子直接用Term进行布尔操作)： 查询：2010 AND 世界杯AND NOT 小组赛 文档1：2010年世界杯在南非举行 文档2：2006年世界杯小组赛已经结束 相似度计算 查询布尔表达式和所有文档的布尔表达式进行匹配，匹配成功的文档的得分为1，否则为0 类似于传统数据库检索，是精确匹配

35 布尔模型 遵循两条基本规则 每个索引词在一篇文档中只有两种状态：出现或不出现，对应逻辑值为 0 或 1
查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式

36 布尔模型——形式化表示 任意查询都可转化为一个主析取范式DNF 例如：查询为q=ka∧(kb∨¬kc)可表示为
q=ka∧(kb∨¬kc)=kakbkc∨kakb¬kc∨ka¬kb ¬kc qbnf=(1,1,1)∨(1,1,0)∨(1,0,0) 即：每一个分量都是三元组的二值向量 任一文本可以写成所有Term的交，如doc=a∧b∧c∧d∧e 因为doc(蕴含)q，所以相似度为1  在布尔逻辑中，析取范式(DNF)是逻辑公式的标准化(或规范化)，它是合取子句的析取。作为规范形式，它在自动定理证明中有用。一个逻辑公式被认为是 DNF 的，当且仅当它是一个或多个文字的一个或多个合取的析取。同合取范式(CNF)一样，在 DNF 中的命题算子是与、或和非。非算子只能用做文字的一部分，这意味着它只能领先于命题变量。例如，下列公式都是 DNF: 但如下公式不是 DNF: NOT 是最外层的算子 一个 OR 嵌套在一个 AND 中 把公式转换成 DNF 要使用逻辑等价，比如双重否定除去、德·摩根定律和分配律。注意所有逻辑公式都可以转换成析取范式。但是，在某些情况下转换成 DNF 可能导致公式的指数性爆涨。例如，在 DNF 形式下，如下逻辑公式有 2n 个项:

37 布尔模型 定义 sim(dj, q) 为该模型的匹配函数(相似度)
用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分项，文献dj 与查询q的相似度为 如果 ，则表示文献dj与q相关，否则为不相关。 sim(dj, q) 为该模型的匹配函数(相似度)

38 布尔模型——优缺点 布尔模型的优点 布尔模型的缺点 布尔模型目前仍然是商业文档数据库的主流模型，并为一些新的领域提供了一个好的起点
简单而整齐，为现代许多商业系统所用 自我保护功能，降低用户对搜索系统的期望，使自己不在责任方，检索结果不好的原因在于用户构造查询不好 简单、易理解、简洁的形式化 布尔模型的缺点 它的检索策略是基于二值决策准则，即一个文档只被判断成相关的或不相关的，无任何等级变化 当用布尔表达式表示精确语义的时候，很难将信息表达为一个布尔表达式 准确匹配，信息需求的能力表达不足 布尔模型目前仍然是商业文档数据库的主流模型，并为一些新的领域提供了一个好的起点 布尔模型的优点 布尔模型为普通用户提供了一个容易掌握的框架。在模型中，查询被描述为具有精确语义的布尔表达式，其特点简单而整齐，为现代许多商业系统所用 只能严格匹配(得分不是0就是1)，不能近似或者部分匹配，多个结果无法排序 􀂄一般用户构造查询不是很容易，构造不利可能造成结果过多或者过少

39 布尔模型——布尔模型的改进 布尔模型的典型问题 扩展布尔模型 两个索引词 K1 and k2 and k3 and ……and k8
含有7个k和0个k的文献一样被排除 K1 or k2 or k3 or ……or k8 含有8个k和含有1个k的文献没有区别 扩展布尔模型 两个索引词

40 向量模型——n维向量 考虑从空间坐标系原点出发（其他向量可以平移到原点出发）的向量 ，其终点坐标为<x1,x2,…,xn>，我们称之为一个n维向量 向量的运算 加、减、倍数、内积

41 向量模型——空间概念 文献空间 标引词空间 如果把每个标引词看作是一个向量，代表了空间的一个维，则由这些标引词集合定义了一个空间
文献集合中的任一文献都可以表示为这个多维空间中的一个向量，这个空间就成为“文献空间” 标引词空间 文献集合中的一篇文献可看成是标引词空间的一个维，空间中的一点代表一个标引词点 从原点到该点的向量就是一个标引词向量 它在各个轴上的分量就是该标引词在各个轴所代表的相应文献中的权重

42 向量模型——模型含义 向量空间模型(Vector Space Model, VSM)
由康奈尔大学Salton等人在上世纪70年代末提出并倡导的，原型系统为SMART* 该模型采用了“部分匹配”的检索策略，即：出现部分索引词也可以出现在检索结果中，以克服布尔模型的缺点  通过给查询或文档中的索引词分配非二值权值来实现 查询和文档都可转化成Term及其权重组成的向量表示，并可以看成空间中的点。向量之间通过距离计算得到查询和每个文档的相似度 * 可从ftp://ftp.cs.cornell.edu/pub/smart/下载全部源码和相关语料

43 向量模型——模型含义 向量模型通过分派非二值权重给查询和文档中的索引项来实现检索目标
这些权重用于计算系统中的每个文档与用户的查询请求的相似程度，向量模型通过对文档按照相似程度降序排列的方式，来实现文档与查询项的部分匹配 结果中的文档排列顺序比通过布尔模型得到的结果要合理得多

44 向量模型——模型含义 在该模型中，与（ki，dj）相关联的权重wi,j是一个非二值数
查询中的索引项也是有权重的，设wi,q是与（ki，q）相关联的权重，且wi,q≥0，则查询向量Q被定义成 Q=（w1,q，w2,q，w3,q…………wt,q） 其中，t是系统中所有索引项的数目， 文档dj的向量可以表示为 wj=（w1,j，w2,j，w3,j………wt,j）， 向量模型通过wj和Q的相关度来评价文档dj和查询q的相关度。这种关系可以用定量表示，一般使用两个向量之间的夹角余弦值来计算

45 向量模型——模型含义 变量wi称为权值，非负 两个基本问题：
表示对应词项ki对于判断d和查询q相关性的重要程度（注意，这里的q是一般的，而d是具体的） q=<v1,v2,…vt> 变量vi的含义类似于wi 两个基本问题： 如何定义wi和vi 如何计算R(d, q)

46 向量模型——模型含义 设wi和vi为对应的词分别在d和q中出现的次数，于是我们有了两个m维向量，用夹角的cos表示“接近度”，即

47 向量模型——例子 查询q：(<2010,1>,<世博会,2>)
文档d1：(<2010,1>,<世博会,3>,<中国,1>,<举行,1>) 文档d2：(<2005,1>,<世博会,2>,<1970,1>,<日本,1>,<举行,1>) 2005 2010 世博会 中国 1970 日本 举行

48 向量模型——例子 查询和文档进行向量的相似度计算：􀂄 采用内积：􀂄 夹角余弦：􀂄 文档d1与q的内积：1*1+3*2=7􀂄

49 向量模型—— 权重规范化 不进行权重规范化，检索结果因文献篇幅的长短而存在不合理现象
长文献词量大，同一词词频更大命中的概率更大 长文献中不同的词量大，增加了查询和文献的相似度 Normalization seeks to remove these effects Related somehow to maximum term frequency But also sensitive to the number of terms

50 向量模型—— Cosine‘s Normalization
Compute the length of each document vector Multiply each weight by itself Add all the resulting values Take the square root of that sum Divide each weight by that length

51 向量模型—— 项向量的规范方法 布尔权重 term i在文档j中的权重aij=0or 1(出现则取1，否则取0)
TF权重：TF(Term Frequency)是term在文档中出现的次数。权重aij=TFij或者归一化后的TF值 TF的归一化(Normalization) ：将一篇文档中所有Term的TF值归一化到[0,1]之间。通常可以采用以下三种方式之一 Maximum Normalization [1,2,1,0,4][0.25,0.5,0.25,0,1] Augmented Maximum Normalization [1,2,1,0,4] [0.625,0.75,0.625,0.5,1] Cosine Normalization [1,2,1,0,4] [0.213,0.426,0.213, ]

52 向量模型——确定权重的方法 How to Weighting? N 文献数 ni 文献集合中包含标引词 ki的词频
freqi,j 某篇文献dj中包含标引词ki的词频(描述能力) fi,j 词频的规范化值（局部权值,描述能力） idfi 标引词ki的逆词频值 （全局权值,区分能力 ）

53 向量模型——确定权重的方法 文档向量权值 tf/idf 查询向量的构造：索引词权值: WI,q 索引词权值wij= tf*idf

54 概率模型 概率模型基本思想是：给定一个用户的查询，则有一个包含相关文档且不包含不相关文档的集合。设想这个文档集合是一个理想的结果集
我们可以认为查询的过程是说明理想结果集属性的过程，初始的时候努力的猜测它们是什么，猜测结果我们将产生一个对理想结果集的概率描述，检索出最初的结果集，然后引入用户的交互，改善结果集

55 概率模型 基本假设 给定一个查询q和文档集中一个文档dj，概率模型试图找出用户对其感兴趣的概率 模型假设这个概率只是依赖于查询和文档的表示，进而模型假设文档集中存在一个子集，它使得总体相关概率在集合中的文档被认为是与查询相关的，不在集合中的则被认为是不相关的

56 概率模型——贝叶斯定理 贝叶斯定理 词条的独立假设 对一篇文档而言，若文档中的各个索引词相互独立，则有
 贝叶斯定理 词条的独立假设 P(AB)= P(A) P(B) 当且仅当 A与B相互独立 对一篇文档而言，若文档中的各个索引词相互独立，则有 P(dj)=P(k1)…P(kt)

57 概率模型——模型定义 定义 设索引词的权重为二值的，即：
R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj, q)可以定义为：

58 概率模型——优缺点 优点 缺点 理论上讲，文档按照其与目标集合的相关概率 降序排列 需要最初将文档分为相关和不相关的集合
所有权重都是二值的，模型中仍然假设索引项之间是相互独立的

59 结构化文本检索模型 结构化文档检索算法可以看作是一种信息检索算法，但排序机制并不健全
使用“匹配点”来表示文本与用户查询相匹配的词串位置 使用“区域”表示文本的块 使用“节点”表示文档的结构化组元 这样，一个节点是一个区域，具有文档的作者与用户所共知的、预定义的逻辑属性

60 结构化文本检索模型 基于非重叠链表的模型是把文档中的整个文本划分为非重叠文本区域，并用链表连接起来
因为有多种方法将文本分为非重叠的区域，所以，对于同一个文档，会产生多个链表 这些链表清晰的记录了文档的数据结构 在相同链表中的文本区域没有重叠，而不同链表中的文本区域可能会重叠

61 结构化文本检索模型 该模型是一种允许在相同文档上独立定义分层索引结构的模型，每个索引结构是一个严格的层次结构，其中每个结构组元称为节点，每个节点与一个文本区域相关，两个不同的层次结构可能涉及到两个重叠的文本区域 针对不同层次结构的用户查询，所汇集的结果是由来自其中一个层次结构的节点组成

62 信息浏览模型——平坦浏览 该模型的思想假设用户浏览一个具有平坦组织的文档空间，文档集可以被描述为平面上的点或是链表中的元素 该模型的不足
用户在这些文档上到处浏览，以寻找有关信息，在反馈过程中，用户通过在邻近文档中的浏览，查找出相关的资料，找出一些感兴趣的关键词。这些关键词将被输入到原始的查询中，以试图提供更好的、新的查询 同样，用户也可以以平面方式，浏览单一的文档。例如使用滚动条来浏览一个Web页面。 该模型的不足 在给定的一个页面或屏幕上，可能没有任何用户所处上下文情况的指示 平坦模型缺乏层次性的视图、用户的浏览行为很容易迷航 浏览模型，用户的兴趣可能不在于提交一个对系统的查询。而是有意花一点时间来浏览文档空间，以寻找所关心的文档。 在这种情况下，用户是进行文档空间的浏览而不是搜索； 浏览和搜索是不同的信息发现行为，通常来说，搜索比浏览更适合于有明确查找目标的用户。 平坦模型，结构向导模型，超文本模型

63 其他模型与经典模型的比较 布尔、向量和概率模型是三个传统的检索模型 布尔模型是基于集合理论和布尔代数的一种简单检索模型
向量模型采用非二值的索引项权重，把文档和查询用t维权重向量表示，计算这两个向量之间的相似度来实现查询与文档的匹配 概率模型是一种规范的模型，它试图预测给定查询的相关文档，排序原则根据文档与集合的相似度进行排序

64 其他模型与经典模型的比较 文档的结构也包含了信息，基于非重叠链表和邻近节点模型是两个典型的结合和内容结合起来进行检索的模型
三种浏览模型：平坦模型，结构导向模型和超文本模型 平坦模型把文档（集）看成是一个平坦的文档空间。由于是平坦的，这种模型的导航关系不清楚 结构导向模型提供了层次性目录式的导航模型，是一种非平坦模型 超文本模型是由节点和链组成的非线性的信息组织网络，能够为用户提供比上两种模型更多的信息，更方便的浏览，Web是它最成功的应用

65 四种关系的矩阵表示

66 评价指标 召回率(Recall): RR/(RR + NR)，返回的相关结果数占实际相关结果总数的比率，也称为查全率，R∈[0,1]
正确率(Precision): RR/(RR + RN)，返回的结果中真正相关结果的比率，也称为查准率，P∈[0,1] 两个指标分别度量检索效果的某个方面，忽略任何一个方面都有失偏颇。两个极端情况：返回1篇，P=100%，但R极低；全部返回，R＝1，但P极低

67 正确率和召回率的问题 两个指标分别衡量了系统的某个方面，但是为比较带来了难度，究竟哪个系统好？大学最终排名也只有一个指标。
解决方法：单一指标，将两个指标融成一个指标 两个指标都是基于集合进行计算，并没有考虑序的作用 举例：两个系统，对某个查询，返回的相关文档数目一样都是10，但是第一个系统是前10条结果，后一个系统是最后10条结果。显然，第一个系统优。但是根据上面基于集合的计算，显然两者指标一样。 解决方法：引入序的作用 召回率难以计算 解决方法：Pooling方法，或者不考虑召回率

68 评价指标—P和R融合 F值：召回率R和正确率P的调和平均值，if P=0 or R=0, then F=0, else 采用下式计算：
E值：召回率R和正确率P的加权平均值，b>1表示更重视

69 评价指标－引入序的作用 R-Precision：检索结果中，在所有相关文档总数位置上的准确率，如某个查询的相关文档总数为80，则计算检索结果中在前80篇文档的正确率。

70 评价指标—引入序的作用 正确率-召回率曲线(precision versus recall curve)
检索结果以排序方式排列，用户不可能马上看到全部文档，因此，在用户观察的过程中，正确率和召回率在不断变化(vary)。 可以求出在召回率分别为0%,10%,20%,30%,…, 90%,100%上对应的正确率，然后描出图像

71 P-R的优缺点 优点 缺点 简单直观 既考虑了检索结果的覆盖度，又考虑了检索结果的排序情况

72 评价指标 平均的求法 MAP(MeanAP)：对所有查询的AP求宏平均
宏平均(Macro Average): 对每个查询求出某个指标，然后对这些指标进行算术平均 微平均(Micro Average): 将所有查询视为一个查询，将各种情况的文档总数求和，然后进行指标的计算 如：Micro Precision=(对所有查询检出的相关文档总数)/(对所有查询检出的文档总数) 宏平均对所有查询一视同仁，微平均受返回相关文档数目比较大的查询影响 MAP(MeanAP)：对所有查询的AP求宏平均

73 面向用户的评价指标 前面的指标都没有考虑用户因素。而相关不相关由用户判定。
假定用户已知的相关文档集合为U，检索结果和U的交集为Ru，则可以定义覆盖率(Coverage) C=|Ru|/|U|，表示系统找到的用户已知的相关文档比例。 假定检索结果中返回一些用户以前未知的相关文档Rk，则可以定义出新率(Novelty Ratio) N=|Rk|/(|Ru|+|Rk|)，表示系统返回的新相关文档的比例。

74 TREC的目标 总目标：支持在信息检索领域的基础研究，提供对大规模文本检索方法的评估办法 1.鼓励对基于大测试集合的信息检索方法的研究
2.提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解； 3.示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应用的速度； 4.为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。

75 TREC中名词定义 Track Topic Document Relevance Judgments
TREC的每个子任务，QA、Filtering、Web、Blog等 Topic 预先确定的问题，用来向检索系统提问 topic query (自动或者手工) Question (QA) Document 包括训练集和测试集合(TIPSTER&TREC CDs、WT2G、WT10G、GOV2) Relevance Judgments 相关性评估，人工或者半自动

76 Topic的一般结构 Title：标题 Description：描述 Narrative：详述 通常由几个单词构成，非常简短
一句话，比Title详细，包含了Title的所有单词 Narrative：详述 更详细地描述了哪些文档是相关的

77 菊池敏典算法——信息检索系统的构成 信息采集子系统 标引子系统 建库子系统 词表管理子系统 用户接口子系统 提问处理子系统
广泛地、定期地采集各种信息源 标引子系统 人工或者自动标引 建库子系统 数据录入、错误检查与处理、数据格式转换、生成各种文档。仅提供定题(SDI)服务，则建立能支持顺序检索的顺排文档。若需支持回溯检索，则建立各种倒排档 词表管理子系统 管理维护系统中已有的词表，使它与标引、建库等子系统相连接，支持用户查询操作 用户接口子系统 由用户模型、信息显示、命令语言和反馈机制 提问处理子系统 ①接收提问 ②提问校验 ③提问加工，指对原提问式进行解释性或编译性的加工，生成便于机器处理的目标提问式。加工方式常有顺序检索中的表展开法、倒排检索分别以菊池敏典法和福岛方式 ④检索

78 菊池敏典算法 展开表概念 1968年，日本科技情报中心的菊池敏典研究出脱机批处理检索信息的表展开法(菊池敏典算法)
属于传统的布尔逻辑检索模型，基于文本信息检索，主要适用于二次文献信息的检索。 主要思想是将代表用户的逻辑提问式转换成表的形式。该表规定了表的内容走向和是否命中的判断，检索时根据表的走向及其相关信息来判断每条记录是否命中。 原文对顺排文档的检索通常是采用日本人菊池敏典研制出的表展开法进行的。其关键技术是采用列表处理方法将提问逻辑式（检索式）变换成等价的提问展开式，按提问展开表的内容对顺排文档的每篇文献进行检索。其优点是能够缩短每一个提问式的查找时间，并且对所存储情报的任何可检项目都能够进行相同的处理。 而提问式的构造不仅要能正确全面反映用户的情报需求，还要有一个便于计算机处理的适当的表示形式。一般的，在计算机内一个提问逻辑式的表达分两个部分。第一部分是表达检索词及对它的各种检索要求的，包括检索词本身、它的代号、所属字段、截断说明、比较条件等。如果是加权检索，还应有该检索词的权值。第二部分是由检索词代号组成的提问逻辑式（如果是加权检索，则没有这部分。）第一部分称为检索词表，第二部分称为提问逻辑式，两部分间通过检索词代号来联系。

79 菊池敏典算法——展开表生成 前处理 若是检索词 若是运算符 若是括号 判断提问式中的字符，从上而下填写表格
则将其存入展开表内的检索词栏，并记下在表中的地址 若是运算符 “+”：前一词满足，指向“*”；不满足，指向后一词 “*”：前一词满足，指向后一词 若是括号 “（”：逢“（”在其后的检索词所在行的“级位”栏值加1 “）” ：逢“）”在其后的检索词所在行的“级位”栏值减1 若遇结束，则最后一个检索词所在行的“条件满足指向”栏放入“命中”，“条件不满足”放入“落选”

80 菊池敏典算法 后处理 依据表中“级位”值，从下而上填写 若当前行级位值大于上一行的级位值，表示上一行的检索词后有右括号
若所在行的“条件不满足指向”栏为“空”，则表明当前行和上一行的检索词之间为“*”运算，应把上一行“落选”内容复制到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，则表明当前行和上一行的检索词之间为“+”运算，应把上一行“命中”内容复制到当前行的不满足栏 若当前行的级位值等于上一行的级位值，则作以下处理： 若所在行的“条件不满足指向”栏为“空”，复制上一行“落选”内容到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，复制第一个右括号或提问式结束号前检索词所在行的满足栏内容到当前行的满足栏 若当前行的级位值小于上一行的级位值，表示当前行的检索词前有左括号： 若所在行的“条件不满足指向”栏为“空”，复制表中已处理过的第一个与当前行级位值相等或小的不满足栏到当前行的不满足栏 若所在行的“条件满足指向”栏为“空”，复制当前行紧后复合检索项中最后一个检索词所在词所在行的满足栏内容到当前行的满足栏

81 菊池敏典算法——优点 以提问中的提问条件项为检索查比的主动项 菊池敏典算法用便于查找的提问展开表代替了原来的提问逻辑式
由于每个独立的提问所涉及的提问条件项的属性范围都不太多，因此，检索时，在文献巾查找的范围只需局限于单个提问所涉及的那一小部分(如关键词，标题等等，具体的提问条件项只在其本身属性范围内查找)。 菊池敏典算法用便于查找的提问展开表代替了原来的提问逻辑式 电脑可以顺着提问的思路查阅有关文献。一旦提问要求得到判定性的答案后，则可立即停止关于其他提问项的查比，而不一定要求将提问中所有提问条件项都一一查比。 菊池敏典算法的实质是: 凡是可不查阅的文献属性一定不查， 凡是可不再查比的提问条件项一定不再查， 节约了机器的查比时间，使菊池敏典算法在早期开发情报检索自动化系统得到相当的重视及广泛的应用

82 福岛算法—倒排文档的建立 倒排文档相对顺排文档而言，是将顺排文档中的可检索字段取出，按照一定的规则排序，归并相同词汇，并把在顺排文档中的记录号集合赋予其后，形成的文档，可看成为辅助文档。 倒排文档将两个检索词的逻辑运算转换成了两个检索词之间的记录号集合的运算。目前最常见的倒排文档检索为逆波兰展开法。 倒排文档的组成元素主要包括 关键字：作者，主题词，分类号 目长： 含有该关键字记录的条数 记录号集合：所有与该关键字有关的记录号

83 福岛算法 1929年波兰的逻辑学家卢卡西维兹提出将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式” 日本的福岛首先将逆波兰表达式应用于情报检索，故又称“福岛方法” 逻辑提问式 A*(B+C)+D →逆波兰表达式 ABC+*D+ 逻辑提问式中运算符优先次序（）， -， *， + 逆波兰表达式中的次序（），+，*，- 说说逆波兰的转换和计算算法。 逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为ab+cd+*d+ 它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下： 如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。 将一个普通的中序表达式转换为逆波兰表达式的一般算法是： 1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 其中运算符优先级如下： */:4 +-:3 (:2 ):1 逆波兰表达式 Time Limit:1000MS  Memory Limit:65536K Total Submit:954 Accepted:425 Description 逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* 。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。 Input 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。 Output 输出为一行，表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。 Sample Input * Sample Output Hint 可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。 此题可使用函数递归调用的方法求解。 Source 计算概论05

84 加权检索 根据用户的检索要求来确定检索词，并根据每个词在检索要求中的重要程度不同，分别给予一定的数值(权值)加以区别，同时利用给出的检索命中界限（ 阈值，threshold）限定检索结果的输出 加权检索是对每个检索词赋予一个数值，即“权”，权值越大，检索出的文献命中程度越高。 不同的检索系统对加权有不同的定义，也并非所有计算机检索系统都具备加权检索功能。 加权检索的侧重点不在于是否检索到某篇文献，而是对检索出的文献与需求的相关度作评判。

85 文本预处理——分词 语素是最小的语音语义结合体，是最小的语言单位。 词是代表一定的意义，具有固定的语音形式，可以独立运用的最小的语言单位。
“字”：简单高效,国家标准GB 中定义的常用汉字为6763个.表示能力比较差，不能独立地完整地表达语义信息。 词是代表一定的意义，具有固定的语音形式，可以独立运用的最小的语言单位。 “词”：表示能力较强，但汉字的词的个数在10万个以上,面临复杂的分词问题

86 文本预处理 哈希函式從上世紀八十年代開始就有了相關研究。Knuth的研究結果表明，對最常用的31個英文單詞建立哈希函式包括1043種可能擻索空間，對39個Pascal預定義標識符擻索空間為2039個節點。 哈希函数从上世纪八十年代开始就有了相关研究。Knuth的研究结果表明，对最常用的31个英文单词建立哈希函数就包括1043种可能搜索空间，对39个Pascal预定义标识符搜索空间为2039个节点。

87 文本预处理——分词主要方法 基于字符串匹配的分词方法 基于理解的分词方法 基于统计的分词方法 1）正向最大匹配法 2）逆向最大匹配法
 1）正向最大匹配法 2）逆向最大匹配法 3) 双向最大匹配法 4）最少切分 基于理解的分词方法 基于统计的分词方法

88 文本预处理—正向最大匹配分词 就是从左至右尽可能查找最长的词，直到当前字符与已经处理的字符串不构成词，输出已经识别的词，并从识别出来的词后面接着查找词。 分词速度比较快 但是分词错误率比较高

89 文本预处理—快速检索词典的意义 分词是索引的瓶颈 分词的速度决定了索引的速度 分词就是循环的词典查找过程 词典的查找速度决定索引的速度

90 文本预处理——汉字分词 N元切分法(N-gram) ：对一个字符串序列以N为一个切分单位进行切分。
如二元切分法： “ABCDEFG” →“AB\CD\EF\G” 交叉二元切分法(Overlapping Bigram)：“ABCDEFG” →“AB\BC\CD\DE\EF\FG” 简单快速，但会产生大量无意义的标引词，导致标引产生的索引文件的空间，以及检索和进行标引的时间都大大增加。同时，因为它的切分单位并非语言学意义上的词语，所以也会导致检索的查准率下降。

91 文本预处理——汉字分词 切分歧义(Ambiguition)的消除 交集型歧义（交叉歧义）：“组合成”
我们/小组/合成/氢气了；组合/成/分子； “部分居民生活水平”：部分、分居、居民、民生、生活、活水 “学生会组织义演活动” : “学生/会/组织/义演/活动” or “学生会/组织/义演/活动”? 组合型歧义（覆盖歧义）： 他/从/马/上/下/来；我/马上/就/来/了 ； “老人家在天津”：老人、老人家 请把手拿开 这个门把手坏了 真/伪歧义 “大学生活象白纸” 大学 生活 象白纸 大学生 活象 白纸

92 文本预处理——中文词法分析 正向最大匹配(基于词典的方法)

93 文本预处理——中文词法分析 逆向最大匹配(基于词典的方法)

94 文本预处理——基于词典和规则的方法 最大匹配 正向最大匹配、反向最大匹配和双向最大匹配
实现简单，而且切分速度快。但无法发现覆盖歧义，对于某些复杂的交叉歧义也会遗漏。 全切分 利用词典匹配，获得一个句子所有可能的切分结果。 时空开销非常大。 基于理解的分词算法 模拟人的理解过程，在分词过程中加入句法和语义分析来处理歧义问题。 难以将各种语言信息组织成机器可直接读取的形式，还处在试验阶段

95 文本预处理——汉字分词 1.按字切分 优点： 缺点
采用单汉字切分的方法,字典体积最小,切分方法最为简单,最接近自然语言。单汉字存储是处理新词和任意汉字串的天然单元,具有其它方法无法比拟的优点 缺点 不能自动切分主题词,只能在检索时由用户通过对单字的多词匹配组合主题词。另外,随着数据库容量的增加,索引量急骤上升,耗费时空,且检索速度慢,效率低，其查准率和查全率的高低取决于后控制的智能水平。

96 文本预处理 2.按词切分 3.按主题词切分 优点： 缺点 优点
字典体积较小,比采用规范主题词更灵活,比单汉字更接近自然语言,便于与其他自然语言处理系统联系。 缺点 由于切词存在歧义的可能性,切词的组合有随意性,一个名词性概念有代用、相关、属分等关系,动词性概念有方式、工具、强度、时间和原因等谓词框架,所以按词切分技术需要结合其他技术措施。 3.按主题词切分 优点 按主题词切分的方法,以综合、专业主题词典为切词依据,优点是切词正确率和专指性高,借助主题词典便于隐含标引。 系统空间开销大,而且不能切分主题词典没有收入的自由词和新词等

97 文本预处理——规则和统计结合的方法 利用词典匹配进行初切分得到一个切分词图，然后利用词频信息求词图N条最短路径的N-最短路径法。
通常利用词典进行初切分，然后用其它的概率统计方法和简单规则消歧和进行未登录词识别。 比如： 利用词典匹配进行初切分得到一个切分词图，然后利用词频信息求词图N条最短路径的N-最短路径法。 最大匹配算法、state-of-the-art分类器和支持向量机的结合。 通过词典匹配找出所有交叉歧义，利用Bigram语言模型或其变形来消除歧义。 基于大规模语料库的统计方法 规则和统计结合的方法

98 文本预处理 核心词典 待切分文本 交叉歧义检测 初切分结果 消除交叉歧义 新词词典 未登录词识别 切分结果
图3 面向大规模中文信息检索的分词算法流程图

99 文本预处理 未登录词(Out of Vocabulary )识别 先识别已知词还是先识别未登录词
命名实体：数词、人名、地名、机构名、译名、时间、货币 缩略语和术语：“超女”、“非典”、“去离子水” 新词：“酱紫”、“星盘” 先识别已知词还是先识别未登录词 先识别已知词：“内塔尼亚/胡说” 先识别未登录词：“胜利取决/于勇/气”

100 文本预处理——英文分词 英文词法分析 数字的考虑：
某人想查询1978到1989年间车祸的死亡人数，可能查出来的结果有很多这两年本身的死亡人数，因此，上面的查询中，数字不是一个很好的index term。 但是，一些和字符组合的数字，如“510B.C.”，还有一些长数字，如身份证号、手机号， ，可能是非常好的index term。 最简单的做法就是所有数字都去掉，复杂的方法需要引入规则来分析，包括对时间的识别和归一化，如：October 1978，Oct. 1978都要归一化成某个统一表示。

101 文本预处理——英文词法分析 对连字号的考虑： 对标点符号的考虑 对大小写的考虑： 进行词法分析时需要考虑引入一些规则方法
有些连字号中的词可以分开，如state-of-the-art变成state of the art 有些连字号中的词不宜分开，如B-49(一款分机型号) end-of-line hyphens are noise 对标点符号的考虑 Obvious: segment on puctuation, but… "B.C.", "B.S.": without periods, these are just single letters URLs as index terms? 对大小写的考虑： 通常情况下，不考虑大小写，词法分析程序会将所有字母全部变成大写或者小写。但是，某些情况下，同一个单词的大小写含义不一样，如: China和china 进行词法分析时需要考虑引入一些规则方法

102 文本预处理——禁用词消除 禁用词(stop words) 优点： 缺点：
那些在文档中出现过于频繁(如超过80%以上的文档均出现该词)而对于检索没有区分意义的词，常见的禁用词包括冠词、介词、连词 优点： 禁用词消除可以减少term的个数，降低存储空间 缺点： 有时消除的禁用词对检索是有意义的，如：“的士”中的“的”，“to be or not to be”中的各个词，因此有些搜索引擎直接采用全文索引（full index）

103 文本预处理 消除方法： 查表法 基于词频的方法 建立一个禁用词表，通过查表的方式去掉禁用词
统计每个词的词频，如果超过总文档数目的某个百分比(如80%)，则作为禁用词去掉

104 文本预处理—— Stemming算法 Stemming的必要性 名词的单复数形式，动词的各种时态，形容词的各种级等本身含义非常类似。
当用户提交某个查询时，很有可能各种相关形式都是用户期望的结果 提高检索的召回率 用户输入查询关键词goose，一篇介绍goose的文档，虽然不包含单词goose，只包含单词geese，应该是相关的。

105 文本预处理——常用stemming算法 Elementary methods：大小写合并 Stemmer：单复数合并
Porter：使用规则去后缀 Porter 算法—使用一系列后缀变换规则对单词进行变换 ed null ing null ational ate tional tion Lovins‘s method：260后缀，特例表 The dictionary method：词典保存后缀 Corpus-Based Stemming：根据单词的共现度

106 文本预处理——stemming算法的争议
斯拉夫语等有很大必要。 不同的论文用同样的stemming工具，针对同样的测试集得出完全相反的结论。 一般认为：Stemming降低了查准率，提高了查全率。 查准率的降低不是stemming本身的问题，而是算法实现的效果不好。 Stemming本身很有必要，关键是要提高stmming的效果。

107 索引和排序 排序就是扫描每篇文档产生的（文档号，单词号，出现位置）三元组按照单词号重新排序，单词号相同的项再按照文档号排序，单词号和文档号都相同的再按照出现位置排序。 排序的过程正好是实现“倒排”的过程 排序以后的结果写入临时索引文件。

108 索引和排序 前向索引(1) 前向索引(Forward index) ：
直接对文本进行逐篇扫描费时费力，为解决这个问题，考虑将文本预先处理（由前向索引转换成倒排索引）后进行匹配，就能较快地得到结果。 前向索引(Forward index) ： 将每篇文档表示成Doc ID及其文本内容组成的类向量模式。

109 索引和排序 前向索引(2)

110 索引和排序 前向索引(3) 仍然是依次扫描每个文档，但是对于一个字符串的多次出现不需要一一扫描，而且对同一文档内的字符串查找可以采用二分查找的方式，加快匹配过程。也就是说通过预处理的方式加快对每篇文档的匹配速度。

111 索引和排序 倒排索引 使用前向索引，仍然需要逐篇扫描每个文档。如果文档数目较多，那么就非常费时费力。
倒排索引(inverted index) 能够直接从查询词定位到文档。

112 索引和排序 倒排索引的更新 情况一：出现了新的词，则需要修改词典结构，在词典中增加词条。 情况二：出现了新的文档，则在相应的词条下增加posting list。 情况三：某些文档不复存在，则在相应的位置进行标记，等积累到一定时期进行一次性操作。 倒排索引对于单个查询词，搜索就是词典查找的过程，不需要扫描所有文档，只需要访问这个词对应的posting list，速度相当快。

113 全文检索方法——位置级检索 位置检索的四种类型： 记录级 字段或段落级 子字段或自然句级 词位置级

114 全文检索方法 采用同义词典，提高查全率 采用排除词词典，提高查准率
关联含义相同的词汇，当用户使用某个词汇检索时，系统直接将同义词取出，构成“或”运算检索式，在全文中匹配查询 采用排除词词典，提高查准率 关联检索词(例如民法)与希望排除的词(例如人民法院、移民法等)，一种排除方法是系统直接将排除词取出，构成“非”运算检索式，在全文中匹配查询

115 全文检索方法 多级索引结构 基于成本优化的索引跳跃式扫描技术 基于词频的BI-GRAM算法 多库并行检索 大内存技术和CACHE技术
比如用户的检索词为“中国足球”，检索词“中国”的命中篇数非常多，而“足球”相对较少，因此在检索逻辑运算时，可以利用索引中的信息，以足球为主运算对象，这样可以有效提高检索速度。 􀁺 基于词频的BI-GRAM算法 多库并行检索 大内存技术和CACHE技术

116 多媒体对象 网上存在大量多媒体文档 声音：mp3/wav/rm… 图片：jpg/bmp/gif/tiff/… 动画：swf/gif…
图形：(矢量图形文件)dwg/dxf/3ds… 视频：mov/wmv/mpeg/mpg/rm…

117 多媒体检索非常困难 对同一主题，多媒体表达千差万别 多媒体对象具有十分复杂的特征，进行特征表示比较困难，对多媒体对象的理解就更困难
用户的检索需求也非常复杂，有时是基于低级特征、有些是基于元数据文字描述、有些是基于高级语义特征

118 多媒体检索的方法(1) 基于关键词检索的方法
人工标注：对多媒体对象进行手工标注，可标注元数据(作者、标题、日期等)或者内容数据(内容关键词)。如WEB2.0中提交多媒体对象时的标签(tag)数据就是标注文本。 自动抽取： 在多媒体对象周围抽取能够表示对象的文本数据用于标注。如在WEB中通过图片周围的文字来描述图片。 在视频中抽取字幕、对话，从音频中抽取语音，从图片中识别文字等等。

119 多媒体检索的方法(2) 基于内容的方法(Content Based Retrieval，CBR) CBR是当前大多数研究所关注的方法
从多媒体对象的内容出发，抽取它们的特征并进行特征表示，在特征层面上进行相似度计算，得到检索结果。 如：基于颜色或形状的图像检索、哼一句歌找整支歌曲、基于概念的检索(如：检索有关“日出”的图片) CBR是当前大多数研究所关注的方法

120 多媒体对象中的特征 视觉类媒体的特征：颜色、形状、纹理、空间约束、运动、对象(如太阳)、场景、语义(如日出)等等
听觉类媒体的特征：音调、音量、音色、旋律、和谐度、语义(如爆炸声)等

121 相似度计算 假设多媒体对象采用N个特征来表示，两个多媒体对象分别表示为：向量X=(x1,x2,..,xN)，向量Y=(y1,y2,…,yN)
欧氏距离 马氏距离：C是特征向量的协方差矩阵 其他方法

122 Browsing 手工选择文档

123 初始结果

124 (用户)相关反馈

125 再次检索的结果

126 跨媒体检索(Cross-media retrieval)
是指查询和检索对象分属于不同媒体表达形式的检索，如：利用天鹅的叫声去检索天鹅的图片。 跨媒体检索通常还会涉及两个意思： 检索结果的呈现上，可以采用多种媒体形式共同表达 利用多模态(multimodal)信息弥补单模态信息的不足：如视频中通常也包含文字和音频流，可以利用它们的综合信息为检索服务

127 音频中的特征层次

128 查询形式(1) 样例 用户选择一个声音例子表达其查询要求，查找出与该声音在某些特征方面相似的所有声音。如查询与飞机的轰鸣声相似的所有声音 直喻 通过选择一些声学/感知物理特性来描述查询要求，如亮度、音调和音量等

129 查询形式(2) 拟声：发出与要查找的声音性质相似的声音来表达查询要求。如用户可以发出嗡嗡声来查找蜜蜂或电气嘈杂声。
主观特征：用个人的描述语言来描述声音。这需要训练系统理解这些描述术语的含义，如用户可能要寻找“欢快”的声音。 浏览：基于分类目录或音频的结构进行浏览

130 语音检索(Speech Retrieval)
主要利用语音识别(Speech Recognition)技术，从语音中获取全部文本或者关键文本、或者辨别说话人 抽取全部文本，根据文本建立索引，进行文本检索 抽取关键词，比如抽取“进球”来标识进球语音 辨别说话人，比如通过辨别说话人的变化对语音进行分割

131 普通音频检索 以波形声音为对象的检索，这里的音频可以是汽车发动机声、雨声、鸟叫声，也可以是语音和音乐等，这些音频都统一用声学特征来检索
音频分割 音频训练及分类 基于听觉特征检索

132 音乐检索 以音乐为中心的检索，利用音乐的音符和旋律等音乐特性来检索 如检索乐器、声乐作品等 基于样例检索 基于哼唱曲调来检索

133 查询形式 样例 绘图 属性说明方式 浏览方式：按类别或者库结构进行浏览
根据库中或者库外已有图像或者人工绘制的图像进行检索。比如通过输入一个红色圆形物体来检索相似的图像 绘图 手工绘制草图用于检索 如通过勾画衣服形状对服装设计图进行检索 属性说明方式 指定特征进行检索 如通过限定人的脸形、五官特征从人脸库中进行检索 浏览方式：按类别或者库结构进行浏览

134 基于视觉特征的检索 基于颜色特征进行检索 基于纹理特征的检索 基于形状特征的检索
检索出与用户颜色要求相似的图像。在检索中，颜色空间常常不采用RGB方法，而是采用HSV方法(hue-色调，saturation-饱和度，value-亮度) 基于纹理特征的检索 检索出与用户纹理要求相似的图像 基于形状特征的检索 检索出与用户形状要求相似的图像 主要通过主要边界特征或轮廓特征来实现

135 基于对象和区域特征的检索 基于全局特征 基于局部特征
全局特征包括图像总的色调、颜色统计分布、图像的一般属性(如图像中的对象数目、总面积等等)和视觉特征 基于局部特征 局部对象的颜色、纹理或形状，对象在空间的约束逻辑关系(方向、邻接或包含)

136 基于综合特征的检索 将不同侧面的特征综合起来进行图像的检索
如将图像的客观属性(如：作者、时间)、主观属性(如：人的胖瘦)或者语义属性(如：日出)结合在一块进行检索

137 文字型图像的检索 文字型图像(textual image) 通过OCR系统识别图像中的文本，基于文本进行检索
通过对书面文本进行扫描得到的图像。 通过OCR系统识别图像中的文本，基于文本进行检索

138 视频的浏览 基于基本结构的浏览 按照视频层次结构找到视频单元进行播放或者浏览 基于事件和故事进行浏览 按照事件或者故事的发生进行浏览

139 视频的检索 基于关键帧的检索 基于运动特征的检索 基于视频对象的检索 类似于图像检索的方法，利用全部和局部的图像特征进行检索
基于摄像机运动或者像素运动特征的检索 基于视频对象的检索 利用视频对象的特性，从库中检索出包含相关视频对象的所有场景或者镜头

140 WEB IR的定义 基于WEB的信息检索研究 搜索引擎(Search Engine，简称SE)是实现如下功能的一个系统
搜索引擎是最典型的代表 搜索引擎(Search Engine，简称SE)是实现如下功能的一个系统 收集、整理和组织信息并为用户提供查询服务 面向WEB的SE是其中最典型的代表 三大特点：事先下载，事先组织，实时检索 搜索引擎也是信息检索(Information Retrieval) 这门学科的典型应用

141 WEB搜索引擎和一般IR的区别 检索对象不同 查询方式不尽相同 用户对结果的反应不同
一般检索通常只考虑较高质量自然语言表述的书面文本(如新闻等) 查询方式不尽相同 前者通常为1~3个词的短查询，后者考虑各种方式的查询 用户对结果的反应不同 前者的用户通常只关心前几页的结果，更关注准确度；而后者准确度和全面度并重

142 WEB图中的一些概念 节点(Node) 入度(In degree) 出度(Out degree)
每个Node的入度指的是指向该Node的Node数目 出度(Out degree) 每个Node的出度指的是该Node指向的Node数目

143 WEB的相关特性(1) Power Law(幂分布定律)：WEB的很多属性满足f(x)=x-λ，λ>1

144 WEB的相关特性(2) Small world(小世界)理论 人类社会的六度分离理论，人类社会至多通过6人可以实现两人的互通
整个WEB虽然庞大，但是任意两点之间的平均距离却不大。有人做过实验，计算出整个WEB的平均距离约为19 人类社会的六度分离理论，人类社会至多通过6人可以实现两人的互通

145 搜索引擎类型 按照检索机制分类 按照检索内容分类 按照检索工具数量分类 按照检索资源的类型分类 检索型/目录型/混合型
综合型(通用型)/专题型/特定型 按照检索工具数量分类 单独型/集合型(元搜索引擎) 按照检索资源的类型分类 WEB型/非WEB型

146 检索型/综合型搜索引擎

147 目录型搜索引擎

148 专题型搜索引擎

149 特定型搜索引擎

150 元搜索引擎

151 非WEB型搜索引擎

152 搜索引擎简史回顾 1986年，Internet正式形成 现代搜索引擎的祖先
1990年由加拿大蒙特利尔McGill大学学生Alan Emtage发明的Archie，是对FTP文件名搜索，首次采用“机器人”自动爬行程序 第一个用于监测互联网发展规模的“机器人”程序是1993年MIT的Matthew Gray开发的World wide Web Wanderer 刚开始它只用来统计互联网上的服务器数量，后发展为能够检索网站域名 Lycos 第一个现代意义上的WEB搜索引擎，CMU机器翻译中心的Michael Mauldin于1994年7月创建 Yahoo 斯坦福大学博士生DavidFilo和Jerry Yang(杨致远)创建1995年 Google 斯坦福大学博士生Larry Page与Sergey Brin于1998年9月创建，目前是全世界最受欢迎的搜索引擎 Baidu 超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇发布于2001年10月，是目前最受欢迎的中文搜索引擎之一

153 搜索引擎索引网页数目变化(1)

154 搜索引擎索引网页数目变化(2)

155 搜索引擎基本组成示意图

156 Google的组成

157 组成模块的功能 信息收集或采集(Information Gathering)
获取信息，通常是指从Internet上自动获取信息 信息整理和组织(Information Organization) 预处理 文本分析和处理 信息标引——将查询和文档表示成方便检索的某种方式 信息搜索(Information Search) 查询的分析 相似度计算和排序(Ranking) 结果摘要

158 信息采集的概念 主要是指通过Web页面之间的链接关系从Web上自动获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程，信息采集系统也常常称为Robot, Spider, Crawler等等 信息采集是搜索引擎获得数据来源的过程，地位相当重要 信息采集的目标：快速获得高质量的网页 信息采集是一项十分繁杂和庞大的工程 不同的协议 不同的网络情况 时效性的要求 网页质量的要求 实际上是图的遍历过程 通过种子页面或站点(Seed)，获取更多的链接，将它们作为下一步种子，循环 这个过程一般永远不会结束

159 信息采集的基本结构

160 采集的遍历算法 宽度优先vs. 深度优先 网站采集vs. 全局URL采集 宽度优先：先采集完同一层的网页，再采集下一层网页
深度优先：先沿一条路径采到叶节点，再从同层其他路径进行采集 有研究表明：宽度优先的方法得到的网页集合的重要性更好 网站采集vs. 全局URL采集 网站采集：一个网站一个网站采集 全局URL采集：将所有URL放入一个URL池，从中使用某种方法进行选择 网站采集在支持应用方面灵活性大一些，但是采集效率可能不如全局URL采集，通常的搜索引擎采用全局URL采集的方法

161 采集网页的更新策略 定期重采 一段时间以后重新采集所有网页，全部采完以后替换原来的网页 增量采集 只按照某种策略采集那些可能新增、变化的网页，并删除那些已经不存在的网页 定期重采非常简单，但是浪费带宽，周期也长；增量采集可以节省带宽，网页更新周期相对较短，但是系统的复杂性增大

162 采集网页的速度保证措施 本地DNS解析 多机分布式并行 局域网联接多机进行采集并行 广域网分布式采集 单机多程序并行 多进程并行 多线程并行

163 采集网页的质量保证措施 减少重复页面的采集 保证重要页面的高优先级 URL重复的检测和排除 内容重复的检测和排除 入度高的网页相对重要
含有被别人广泛映像的内容的网页重要

164 采集中的行为问题 遵守网站上发布的Robot.txt采集限制协议
采集时尽量不要太过密集地采集某个网站，这种密集访问类似于DoS攻击，导致普通用户正常浏览网站产生困难。有些网站会严密控制这种密集访问行为

165 信息采集的研究趋势 高速、高质量的信息采集 个性化信息采集 基于主题的信息采集 信息的采集及抽取 只采集符合用户的兴趣的数据
采集某个领域的数据 信息的采集及抽取 采集后提取结构化信息

166 信息分析 对原始数据的预处理 信息分类&聚类 格式分析与转换(html/xml/doc/pdf/rtf)
语种识别、编码识别与转换(GB/BIG5/Unicode) 噪声数据的清洗 冗余数据的处理 信息分类&聚类

167 分类/聚类基本概念 分类/聚类是大自然的固有现象：物以类聚、人以群分 相似的对象往往聚集在一起 相对不相似的对象往往分开

168 关于分类 简单地说，分类(Categorization or Classification)就是按照某种标准给对象贴标签(label)
男/女、老人/青年

169 关于聚类 简单地说，聚类是指事先没有“标签”而通过某种成团的分析，找出事物之间存在聚集性原因的过程
在一个自习教室，往往发现大家三三两两扎推地坐，经过打听，总能找出扎堆的原因 事先不知道“标签”，根据对象之间的相似情况进行成团分析后，加上“标签”的过程

170 信息处理中分类和聚类的原因 分类/聚类的根本原因就是因为对象数目太多，处理困难 一些信息处理部门，一个工作人员一天要看上千份信息
分门别类将会大大减少处理难度，提高处理效率和效果

171 分类/聚类的过程 对对象进行表示 表示方法 特征选择 根据某种算法进行相似度计算 相似度计算方法 分类/聚类方法

172 文本分类的定义 Text Categorization/Classification
事先给定分类体系和训练样例(标注好类别信息的文本)，将文本分到某个或者某几个类别中 计算机自动分类，就是根据已经标注好类别信息的训练集合进行学习，将学习到的规律用于新样本(也叫测试样本)的类别判定 分类是有监督/指导学习(Supervised Learning)的一种

173 文本分类的模式 从类别数目来分 从是否兼类看分 2类(binary)问题，类别体系由两个互补类构成，一篇文本属于或不属于某一类
多类(multi-class)问题，类别体系由三个或者以上的类别构成，一篇文本可以属于某一个或者多个类别，通常可以通过拆分成多个2类问题来实现，也有直接面对多类问题的分类方法 从是否兼类看分 单标签(single label)问题：一个文本只属于一个类 多标签(multi-label)问题：一个文本可以属于多类，即出现兼类现象

174 分类体系 分类体系的构建标准可以是按照语义(如：政治、经济、军事…)，也可以是按照其他标准(如：垃圾vs. 非垃圾；游戏网站vs. 非游戏网站)，完全取决于目标应用的需求 分类体系一般由人工构造，可以是层次结构 Reuters语料分类体系、中图分类、Yahoo分类目录 对于计算机而言，分类体系就是一棵目录树，训练样例文本就是最后的叶子节点。而且对于计算机处理而言，只需要训练样例文本及其对应类别信息，整个过程通常并不会考虑类别标签的意义。也就是说：几篇文档合在一起表示某个类别

175 分类的应用 垃圾邮件的判定 新闻出版按照栏目分类 词性标注 词义排歧 计算机论文的领域 类别{spam, not-spam}
类别{政治,体育,军事,…} 词性标注 类别{名词,动词,形容词,…} 词义排歧 类别{词义1,词义2,…} 计算机论文的领域 类别ACM system H: information systems H.3: information retrieval and storage

176 文本分类——人工方法和自动方法 人工方法：人工总结规则 自动的方法(学习)：从训练语料中学习规则 优点 缺点
结果容易理解：如足球and 联赛􀃆体育类 缺点 费时费力 难以保证一致性和准确性(40%左右的准确率) 专家有时候凭空想象，没有基于真实语料的分布 代表方法：人们曾经通过知识工程的方法建立专家系统(80年代末期)用于分类 自动的方法(学习)：从训练语料中学习规则 快速 准确率相对高(准确率可达60%或者更高) 来源于真实文本，可信度高 结果可能不易理解(比如有时是一个复杂的数学表达式)

177 文本分类——规则方法和统计方法 规则方法通过得到某些规则来指导分类，而这些规则往往是人可以理解的
统计方法通过计算得到一些数学表达式来指导分类 规则方法和统计方法没有本质的区别，它们都是想得到某种规律性的东西来指导分类，统计方法得到的数学表达式可以认为是某种隐式规则 在目前的文本分类当中，统计方法占据了主流地位

178 文本分类的过程(1) 两个步骤： 文本表示(text representation) 训练(training)
即从训练样本中学习分类的规律 测试(test或分类classification) 根据学习到的规律对新来的文本进行类别判定 文本表示(text representation) 不管是训练还是测试，都要先分析出文本的某些特征(feature，也称为标引项term)，然后把文本变成这些特征的某种适宜处理的表示形式，通常都采用向量表示形式或者直接使用某些统计量

179 特征抽取(Feature Extraction)
预处理 去掉html一些tag标记 禁用词(stop words)去除、词根还原(stemming) (中文)分词、词性标注、短语识别、… 标引项频率统计 TFi,j: 特征i在文档j中出现次数，标引项频率(Term Frequency) DFi: 所有文档集合中出现特征i的文档数目，文档频率(Document Frequency) 数据清洗：去掉不合适的噪声文档或文档内垃圾数据 文本表示 向量空间模型 降维技术 特征选择(Feature Selection) 特征重构(Re-parameterisation，如LSI)

180 文本表示 向量空间模型(Vector Space Model，VSM) m个无序标引项ti(特征)，可以采用词根/词/短语/其他等单位
n个训练文档 每个文档dj可以用标引项向量(每个aij是权重)来表示 (a1j,a2j,…,amj) 通过向量的距离可以计算文档之间的相似度(分类的主要计算目标就是度量两篇文档之间的距离)

181 Term的粒度 Character，字：中 Word，词：中国 Phrase，短语：中国人民银行 Concept，概念
同义词：开心、高兴、兴奋 相关词cluster，word cluster：葛非/顾俊 N-gram，N元组：中国国人人民民银银行 某种规律性模式：比如某个window中出现的固定模式 David Lewis等一致地认为：(英文分类中)使用优化合并后的Words比较合适

182 权重计算方法(1) (Term i在文档j中的)布尔权重 TFIDF型权重 aij=1(TFij>0) or 0 (TFij=0)
TF: aij=TFij TF*IDF: aij=TFij*log(N/DFi) TFC: 对上面进行归一化 LTC: 降低TF的作用

183 权重计算方法(2) 基于熵概念的权重(Entropy weighting)* ni是term i在整个文档集合中出现的总次数(≠DFi)
Entropy(i)称为term i的某种熵 如果term i分布极度均匀：Entropy(i)等于-1 如果只在一个文档中出现：Entropy(i)等于0 *DumaisS T. Improving the retrieval of information from external sources[J]. Behavior ResMeth& Comp, 1991,23:

184 特征选择Feature selection(1)
基于DF的选择方法(DF Thresholding) Term的DF小于某个阈值去掉(太少，没有代表性) 信息增益(Information Gain, IG) 该term为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值)

185 特征选择(2) Term的某种熵 相对熵(not 交叉熵)
该值越大，说明分布越均匀，越有可能出现在较多的类别中；该值越小，说明分布越倾斜，词可能出现在较少的类别中 相对熵(not 交叉熵) 也称为KL距离(Kullback-Leiblerdivergence)，反映了在出现了某个特定词的条件下的文本类别的概率分布和无任何条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大

186 特征选择(3) χ2统计量(念xi, chi) 互信息(Mutual Information，MI)
度量两者(term和类别)独立性的缺乏程度 χ2 越大，独立性越小，相关性越大(N=A+B+C+D) 互信息(Mutual Information，MI) MI越大t和c共现程度越大

187 特征选择(4) Robertson & SparckJones公式 其他 Odds: Term Strength(TS)

188 特征重构 特征重构的目的是将现有的特征空间映射到其他更合适的特征空间当中去，以便获得更好的特征表示
隐性语义索引(Latent Semantic Index)是其中最有代表性的方法 另外，PCA(主成份分析)也可以用于特征重构

189 自动文本分类方法 决策树方法Decision Tree Decision Rule Classifiers 回归(Regression)方法
Rocchio方法 kNN方法 Naïve Bayes􀂄Online LinearClassifiers 多重神经网络方法Neural Networks 支持向量机SVM 基于投票的方法(Voting methods) 规则方法 统计方法

190 文本聚类定义 聚类是一个无导的学习过程 是指根据样本之间的某种距离在无监督条件下的聚簇过程 利用聚类方法可以把大量的文档划分成用户可迅速理解的簇(cluster)，从而使用户可以更快地把握大量文档中所包含的内容，加快分析速度并辅助决策 大规模文档聚类是解决海量文本中数据理解和信息挖掘的有效解决手段之一

191 文本聚类的应用 TDT(TopicDetection and Tracking)中主题事件的检测 检索结果的聚类显示 大规模文档的组织和呈现
将文档进行聚类，从聚出的类中发现新的热点主题 检索结果的聚类显示 检索结果聚类，以便用户浏览 大规模文档的组织和呈现

192 聚类算法(1) 层次方法（Hierarchical Methods） 划分方法(Partitioning Methods)
凝聚算法（Agglomerative Algorithms） 分裂算法（Divisive Algorithms） 划分方法(Partitioning Methods) Relocation Algorithms 概率聚类(Probabilistic Clustering) K-中心点算法(K-medoidsMethods) K-平均算法(K-means Methods) 基于密度的算法（Density-Based Algorithms） Density-Based Connectivity Clustering Density Functions Clustering

193 聚类算法(2) 基于网格的方法(Grid-Based Methods)
Methods Based on Co-Occurrence of Categorical Data Constraint-Based Clustering Clustering Algorithms Used in Machine Learning Gradient Descent and Artificial Neural Networkds Evolutionary Methods Scalable Clustering Algorithms Algorithms For High Dimensional Data Subspace Clustering Projection Techniques Co-Clustering Techniques

194 凝聚式层次聚类(HAC) 算法流程 Step1: 将所有的点各自单独形成一个簇;
Step3: 如果只剩下一个簇或者达到终止条件(比如达到需要的簇的数目),聚类结束,否则返回Step2.

195 k-Means聚类分析 算法流程 Step1: 初始化k个簇中心;
Step4: 如果簇变化不大或者满足某种退出条件(达到最大迭代次数、满足某种目标函数等)，那么结束聚类，否则返回Step2

196 BiSectingk-Means聚类(BiSect)
算法流程 Step1: 将所有的点形成一个簇; Step2: 从现有所有的簇中选择包含文档数最大的簇进行拆分，用k-Means算法(k=2)将该簇分成2个簇; Step3: 如果达到了需要的簇的数目则结束

197 最近邻聚类(Nearest Neighbour)
算法流程 Step1：随机选择一个样本，以该样本为中心建立一个新簇; Step2：取下一个要分析的对象，如果没有对象需要聚类，那么聚类结束； Step3：计算当前对象与当前所有簇的相似度，得到相似度最大的簇及对应的相似度d,如果d>阈值T,那么将该对象分配给选中的簇，更新簇的中心；否则以该对象为中心新建一个簇； Step4：返回Step2

198 MaxDist算法 算法流程 Step1：从Ds中任取一个样本，例如D1，以D1作为簇中心新建一个簇
Step2：在Ds中找一个与D1最远的样本并以之为中心新建一个簇，从而形成两个簇，记录该最远距离为max,同时算出阈值(可以为max的p倍，1/2<=p<1)； Step3: 对于剩下的点顺序扫描,计算该点与所有的簇的距离的最小值； Step4: 如果最小距离大于阈值并且未达到需要的类数,则以该点新建一个簇;返回Step3，否则如果没有点了或者达到需要的类数,结束聚类 Step5:返回Step3

199 文本聚类评估——纯度 用已有分类结果作为评测集合来评估 对于聚类结果中的类别r，nr是r中文档个数，表示属于分类中第i类在r中的文档个数
整个结果的纯度

200 文本聚类评估——F值 n(i,r)是属于i类但是分到r类中文档个数，nr是r类文档个数，ni是测试集合中i类中的文档个数，F是R和P的调和平均 最终结果，n是文档总数

201 查询的分析和挖掘 查询的意图分析 查询日志挖掘 查询的意图分类 通过查询的意图分析可以指导后续的工作，是一个新的研究方向 发现用户的兴趣
informational: 中国科学院 navigational: 中国知识产权局主页 transactional: 赴美签证表格下载 通过查询的意图分析可以指导后续的工作，是一个新的研究方向 查询日志挖掘 发现用户的兴趣

202 查询扩展 对用户的查询进行扩充 查询重构 比如用户输入计算机，我们扩充一个词电脑 同义词扩展 相关词扩展
同义词词典 通过统计构造的同义词词典 相关词扩展 相关词：“2006世界杯”与“德国” 基于全局分析的查询扩展：对文档集合进行分析得到某种相关词典 查询重构 对用户的初始查询进行修改(可以是加词、减词，或者对于向量模型表示的初始查询进行权重的修改等等)，是比查询扩展更泛的一个概念

203 相关反馈 指根据用户对初始检索结果的干预来重新生成查询或者修改模型参数等等 伪相关反馈
系统假定一些相关的结果，并根据这些结果来进行返回 相关反馈是一种手段，目的可以是查询扩展或者重构，也可以是模型的调整 基于伪相关反馈和局部分析进行查询重构 根据某些文档中的信息来对查询进行重构

204 摘要生成 静态摘要 动态摘要 静态摘要比较简单，但是由于多Topic问题的存在，效果往往不好
一个网页事先生成其摘要 动态摘要 基于Query的摘要，不同的Query会生成不同的摘要 静态摘要比较简单，但是由于多Topic问题的存在，效果往往不好 现代搜索引擎往往采用动态摘要，用户也认可这种方式

205 Web作弊与反作弊 Web作弊(Web Spam)是指采取一些迷惑、欺骗搜索引擎的手段，使某些Web页面在检索结果中的排名高于实际应得的排名的行为 有人估计WEB中有10%~15%的作弊内容 搜索引擎优化(Search Engine Optimizing) 行业的诞生 正当手段：对网页进行优化(标题、布局) 作弊手段：欺骗搜索引擎的手段 反作弊(anti-spam)是搜索引擎公司的一项重要任务 学术界2005年开始就有AIRWeb Adversarial Information Retrieval的Workshop

206 Web作弊的危害 降低用户体验的满意程度，降低用户对搜索引擎的信任 搜索引擎公司会因用户的满意度降低而使其商业价值受到损害
作弊或者垃圾页面也消耗了大量时间和空间

207 Web作弊的方法 各种提高排名的技术 各种隐蔽技术，用于使第一类技术的使用不被发现

208 利用关键词提高排名 内容匹配仍是大部分搜索引擎排名算法的重要组成部分。TF*IDF仍是基本思想。 作弊方法一 作弊方法二
在网页(标题或者元信息域)中加入大量关键词，使得查询和目标网页匹配上的关键词个数增多，从而提高排名 作弊方法二 在网页中(标题或者元信息域)加入大量与某些查询相关的重复“关键词”，使得网页排名上升

209 利用链接提高排名(1) 根据搜索引擎所采用的链接分析算法，构造具有某些链接结构的作弊网站，迷惑搜索引擎，提高排名
出链接作弊(破坏HITS算法)：在网页上加入大量的出链接指向著名站点，提高本网页的Hub值 如采用目录克隆(directory cloning)方法直接拷贝 如DMOZ Open Directory Project上的全部或者部分目录

210 利用链接提高排名(2) 入链接作弊： 蜜罐诱饵(honey pot) 渗入Web目录
一组提供有用资源的网页，包含了许多指向目标作弊网页的链接，它们像蜜罐一样引诱其他页面指向它们，从而间接提高的目标作弊网页的排名 渗入Web目录 作弊者提交网页到一些著名的WEB目录，编辑者可能没有严格审查，而上述提交网页中含有指向目标作弊网页的链接，由于WEB分类目录通常具有很高的PageRank和Hub，所以目标网页的排名也能提高

211 利用链接提高排名(3) 入链接作弊 张贴法：在Blog、BBS、留言板或Wiki上张贴链接指向目标作弊网页
链接交换：作弊者联合作案，作弊网站互相链接 购买过期域名：过期域名指向作弊链接 构造链接农场(link farm)：操作大量网站，构造能够提高PageRank的任意网站。现在投资已经很少。 泛域名作弊(二级域名作弊)：最低一级域名是随机生成的，这些域名代表的页面要么互相链接，要么指向同一作弊网页，要么重定向到一个作弊页面。如：中文互联网上的oouv.com, com等

212 隐蔽技术——内容隐藏 浏览器显示页面时，用户看不到作弊的关键词或者链接 通过颜色配置使得关键词和背景颜色一样 作弊链接不加上文字后不可见
将作弊链接加在非常小的透明或者和背景一样颜色的图片上 使用脚本技术来隐藏网页中的一些可见成分，如将HTML风格中的Visible属性设为false

213 隐蔽技术——覆盖(Cloaking) 通过识别网站的访问者是否搜索引擎的爬虫来提供不同的URL。作弊网页被提供给搜索引擎用于建立索引。而用户访问时显示为另一个正常页面

214 隐蔽技术——重定向 网页在被浏览器载入时自动重定向到另一个URL。这样的网页仍然可以被搜索引擎抓取，但是用户却看不到它
这样作弊网页被抓取，而用户看到的却是重定向后的目标文件 简单的方法就是在网页头部meta中的refresh时间设为0 更高级的方法采用一些脚本技术

215 一些反作弊技术 TrustRank：为网页建立信任值 改进的PageRank方法：识别链接农场作弊方法。
语言模型方法：根据不同类型网页内容的语言模型的差别进行判别 网页版本差异判断方法：采用浏览器方法和爬虫方法同时抓取 目前这些方法的精度仍然不是很高，因受各种限制，很多方法在搜索引擎中并没大量使用

216 信息可视化研究的一般概念 什么是可视化? Visualize:
现代可视化技术是指运用计算机图形学和图像处理技术，将数据转换为图形或图像在屏幕上显示出来，并进行交互处理的理论、方法和技术 Visualize: Interactive -- 互动式的 Visual representation – 可视的 Amplify cognition – 提高认知功能的

217 信息可视化研究的一般概念 信息可视化的三大支柱 The power of Perception The power of Graphics
感知的功能 The power of Graphics 图形的功力 The power of Associations 联想的潜力

218 信息可视化应用研究 信息可视化的应用 数据分析 海量数据的图形化表示 实现与数据的可视化交互
Visual inspection of data properties Dimensional deduction 海量数据的图形化表示 Clustering and grouping Discovery of hidden internal structures 实现与数据的可视化交互 interactive online searching browse large amount of information

219 信息可视化应用研究 在电子数字图书馆中的应用 揭示信息的分布 显示检索的结果 为大量的信息分类 帮助用户浏览 提供个性化信息服务

220 信息可视化应用研究 帮助浏览

221 可视化检索 两个有影响的国际研讨会 国际上已经取得的成果 1995年起，每年10月美国IEEE信息可视化国际研讨会
1997年起，每年7月英国信息可视化国际研讨会 国际上已经取得的成果 可视化理论模型研究 出现一批原型系统

222 可视化检索 可视化检索技术 格式刷和连接，颜色联动 摇镜头 魔幻镜头 两个和更多窗口的连接 变换聚焦，变换景深
通过点击代表不同的检索对象，实现覆盖对象和未覆盖对象之间的切换

223 信息检索评价的类型 系统评价主要包括 信息检索系统还包括其他一些度量指标。 功能评价，即评价一个系统是否完成了它所侧重的目标。
性能评价，主要指标是时间与空间的开销。（如：对数据检索系统的评价）响应时间越短，占用的空间越少，系统性能越好 信息检索系统还包括其他一些度量指标。 这是由于用户的查询请求本身具有模糊性，检出的结果不一定是精确答案。需要依照与查询的相关度，对结果集合的准确度进行评价。

224 信息检索评价的类型 检索性能评价 批处理模式 交互模式 用户提交提问，并得到检索结果 产生检索结果集合的方法
用户通过于系统一系列交互步骤提交信息需求 涉及的因素 用户因素 界面性能 系统的导引性能 过程的时间

225 检索评测基础 检索评测基础: 建立在测试参考集和一定的评价测度基础之上。 检索策略的评价
检索评测基础: 建立在测试参考集和一定的评价测度基础之上。 测试集由一个文档集、一组信息查询实例、对应于每个信息查询实例的一组相关文档（由专家提供）所组成。  检索策略的评价 对一个给定检索策略S，对每个信息查询实例，评测由S检出的结果集合与由专家提供的相关文档集之间的相似性，量化这一指标。

226 国内外检索评价历史 理论研究综述： 思辨性论述
Shamber1994年的综述：相关性的意义及其在信息行为中扮演的角色 归纳了6类80个影响因素，偏重于定量的查全率和查准率，以及定性的效用(utility)和满意度(satisfaction) Saracevic1994年的综述 归纳了系统、通信、情景、心理四种模型，据此提出了第5种模型：交互式模型，它借用了人机交互研究种的阐释理论和语言学中的分层理论 Mizzaro1998年的综述 以4维框架描述了所有的相关性概念和模型：信息资源维、用户信息需求的描述维、时间维、主题任务和背景维 思辨性论述 Borlund的论述 不能形成相关性定义的原因是相关性是一个多维的、认知的、动态的概念。通过重新引入情景相关性，构建整体的相关性框架

227 国内外检索评价历史 纵观80年的研究历史 两个主要流派 两个研究高峰 相关性是一个多维的、认知的、动态、可测度的概念，已经成为共识。
面向系统和面向用户 两个研究高峰 60年～79年代前期，80年代中后期至今 相关性是一个多维的、认知的、动态、可测度的概念，已经成为共识。 国外实证研究是最基本的研究手段，国内则鲜有开展，这是国内研究没有实质性成果的一个关键原因。

228 国内外检索评价历史 系统性 主观性 认知性 情景性 多维性 动态性 可测度性 是目前信息检索系统的主要实现方式
依赖于人的判断，不是文献和信息的内在特征 认知性 最终依赖于人的知识和理解 情景性 与个体用户的信息问题紧密相连 多维性 受到多种因素的影响 动态性 随着时间的推移不断变化 可测度性 在某个特定的时间是可以观察的

229 国内外检索评价研究的遗憾 面向系统的研究没有考虑用户层面 面向用户的研究没有考虑系统层面 融合两者研究，是将相关性研究引向深入的一大难题

230 面向用户的相关性 信息观的相关性 Ingwersen的研究：4种关于性(aboutness)
判断主要基于信息问题与信息外在表现间的关系，判断的实质是判断者内在的知识储备 Ingwersen的研究：4种关于性(aboutness) 作者关于性 相关性与作者撰著的文档中的内容相联系，因而可以直接采用文档中的词汇表示信息，是自动标引和匹配技术的理论基础 标引者关于性 相关性由标引者以控制词表描述作者自然语言的标引结果决定。理论上，这种相关性要优于作者关于性的，实践中不一致性客观存在。 查询关于性 相关性由用户将查询七国求转换为查询表达式决定 用户关于性 相关性由标引者在标引时对用户的所知和所想的考虑

231 用户评价指标——情景观的相关性 描述信息与用户信息问题情景之间的关系，认为只有用户才能完成有效的相关性判断，在主观性方面，比信息观的相关性前进了一步。 Wilson的研究 判定情景相关的先决条件，必须先了解并描述信息需求者个人所处的情景。影响情景相关的要素 偏好，用户偏好与问题和答案息息相关 兴趣，用户所关心的事物多为其有兴趣的 时间，相关会随着时间、时代的改变有所不同 程度，相关应有程度上的不同 显著信息，可改变认知状态的价值大的信息 实用信息，

232 用户评价指标——情景观的相关性 Wilson的研究的影响 情景相关研究面临的最大问题是如何描述个人的认知状态，文字与文字指甲的演绎与归纳关系
将相关的范围延伸到个人的知识状态，和当今的信息系统设计理念不谋而合 情景相关研究面临的最大问题是如何描述个人的认知状态，文字与文字指甲的演绎与归纳关系 需要研究者在认知心理学、学习理论、人类思维领域进行深入的研究，需要多学科的合作

233 并行计算 并行计算 用多个处理器去求解单个问题，把单个大问题分解成若干“部分”，每个“部分”采用单个处理器去解决
并行计算通过“以成本换时间”的方式来减少求解问题的总时间 总时间取决于时间最长的那个“部分”问题的求解 通过并行计算，系统具有较好的可伸缩性

234 并行体系结构 可以将多处理器进行不同组合构成并行体系结构
按照指令(Instruction)流和数据(Data)流的数目，Flynn将并行体系结构分成四类： SISD：单指令流单数据流，如传统的冯.诺依曼计算机 SIMD：单指令流多数据流，N个处理器，N个数据流，但是多个处理器执行相同的操作 MISD：多指令流单数据流，N个处理器处理共享内存中的单数据流，每个处理器的操作不同，目前MISD结构已经非常少见 MIMD：多指令流多数据流，N个处理器，N个数据流，每个处理器处理自己的操作。多处理器可以处理不同任务或者协同处理单个任务。MIMD是目前最通用和最流行的一类并行体系结构。处理器之间交互(通信)频繁的MIMD系统称为紧耦合系统，反之称为松耦合系统

235 分布式计算 分布式计算 通过局域网或者广域网将多台计算机连接起来，协同处理一个问题 分布式结构可以看成MIMD并行结构的一个松耦合特例。
当然，所谓“大小”都只具相对意义

236 并行计算的性能度量 与运行在单处理器上的顺序计算相比，并行计算所获得的性能改善通常采用加速比(speedup)来度量 S=Ts/Tp

237 一般检索过程 此处讨论不考虑采集，其实采集可以、也常常通过并行的方式来实现

238 多任务(multitasking)并行 多条查询之间是并行处理的，互不干扰 多任务并行的方式非常容易扩展 对于单条查询而言，检索时间并没减少
复制一个搜索引擎即可

239 单查询内部并行 如将“大规模信息检索技术”拆分成三个子查询同时进行处理，然后合并。或者不进行拆分，但是对每个搜索程序只搜索部分数据集(类似于元搜索)，然后合并。因为，查询的切分着实不易，应该说后一种方法更加普遍。所以需要进行数据分割 相对而言，这种单查询内部并行，处理上复杂一些，但是能提高单条查询检索的速度

240 Term-Document视图

241 基于文档分割的倒排索引分割

242 基于文档分割的倒排索引分割 逻辑文档分割后的检索过程
用户输入查询，代理将所需词典词条和所有posting list放入共享内存，每个处理器负责访问各自的文档信息，进行相似度计算，最后将结果汇总 因为，多个处理器对索引的访问都是“读”操作，所以没有访问冲突问题。每个处理器返回结果都在自己的文档子集中，所以也没有“写”冲突

243 基于文档分割的倒排索引分割 物理文档分割 检索过程 问题 解决办法 逻辑文档分割 vs. 物理文档分割
把倒排表真正分开为分离的文档子集，每个子集对应一个处理器 检索过程 和逻辑文档分割类似 问题 在每个处理器进行检索时，需要用到全局统计信息(如IDF)以便获得全局一致的相似度计算值。而如果一开始就进行文档分割，然后分别建立索引，则缺乏全局信息 解决办法 索引建立阶段即将全局统计信息随同每个文档子集一起保存 通过代理先搜集每个文档子集的统计信息，计算成全局统计信息，然后将查询和全局信息一起发给每个搜索进程 逻辑文档分割 vs. 物理文档分割 前者不需要通讯过程，整体性能可能好一些，但是灵活性和可扩充性不如物理分割

244 基于Term分割的倒排索引分割 Term分割 检索过程 文档分割 vs. Term分割
将不同Term的posting list分配给不同的处理器 检索过程 将查询分解成多个Term，每个Term送到一个处理器上去，处理器处理对应的倒排文件 每个处理器的检索结果返回给代理，代理根据查询的语义(如布尔查询中的与或非)将结果进行合并 文档分割 vs. Term分割 对于倒排表构建和维护，前者比较简单。而在查询处理方面，如果每个处理器具有自己的I/O和磁盘，则实验表明：如果Term在查询和文档中的分布比较偏斜(skewed，扭曲，不对称)时，文档分割方法较好 如果，Term在Query中均匀分布，则Term分割方法较好

245 分布式信息检索 分布式信息检索将更大范围分布的异构数据联合起来，形成一个逻辑整体，为用户提供强大的信息检索能力
分布文档集包括文本、多媒体等多种格式数据，后台可能存在无格式、半格式和格式数据 分布式检索的目标就是按照一致的信息描述，标识和检索分布文档集。根据用户的查询请求，分布式检索工具将之转换为每个数据集合的对应查询并选择部分数据子集合进行检索，检索结果进行合并输出

246 分布式检索体系结构

247 分布式检索 vs. 并行检索 分布式检索通过网络协议(如TCP/IP)来通信，而并行检索有时采用共享内存的方式通信
分布式检索只选择部分搜索服务器进行检索，有数据分割和选择问题，而并行检索通常采用广播方式 分布式检索的各搜索服务器之间通信开销大，因此通信较少，而且通常采用文档分割的方式。而并行检索各搜索进程之间可以有较频繁的通信，可以采用文档分割或Term分割方式 分布式检索面向异构数据，要考虑检索协议问题

248 分布式信息检索的文档集分割 分开管理的检索系统 集中管理下的检索系统
每个搜索服务被独立管理，此时文档集分割不受自己控制。不同检索系统可能各有侧重，比如：不同搜索厂商提供不同领域的检索。这样通过元搜索的方式可以实现分布式检索 集中管理下的检索系统 方法1：在所有搜索服务器上复制文档集。 适合于文档集合比较小的情况，但是需要高可靠性和强查询处理能力。这种情况下，可以通过多任务方式实现搜索服务 方法2：将文档在所有搜索服务器上进行随机分布。 查询发给所有搜索服务器，然后进行结果汇总 方法3：对文档集进行语义分割。 只将查询选择性地发给一些文档子集，然后将结果进行合并

249 分布式信息检索中的查询处理 基本步骤 资源选择 查询分发 并行搜索 结果合并 选择合适的文档集，用于搜索 将查询分发到这些文档集上
对文档集并行执行查询 结果合并 合并从各文档集返回的检索结果，从而形成最终查询结果

250 资源选择 首先对资源进行描述，某个查询选择和自己最相关的N个资源或相似度大于某个阈值的文档集进行检索
如果资源是随机分割时或者资源之间语义重叠时，只需将查询分发到所有资源上去，此时不存在资源选择问题 当资源按语义进行分割，则： 方法1 计算查询和资源之间的余弦距离对资源进行排序 方法2 将k个文档组成1块，计算查询和每个块的距离 方法3 建立资源的查询样本，新查询和这些查询样本进行相似度计算

251 结果合并 布尔查询的结果合并 对自由文本查询的结果合并 根据布尔操作的语义对结果进行合并 方法1：不同检索结果交替排序
方法2：基于全局相似度进行排序 方法3：选择资源时，不同资源具有不同权重，利用这些权重信息进行排序 方法4：利用归一化的相似度来排序

252 跨语言检索概念 跨语言检索(Cross-Language Information Retrieval, CLIR)：输入某种语言(源语言)的查询，在一个或者多个其他语言(目标语言)的文档库中检索结果 例子：输入“信息检索”，在英文文档库中检索结果 也称为Cross-lingual IR, Trans-lingual IR 当只有一种目标语言时，称为双语检索(Bilingual IR) 当有多个目标语言时，称为多语言检索(Multilingual IR) 与此对应，传统的检索称为单语检索(Monolingual IR 或者Single Language IR)

253 CLIR的难点 CLIR仍然依赖于单语检索的效果，而单语检索本来就不容易
目前单语检索仍然主要是基于关键词匹配的方法，不能准确地理解用户的查询需求，检索的准确性仍然不高 源语言和目标语言之间可能存在巨大的语言鸿沟 以世界上使用最广泛、使用人口最多的英文和 中文为例，两种语言不论在词法、句法还是语义处理等方面都有巨大差异 同根语言对之间可能翻译的难度小一些，但是作为不同的语言，仍然具有较大的差异，全自动翻译仍然达不到实用水平

254 主要的解决办法—翻译 方式一 优点 缺点 将所有文档翻译成源语言，采用单语检索的方法 检索结果可读
文档的翻译理论上相对准确(可以依靠上下文解决翻译中的歧义) 缺点 翻译量巨大，翻译的时间消耗较大 在多语言检索情况下，需要多个语言对之间的翻译工具

255 主要的解决办法—翻译 方式二 优点 缺点 查询翻译方法是目前CLIR中的主要方法。 将查询翻译成目标语言 翻译量小，相对灵活
由于查询通常很短，翻译质量难易保证 如果用户不懂目标语言，仍然需要把结果再翻译成源语言 查询翻译方法是目前CLIR中的主要方法。

256 翻译的主要做法 基于词典的方法 基于机器翻译工具的方法 基于并行语料库的方法
通过查词典(双语词典、同义词词典、统计词典等)，将源语言的Term变成目标语言的Term 基于机器翻译工具的方法 通过机器翻译工具，将源语言翻译成目标语言 基于并行语料库的方法 对于一个查询，先在一个并行语料库中搜索，利用并行语料之间的对齐关系，将源语言搜索结果映射成目标语言

257 CLIR中两个主要技术难点 一词多译 未定义词(Out Of Vocabulary，OOV)问题
一个词或者片断有多个可能的译文。一般通过上下文进行排歧 未定义词(Out Of Vocabulary，OOV)问题 词典里找不到这个词 一般通过并行语料获取及对齐等方法来解决

258 多语言检索的实现 separate-retrieval-then-merging middle-language 类单语言检索方法
将查询翻译成各种语言，分别进行单语检索，最后将结果合并 middle-language 将查询翻译成某个中间语言，然后将中间语言查询翻译到目标语言分别进行检索，最后将结果合并 类单语言检索方法 将原始查询和翻译到每种目标语言的查询综合在一起，在所有文档库上进行单语检索

259 国际CLIR评测 TREC中CLIR评测 CLEF(CrossLanguage Evaluation Forum)
1997年开始设立CLIR评测，近几年取消，转入CLEF和NTCIR CLEF(CrossLanguage Evaluation Forum) 主要针对欧洲语言对之间的检索评测 NTCIR(NII-NACSIS Test Collection for IR Systems )会议 日本国立信息研究所（National Institute of Informatics）主办的信息检索测试集评测会议。主要针对英文及主要亚洲语言的检索评测

260 问答系统概念 问答系统(Question Answering，QA) 比搜索引擎更进一步，不仅仅返回相关的文档，而且直接返回正确答案
给定一个问题，从大规模文档集合中返回答案的系统 例子：谁获得2006年多哈亚运会男子体操全能冠军？杨威 比搜索引擎更进一步，不仅仅返回相关的文档，而且直接返回正确答案

261 QA系统的两种做法 方法一：模板匹配(Template Matching)方法 严格地说，此类系统不算是QA系统。如：ASKJeeves
模板：[NP] 是谁？ 孙中山是谁？ 美国总统是谁？ 一个问题提出以后，从已有的模板库中进行匹配，匹配上以后，根据模板对应的处理方法调处理过程 严格地说，此类系统不算是QA系统。如：ASKJeeves

262 QA系统的两种做法 方法二：先分析问题的类型，然后从可能存在答案的结果文档中抽取答案
TREC QA系统：大部分系统采用了此种类型，先通过问题类型分析模块确定问题的类型，然后通过检索返回可能的文档或者段落，最后在这些文档或段落中抽取相应类型的问题答案

263 问题类型的判定 人工规则 人工总结出一些判定规则，如：who􀃆找人 机器学习的方法 建立训练语料，通过统计学习的方法学习到统计规则

264 答案的抽取(以事实型问题为例) 命名实体的识别 人名、地名、机构名等等命名实体的识别 命名实体的评分 为命名实体打分，找出最可能的命名实体

265 云计算综述 PC C/S 云计算 数据在云端：不怕丢失,不必备份,可以任意点的恢复 ； 软件在云端：不必下载自动升级 ；
无所不在的计算：在任何时间，任意地点，任何设备登录后就可以进行计算服务； 无限强大的计算：具有无限空间的，无限速度。 PC C/S 云计算 硬件为中心 软件为中心 服务为中心

266 基本概念 狭义上的云计算是指用虚拟技术构建的虚拟化数据中心，将分布在大量的计算机和存储设备（包括本地或远程设备）上的计算和存储资源（包括内存、I/O设备、存储、带宽、计算能力等）集中起来成为一个虚拟的资源池，以服务方式按需（免费或租用）提供给网络用户 这种云计算被称为“基础设施即服务”IaaS（Infrastructure as a Service，也被称为“硬件即服务”HaaS，Hardware as a Service）的模式。Amazon的E2和E3是这类模式的代表

267 基本概念 广义上的云计算还包括软件即服务SaaS（Softwre as a Service）、平台即服务PaaS（Platform as a Service）等多种服务模式。SaaS通过浏览器把程序以服务方式交付给用户，向用户收取服务费 用户通过互联网使用程序，降低在服务器和软件的购买及系统运维成本；供应商只需统一安装和维护一套软硬件系统，如Salesforce.com等。很多SaaS还提供了开放API，让开发者能够开发更多的互联网应用。PaaS将把开发环境、应用程序运行环境、数据库环境等作为一种服务来提供给开发商，由后者开发程序并通过互联网提供给用户 这类服务商有Google的应用软件引擎Google AppEngine和Salesforce的网络应用软件平台force.com等 图情界一般引用其广义概念

268 云计算的形式 云计算的内涵非常丰富。云计算形式包括： 云计算的特性 以服务为交付模式的计算和存储基础设施；
包括虚拟主机租用、应用服务环境租用、数据库环境租用、编程模型、数据服务（Data as a Service）、商业流程服务（Process as a Service）、应用服务（Application as a Service）等各种模式 云计算的特性 对资源动态分配；以Web为中心；交付的是服务

269 云计算六种服务方式 SAAS( Software as a Service ) PAAS( Platform as a Service )
IAAS( Infrastructure as a Service ) 云存储 MSP（管理服务提供） 商业服务平台

270 云服务示例- Amazon 云计算服务领跑者亚马逊继续保持领先的位置 Simple Queue Service（简单排列服务）
Simple Storage Service（即S3，简单的存储服务 Amazon Elastic Compute Cloud（弹性计算云，EC2、EBS ） Amazon Flexible Payments Service Amazon SimpleDB Amazon DevPay

271 云服务示例 - IBM Cloud Computing Virtual Client service
Service Catalog Datacenter Infrastructure Virtual Client service Web Application Service Compute Service Database service Storage service Content Classification Storage backup, archive… service Job Scheduling Service Collaboration Services

272 云服务示例 - Microsoft 2008年10月份，微软相继发布了一系列产品，以迎接“云计算”时代的到来
推出了新操作系统Azure，企业用户既可以在公司电脑上运行，也可以经由微软通过互联网提供相同服务；将以“即用即付”模式对Azure定价； 新推出的Windows Live可以让个人用户与好友一起存储、恢复和共享图片、博客和其它网站内容 推出企业级Exchange电邮的网络版和Office网络版

273 云带来的变化 最重要的产业变化体现在5个方面
第一，信息产业从PC 时代走向互联网时代，而产业也将从PC时代的应用为中心走向以数据为中心，谁拥有最多、最智能、最结构化、最相关的数据，谁就拥有优势 第二个变化体现在，PC功能和定义将发生很大改变，虽然PC仍是重要的工具，但PC将走向PC+：个人计算能力进入手机、电视、汽车、传感器等，只要有电的地方都有计算的时代 第三个变化是，计算的架构从过去集中于PC或服务器的某一“端”走向“云”+“端”，即"C+C"(Cloud+Client) 第四个变化是，软件企业的业务模式从软件走向了“软件+服务” 第五个变化是，市场的基础将从过去几十年来服务了第一个10亿人(1B)走向服务更多用户 “云计算”已经能够把PC上好的应用放到手机、电视等终端设备上，让发展中国家的用户先体验到“云计算”带来的服务。

274 文献管理（noteexpress，endnotes、refworks） 机构知识库（Dspace，Eprints）
面向科研学术活动的信息服务 需求调研 科研实施 成果共享与推广 科研数据采集与分析 学术论坛 交流通讯（微软、北电的统一沟通平台） 文献管理（noteexpress，endnotes、refworks） 项目管理（Project、Jira） 企业需求与技术转移 文献资源查找 网络出版（Apabi） 机构知识库（Dspace，Eprints） 项目申请助手 信息检索与搜索引擎 学 研 产 服务开始渗透到活动全过程、全方位 274

275 数字图书馆与读者的关系 数字图书馆为用户提供一个学习与研究的平台 海量文献资源 专业的、个性化的服务 学习与研究的工具 决策参考工具
本地化信息化服务

276 数字图书馆的云模式需求 包括两个方面：云构建和云提供 基本服务 高级服务
硬件及应用托管 提供计算服务和存储服务 资源整合 高级服务 链接整合，统一检索 数字资源调度服务 用户行为分析、资源访问统计及分析 读者的观点、评价挖掘 用户不管资源在哪，是哪个数据库，希望最快、最直接的方式，得到他所希望的文献格式

277 数字图书馆云服务的构建 ——从管理者角度 云服务的构建——云平台 以基础设施服务IaaS和基础平台服务PaaS为基础，包括以下4个方面的内容
1）面向图书馆的公共服务平台 2）面向图书馆的SaaS服务平台 3）面向图书馆的本地服务平台（包括本地应用基础平台和本地应用系统） 4）面向图书馆的服务整合平台 开放架构，以便将不同的图书馆本地服务、区域DL公共服务、行业公共服务以及第三方公共服务集成起来

278 数字图书馆云服务模型图 公共云 私有云 混合云 服务接口
基础设施服务 (虚拟服务器、存储和网络) Applications, Processes and Information as a service 软件平台服务 (中间件 – 桌面，应用服务器，数据库服务器, 门户服务器等.) 公共云 (Google,NSTL,CALIS,CSDL) 私有云 (本地数据中心) 混合云 (public and private) 服务接口

279 数字图书馆公共服务平台 该公共服务平台由一组软件构成，可以在云中使用，提供的基本服务包括
统一认证服务 计费服务 联合资源检索服务 数据服务、知识服务 数字对象存储和下载服务 元数据联合编目服务 文献联合订购服务 全局资源调度服务 上述服务既可以直接面向图书馆，也可以通过一组Open API提供给图书馆

280 数字图书馆SaaS服务平台 SaaS服务平台直接面向图书馆提供最终的应用服务 包括 馆际互借SaaS服务 参考咨询SaaS服务
各个馆可以按需租用部分或全部服务

281 本地服务平台 本地应用基础平台 本地应用系统
具有统一服务注册和管理、统一监控和日志管理、本地统一认证/授权、单点登录、公共服务发布、外部服务订阅功等核心功能 提供状态管理、负载管理等实时服务，提供简化和自动化的部署和管理方式，保证服务的可获得性和伸缩能力 本地应用系统 用于为图书馆提供具体的业务功能

282 服务整合 统一基础信息 数字图书馆云服务平台建立和管理统一的基础信息，包括用户信息、知识库信息、应用/资源/服务/仓储注册信息、数据信息、订阅信息、计费信息等。这些信息为服务整合奠定了基础。 统一API Open API是web 2.0的一种服务模式，也是云计算的服务方式。利用这些API可以实现对分散数据和服务进行整合（mash-up），能带来有新价值的web服务。

283 数字图书馆服务平台 服务平台提供的所有服务分为三个层次
系统内的私有服务：同一系统内的私有服务的注册和管理由OSGi基础框架完成。这些服务无需对系统外提供。 馆内/平台内的私有服务（即私有API），可以被同一个平台内的其他系统调用，如，读者借阅 馆/平台的公有服务（即Open API）可以被另一个馆/平台所访问，例如，OPAC

284 数据连通 按照用户需求进行数据的整合 整合不同来源、不同类型的各种数据 整合的深度 机构数字图书馆 学科数字图书馆 个人数字图书馆（在线）
中文、英文、…… 期刊、报纸、学位论文、…… 整合的深度 元数据级的整合

285 服务的互连通 统一服务协议 服务构建 例如，订阅服务 通过统一的订阅服务协议，订阅不同系统的服务 由不同系统的元服务构建成一项新的服务
服务来源于外部公共“云”，本地私有“云” 用户不管服务来自哪里，本地，其它DL，其它数字图书馆联盟

286 云成为信息服务的超级引擎 地域化的互联网信息服务的重要组成 网络档案 社区交友 信息资源 产业（面向产业的特色库） 商家档案，服务档案
人物档案 专家学者档案 信息资源 区域数字资源整合 网页资源

287 学术交流：学术社区网络 以文献资源为基础建立起来的学术社区网络 交流手段 研究人员通过文献发现相关的研究人员
研究人员之间建立联系，并构建社交网络 交流手段 即时通讯 邮件 实时讨论会 大型网络会议

288 CALIS馆际互借系统共享版模式图

289 建设模式

290 联机编目 保留现有各成员馆联机编目模式 与图书公司合作，建立集中编目点 电子资源编目：集中加工，免费下载 小语种：与外语类院校合作
联机编目中心培训、认证 质量控制 电子资源编目：集中加工，免费下载 小语种：与外语类院校合作

291 数字图书馆云服务的终极目标 云计算是目前IT发展速度最快的 云里雾里，在全球超大的云计算平台中，有一朵数字图书馆的云
用户象使用水、电一样，通过互联网，或各种计算终端，方便地使用本地和远程数字图书馆所提供的各种资源和服务