精华内容
参与话题
问答
  • 信息检索基础知识总结

    千次阅读 2017-04-25 09:46:19
    在文本检索和处理应用中, 可以通过该模型很方便的计算词频。有如下例子: S1:more ugly less bug is ugly. S2:more ugly less bug have bug. 根据上述S1、S2中出现的单词, 我们能构建出一个字典,{1:"more",2:...

    此篇为我在学习检索时遇到的基础知识的总结,以便巩固复习。

    一、信息检索评价指标

    最基本指标:查全率R(召回率 Recall rate)、查准率P(Precision rate),计算公式如下:


    准确率和召回率是互相影响的,一般情况下查准率高、召回率就低,召回率低、查准率高。在检索中往往要在保证召回率的前提下提高查准率。在对查准率和召回率都要求高时,可以用F-Measure综合考虑他们,当a=1时,就是常见的F1了,F1综合了P和R的结果,当F1较高时则比较说明实验方法比较理想。计算公式如下:


    1.1、MAP

    无论是召回率R、查准率P还是F1,都存在有单点值局限性,为了得到 一个能够反映全局性能的指标,引入MAP(mean average precision)。对于P和R,用不同的阀值,可以统计出一组不同阀值下的精确率和召回率,叫做P-R图,如下图所示,两条曲线分布对应了两个检索系统的P-R曲线。虽然两个系统的性能曲线有所交叠。但是以圆点标示的系统的性能在绝大多数情况下要远好于用方块标示的系统。所以P-R曲线更向上突出的系统性能更好,也就是说,P-R曲线与坐标轴之间的面积应当越大越好。MAP即为求P-R曲线与坐标轴包围的面积,理想情况下面积为1。

             

    关于上述对MAP的解释,博主仔细翻看了周志华老师的《机器学习》,虽然我对P-R曲线面积的作用描述是没问题的,但是并未发现书中对P-R曲线的面积有过称为MAP的情况。而博主在论文中看到的MAP的使用,应该属于我下一种的解释。两者之间有无关系,我会继续关注。

    MAP是评估检索策略效果的方式之一,除了考虑召回结果的整体准确率之外,MAP也考量召回结果条目的顺序。在了解MAP之前,我们要先了解Prec@K和AP@K的概念。

    Prec@K表示设定一个阈值K,在检索结果到第K个正确召回为止,排序结果的相关度。假设某次的检索结果如下:


    在这个案例中Prec@1=1、Prec@2=2/3、Prec@3=3/5。但是,Prec@K也只能表示单点的策略效果,我们需要使用AP@K体现策略的整体效果

    Average Precision@K是指到第K个正确的召回为止,从第一个正确召回到第K个正确召回的平均正确率。下图为两种K=6的排序策略的结果。

    根据经验,我们容易判断出第一种排序好于第二种。对于结果1,AP=(1.0+0.67+0.75+0.8+0.83+0.6)/6=0.78,对于结果2,AP=(0.5+0.4+0.5+0.57+0.56+0.6)/6=0.52,可以看到,效果优的策略1的AP@K值大于效果劣的
    策略2。

    对于一次查询,AP值可以判断优劣,但是如果涉及到一个策略在多次查询的效果,我们需要引入另一个概念MAP(Mean Average Precision),简单的说,MAP的计算的是搜索查询结果AP值的均值。如上图如果表示的是一个策略下,两次不同的搜索的结果,则MAP = (0.78+0.52)/2。

    评价查询和文档的相关度传统上使用两种特征,一种是和词项Term相关的特征,例如BM25。另一种是独立于Term的特征,例如PageRank。

    1.2、TF-IDF

    TF-IDF是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。英文为Term Frequency-Inverse Document Frequency, 意思是词频-逆文件频率。它的思想在一个文章集中,如果一个词语在一篇文章中出现次数越多(TF越大), 同时在所有文档中出现次数越少(IDF越大), 越能够代表该文章。它由词频TF,逆向文件频率文件IDF两部分组成,表达式为TF-IDF = TF * IDF。例如,查询词X对于文章C的重要程度,它的TF和IDF的计算如下:

    1.3、page rank

    浏览该页面的概率,是谷歌搜索的排名算法。它通过网站外部链接和内部链接的数量和质量来评价网站的价值,PR越高,网站越受欢迎,越重要,排名也越高。
    简单的例子如下图所示,图中每个节点表示一个网页,箭头表示网页链接方向。页面x的page rank为PR(x),那么PR(C)= PR(A)/2 + PR(B)/1。

    问题在于,要计算PR(C),就要先知道PR(A)和PR(B),要知道PR(A)和PR(B)又要先知道PR(C)。这就是一个先有鸡还是先有蛋的问题 了,在计算机学习的时候不止一次碰到过这种纠结的问题,不过解决方法我碰到过的都是先按照一定方法给定一个初值。[1] Google的两个创始人拉里佩奇和谢耳盖把这个问题变成一个二维矩阵相乘的问题,并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的,并且根据这个初始值,算出各个网页的第一次迭代的排名,然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取,这种算法都将能够保证了网页排名的估计值能够收敛到它们就有的真实值。值得一提的是,这种算法的执行是完全没有任何人工干预的。

    1.4、bag-of-words(BOW)

    BoW模型可认为是一种统计直方图。在文本检索和处理应用中, 可以通过该模型很方便的计算词频。有如下例子:
    S1:more ugly less bug is ugly.
    S2:more ugly less bug have bug.
    根据上述S1、S2中出现的单词, 我们能构建出一个字典,{1:"more",2:"ugly",3:"less",4:"bug",5:"is",6:"have"}。用这个字典可以构建出下面两个向量。
    S1:(1,1,1,1,1,0)。S2:(1,1,1,2,0,1)。这两个向量共包含6个元素, 其中第i个元素表示字典中第i个单词在句子中出现的次数,在文本检索和处理应用中, 可以通过该模型很方便的计算词频。

    1.5、BM25

    BM25算法通常用来作搜索相关评分。主要思想是对查询词进行分词成Term,标记为qi。然后对于每个搜索结果D,计算每个qi与D的相关性得分,最后,将qi相对于D的相关性得分进行加权求和,从而得到Query与D的相关性得分。BM25是一个bag-of-words模型的检索函数,基于在各文件中出现的查询词项计算相关性评分。它不像Term Proximity检索查询词在文件中内在的联系。
    BM25算法的一般性公式如下:

    其中,Q表示Query。qi表示Q解析之后的一个Term。d表示一个搜索结果文档。Wi表示语素qi的权重,用IDF计算。R(qi,d)表示词qi与文档d的相关性得分。其实就是计算一个query里面所有词和文档的相关度,然后在把分数做累加操作,而每个词的相关度分数主要还是受到TF-IDF的影响。

    更完整的BM25公式如下:

    其中k1,b都是调节因子,|d|是文档d的长度,avgd是这个文档集的平均文档长度。fd,t是词t在文档d中出现的次数wt是用IDF计算而来的。

    总结一下影响BM25公式的因数主要有三点:1、IDF越高分数越高。2、TF越高分数越高。3 如果查询到的文档长度相对文档集的平均长度越长,则分数越低。

    1.6、Proximity

    搜索引擎还有一个叫做 Proximity Measures 的特征计算,可以理解为计算文档里面出现的 查询Term 的相近程度。为什么需要Proximity Measures呢?我们可以看下面这个例子:


    可以很明显看出文档2与查询词的相关性要比文档1好,但是只用bag-of-words则很难保证这一点,查询词项在文档中出现的顺序,和词之间的距离同样是影响相关性的重要因素。所以要引入Proximity保证查询词之间的相近度。可以有以下几种方式:

    1.7、使用距离度量

    这种方式主要是计算 Term 之间距离作为 Proximity 得分。主要分为 Span-based和Distance aggregation两类。假设现在有文档 D = t1, t2, t1, t3, t5, t4, t2, t3, t4,接下来通过基于文档D的举例说明,解释两类算法。 

    1、Span :在文档中可以覆盖所有term的最小距离称为 Span , 需要包含所有重复的term 。比如Query=t1,t2,则这个查询的Span=6。
    2、MinCover :在文档中可以覆盖所有term的最小距离称为 MinCover , 每个term至少被包含一次 。比如这里的Q=t1,t2,则查询的MinCover=1
    3、Distance aggregation:这种方式计算的最近单元是计算一个term pair的最小距离,使用Dis(ti,tj;D)来表示。先计算两两之间的距离,再聚集起来。
    4、MinDist(Minimum pair distance) :计算所有pair的最小距离的最小值。比如Q=t1,t2,t3,则MinDist=min(1,2,3)=1。
    5、AveDist(Average pair distance) :计算所有pair的最小距离的平均值,比如Q=t1,t2,t3,则AveDist=(1+2+3)/3=2
    AveDist=(1+2+3)/3=2。
    6、MaxDist(Maximum pair distance) :与 MinDist 正好相反,它是求最大值。比如Q=t1,t2,t3,则MaxDist=max(1,2,3)=3。
    但是,研究显示并不是所有查询都要用上Proximity measures,有些查询不适合用。如果对不适合用Proximity的查询使用的话,不仅会增加计算时间,还有可能产生差的排名。

    1.8、倒排索引

    在解释倒排索引之前,我们先了解一下什么是正向索引(forward index),以及为什么不用正向索引要使用倒排索引。
    在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合(实际上在搜索引擎索引库中,关键词也已经转换为关键词ID)。例如“文档1”经过分词,提取了数个关键词,每个关键词都会记录它在文档中的出现次数和出现位置,得到正向索引的结构如下:

    文档ID;单词1:出现次数,出现位置列表;单词2:出现次数,出现位置列表;......

    用正向索引,搜索关键词时,需要扫描库中的所有文档,对每个文档中的关键词进行搜索,因为互联网上收录在搜索引擎中的文档的数目是个天文数字,这样的索引结构根本无法满足实时返回排名结果的要求。因此引入了倒排索引。

    正向索引是文件ID对应到关键词的映射。倒排索引则相反,是关键词到文件ID的映射,每个关键词都对应着一系列的文件,这些文件中都出现这个关键词,倒排索引的结构如下:

         “关键词文档1”ID文档2”ID,......

    二、分词方法

    2.1正向最大匹配法

    正向最大匹配法是分词算法的其中一种,它是按照一定的策略将待分析的汉字串与词典中的词条进行配,若在词典中找到某个字符串,则匹配成功(识别出一个词)。算法的核心就是从左到右搜索,然后找到最长的字典分词。算法使用时首先要定义一个最大长度,下面的例子中最大长度为5。
    例子:南航是一所知名大学
    过程如下:
    南航是一所
    南航是一
    南航是
    南航 ----> 得到一个词–南航
    是一所知名
    是一所知
    是一所
    是一
    是 ----> 得到一个词–是
    一所知名大
    一所知名
    一所知
    一所 ----> 得到一个词–一所
    知名大学
    知名大
    知名 ---->得到一个词– 知名
    大学 ---->得到一个词– 大学
    最后正向最大匹配的结果是:
    /南航/是/一所/知名/大学


    常见词汇

    Term:信息检索的第一步是对文档进行分词。这些分词也叫做Term。Term表示文本中的一个词语,是搜索的最小单元。

    posting lists:倒排记录表

    query:查询条件

    Inverted Index:倒排索引

    term proximity(TP) :近邻词得分


    参考资料:[1] 深入探讨PageRank
                      [2]BM25相关度打分公式
                      [3]搜索排序评估方法
                      [4]在信息检索中Term之间的Proximity计算研究
    展开全文
  • 信息检索专题复习

    万次阅读 2017-06-20 16:06:49
    信息检索复习重点,山东大学信息检索考前独家整理资料。

    信息检索

    Made by ® Isaac. Ty

    信息检索模型:描述信息检索中的文档、查询和他们之间的关系(匹配函数)的数学模型

    IR新课题

    • 自然语言理解
    • 多媒体检索
    • 垂直检索技术
    • 移动搜索
    • 对社会媒体信息检索
    • 问答
    • 知识发现
    • 行为分析、舆情控制
    • 自动对话

    2.布尔检索

    信息检索模型概述

    定义

    文档表示

    一个文档被表示为关键词(bag of words)的集合

    查询表示

    查询式(Queries)被表示为关键词的布尔组合,用“与、或、非”连接起来(主析取范式)

    相关度计算
    • 一个文档当且仅当它能够满足布尔查询式时,才将其检索出来
    • 检索策略是二值匹配
    非结构化数据

    没有清晰和明显的语义结构的数据,计算机不易处理这些数据

    结构化数据

    最典型的时关系数据库,用来保存公司的产品清单和人事记录

    聚类(clustering)

    基于文档内容进行自动聚团的任务。很像在书架上将一系列书按照它们所属的主题重新摆放的过程。

    分类(classification)

    根据给定的主题、固定的信息需求或者其他类别体系,将每一个文档分到一个或多个类别的任务。

    布尔模型:优缺点

    优点
    • 查询简单,容易理解
    • 通过使用复杂的布尔表达式,可方便地控制查询结果
    • 相当有效的实现方法
    • 经过某种训练的用户可以容易地写出布尔查询式
    • 布尔模型可以通过扩展来包含排序的功能
    缺点
    • ,不支持部分匹配,完全匹配会导致结果太多或太少
    • 非常刚性:“与”意味着全部;“或”意味着任何一个,所有匹配文档都将被返回
    • 不考虑索引词的权重,所有文档都以相同的方式和查询相匹配
    • 很难进行自动的相关反馈

    信息检索的基本假设

    • 集合:固定数量的文档
    • 目标:找到与用户信息需求相关的含有信息量的文档,帮助用户完成一个任务。

    典型的搜索模型

    • 构造矩阵→信息需求→文字形式→查询→查询优化→结果

    返回文档的好坏

    查准率

    返回的能满足用户信息需求的文档占总的返回文档的百分比

    召回率

    返回的能满足用户信息需求的文档占总的能满足用户信息需求的文档的百分比

    倒排索引

    • 对于每一个词项,存储所有包含这个词项的文档的一个列表。一个文档用一个**序列号**docID来表示
    • 应当使用可变长度的记录表
      • 在硬盘上,一串连续的记录是正常的,也是最好的
      • 在内存里,可以使用链表,或者可变长度的数组

    倒排索引建立步骤

    1. 收集需要建立索引的文档
    2. 将每篇文档转换成一个个词条(token)的列表,此个过程称为词条化(tokenization)
    3. 进行语言预处理,产生归一化的词条来作为词项
    4. 对所有文档按照其中出现的词项来建立倒排索引,索引中包括一部分词典和一个全体倒排索引表

      • 词条序列Token Sequence

    (修改过的词条,文档ID)对序列

    • 排序

      先按照词条排序,再按照docID排序

    • 词典和倒排表

      • 同一篇文档中多次出现的词被合并
      • 分割成词典倒排表
      • 词汇的文档频率也被记录
    • 查询的处理:AND

      • 考虑这样的查询: Brutus AND Caesar
      • 在字典中找到Brutus,得到它的倒排记录表
      • 在字典中找到Caesar,得到它的倒排记录表
      • 合并两个倒排列表
      • 同时扫描两个倒排记录表求交集,所需时间和倒排记录的数量呈线性关系。

    布尔检索模型

    文档表示

    一个文档被表示为关键词的集合

    查询表示

    查询式(Queries)被表示为关键词的布尔组合,用“与、或、非”连接起来(主析取范式DNF)

    相关度计算

    • 一个文档当且仅当它能够满足布尔查询式时,才将其检索出来
    • 检索策略是二值匹配{0,1}

    形式化表示

    1. 定义:用q~dnf~ 表示查询q的析取范式,q~cc~表示q~dnf~的任意合取分量
    2. 文献d~j~与查询q的相似度为

    布尔检索模型:布尔代数

    布尔变量
    • 只有“真”、“假”取值的变量
    布尔操作(关系)
    布尔表达式

    精确匹配

    布尔模型可以用来处理布尔表达式形式的查询

    • 布尔查询使用AND,OR和NOT来连接查询词汇
      • 将文档看作词汇的集合
      • 精确:匹配或不匹配
    • 布尔模型式IR系统中最简单的模型

    查询优化

    • 按照文档频率的顺序进行处理。先处理文档频率小的,再处理大的。

    3.词项词典和倒排记录表

    建立词项词典

    文档解析

    • 文档格式
    • 文档中的语言
    • 文档的编码方式

    词条化

    • 将给定的字符序列拆分成一系列子序列的过程,其中每一个子序列称之为一个“词

      条”Token。

    • 词条(Tokens)、词项(Terms)

    • 针对不同的语言,采用不同策略的词条化方法

    • 分词的基本方法:

      • 基于词典的最大匹配法
      • 机器学习方法

    停用词

    • 停用词表:将词项按照文档集频率,从高到低排列。选取与文档意义不大,高频出现的词,例如a ,an , the , and, ….
    • 优点:停用词消除可以减少term的个数
    • 缺点:有时消除的停用词对检索有意义的 。 的士 , to be or not to be
    • 消除方法:查表法,基于文档频率

    词项归一化

    • 将不完全一致的多个词条归纳成一个等价类,以便在它们之间进行匹配。
    • 归一化结果:在IR系统的词项词典中,形成多个近似词项的一个等价类
    • 归一化策略:建立同义词扩展表

    词干还原

    • 很粗略的去除单词两端的词缀的启发式过程
    • 能提高召回率,但是会降低准确率
    • porter算法

    词形归并

    • 利用词汇表和词形分析来减少曲折变化的形式,将其转变为基本形式
    • 词形归并可以减少词项词典中的词项数量

    区别:

    • 词干还原在一般情况下会将多个派生相关词合并在一起
    • 词形归并通常只将同一词元的不同曲折形式进行合并

    实现倒排记录表

    合并算法

    • 通过在两个倒排表之间同时移动指针来实现合并,此时的操作与线性表的总数成线性关系。

    基于调表的倒排记录表快速合并算法

    • 跳表指针能够跳过那些不可能出现在检索结果中的记录项
    • 如果倒排表的长度是L,那么在每个L处均放置跳表指针
    • 跳表指针只对AND类型查询有用,对OR类型查询不起作用

    短语查询

    二元词索引
    • 将文档中每个连续词对看成一个短语,其中的每个二元词对豆浆作为词典中的词项。
    扩展的二元词索引
    位置信息索引
    • 在此索引中,对每个词项,都采取以下方式存储倒排表记录:

      <词项,词项频率;

      文档1:位置1,位置2,……

      文档2:位置1,位置2,……

    4.索引构建

    硬件基础

    语资料库

    索引构建算法

    基于块的排序索引算法(BSBI:Blocked sort-based Indexing)

    • 在索引构建过程中需要依次分析所有的文档,不能很容易利用压缩技巧。只有分析完所有文档,最终的倒排记录表才会完整。

    • 基本思想:对每一个都生成倒排记录,并排序,写入硬盘。然后将这些块合并成一个长的排好序的倒排记录。

    • 每条数据占用12字节(4+4+4)(词项,文档,频数)
    • 在内存中处理,累积放满固定的块,排序后写入硬盘f~i~ ,合并所有索引文件成一个
    基于BSBI排序算法存在的问题
    • 假设能够将词典存入内存
    • 需要该词典动态增长去查找任一词项和词项ID之间的对应关系。
    • (一个可扩展的,但效率非常低的构建索引算法)

    内存式单遍扫描索引算法(SPIMI Single-pass in-memory indexing)

    • 核心思想:为每个块单独生成一个词典—— (不需要维护全局的<词项,词项ID>映射表)

    • 不进行排序。有新的<词项,文档ID>对时直接在倒排记录表中增加一项。

      • 可以为每个块生成一个完整的倒排索引,然后将这些单独的索引合并为一个大的索引
    • 压缩技术将会使SPIMI算法更加高效
      • 压缩词项
      • 压缩倒排记录表

    分布式索引构建(Distributed indexing)

    • Web规模的索引构建

      必须使用一个分布式的计算机集群

    • 计算机都是故障频发的

      • 可能会在任意时刻失效
    • 利用集群中的主控节点来指挥索引构建工作

      • 认为主控节点是“安全的”
    • 将索引构建过程分解成一组并行的任务

    • 主控计算机从集群中选取一台空闲的机器并将任务分配给它

    • 采用两组不同的并行任务

      • Parsers分析器

        1. 主节点将一个数据片分配给一台空闲的分析服务器

        2. 分析器依次读取文档并生成<词项,文档>对。

        3. 分析器将这些<词项,文档>按照词项对分成j个段

        4. 每一段是按照词项首字母划分的一个区间。

          例如:a-f,g-p,q-z 这里j=3

        5. 然后进行索引的倒排

      • Inverters倒排器
        1. 对于一个词项分区,倒排器收集所有的<词项,文档>对(倒排记录)。
        2. 排序,并写入最终的倒排记录表。
    • 首先,将输入文档集分割成n个数据片

      • 每个数据片就是一个文档子集(与BSBI/SPIMI算法中的数据块相对应)
      • 两种分割方法
        • 基于词项的分割
        • 基于文档的分割
    • 数据流图

    动态索引

    动态索引构建方法

    文档集通常不是静态的

    • 文档会不断的加入进来
    • 文档也会被删除或者被修改

    词典和倒排记录表需要修改

    • 对于已在词典中的词项更新倒排记录
    • 新的词项加入到词典中

      1. 周期性索引重构
    • 建立索引的同时,旧索引继续工作

    • 条件

      • 更新次数不是很多
      • 能够接受对新文档检索的一定延迟(重构之前新文档检索不到)
      • 有足够的资源进行重构

        1. 维护一个大的主索引
      • 新文档信息存储在一个小的辅助索引中(位于内存)
      • 检索可以同时遍历两个索引并将结果合并
      • 删除
        • 文档的删除记录在一个无效位向量
        • 在返回结果前利用它过滤掉已删除文档
      • 定期地将辅助索引合并到主索引中
      • 文档更新通过先删除后插入的方式实现

    主索引与辅助索引存在的问题

    • 频繁的合并带来很大开销
    • 合并过程效率低
      • 如果每个词项的倒排记录表都单独成一个文件,那么合并主索引和辅助索引将会很高效。
      • 合并是一个简单的添加操作
      • 需要使用很多倒排文件—— 对文件系统来说是低效的

    对数合并

    • 维护一系列索引I0,I1,I2,,每个都是前一个的两倍大小
    • 辅助索引Z0存储在内存中,而较大的(I0,I1,I2,,)存储在磁盘中
    • Z0达到上限时,将它写入磁盘I0中,当下一次达到上限时,它会和I0合并,生成Z1
      • 此时,如果I1不存在,存储到I1
      • 如果I1已存在,则Z1I1合并成Z2(大小22n)
      • 此时,如果I2不存在,存储到I2
      • 如果I2已存在,则Z2I2合并成Z3 (大小22n)
      • ……

    4.索引压缩

    压缩

    • 节省磁盘空间
    • 提高内存的利用率(加快速度)
    • 加快数据从磁盘到内存的传输速度
      • [读取压缩数据][解压缩] 比直接 [读取未压缩的数据]快
      • 前提:解压缩算法要很快

    压缩倒排索引的原因

    • 词典
      • 压缩的足够小以便放入内存中
      • 当词典足够小时,也可以在内存中存储一部分倒排索引记录表
    • 倒排记录文件
      • 减少所需要的磁盘空间
      • 减少从磁盘读取倒排记录文件所需的时间
      • 大的搜索引擎在内存中存储了很大一部分倒排记录表
      • 压缩可以在内存中存储的更多
    • 将涉及各种基于IR系统的压缩架构

    词项统计量

    词典压缩

    有损压缩和无损压缩

    • 无损压缩:压缩之后所有原始信息都被保留
      • 在IR系统中常采用无损压缩
    • 有损压缩:丢掉一些信息
    • 一些预处理步骤可以看成是有损压缩:大小写转化,停用词剔除,词干还原,数字去除等
    • 有损还是无损与需求相关

    Heaps定律:M=kT^b^

    • M是词项的数目,T是文档集中词条的个数
    • 词汇量大小M和文档集大小T在对数空间存在斜率为1/2的线性关系。
    • 不同单词的数目与文本篇幅之间存在幂函数的关系,其幂指数小于1
    • 提供了对文档集中词汇量的估计

    Zipf定律

    • 词项在文档中的分布情况

    • 排名第i多的词项的文档集频率与1/i成正比

    • 词项t~i~在文档集中出现的次数
    • 高频词项很少,低频罕见词项很多

    为什么要压缩词典

    • 搜索从词典开始
    • 想将词典放入内存中和其他应用程序共享内存资源
    • 手机或者嵌入式设备通常只有很小的内存
    • 即使不在内存中,也希望足够小以便搜索能够快速启动

    压缩词项列表:将词典看成单一字符串

    • 将所有词项存储为一个长字符串
      • 指向下一词项的指针同时也标识着当前词项的结束
      • 期望节省60%词典空间

    按块存储(Blocking)

    • 每k个词项分词一块,只保留第一个指针
    • 需要存储词项长度(额外一字节)

    前端编码

    • 按照词典顺序排列的连续词项之间往往具有公共前缀
    • (块内k个词项的最后k-1个)

    倒排记录表压缩

    • 倒排记录表远大于词典,至少10倍
    • 紧密地存储每一个倒排记录表
    • 每个倒排记录用文档ID来定义

    倒排记录表:相反的两点

    • 像“arachnocentric”这样的词项可能在一百万 个文档中才会出现一次 可以用log21M ≈ 20 bits来存储这一倒排记录。
    • 像“the”这样的词项在每个文档中都会出现, 所以对它采用20bit/倒排记录太浪费了。
      • 这种情况更希望是0/1的bit向量

    倒排记录表项中文档ID的间距(GAP)

    • 按照文档ID的递增顺序来存储一个词项的倒排列表
      • Computer: 33,47,154,159,202,…
    • 可以存储间距
      • 33,14,107,5,43,…
    • 期望:绝大多数间距存储空间都远小于20bit

    可变长度编码

    • 目标:
      • 对于arachnocentric,使用20bit/间距项
      • 对于the,使用1 bit/间距项
    • 如果词项的评价间距为G,我们想使用log2Gbit/间距项
    • 关键问题:需要利用整个字节对每个间距编码
      • 可变长度编码:对一些小数字用短码来实现
    • 可变字节码:
      • 用一个字节来存储G,并分配1bit作为延续位
      • G127 对7位有效码采用二进制编码并设置延续位c=1(结束)
      • G>127 则先对G低阶的7位编码,然后采用相同的算法用额外字节对高阶bit位进行编码
      • 设置最后一个字节的延续位为1(c=1),其他字节的c=0(未结束)

    5.Web搜索

    Web搜索基础

    重复文档

    • 完全复制Duplication : 可以通过指纹(fingerprints)来检测精确匹配
    • 近似重复Near-Duplication:通过编辑距离计算语法上的相似性

    相似性计算

    • 搭叠Shingles(N元词N-Grams)
      • 给定正整数K及文档d的一个词项序列可以定义文档d的k-shingle为d中所有k个连续词项构成的序列
    • Jaccard系数:衡量重复度
      • 表示公式: 交集 / 并集
      • 计算所有文档对之间搭叠的精确交集非常费时而且难以处理
      • 使用冲Shingles中选出一个子集(素描sketch)来近似计算(抽样Sample)

    小结:近似重复检测

    • Shingle算法的核心思想是将文件相似性问题转换为集合的相似性问题
    • 数量较大时,对Shingle集合进行抽样,以降低空间和时间计算复杂性
    • shingle取样三种方法:Min-Wise,Modm,Mins

    Web采集

    采集器

    1. 从已知种子URL开始
    2. 获取页面并解析
      1. 提取页面中包含的链接
      2. 将链接放入URL队列
    3. 对队列中的URL转2
    采集器必须具有的功能
    • 礼貌性:Web服务器有显示或隐式的策略控制采集器的访问
    • 鲁棒性:能从采集器陷阱中跳出,能处理Web服务器的其他恶意行为
    • 分布式:可以在多台机器上分布运行
    • 可扩展性:添加更多机器后采集效率应该提高
    • 性能和效率:充分利用不同的系统资源,包括处理器、存储器和网络带宽
    • 新鲜度:对原来爬取的网页进行更新
    • 功能可扩展性:支持多方面的功能扩展,例如处理新的数据格式、抓取新的协议。

    采集器基本架构

    采集器

    Web 图

    Web →Web图
    • 将静态Web看成静态HTML网页通过超链接互相连接而成的有向图,其中每个网页图的顶点,而每个超链接式图的有向边
    • 该有向图可能不是一个强连通图,即从一个网页出发,沿着超链接前进,有可能永远不会到达另外某个网页
    • 指向某个网页的链接称为 入链接(in-link),而从某个网页指出去的链接称为出链接(out-link)。
    • 入度:网页的入链数目。 出度:网页的出链数目
    邻接表
    • 每个网页都用唯一的整数来表示
    • 建立一个类似于倒排索引的邻接表,每行对应一个网页,按照其对应的整数大小排序。
    • 任一网页P对应的行中包含的也是一系列整数的排序结构,每个整数对应链向P的网页编号。(那些网页指向P)

    链接分析

    Web是有向图
    • 假设1:A到B的超链接表示A的作者对B的认可
    • 假设2:指向页面B的锚文本式对B一个很好的描述
    索引锚文本
    • 索引文档D的时候,也索引指向文档D的锚文本
    • 可以根据锚文本所在页面的权威性来确定锚文本的权重
    小结:锚文本
    • Web上很多网页的内容并不包含对自身的精确描述
    • Web搜索者不一定要使用网页中的词项来对网页进行查询,而使用锚文本。
    • 锚文本周围窗口中的文本也可以当成锚文本一样来使用。

    链接分析:PageRank

    PageRank
    • 对Web图中的每个节点赋一个0~1间的分值,这个分值为PageRank
    • 查询词无关的排序
    • 第一代版本:使用链接的数目作为流行程度的最简单度量
    • 两个改进:
      • 无向流行度:赋予每个页面一个分:出链数+入链数
      • 有向流行度:页面分数 = 入链数
    查询处理
    • 检索出所有满足文本查询词的页面,然后把这些页面按照链接的流行的排序。
    • 更复杂:把链接按流行度当作静态得分,结合文本匹配的分数进行综合排序
    PageRank打分
    • 假设一个浏览者在网络上随机行走
      • 从一个随机页面开始,每一步从当前页等概率地选择一个链接,进入链接所在页面
    • 在稳定状态下,每个页面都有一个访问概率——用这个概率作为页面的分数
    • 当浏览者在Web上进行节点间的随机游走时,某些节点的访问次数会比其他的节点更多
    • 访问频繁的节点具有很多从其它频繁访问节点中指向的入链接
    • PageRank思路:在随机游走过程中越频繁访问的网页越重要
    随机跳转(Teleporting)
    • 遇到dead end时,随机跳转到一个页面,如果页面总数总是N,那么随机跳转的概率式1/N
    • 非dead end, 以a(值较小)的概率跳转到一个随机页面;以剩余1-a的概率从页面的出链中选择一个
    • 随机跳转结果:不会再困在一个地,将会有比率表示所有网页长期被访问的概率
    马尔科夫链
    • 一个Markov链有N个状态,以及一个NxN的转移概率矩阵P。每一步只能处在一个状态
    • 1i,jN,转移概率矩阵P~ij~给出了从状态i到下一个状态j的条件转移概率
    • P中每一行的元素之和为1,从该页面跳转道其所有出链的概率之和为1
    • 满足上述性质的非负矩阵被成为随机矩阵。最大特征值是1,与该特征值对应的有一个左特征向量
    • 马尔科夫链中下一个状态的分布仅仅依赖于当前的状态,与如何到达当前状态无关。
    • 马尔科夫链的状态概率分布可以看成一个概率向量,每个元素都在[0,1],且所有元素的和为1(行)
    邻接矩阵A→概率转移矩阵P
    • 如果一行没有1(没有出链),用1/N代替每个元素
    • 否则
      • 每行中用1的个数除每个1。(归一化) 若某行3个1,每个1用1/3表示
      • 上面处理的结果矩阵乘以1-a
      • 上面结果矩阵元素加上 a/N
    概率向量的变化
    • 最终访问频率收敛与固定的、稳态概率π
    • 算法: 给 X 乘上P的k次方,k不断增加,直到乘积稳定
    • π***P = π*
      • 解矩阵等式得到π
      • π是P的主左特征向量,π~i~是页面i的PageRank

    链接分析:HITS

    • 对每个网页给出两个得分 hub值(导航) ,authority值(权威)
    • 确定基本集
    • 精选出Hub页和Authority页
    • 迭代跟新h(x),a(x)
      • 输出h(x)最高作为Top Hub页,a(x)最高作为Top Authority页
    • 大概5次迭代就会稳定
    • h是AAt的特征向量,a是AtA的特征向量

    6.向量模型

    排序式检索

    布尔检索:文档要么匹配要么不匹配。对自身需求和文档集性质非常了解的专家而言,布尔查询式不错的选择。然而对大多数用户来说不方便

    • 布尔查询的结果不是太多就是太少
    • 需要花费很多精力去构造一个合适的query才可以获得一个在数量上可以接受的查询结果。

    排序检索模型

    • 在排序检索模型中,系统根据文档与query的相关性排序返回文档集合中的文档,而不是简单地返回所有满足query描述的文档集合。
    • 自由文本查询:用户query是自然语言的一个或多个词语而不是由查询语言构造的表达式。
    • 总体上,排序检索模型中有布尔查询和自由文本查询两种方式,但是实际中排序检索模型总是与自由文本查询联系在一起,反之亦然。

    过多、过少不再是问题

    • 当系统给出的式有序的查询结果,查询结果数目多不再是问题。只需要给出top K(10个左右)个结果,为用户减轻负担。
    • 前提是有合适的排序算法

    排序检索的基本—-评分

    希望根据文档对查询者的有用性大小顺序将文档返回给查询者

    • 给每个“查询—文档”对进行评分,在[0,1]之间
    • *这个评分值衡量文档与query的匹配程度*
    • 以单个单词组成的query为例
      • 如果单词不出现在文档中,该文档得分为0
      • 该词项在文档中出现的频率越高,则评分越高
    评分方案一—-Jaccard系数

    一种常用的衡量两个集合A,B重叠度的方法

    • Jaccard(A,B)=|AB|/|AB|
    • Jaccard(A,A)=1
    • Jaccard(A,B)=0 if AB=0
    • 集合A和B不需要具有同样的规模
    • Jaccard(A,B)的取值在[0,1]

    用Jaccard系数评分的问题

    • 没有考虑词项频率(词项在文档中出现的次数)
    • 没有考虑罕见词比高频词的信息量更大,更具区分度

    词项频率

    词项–文档二值关联矩阵

    • 每个文档用一个二值向量表示 {0,1}|v| 。每个词项是否属于某个文档

    词项—文档词频关联矩阵

    • 考虑词项在文档中出现的频率,将每个文档看成是一个词频向量:矩阵中的一列

    词袋模型(Bag of words)

    • 不考虑词在文档中出现的顺序

      “John is quicker than Mary” 和 “Mary is quicker than John” 的表示结果一样

    词项频率tf(Term frequency)

    词项频率:词项t在文档d中出现的次数,记为tft,d

    1. 采用原始tf值(raw tf)
      • 某个词项在A文档中出现10次,即tf=10,在B文档中tf=1,那么A比B更相关,但是相关度不会相差10倍
      • 相关性不会正比于词项频率
    2. 对数词频
      • 词项t在文档d中的对数频率权重
      • 对数词频
        • 文档——词项的匹配得分是所有同时出现query文档d中的词项的词频的对数之和
        • Score(q,d)=tqd(1+logtft,d)
        • 评分为0,表示文档和query没有公共词项

    tf-idf权重计算

    除词项频率tf之外,利用词项在整个文档集中的频率进行权重和评分计算

    罕见词所期望的权重

    • 罕见词比常见词所蕴含的信息更多
    • 考虑查询中某个词项,它会在整个文档集中非常罕见
    • 某篇包含该词项的文档很可能相关,故罕见词项将有较高权重

    常见词项所期望的权重

    • 常见词项的信息量不如罕见词
    • 考虑一个查询此项,它频繁出现在文档集中
    • 一篇包含该词项的文档当然比不包含该词项的文档的相关度要高
    • 但是,这些词对于相关度而言并*不是非常强的指示词*,故*给一个正的权重,但是整个权重小于罕见词权重*

    文档频率(Document frequency,df)

    • 罕见词项赋予高权重
    • 常见词项赋予正的低权重
    • 文档频率df因子来计算 查询–文档的匹配得分
    • 文档频率:出现词项的文档数目

    idf(inverse document frequency)逆文档频率

    • dft是词项t的文档频率文档集合中包含t的文档数目
      • dft与词项t包含的信息量反比(出现文档数目越多,该词项的信息量相对较小)
      • dftN (N是文档的总数)
    • 定义t的逆文档频率idf

      idft=log10(N/dft)

    • idft是反应词项t的信息量的一个指标
    • log10(N/dft)来代替Ndft来抑制idf的作用

    idf对排序的影响

    • 对于含有两个以上查询词的queryidf才会影响排序结果;只有一个查询词的query,idf对排序结果没有影响
    • 例如 Query: arachnocentric line , idf会提高 arachnocentric的相对权重,同时减低line的相对权重

    文档集频率和文档频率

    • 文档集频率(collection frequency,cf)是指t在整个文档集合中出现的*词的次数*
    • 文档频率(document frequency,df)包含该词项的*文档数目*
    • df比cf更适合权重计算

    tf–idf文档-逆文档频率(单个词)

    • tf-idf是信息检索中最著名的权重计算方法
    • 词项t的tf-idf式由它的tf和idf组合而成
    • wt,d=(1+logtft,d)×log10(N/dft)
    • tf-idf值随着词项在单个文档中出现次数(tf)增加而增加,随着词项在文档集中数目(df)增加而减小

    Query 最终文档排序

    Score(q,d)=tqdtfidft,d

    向量空间模型

    • 二值关联矩阵:每个文档用一个二值向量表示 0,1|v|
    • 词频矩阵:每篇文档表示成一个词频向量 N|v|
    • tf-idf矩阵:每篇文档表示成一个基于tf-idf权重的实值向量R|v|

    文档表示成向量

    • 每篇文档表示成一个基于tf-idf权重的实值向量R|v|(V式词项集合,|v|表示词项个数)
    • |v|维实向量空间
      • 空间每一维都对应词项
      • 文档是空间的点或者向量
      • 维度非常高:特别是互联网搜索引擎,空间可达千万维或更高
      • 向量空间非常稀疏:对每个向量来说大部分都是0

    Queries表示成向量

    1. 对于查询做同样的处理,即将查询表示成统一高维空间的向量
    2. 在向量空间内根据query与文档相量间的距离来排序

    利用夹角代替距离

    • 按query与文档夹角递减给文档排序,按余弦递增给文档排序 是的等价的。
    • 按余弦cosine(query,document)递减给文档排序,只考虑相对顺序

    文档长度归一化

    • 利用二范数对文档长度进行归一化,一个文档向量除以它的L~2~范数就是给这个文档进行长度归一化

    6.检索系统

    排序的重要性

    • 用户只希望看到一些而不是成千上万的结果
    • 很难构造只产生一些结果的查询,即使是专家也很难
    • →排序能够将成千上万条结果缩减至几条结果,因此非常重要
    • 实际上大部分用户只看到1-3条结果

    摘要阅读

    用户更可能阅读前几页(1, 2, 3, 4)的结果的摘要

    点击

    点击的分布甚至更有偏向性

    • 一半情况下,用户点击排名最高的页面
      • 即使排名最高的页面不相关,仍然有30%的用户会点击它
    • 正确排序相当重要,把相关的页面放在首页非常重要

    结果排序的实现

    tf和idf的存储

    • 词典中保存每个词的idf

    • 词项频率tf存入倒排索引

      term|idf → d1,tf , \

    精确top K检索机器加速办法

    • 从文档集所有文档中找出K个离查询最近的文档
    • 步骤:对每个文档频繁(余弦相似度),按评分高低排序,选出前K个结果
    • 如何加速:
      • 加快每个余弦相似度的计算
      • 不对所有文档的评分结果排序而直接选出top K篇
      • 能否不需要计算所有N篇文档的得分

    快速计算余弦相似度

    • 检索排序就是找查询的k临近
    • 如果查询很短,可以加速
      • 查询的多个词项无权重
      • 排序只需要相对得分

    堆排序法N中选K

    • 检索时,通常只需要返回前K条结果
    • 令J=具有非零余弦相似度值的文档数目,利用对结构从J中选K个最大的

    提前终止计算

    非精确top K检索的可行性

    • 索引去除:
      • 对于一个包含多个词项的查询来说,可以只考虑至少包含一个查询词项的文档
      • 只考虑那些词项的idf值超过一定阈值的文档
      • 只考虑包含多个查询词项
    • 胜者表
      • 对于词典中的每个词项t,预先计算出r个最高权重的文档
      • 词项t所对应的tf值最高的r篇文档构成t的胜者表,r值在索引建立时给定可能r

    评价

    信息检索的目标式*较少消耗情况下尽快、全面返回准确的结果。*

    评价方式

    效率(Efficiency)

    • 时间开销
    • 空间开销
    • 响应速度

    效果(Effectiveness)

    • 返回的文档中有多少相关文档
    • 所有相关文档中反回了多少
    • 返回得靠不靠前

    其他指标

    • 覆盖率(Coverage)
    • 访问量
    • 数据更新速度

    评价效果

    • 相同的文档集合,相同的查询主题集合,相同的评价指标不同的检索系统进行比较。

    无序检索结果的评价

    对单个查询进行评估的指标

    对整个文档集合的划分
    • 未检索出(Not Retrieved)
      • 未检索出的相关文档(NR)
      • 未检索出的不相关文档 (NN)
    • 检索出(Retrieved)
      • 检索出的相关文档(RR)
      • 检索出的不相关文档(RN)
    评价指标
    • 召回率(Recall):RR/(RR+NR),返回的相关结果数占实际相关结果总数的比率,也称为查全率,R[0,1]
    • 正确率(Precision):RR/(RR+RN),返回的结果中真正相关的比率,也称查准率,P[0,1]
    • 两个指标分别度量检索效果的某个方面,忽略任何一个方面都有偏失。
    • 两个极端情况
      1. 返回有把握的1篇,P=100%,但R极低
      2. 全部文档都返回,R=1,但P极低
    • 虽然Precision和Recall都很重要,但是不同的应用、不同的用户对两者的要求不一样。

    正确率和召回率的问题

    • 应用领域

      • 拼写校对、中文分词、文本分类、人脸识别、……
    • 召回率难以计算

      • Pooling方法,或则不考虑召回率
    • 两个指标分别衡量了系统的某个方面,但是如何评价哪个系统好
      • 将两个指标融成一个指标
    • 两个指标都是基于集合(无序)进行计算,并没有考虑序的作用
      • 引入序的作用
    召回率的计算

    对于大规模语料集合,列举每个查询的所有相关文档不可能,因此不可能准确地计算召回率
    - 缓冲池(Pooling)方法:对多个检索系统的TopN个结果组成的集合进行人工标注,标注相关文档集合作为整个相关文档集合

    使用查准率/查全率的问题
    • 需要在大规模的文档集合和查询集合上进行计算
    • 需要人工对返回的文档进行评价

      • 由于人的主观因素,人工评价往往不可靠
    • 评价是二值的

      • 无法体现细微的差别
    • 文档结合和数据来源不同,结果也不同,有严重的偏差
      • 评价结果只适用于某个范围,很难引申到其他范围

    综合评价准则 F=P和R融合

    • F值(F-measure):召回率R和查准率的加权调和平均值
    • F=1α1p+(1α)1R=(β2+1)PRβ2P+R
    • Fβ :表示召回率的重要程度是查准率的β(>=0)
      • β>1 更重视召回率,β<1更重视查准率
      • 取等权重
      • Fβ=1=2PRP+R
    • 调和平均比较保守

    精确率不适合IR的原因

    • 和查询相关的文档占文档集的极少数,即使什么都不返回也会得到很高的精确率
    • 用户希望找到某些文档并且能够容忍结果中有一定的不相关性
    • 返回一些即使不好的文档也比不反回任何文档好

    有序检索结果的评价

    评价排序后的结果

    • P、R、F值都是基于集合的评价方法,它们都是利用无序的文档集合进行计算。如果搜索引擎输出为有序的检索结果时,需要扩展
    • 对于特定检索词的有序检测结果
      • 系统可能返回任意数量的结果(=N)
      • 考虑Top k返回的情形
      • 则每个k的取值对应一个R和P
    • 计算得到查准率-查全率曲线

    P-R的优缺点

    • 优点:
      • 简单直观
      • 既考虑了检索结果的覆盖度,又考虑了检索结果的排序情况
    • 缺点:
      • 单个查询的P-R曲线虽然直观,但是难以明确表示两个查询的检索结果的优劣

    基于P-R曲线的单一指标

    • 固定检索等级的查准率
      • Precision@k:前k个结果的查准率
      • 对大多数的web搜索适合,因为用户看重在前几页中有多少好结果
      • 平均的方式不好,通常所用指标中最不稳定的
    • 11点平均正确率
      • 对每个信息需求,插值的正确率定义在0,0.1,0.2,…,0.9,1共11个召回率水平上
      • 对每个召回率水平,对测试集中多个查询在该点的插值正确率求算术平均

    更多的评价准则:AP

    • 平均查准率(Average Precision,AP):对不同召回率点上的正确率进行平均

      • 未插值AP:某个查询Q共有6个相关结果,某系统排序反回了5篇相关文档,其位置分别为 第1,第2,第5,第10,第20位。
      • AP=(11+22+35+410+520+0)/6,等价于6点平均

      • 插值的AP:在召回率分别为0, 0.1, 0.2, … ,1.0的十一个点上的正确率求平均,等价于11点平均

      • 只对返回的相关文档进行计算的AP

        AP=(11+22+35+410+520)/5,倾向返回那些快速返回结果的系统,没有考虑召回率,等价于5点平均

    不考虑召回率

    • Precision@N:在第N个位置上的正确率
      • 对于搜索引擎,大量统计数据表明,大部分搜索引擎用户只关注前一、两页结果。因此P@10、P@20对大规模搜索引擎来说是很好的指标

    宏平均vs微平均

    • 平均的求法:
      • 宏平均(Macro Average):对每个查询求出某个指标,然后对这些指标进行算术平均
      • 微平均(Micro Average):将所有查询视为一个查询,将各种情况的文档总数求和,然后进行指标运算。(一个系统的所有查询)
      • Eg: MicroPrecision=
      • 宏平均对所有查询一视同仁,微平均受返回相关文档数目比较大的查询影响(宏平均保护弱者)

    平均查准率均值 Mean Average Precision(MAP)

    • 每个相关文档位置上查准率的平均值,被称为平均查准率(AP)
    • 对所有查询求宏平均,就得到平均查准率均值(MAP)
    • Map(Q)=1|Q||Q|j=11mjmjk=1Precision(Rjk)
    • Q为信息需求,qjQ所对应的所有相关文档集合为{d1,d2,,dmj}Rij是查询qj的返回结果,该结果中包含而不含有dk+1及以后的相关文档

    面向用户的评价指标

    • 假定用户已知的相关文档集合为U,检索结果和U的交集为Ru,则覆盖率
      • C=RuU检索系统找到的用户已知的相关文档比例
    • 假定检索结果中返回一些用户以前未知的相关文档Rk,则可以定义新颖率
      • N=|Rk||Ru|+|Rk|,表示系统返回的新相关文档的比例

    GMAP

    • AP的集合平均值(更能体现细微差别)

    NDCG

    • 每个文段不仅仅只有相关和不相关,而是有相关级别
      • 相关度级别越高的结果越多越好
      • 相关度级别越高的结果越靠前越好

    摘要

    • 标题通常是从文档的元数据中自动抽取出来的
      • 用户根据描述信息来判断这个文档是否相关
    • 两种基本类型
      • 静态:不论输入什么查询,文档的静态摘要都是不变的
      • 动态:动态摘要依赖于查询,试图解释当前文档返回的原因

    本讲小结

    • 信息检索的评价方法
      • 不考虑序的检索评价指标:P、R、F
      • 考虑序的评价指标:P/R曲线、MAP、NDCG
    • 检索结果的摘要

    相关反馈及查询扩展

    • 交互式相关反馈:在初始检索结果基础上,通过用户指定哪些文档相关或不相关,然后改进检索的结果。Rocchio相关反馈
    • 查询扩展(Query expansion):通过在查询中加入同义或者相关的词项来提供检索结果。人工编辑的同义词辞典、自动构造的同义词词典、查询日志

    动机

    搜索中提高召回率的方法

    • 提高召回率的方法—— 相关反馈及查询扩展
    • 返回不包含查询词项的相关文档

    关于召回率Recall

    • 放松召回率的定义,给用户返回更多的相关文档

    提高召回率的方法

    • 局部(local)方法:对用户查询进行局部的实时分析
      • 主要局部方法:相关反馈(relevance feedback)
    • 全局(global)方法:进行一次性的全局分析产生同/近义词词典(thesaurus)
      • 利用该词典进行查询扩展

    相关反馈基础

    相关反馈的基本思想

    • 用户提交一个(简短的)查询
    • 搜索引擎返回一系列文档
    • 用户将部分返回文档标记为相关的,将部分文档标记为不相关
    • 搜索引擎根据标记结果计算得到信息需求的一个新查询表示。(希望好于初始查询)
    • 对新查询进行处理,返回新结果。
    • 新结果渴望有更高的召回率

    相关反馈分类

    • 用户相关反馈或显示相关反馈(User Feedback or Explicit Feedback):用户显示参加交互过程
    • 隐式相关反馈(Implicit Feedback):系统跟踪用户的行为来推测返回文档的相关性,从而进行反馈
    • 伪相关反馈或盲目相关反馈:(Pseduo Feedback or Blind Feedback):没有用户参与,系统直接假设返回文档的前K篇相关的,然后进行反馈。

    相关反馈详细介绍

    相关反馈中的核心概念:质心

    • 质心是一系列点的中心
    • 前面将文档表示成高维空间中的点
    • 计算文档质心的公式:

    相关反馈基本理论

    • 基本理论:假定要找一个最有查询向量q,它与相关文档之间的相似度最大且同时又和不相关文档之间的相似度最小。
    • q~opt~是将相关文档与不相关文档区分开的向量
    • 当sim()函数采用余弦相似度计算时,能够将相关文档与不相关文档区分开的最有查询向量为:
    • 最优查询向量等于相关文档的质心向量和不相关文档的质心向量的差

    Rocchio算法

    • 假定有一个用户查询,并知道部分相关文档和不相关文档的信息,最优查询向量为
    • q-
    • 修改后的新查询从q~0~开始,向相关文档质心靠近,同时与不相关文档质心远离。
    • 相关文档的质心移动一个量,该量为相关文档质心和不相关文档质心的差异量
    • 修改后的新查询,向着相关文档的质心向量靠近了一段距离,与不相关文档的质心向量远离了一段距离。

    相关反馈策略的评价

    • 使用初始查询q~0~ ,计算”查准率-查全率“曲线
    • 使用相关反馈后修改查询q~m~,然后计算”查准率-查全率“曲线
      • 方案1:在整个文档集合上评价
      • 有显著的改善,但是有作弊嫌疑部分原因是会把已知的相关文档排在很前
      • 需要用用户没有看到的文档集合来评价
      • 方案2:使用剩余的文档集合来评价(总的文档集合减去评价过的相关性文档)
      • 评价结果往往比初始查询的结果差,但是这种方法更现实
      • 可以用来有效比较不同相关反馈方法之间的相对效果
      • 方案3:使用两个文档集合
      • 在第一个文档集合上使用初始查询q~0~,并进行相关反馈
      • 在第二个文档集合上使用初始查询q~0~和修改过的查询q~m~进行评价

    评价的误区

    • 评价不同相关反馈的效用的时候,必须考虑消耗时间的要素。
    • 代替相关反馈的方法:用户修改并重新提交查询
    • 相对于判断文档的相关性,用户可能更愿意修改并重新提交查询
    • 没有证据能表明相关反馈占用了用户的时间就能给用户带来最大的效用。

    查询扩展

    • 提高召回率
    • 查询重构的全局方法。在全局查询扩展中,查询基于一些全局的资源进行修改。
    • 主要使用 同义词或近义词词典(人工构建和自动构建)

    概率检索模型

    向量空间模型回顾

    向量空间模型

    • 文档表示成向量
    • 查询也表示成向量
    • 计算两个向量之间的相似度:余弦相似度、内积相似度
    • 向量表示中的词项权重计算方法主要是tf-idf公式,实际考虑**tf、idf及文档长度**3个因素

    向量空间模型优缺点

    优点
    • 简洁直观,可以应用到很多其他领域(文本分类、生物信息学)
    • 支持部分匹配和近似匹配,结果可以排序
    • 检索效果不错
    缺点
    • 理论上不够:基于直觉的经验性公式
    • 索引项之间的独立性假设与实际不符:实际上,term的出现之间是有关系的,不是完全独立。

    基本概率统计知识

    随机试验和随机事件

    概率和条件概率

    乘法公式、全概率公式和贝叶斯公式

    事件独立性

    概率检索模型

    • 概率检索模型:通过概率的方法将查询和文档联系起来
      • 定义3个随机变量R、Q、D:相关度R={0,1},查询Q={q1,q2,…},文档D={d1,d2,…}
      • 通过计算条件概率P(R=1|Q=q,D=d)来度量文档和查询的相关度

    概率排序原理PRP

    • 利用概率模型来估计每篇文档和需求的相关概率P(R=1|d,q),然后对结果进行排序
    • 最简单的PRP情况
      • 检索没有任何迭代因子,或者说不会对不同行为或错误采用不同的权重因子。
      • 在返回一篇不想管文档或者返回一篇相关文档不成功的情况下,将失去1分
      • 而检索的目标是对于用户给定的k值,返回可能性最高的文档前k篇作为结果输出。即RPR希望可以按照P(R=1|d,q)值的降序来排列所有文档
    • 公式的理解

    基于检索代价的概率排序原理

    • C~1~表示一篇相关文档未返回所发生的代价
    • C~0~表示返回一篇不相关文档所发生的代价
    • PRP认为,如果对于一篇特定的文档d及其所有其他未返回的文档d’都满足:
    • C0P(R=1|d)C1P(R=0|d)C0P(R=1|d)C1P(R=0|d)
      • C0P(R=1|d):当d不相关时却返回的代价(判为相关)
      • C1P(R=0|d):当d相关却没有返回的代价
      • 两者相减表示返回文档d的代价函数,即此时前者越低越好,后者越高越好
    • 那么d就应该是下一篇被返回的文档

    二值独立概率模型BIM

    • 为了对概率函数P(R|q,d)进行估计,引入了一些简单假设。
      • ”二值“等价于布尔值:文档和查询都表示为词项出现与否的布尔向量
      • 类似,查询q表示成词项出现向量q
      • ”独立性“指的式词项在文档中的出现是相互独立的,BIM不识别词项之间的关联。

    平滑

    • 在减少出现事件的概率估计值的同时提高未出现事件的概率估计值的方法

    BIM模型的优缺点

    优点
    • BIM模型建立在数学基础上,理论性较强
    缺点
    • 需要估计参数
    • 原始BIM没有考虑TF、文档长度因素
    • BIM中同样存在词项独立性假设

    理论上的概率估计方法

    • P~t~词项出现在一篇相关文档中的概率
    • pt=P(xt=1|R=1,q)=s/S
    • u~t~词项出现在一片不相关文档中的概率
    • ut=P(xt=1|R=0,q)=(dfts)/(NS)

    基于语言建模的检索模型

    • 传统概率模型
      • 需要对文档d与查询q的相关概率P(R=1|q,d)进行显示建模
    • 概率语言模型
      • 首先对每篇文档d建模得到文档的概率语言模型 Md
      • 然后按照模型生成查询q的概率P(q|Md)的高低来对文档进行排序

    语言模型

    最简单的语言生成器模型

    • 一个简单的又穷自动机及其生成语言中的一些字符串
      • 指向的是自动机的初始状态
      • 双圈节点对应的是终止状态
    • 如果每一个节点都有一个生成不同词项的概率分布,便得到一个语言模型,或概率语言模型,或统计语言模型
      • 语言模型的概念本质上是基于概率的

    有穷自动机语言模型

    • 一个语言模型(LM)是从某词汇表上抽取的字符串概率的一个映射函数。对字母表上的语言模型M有:sP(s)=1
    • 最简单的语言模型等价于一个仅仅包含一个节点的概率有穷自动机,只有一个生成不同词项的概率分布,因此有tVP(t)=1
    • 假定停止概率是固定的,因此不会影响文档的排序。因此可以不考虑停止概率,但形式上得到的结果将不再是概率,而只是概率的部分项

    语言模型的比较

    • 比较两个模型,可计算似然比,即将其中一个模型的数据生成概率除以另外一个模型数据的生成概率。

    语言模型的种类

    对于词项序列如何求解其生成的概率值

    • 根据链式规则将一系列事件的概率分解成多个连续事件概率之积,每个概率是每个事件基于其历史事件的条件概率。
    • P(t1t2t3t4)=P(t1)P(t2|t1)P(t3|t1t2)P(t4|t1t2t3)

    语言模型的种类n-gram

    • 一元语言模型(Unigram LM):上下文语言无关模型,是最简单的语言模型,去掉所有条件概率中的条件来独立地估计每个词项的概率

      • Puni(t1t2t3t4)=P(t1)P(t2)P(t3)P(t4)
      • 词袋模型Bag of words
    • 二元语言模型(Bigram LM):即计算条件概率时只考虑前一个词项的出现情况

      • Pbi(t1t2t3t4)=P(t1)P(t2|t1)P(t3|t2)P(t4|t3)
    • 三元语言模型(Trigram LM)

    词的多项式分布

    • 词的多项式分布

    语言模型应用到IR

    总体分布&抽样

    • 文档模型实际是某种总体分布
    • 文档和查询都是该总体分布下的一个抽样样本示例
    • 根据文档,估计文档的模型,即求出该总体分布,然后计算该总体分布下抽样出查询的概率
    • 文档 总体分布 查询

    查询似然模型

    • 每篇文档d构建其对应的语言模型Md
    • 将文档按照其余查询相关的似然P(d|q)排序
      • P(d|q)=P(d|q)P(d)P(q)
    • 最后会按照P(d|q)进行排序,它是在文档d对应的语言模型Md下生成q的概率

    • IR中的语言建模方法实际上是在对查询的过程进行建模

      • 首先每篇文档d对应一个文档模型Md
      • 然后计算查询被视为每个文档模型的随机抽样样本的概率
      • 最后根据这些概率对文档排序
      • P(q|Md)=KqtVP(t|Md)tft,d
      • Kq是查询q的多项式系数,对于某个特定查询,是一个常数可以忽略。
    • 模型的直观意义是,用户脑子里有一篇原型文档,然后按照该文档中的词语用法来生成查询。

    查询生成的概率估计

    • 每篇文档d构建其对应的语言模型Md
    • 采用最大似然估计:使得观察样本出现概率最大的估计
      • P(q|Md)=tqPmle(t|Md)=tft,dLd
      • Ld是d中的词条数目

    线性插值LM示例

    平滑的方法:线性插值LM

    • 需要对文档LM的概率进行平滑(Smoothing),即对出现事件的概率结果进行折扣,并对未出现的词的概率赋予一定的值。

    • 将基于文档的多项式分布和基于全部文档集估计出的多项式分布相混合

    • P(t|d)=λPmle(t|Md)+(1λ)Pmle(t|Mc)
      • λ(0,1) , Mc是基于全部文档集构造的LM

    扩展的LM方法

    • a查询似然类:文档建模,计算查询的似然
      • 基本QLM模型、翻译模型
    • b文档似然类:查询建模,计算文档的似然
      • BIM模型、相关性模型
    • c模型比较类:文档建模,查询建模,kl距离模型

    文本分类及朴素贝叶斯分类器

    本讲要点

    • 什么是文本分类
    • 什么是朴素贝叶斯分类器
    • 朴素贝叶斯分类器的生成模型
    • 朴素贝叶斯分类器的性质
      • 条件独立假设&位置独立性假设
    • 特征选择:互信息、x2统计量、词项频率
    • 文本分类评价:宏平均和微平均

    文本分类

    • 给定分类体系,将一篇文本分到其中一个或者多个类别中的过程。

    • 文本分类中,给定文档dX 和一个固定的类别集合 C={C1,C2,,Cj} , 其中X表式文档空间,类别也通常称为类或类标签

      • 按类别书目:binary vs multi-class
      • 按每篇文档赋予的标签书目: sing label vs multi label

    分类方法1: 手工方法

    • 使用人工分类方法来分类,如果专家来分类精度会非常高
    • 如果问题规模和分类团队都很小时,能否保持分类结果的一致性

    分类方法2:规则方法

    • 繁琐,开销大

    分类方法3:机器学习方法

    • 文本分类被定义为一个学习问题,包括:
      • 通过有监督的学习,得到分类函数γ,然后将其应用于对新文档的分类
    • 一系列的分类方法:朴素贝叶斯、Rocchio、KNN、SVM
    • 当学习方法基于统计时,此方法也称为统计文本分类:
      • 在统计文本分类中,对每个类别需要一些好的文档样例(训练文档)
      • 需要人来标注训练文档,所以对人工分类的需求依然存在
      • 标注(labeling)指对每篇文档赋予类别标签的过程

    基于学习的文本分类

    • 文档空间X
      • 文档都在该空间下表示—— 通常都是某种高维空间
    • 固定的类别集合C=C1,C2,...,Cj
      • 类别往往根据应用的需求来人为定义
    • 训练集D,文档d用c来标记,<d,c>X×C
      • 利用学习算法,可以学习一个分类器γ,它可以将文档映射成类别: γXC
    • 文档分类的实现
      • 对于文档空间中文档,dX,可确定γ(d)C即确定d最可能属于的类别ci=γ(d),cC

    无监督/有监督的学习

    • supervised learning 监督学习
      • 利用一组已知类别的样本调整分类器的参数,使其达到所求性能的过程,也称为监督训练或有教师学习
    • 无监督学习
      • 若所给的学习样本不带有类别信息,就是无监督学习

    搜索引擎中的文本分类应用

    • 语言识别
    • 垃圾网页识别
    • 是否包含淫秽内容
    • 领域搜索或垂直搜索—— 搜索对象限制在某个垂直领域
    • 静态查询
    • 情感识别

    朴素贝叶斯分类器

    • 是一个概率分类器
    • 文档d属于类别c的概率计算
    • P(c|d)=P(c)P(d|c)P(d)P(c)P(d|c)P(c)1KndP(tk|c)
    • t~k~是d中的词条,n~d~是文档的长度(词条个数)
    • P(t~k~|c)是此项t~k~出现在类别c中文档的概率,或类别c生成词项t~k~的概率,或是度量的是当c是正确类别时t~k~的贡献
    • P(c)是类别c的先验概率
    • 如果文档的词项无法提供属于哪个类别的信息,那么直接选择P(c)最高的那个类别

    朴素贝叶斯理论

    两种模型文本生成过程

    • 给定类别时文档生成的条件概率计算有所不同
      • 多项式模型P(d|c)=P(<t1,,tk,,tnd>|c)
      • 贝努利模型P(d|c)=P(<e1,,ek,,eM>|c)
      • 其中 多项式模型是d中出现的词项序列(去掉词)
      • 贝努利模型是一个M维的布尔向量,表示每个词项在文档d中存在与否。
    • 两种不同的文档表示方法
      • 多项式模型是文档空间X是所有词项序列的集合
      • 贝努利模型是文档空间X是{0,1}M

    具有最大后验概率的类别

    • 朴素贝叶斯分类的目标是寻找“最佳”类别

    特征选择

    • 文本分类中,通常要将文本表示在一个高维空间下,每一维对应一个词项。特征选择是从训练集合出现的词项中选出一部分子集的过程。在文本分类过程也仅仅使用这个子集作为特征
    • 特征选择有两个主要目的:
      1. 通过减少有效的词汇空间来提高分类器训练和应用的效率。这对除NB之外的其他训练开销较大的分类器来说尤为重要。
      2. 特征选择能够去除噪音特征,从而提高分类的精度。
    • 噪音特征:加入文本表示之后反而会增加新数据上的分类错误率的特征
    • 由于训练集的偶然性导出的不正确的泛化结果称为过学习

    特征选择算法

    • 给定类别c,对词汇表中的每个词项t,计算效用指标A(t,c),然后从中选择k个具有最高值的词项作为最后的特征。

    不同的特征选择方法

    • 特征选择方法主要基于其所使用特征效用指标来定义
    • 特征效用指标
      • 频率法—— 选择高频词项
      • 互信息—— 选择具有最高互信息的那些词项
      • 卡方x^2^

    分类评价

    • 评价必须基于测试数据进行,而且该测试数据与训练数据完全独立。
    • 很容易通过训练可以子训练集上达到很高的性能
    • 常用指标:正确率、召回率、F~1~值、分类精确率等等
    • 宏平均:在类别之间求平均值 微平均:将每篇文档在每个类别上的判定放入一个缓冲池,然后基于这个缓冲池计算效果指标。

    宏平均

    • 对类别集合C中的每个类都计算一个F~1~值
    • 对C个结果求平均

    微平均

    • 对类别集合C中的每个类都计算TP、FP和FN
    • 将C中的这些数字累加
    • 基于累加的TP、FP、FN计算P、R和F~1~

    宏平均和微平均的适用范围

    • 宏平均和微平均的计算结果可能会相差很大。宏平均对每个类等同对待,而微平均则对每篇文档的判定结果等同对待
    • 由于F1值忽略判断正确的负例,所以它的大小主要由判断正确的正例数目所决定,所以在微平均计算中大类起支配作用。

    基于向量空间模型的文本分类

    • Rocchio方法
      • 基于质心或原型将整个向量空间划分成多个区域
    • kNN方法
      • 将K个最邻近文档所属的主类别赋给测试文档
    • 线性分类器
      • 指基于特征的简单线性组合就可以对文档进行分类的分类器

    基于向量空间的分类方法

    向量空间表示

    • 每个文档表示成一个向量,向量的每一维表示一个term
    • 向量可以归一化成单位长度
    • 高维向量空间
      • 维度非常高
      • 每个term就是一个坐标轴
      • 文档表示为空间的向量

    向量空间模型

    • 词项——文档矩阵:二值—> 计数 —> 权重矩阵(tf-idf)
    • 相关性 = 向量距离 : 欧式距离—> 夹角 —> 余弦相似度

    • 利用向量空间模型进行文本分类的思路主要基于邻近假设

      1. 同一类的文档会构成一个邻近区域
      2. 不同类的邻近区域之间互不重叠
    • 如何找到分类面决策边界(decision boundary)

    Rocchio方法

    Rocchio方法进行向量空间分类的思路

    • 利用质心来定义分类边界
    • 一个类别c的质心可以通过类中文档向量的平均向量或者质心想来来计算
    • 计算公式:

    Rocchio算法

    • 计算每个类的中心向量(所有文档向量的算术平均)
    • 将每篇测试文档分到离它最近的那个中心向量

    Rocchio算法中的决策边界

    • 利用质心来定义分类边界
    • 两类的边界由那些到两个类质心等距的点集组成(超平面)

    Rocchio分类方法的缺陷

    • 为了遵循邻近性的要求,Rocchio 分类中的每个类别一定要近似球形,并且它们之间具有相似球半径。

    KNN邻近方法

    kNN(k邻近)方法

    • kNN = k nearnest neighbors, k邻接
    • k = 1情况下的kNN:将每篇测试文档分给训练集中离它最近的那篇文档所属的类别。
    • 1NN不很鲁棒 —— 一篇文档可能会分错类或者这篇文档本身就返常
    • k>1情况下的kNN:将每篇测试文档分到训练集中离它最近的k篇文档所属类别中最多的那个类别
    • kNN的基本依据
      • 根据邻近假设,一篇测试文档d将和其邻域中的训练文档应该具有相同的类别。

    1NN分类器

    • 1NN分类器的判别边界是Voronoi剖分形成的多个线段的连接。Voronoi剖分会将整个平面分成|D|个凸多边形,每个多边形仅包含其对应的文档,而每个凸多边形是在二维空间种通过直线围成的凸区域。

    小结:KNN方法

    • 思路:将每篇测试文档分到训练集中离它最近的k篇文档所属类别中最多的那个类别
    • KNN的基本依据:根据邻近假设,一篇测试文档d将和其领域中的训练文档应该具有相同的类别
      • 当训练集非常大的时候,KNN分类精度很高
      • 当训练集非常小的时候,KNN效果很差

    线性分类器

    • 定义

    基于向量空间模型的文本分类

    二元线性SVM

    • SVM是最大间隔分类器的一种,它是局域向量空间的机器学习方法,其目标是找到两个类别之间的一个决策边界,使之尽量远离训练集上的任意一点。
    • SVM定义的准则是寻找一个离数据点最远的决策面。从决策面到最近数据点的距离决定了分类器的间隔

    小结:SVM要点

    • 线性SVM的结果分类器为:
    • SVM基本过程:
      • 基于给定训练数据集,通过二次优化过程寻找最佳的分类超平面
      • 对于待分类的新数据点,利用分类函数计算该点到超平面的距离
      • 距离的正负(分类函数的符号)决定了该数据点类别的归属
      • 如果该点在分类器的间隔之内,分了器可以在原来的两个类之外,返回“类别未知”

    文本聚类

    聚类介绍

    聚类的定义

    • 文档聚类是将一系列文档按照相似性聚团成子集或者簇的过程
    • 簇内文档之间应该彼此相似,相似度不大
    • 聚类是一种最常见的无监督学习方法
      • 无监督学习意味着没有已标注好的数据集

    分类VS聚类

    • 分类:有监督的学习
    • 聚类:无监督的学习
    • 分类:类别事先人工定义好,并且是学习算法的输入的一部分
    • 聚类:簇在没有人工输入的情况下从数据中推理而得
      • 但是很多因素会影响聚类的输出结果:簇的个数、相似度计算方法、文档的表示方式等。

    聚类在IR中的应用

    聚类假设

    • 在考虑文档和信息需求之间的相关性式,同一簇中的文档表现互相类似。
    • 聚类在IR中的应用所有应用都直接或间接基于上述聚类假设

    聚类在IR中的应用

    应用 聚类对象 优点
    搜索结果聚类 搜索结果 提供面向用户的更有效的展示
    “分散-集中”界面 文档集和文档子集 提供了另一种用户界面,即不需要人工输入关键词的搜索界面
    文档聚类 文档集 提供了一种面向探索式浏览的有效性的信息展示法
    基于语言建模的IR文档集 文档集 提高了正确率和/或召回率
    基于聚类的检索 文档集 加快了搜索的速度

    文档聚类用于提高召回率

    • 实现将文档集中的文档进行聚类
    • 当文档和查询匹配时,也返回包含d的簇所包含的其它文档
    • 我们希望通过上述做法,在输入查询“car”时,也能包含“automobile”的文档
    • 由于聚类算法会把包含“car”的文档和包含“automobile”的文档聚在一起

    聚类的要求

    • 一般目标: 将相关文档放到一个簇中,将不相关文档放到不同的簇中
    • 簇的数目应该合适,以便于聚类的数据集吻合
      • 一开始,假设给定簇的数目为K
      • 后面介绍K的半自动的方法
    • 其它目标:
      • 避免非常小和非常大的簇
      • 定义的簇对用户来说很容易理解
      • 其它……

    扁平聚类vs层次聚类

    • 扁平算法:

      • 通过一开始将全部或部分文档随机划分为不同的组
      • 通过迭代不断修正
      • 代表算法: K-均值聚类算法
    • 层次算法:

      • 构建具有层次结果的簇
      • 自底向上(Bottom-up)的算法称为凝聚式算法
      • 自顶向下的(Top-down)算法称为分裂式算法

    硬聚类vs软聚类

    • 硬聚类:每篇文档仅仅属于一个簇
      • 很普遍并且相对容易实现
    • 软聚类:一篇文档可以属于多个簇

    扁平算法

    • 扁平算法将N篇文档划分成K个簇
    • 给定一个文档集合及聚类结果簇的个数K
    • 寻找一个划分将这个文档集合分成K个簇,该结果满足最优划分规则
    • 全局优化:穷举所有的结果划分,从中选择最优的那个划分结果(无法处理)
    • 高效的启发式方法:k-均值聚类算法

    K-均值聚类算法

    最著名的聚类算法,算法十分简单,但是在很多情况下效果不错

    聚类中的文档表示

    • 向量空间模型
    • 欧式距离计算向量之间的相关性

    K-均值聚类算法

    • K-均值聚类算法中的每个簇都定义为其质心向量
    • 划分准则:使得所有文档到其所在簇的质心向量的平方和最小
    • 质心向量的定义:
    • 通过下列两部来实现目标优化:
      1. 重分配:将每篇文档分配给离它最近的簇
      2. 重计算:重新计算每个簇的质心向量

    K-均值聚类算法一定会收敛

    • RSS(Residual Sum of Squares)残差平方和 = 所有簇上的文档向量到质心向量的距离的平方和的总和
    • 每次重新分配之后RSS会下降
      • 因为每个向量都被移到离它最近的质心向量所代表的簇中
    • 每次重新计算之后RSS也会下降
    • 可能的聚类结果是有穷的,因此一定会收敛到一个固定点
    • 如果出现了等值的情况,算法都采用前后一致的方法来处理
    • 如果不关心少许文档在不同簇之间来回交叉的话,收敛速度通常会很快。但是完全收敛需要很庞大的迭代过程

    K-均值聚类算法的最优性

    • 收敛并不意味着会达到全局最优的聚类结果,这是K-均值聚类算法最大缺点之一。如果开始的种子选择不好,最终的聚类结果可能会非常糟糕。

    K-均值聚类算法的初始化

    • 种子的随机选择只是K-均值聚类算法的中初始化方法之一
    • 随机选择不太鲁棒:可能会获得一个次优的聚类结果
    • 更好的办法:
      • 非随机地采用某些启发式方法来选择种子(比如,过滤掉一些离群点,或则寻找具有较好文档空间覆盖度的种子集合)
      • 采用层级聚类算法寻找好的种子
      • 选择i次不同的随机种子集合,对每次产生的随机种子集合运行K-均值聚类算法,最后选择具有最小RSS的聚类结果。

    K-均值聚类算法的时间复杂度

    O(IKNM)-线性

    聚类评价

    内部准则

    一个内部准则的例子:K-均值聚类算法的RSS值。

    但是内部准则往往不能评价聚类在应用中的实际效用

    外部准则

    • 按照用户定义的分类结果来评价,即对一个分好类的数据集进行聚类,将聚类结果和事先的类别情况进行比照,得到最后的评价结果。
    • 目标:聚类结果和给定分类结果一致

    纯度

    • 对每个簇,找到类别cj,该类别包含wk中的元素最多,为nkj个,也就是说wk的元素最多分布在cj
    • 将所有n_{kj}求和,然后除以所有的文档数目N

    簇个数确定

    • 基本思路:
      • 从一个簇开始(K=1)
      • 不断增加簇
      • 对每个新的簇增加一个惩罚项
    • 在惩罚项和RSS之间折中,选择满足最佳折中条件的K
    • 给定聚类结果,定义文档的代价为其到质心向量的距离(失真率)
    • 定义全部失真率RSS(K)为所有文档代价和
    • 对每个簇一个惩罚项λ ,对于具有K个簇的聚类结果,总的聚类惩罚项为Kλ
    • 定义聚类结果的所有开销为失真率和总聚类惩罚项的和:RSS(K)+Kλ
    • 选择使得(RSS(k)+Kℷ)最小的K值

    本讲小结

    • 聚类的概念
    • 聚类在IR中的应用
    • K-均值聚类算法
    • 聚类评价
    • 簇个数确定
    展开全文
  • 《现代信息检索导论》课程梳理

    千次阅读 2018-11-30 21:11:18
    什么是信息检索? 一个文本检索系统是怎样的? 一、分词 二、索引 1.索引怎么得来: 2.构建索引: 3.怎么查询: 4.索引压缩: 5.索引的解压 三、评分 那么怎么来评分呢? 四、反馈 1.相关反馈: 2.查询...

    目录

    什么是信息检索?

    一个文本检索系统是怎样的?

    一、分词

    二、索引

    1.索引怎么得来:

    2.构建索引:

    3.怎么查询:

    4.索引压缩:

    5.索引的解压

    三、评分

    那么怎么来评分呢?

    四、反馈

    1.相关反馈:

    2.查询扩展:

    五、结果摘要

    六、怎么加速检索?

    1.精确top K检索及其加速办法

    2.非精确top K检索的可行性

    七、信息检索的评价指标

    1.对单个查询进行评估的指标(对单个查询得到一个结果):

    2.对多个查询进行评估的指标(在多个查询上检索系统的得分求平均)

    八、向量空间模型VS 概率检索模型 VS 统计语言模型

    1.向量空间模型:

    2.概率检索模型:

    3.统计语言模型:(本质上也是概率模型的一种)

    九、文档分类

    十、Web搜索

    1.爬虫

    2.PageRank VS HITS


    什么是信息检索?

    信息检索的概念:从大规模非结构化数据(通常是文本)的集合中找出满足用户需求的资料(通常是文档)的过程。而传统数据库往往是结构化数据(比如一张表中的数据),常常支持范围或者精确匹配查询。信息检索已经替代传统的数据库式搜索而成为信息访问的主要形式。

    一个文本检索系统是怎样的?

    一个文本检索系统=分词+索引+评分+反馈(+结果摘要)

    下面有两幅图,可以让大家在脑海中对一个信息检索系统有个大概的轮廓

    拿到 文本集和查询需求 时,要分词成为某种表现形式,文本集要建立成索引,然后进行查询,对结果,返回分数高的哪些结果(摘要),在打分的过程中还会加入反馈,从而使得结果越来越好。

     

    一、分词

    分词的流程:
    文本通过词条化为词条,词条归一化为词项,词项就是我们最终放入倒排索引的词典中,是我们要索引的对象。

     

    二、索引

    索引是把文档变为一种便于快速查找的数据结构。其中最主要的一种思想是倒排索引(Inverted index)。倒排索引是以词作为关键词,记录词出现的文档编号,以及在文档中的词频、位置等信息。

    倒排索引的数据结构:词典 + 倒排记录表

    1.索引怎么得来:

    2.构建索引:

    面对现实中的信息量大、读取效率、分布式等问题,有各种构建索引的方法:

    2.1两种索引构建算法: BSBI (简单) 和 SPIMI (更符合实际情况)

    2.2分布式索引构建: MapReduce

    2.3动态索引构建: 如何随着文档集变化更新索引

     

    3.怎么查询:

    3.1 布尔检索 (使用布尔表达式):对查询语句进行布尔化,对倒排记录表进行并集,交集,差集等操作

    3.2 查词典:词典是存储词项词汇表的数据结构,在查字典时,用到哈希表和树结构两种数据结构

    3.3 通配查询的处理(包含通配符*的查询):轮排索引和k-gram索引

    3.4 拼写出错的查询:

          对查询进行拼写校正(不改变文档)

          词独立法:只关心当前单词有没有拼错,方法有:编辑距离计算和k-gram相似度

         上下文敏感法:考虑上下文

          soundex算法:针对发音相同而出现的拼写错误

     

    4.索引压缩:

    词典压缩:将整部词典看成单一字符串,把该字符串按块存储,然后采用前端编码(因为同一块下的词项前缀很多相同)

    倒排记录表压缩:对间隔编码,可变字节编码,\gamma编码

    5.索引的解压

            最近的文本压缩方法允许在压缩文本上直接进行查找,而且,查找速度快于在未压缩文本上的查找速度。同时,在压缩文本任一点上的直接存取也可以实现。因此,信息检索系统可以在压缩文本上直接存取一个给定的词,而不需要从压缩文本的开始处解压缩整个文本。

     

    三、评分

    布尔检索,即文档(与查询)要么匹配要么不匹配,结果过少或者过多,需要大量技巧来生成一个可以获得合适规模结果的查询
    而在我们日常浏览器中见到的是排序式检索

    排序式检索会对查询和文档的匹配程度进行排序,即给出一个查询和文档匹配评分,相关度大的文档结果会排在相关度小的文档结果之前。

    那么怎么来评分呢?

    对每个查询-文档对赋一个[0, 1]之间的分值来度量了文档和查询的匹配程度

    不考虑Jaccard系数:计算两个集合重合度的常用方法,很多缺点。

    查询-文档匹配评分计算:

    词项频率 tf:指t 在d中出现的次数,是与文档相关的一个量,可以认为是文档内代表度的一个量

    逆文档频率idf:dft是出现词项t的文档数目,dft 是和词项t的信息量成反比的一个值(物以稀为贵)

     tf-idf权重计算:(采用对数来抑制影响)

    W_{t,d}=(1+\log tf_{t,d})\cdot \log \frac{N}{df_t}

    随着词项频率的增大而增大 (局部信息),随着词项罕见度的增加而增大 (全局信息)

    这里就用到了向量空间模型(VSM)

    评分流程如下;

    1.表示成向量:

    (1)文档表示成向量:

    每篇文档表示成一个基于tfidf权重的实值向量 ∈ R|V|,于是,我们有一个 |V|维实值空间,

    空间的每一维都对应词项,文档都是该空间下的一个点或者向量;极高维向量:对于Web搜索引擎,空间会上千万维;对每个向量来说又非常稀疏,大部分都是0

    (2)查询看成向量:

    对于查询做同样的处理,即将查询表示成同一高维空间的向量,按照文档对查询的邻近程度排序

    2.查询和文档两个向量之间的相似度计算:

    采用夹角而不是距离来计算--->余弦相似度计算:要归一化

    3.按照相似度大小将文档排序,将前K(如K =10)篇文档返回给用户

     

    四、反馈

    两种提高召回率的方法—相关反馈及查询扩展(实际也有可能提高正确率)

    局部方法: 对用户查询进行局部的即时的分析

    主要的局部方法: 相关反馈

    全局方法: 进行一次性的全局分析(比如分析整个文档集)来产生同/近义词词典 (thesaurus),利用该词典进行查询扩展

    1.相关反馈:

    显式相关反馈:在初始检索结果的基础上,通过用户交互指定哪些文档相关或不相关,然后改进检索的结果,也叫用户相关反馈

    隐式相关反馈:通过观察用户对当前检索结果采取的行为(点击行为、眼球行为等)来给出对检索结果的相关性判定

    伪相关反馈:对于真实相关反馈的人工部分进行自动化,对于用户查询返回有序的检索结果

    假定前 k 篇文档是相关的,进行相关反馈 (如 Rocchio)

    最著名的相关反馈方法:Rocchio 相关反馈

    2.查询扩展:

    查询扩展(Query expansion): 通过在查询中加入同义或者相关的词项来提高检索结果

    相关词项的来源: 人工编辑的同义词词典、自动构造的同义词词典、查询日志等等。

     

    五、结果摘要

    怎么呈现出结果,描述该列表中的每篇文档,用户往往根据该描述来判断结果的相关性,而不需要按次序点击所有文档

    静态摘要:不论输入什么查询,文档的静态摘要都是不变的

    动态摘要:而动态摘要依赖于查询,它试图解释当前文档返回的原因

     

    六、怎么加速检索?

    1.精确top K检索及其加速办法

    目标:从文档集的所有文档中找出K 个离查询最近的文档

    (一般)步骤:对每个文档评分(余弦相似度),按照评分高低排序,选出前K个结果

    如何加速:

    思路一:加快每个余弦相似度的计算--->无权重查询

    思路二:不对所有文档的评分结果排序而直接选出Top K篇文档---->用堆方法

    思路三:能否不需要计算所有N篇文档的得分?--->提前终止计算

    2.非精确top K检索的可行性

    索引去除,胜者表,静态质量得分排序方式,影响度(Impact)排序,簇剪枝

    非docID的倒排记录表排序方法,多层次索引等

     

    七、信息检索的评价指标

    1.对单个查询进行评估的指标(对单个查询得到一个结果):

    召回率(Recall),正确率(Precision)

    缓冲池(Pooling)方法:对多个检索系统的Top k个结果组成的集合(并集)进行人工标注,标注出的相关文档集合作为整个相关文档集合。

    F值(F-measure):召回率R和正确率P的调和平均值

    R-Precision:检索结果中,在所有相关文档总数位置上的准确率。

    正确率-召回率 P-R曲线

    2.对多个查询进行评估的指标(在多个查询上检索系统的得分求平均)

    平均的求法:宏平均,微平均

    MAP(Mean AP),Bpref,GMAP,NDCG

     

    八、向量空间模型VS 概率检索模型 VS 统计语言模型

    1.向量空间模型:

    优点:简洁直观,可以应用到很多其他领域(文本分类、生物信息学)。支持部分匹配和近似匹配,结果可以排序;检索效果不错

    缺点:理论上不够严谨,往往基于直觉的经验性公式;词项之间的独立性假设与实际不符:实际上,词项的出现之间是有关系的,并不是完全独立的。如:“张继科”、“乒乓球”的出现不是独立的。

    2.概率检索模型:

    通过概率的方法将查询和文档联系起来

    定义3个随机变量R、Q、D:相关度R={0,1},查询Q={q1,q2,…},文档D={d1,d2,…},则可以通过计算条件概率P(R=1|Q=q,D=d)来度量文档和查询的相关度。

    概率模型包括一系列模型,如Logistic Regression(回归)模型及最经典的二值独立概率模型BIM、BM25模型等等(还有贝叶斯网络模型)

    3.统计语言模型:(本质上也是概率模型的一种)

    广泛使用于语音识别和统计机器翻译领域,利用概率统计理论研究语言
    SLM广泛使用于语音识别和统计机器翻译领域,利用概率统计理论研究语言。
    规则方法:词、句、篇章的生成比如满足某些规则,不满足该规则就不应存在。
    统计方法:任何语言片断都有存在的可能,只是可能性大小不同

    对于一个文档片段d=w1w2…wn,统计语言模型是指概率P(w1w2…wn)求解,根据Bayes公式,有

    统计语言建模IR模型(SLMIR)

    1.查询似然模型:把相关度看成是每篇文档对应的语言下生成该查询的可能性

    2.翻译模型:假设查询经过某个噪声信道变形成某篇文章,则由文档还原成该查询的概率(翻译模型)可以视为相关度

    3.KL距离模型:查询对应某种语言,每篇文档对应某种语言,查询语言和文档语言的KL距离作为相关度度量

     

    九、文档分类

    统计分类是一个成功的搜索引擎所必需的关键技术,给定一系列文档及其归属类别的前提下,将新文档分配到某个或者某几个类别中去。

    朴素贝叶斯算法:该算法概念虽然简单,但是文本分类的效率很高),

    基于向量空间模型的分类方法: Rocchio kNN

    支持向量机:这是目前公认的效果最好的文本分类算法

     

    十、Web搜索

    1.爬虫

    Web 采集器。基本的采集过程为,初始化采集 URL 种子队列,重复的 1.取出 URL 2.下载

    并分析网页 3.从网页中抽取更多的 URL 4.将 URL 放到队列中。

    2.PageRank VS HITS

    PageRank:从很多优质网站链接过来的网页肯定还是优质的网页。

    HITS:既然搜索开始于用户的检索提问,那么每个页面的重要性也依赖于用户的检索提问。现代信息检索

    展开全文
  • 信息检索

    千次阅读 2018-08-21 15:16:20
    1、信息检索(information retrieval):就是非结构化的文本数据的检索。 信息检索与数据库侧重点不同:强调基于关键字的查询、文档与查询的相关性,以及文档的分析、分类和索引等问题。Web搜索引擎不局限于文档...

    关系数据库中:数据----结构化,文本数据----非结构化

    1、信息检索(information retrieval):就是非结构化的文本数据的检索。

    信息检索与数据库侧重点不同:强调基于关键字的查询、文档与查询的相关性,以及文档的分析、分类和索引等问题。Web搜索引擎不局限于文档检索,而同时研究更为广泛的问题来满足用户的信息需求,譬如显示那些信息作为关键字查询的结果。

    在web环境中,每个HTML页面通常被认为是一份文档。

    文档本身已经与一组关键字相关联,如果文档的关键字包含用户提供的关键字,就被检索出来。

    基于关键字的信息检索不仅用于检索文本数据,还可用于检索其他类型的数据,如视频和音频数据。

    在全文检索中,每份文档的所有词都当做关键字。对于非结构化文档,因为可能无法得到有关信息来判断文档中那些词为关键字,所以全文检索是必要的。根据术语出现拼读的信息和超链接信息估计相关性。

    2、术语的相关性排名

    信息检索系统估计文档与查询的相关性,并且只返回高度相关的文档作为结果。相关性排名不是一门精密科学:

    i:    TF-IDF排名方法

    问题:给定一个特定的术语t,某份特定文档d与该术语的相关性如何。

    方法:用该文档中该术语的出现次数作为对相关性的度量,基于的假设:相关的术语很有可能在文档中提及多次。只统计一个术语的出现次数通常不是一个好的相关性指示器:首先,出现次数取决于文档的长度;其次,某个术语出现10次的文档的相关性可能并不是术语只出现1次文档的相关性的10倍。

    TF(d,t)=log(1+n(d,t)/n(d))

    TF(d,t)(term frequency):文档d对术语t的相关性    ; n(d): 文档中术语的个数  ;n(d,t):文档d中术语t出现次数

    公式考虑了文档的长度,文档中术语的出现次数越多相关性越大,尽管不是直接正比于出现次数

    逆文档频率(inverse doucument frequency)对术语赋权值:IDF(t)=1/n(t)

    3、使用超链接的相关性排名

    流行度排名(popularity ranking),威望度排名(prestige ranking)的基本思想:找到流行的页面,并且把它们的位置排在同样包含指定关键字的其它页面之前。

    估计页面的流行度方法:使用链接到该页面的页面数目作为流行度的度量;流行度与站点相关联,而不是页面相关联。一个站点的所有页面获得该站点的流行度。

    3、web的抓取和索引

    网络爬虫(web crawler)是定位和收集web上的信息的程序。它们沿着已知文档中存在的超文本链接递归地找到其他文档。从一组可有人工设定的厨师链接开始,一句URL链接抓取WEB上的页面。随后,爬虫定位抓取到的页面中所包含的所有URL链接信息,若果这些链接所指向的页面没有被抓取过,而且也不存在于当前的待抓取集合中,那么爬虫就把他们加入到待抓取的URL链接集合中。这一过程将以不断抓取集合中的页面并处理这些页面中的链接的形式反复进行。通过以上的过程,所有可以由初始集合中的URL出发以任意的链接顺序到达的页面都将被抓取到。

     

      

    展开全文
  • 信息检索导论》读书笔记

    千次阅读 2015-12-16 23:57:20
    谷歌、百度、雅虎等公司建立了强大的互联网搜索引擎用于快速检索用户需要的网页,一些电商、专业网站往往也建立了内部的检索系统,这一系列背后的技术都离不开信息检索这一门学科的知识。本文将围绕这一方面进行详细...
  • 信息检索的概述

    2019-07-19 16:39:07
    信息检索的概述 信息过载 信息大爆炸 youtube 一分钟上传400小时视频苹果用户一分钟下载51000个应用google一分钟翻译69500000个单词siri一分钟回答错9万个问题。 总结:信息越来越多,如何迅速的定位我们需要的...
  • 网络信息检索

    2020-01-15 19:46:06
    《网络信息检索》课程笔记
  • 信息检索-1

    2020-02-23 21:25:27
    1中英文-其他语言-(增加检索结果) 2.加限定词-(缩小检索结果) 3.逻辑表达式-(缩小检索结果) 4.同义词、近义词、反义词(增加检索结果) 5.加括号--(顺序变化,结果变化) 6.一般情况下,大部分人只会看...
  • 信息检索

    千次阅读 2019-05-10 19:31:00
    这篇文章分享一些我们学习中可以用到的搜索文献资源和其他资料的网站
  • 信息检索的专业解释 其实就是将信息按一定的方式组织和存储起来,并根据用户的需要找出有关信息的过程和技术(想一想图书馆找书,本来就是很简单很平常的概念) 信息检索的基本原理(它所遵循什么样的规律和原则) ...
  • 信息检索的评价指标

    千次阅读 2019-02-27 17:02:18
    文章目录1. 引言2. 基础知识(1)定义(2)图示(3)举例说明3. 准确率(Precision)4....在信息检索、分类、识别、翻译等领域中,两个最基本的指标是准确率(Precision)和召回率(Recall),其中准...
  • 信息检索模型

    万次阅读 多人点赞 2017-09-23 10:11:28
    检索模型搜索结果排序是搜索引擎的核心,排序时最重要的两个因素就是:用户查询和网页的内容相关性及网页链接情况。 检索模型就是用来计算内容相关度的理论基础及核心组件。 一个典型的检索模型通常由三部分组成:...
  • 信息检索

    2012-05-19 10:06:29
    信息检索  信息检索(Information Retrieval)是指信息按一定的方式组织起来,并根据信息用户的需要找出有关的信息的过程和技术。狭义的信息检索就是信息检索过程的后半部分,即从信息集合中找出所需要的信息的...
  • 第四章 信息检索原理与技术 4.1 信息检索的概念 信息检索是指从信息集合中迅速、准确地查找出所需信息的程序和方法。信息检索有广义、狭义之分 • 广义信息检索:信息存储与检索两个过程。 • 狭义信息检索:仅指从...
  • 文章目录信息的含义信息的特征信息的功能信息的类型互联网对信息的影响网络环境下信息的新特点信息检索的原理信息检索的类型信息检索的意义/作用信息检索的历程信息检索系统信息检索方法信息检索效果影响信息检索...
  • 本系列文章为Elasticsearch 的学习笔记,主要是为了便于日后对于相关知识点的回顾,在内容的范围以及正确性上可能...作为本系列博客的开篇,先对信息检索的相关基础知识做个简单的总结 1.基本定义 信息检索的定...
  • 信息检索的评价指标

    万次阅读 2016-03-03 17:13:58
    信息检索评价是对信息检索系统性能(主要满足用户信息需求的能力)进行评估的活动。通过评估可以评价不同技术的优劣,不同因素对系统的影响,从而促进本领域研究水平的不断提高。信息检索系统的目标是较少消耗情况下...
  • 信息检索技术应用的新方向:普及检索和知识检索[2001-09-26]施水才 信息检索和全文检索的发展 如何快速、准确、全面地找到信息,在知识经济时代特别重要。近年来,信息检索技术取得了飞速的发展,特别值得一提的是...
  • 基于领域本体的语义信息检索研究

    千次阅读 2009-01-03 16:56:00
    基于领域本体的语义信息检索研究(马文虎 南京理工大学信息管理系) 目 录引言... 11信息检索与本体概述... 11.1 信息检索... 11.1.1 信息检索的概念... 11.1.2 信息检索模型... 21.1.3 信息检索技术... 21.1.4 ...
  • 信息检索名词解释

    千次阅读 2008-10-19 21:14:00
    ·布尔查询(Boolean query)由词项的布尔组合构成的查询. 如"information and retrieval", "vision orsight", "Clinton and (not Gore)".·分类(Classificaiton)确定给定文件所属相应范畴的过程....

空空如也

1 2 3 4 5 ... 20
收藏数 430,977
精华内容 172,390
关键字:

信息检索