文本分析与检索

主要内容：

1、文本表示与特征提取；

2、隐语义分析LSA和Latent Dirichlet Allocation(LDA)

3、检索模型：Boolean模型、向量模型、概率模型

 

1、文本表示与特征提取

• 文本中抽取出的特征词进行量化来表示文本信息；

利用分词工具：极易中文分词：je-analysis-1.5.3,庖丁分词：paoding-analyzer.jar, IKAnalyzer3.0, imdict-chinese-analyzer, ictclas4j

• 目前通常采用向量空间模型来描述文本向量；
• 文本特征选择：找出对文本特征类别最具代表性的文本特征
• 不能直接用分词算法和词频统计方法得到的特征项来表示文本向量中的各个维（特征项太多）
• 特征项必须具备一定的特性：能够确实标识文本内容；具有将目标文本与其他文本相区分的能力；个数不能太多；特征项分离要比较容易（字，词，短语）
• 基于统计的特征提取方法（构造评估函数）
• lTF-IDF法：以特征词在文档d中出现的次数与包含该特征词的文档数之比作为该词的权重

         

• 词频方法（Word Frequency）
• 文档频次方法（Document Frequency）
• 互信息（Mutual Information）

         

• 期望交叉熵（Expected Cross Entropy）

        

• 信息增益方法（Information Gain）

       

•  统计量方法：度量特征w和主题类C之间的独立性

        

        

2、特征变换——隐语义分析（LSA）

• Latent Semantic Analysis-LDA
• Latent Semantic Indexing-LSI
• 问题提出：一词多义和同义词
• 中心思想：用概念（或特征）代替词
• 基本方法 : 利用矩阵理论中的“奇异值分解（singular value decomposition,SVD）”技术，将词频矩阵转化为奇异矩阵（K×K）

输入：term-by-document matrix

输出：

U: concept-by-term matrix

V: concept-by-document matrix

S: elements assign weights to concepts

• LSA过程：

1.建立词频矩阵，frequency matrix

2.计算frequency matrix的奇异值分解。分解frequency matrix成3个矩阵U，S，V。U和V是正交矩阵（UTU=I），S是奇异值的对角矩阵（K×K）

3.对于每一个文档 d，用排除了SVD中消除后的词的新的向量替换原有的向量

4.用转换后的文档索引和相似度计算

• SVD
• unique mathematical decomposition of a matrix into the product of three matrices:

               two with orthonormal columns

               one with singular values on the diagonal

• tool for dimension reduction
• similarity measure based on co-occurrence
• finds optimal projection into low-dimensional space

• 不足：

概率模型不够完备：在document层面上没有提供合适的概率模型，使得pLSA并不是完备的生成式模型，而必须在确定document i的情况下才能对模型进行随机抽样

(1) the number of parameters in the model grows linearly with the size of the corpus, which leads to serious problems with overfitting.

(2) it is not clear how to assign probability to a document outside of the training set.

• Latent Dirichlet Allocation(LDA)

用一组词及其词频分布来刻画主题，并认为文本片段是从一个概率模型中生成的。

LDA assumes the following generative process for each document w in a corpus D

     1. Choose N ~ Poisson(ξ) (N:文档长度，泊松分布).

     2. Choose θ ~ Dirichlet(α) (θ:k维向量，狄利克雷分布；k:Topic 数量).

     3. For each of the N words wn :

              (a) Choose a topic zn ~ Multinomial(θ). (多项式分布)

              (b) Choose a word wn from p(wn|zn ,β), a multinomial probability conditioned on the topic zn.

                        (β是一个k*V的矩阵, V是词的数量，β (i,j)表示词j在Topic i中出现的概率,矩阵的一行对应一个Topic)

参数估计方法（α, β）

• EM (原文作者方法)；
• Gibbs Sampling.(求解过程)

3、检索模型（Retrieval Model）

信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。 本质上是对相关度建模。

IR模型分类：

• 检索模型的基本概念：

标引项(Index Term)

− 文档表示成多个Term的集合

− 通常用词来表示，但是也可以用其他语言单位来表示

− 关键词(key words) 可以看成Term的一种

标引项的权重(Weight)

− 不同标引项作用是不同的

− 通过权重加以区分

检索模型的定义

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

文档是文献在系统中的存储形式，主要由词构成。词包括关键词或标引词；

查询反映了用户表达的信息需求；

匹配函数把经过处理的文献表示和查询表示同时放在系统中进行匹配，通过设置不同的匹配函数得到不同的输出结果；

4、Boolean模型

•基于集合论的简单模型

•检索词被布尔表达式所指定

         –精确的语义

        –整齐的形式

•Terms在文档里只有两种状态

      – 出现

      – 不出现

      因此, wij ∈ {0,1}

•检索回的文档必然完全满足检索要求:

      —所有与检索词有逻辑关联或其它限制的文档

      —精确: nothing less, nothing more

           有四种运算操作 (就像在代数运算上一样):

1. A: 取回集合A

    我想要包含term library的文档

2. A AND B: 取回集合A 和 B

    交集运算用 表示

    取回同时包含library and digital 的文档

3. A OR B取回集合A 或者 B

    并集运算用表示

    我想要至少包含library 和 digital 之一文档

4.A NOT B: 取回集合A 但不包含集合 B

     否运算 用A – B表示

     取回library但不包含 digital 的文档

• 布尔模型的优点

– 简单而整齐，为现代许多商业系统所用

– 自我保护功能，降低用户对搜索系统的期望，使自己不在责任方，检索结果不好的原因在于用户构造查询不好

•布尔模型的缺点

–检索是基于二值运算确定的，没有部分匹配的概念

–检索回的文档之间没有排序

–检索词必须被翻译成布尔表达式，这让很多用户感觉到不方便

–由用户形式化的布尔检索词大多数情况下太简单了

–因此，用布尔模型检索回的结果不是太多就是太少

•布尔模型目前仍然是商业文档数据库的主流模型，并为一些新的领域提供了一个好的起点

5、基于向量的模型

• 动机：

                •用二值的权重太受限制

                •向量模型通过分派非二值权重给查询和文档中的索引项来实现检索目标

                • 这些权重用于计算系统中的每个文档与用户的查询请求的相似程度，向量模型通过对文档按照相似程度降序排列的方式，来实现文档与查询项的部分匹配

                •文档排列有序可使检索词与文档之间的匹配更好，返回的结果更合理

• 原理：

               •若干独立的词被选作索引项（terms）

              •索引项代表了一个应用中的重要词项

               例如计算机科学图书馆中的索引项应该是哪些？

• Define:

                –wij > 0 当ki 属于dj时

               –wiq >= 0 与(ki,q)关联

               –vec(dj) = (w1j, w2j, ..., wtj)

               –vec(q) = (w1q, w2q, ..., wtq)

               –这些terms之间是不相关的（Bag of Words，实际上它们是相关的），他们形成了一个向量空间（vector space）

               

• 相似性度量

        向量模型通过vec(dj)和vec(q)的相 关度来评价文档dj和查询q的相关度。这种关系可以用定量表示，一般使用两个向量之间的夹角余弦值来计算

       

           

         --N 文献数

        − ni 文献集合中包含标引词 ki的词频

        − freqi,j 某篇文献dj中包含标引词ki的词频(描述能力)

        −fi,j 词频的规范化值（局部权值,描述能力）

            −

       −idfi 标引词ki的逆词频值 （全局权值,区分能力 ）

               

• 文档向量权值tf/idf

          

• 查询向量的构造：索引词权值WI,q

          

• 索引词权值wij= tf*idf

• 向量模型的优点：

•术语权重的算法提高了检索的性能

•部分匹配的策略使得检索的结果文档集更接近用户的检索需求

•可以根据结果文档对于查询串的相关度通过Cosine Ranking等公式对结果文档进行排序

• 向量模型的缺点：

•索引项被假设为彼此之间相互独立的，然而在实际中，考虑索引项之间的相关性也许是个缺陷

• 由于许多索引项之间的相关性具有局限性，不加区别地将其应用到所有文档中，会影响检索系统的整体性能

• 向量模型的改进

• 标引词位置加权

              − 结构位置

                      - 标题、摘要、关键词、正文、结论和超连接

              − 重点句位置

                     - 综上所述、结束语、主要在于

• 辅助主题词表

             − 将带修饰和限制作用的词——形容词和副词做成辅助主题词表，用以扩展用户查询

             − 将检索关键词和字典库中的同义词和修饰词结合起来，形成新的查询，提高了检索的效率

• 个性化协同检索设计

             − 将每次的检索结果、用户兴趣等建立个性化信息库，并进行信息反馈，定期刷新，不断充实

6、概率模型

•概率论模型，亦称为二值独立检索模型

−1976年由Roberston和Sparck Jones提出的经典概率模型。它企图在概率的框架下解决IR的问题

−给定一个用户查询，存在一个文档集合，该集合只包括与查询完全相关的文档而不包括其他不相关的文档，称该集合为理想结果集合

•如何描述这个理想结果集合？

−即：该理想结果集合具有什么样的属性？

−基于相关反馈的原理，需要进行一个逐步求精的过程

•基本假设

−给定一个查询q和文档集中一个文档dj，概率模型试图找出用户对其感兴趣的概率

•模型假设这个概率只是依赖于查询和文档的表示，进而模型假设文档集中存在一个子集，它使得总体相关概率在集合中的文档被认为是与查询相关的，不在集合中的则被认为是不相关的

•贝叶斯定理

•词条的独立假设

   P(AB)= P(A) P(B) 当且仅当 A与B相互独立

   对一篇文档而言，若文档中的各个索引词相互独立，则有

   P(dj)=P(k1)…P(kt)

• 定义

•设索引词的权重为二值的，即：

•R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj, q)可以定义为：

•根据贝叶斯定理有

•假设标引词独立，则

•这是概率模型中排序计算的主要表达式

•取对数，在相同背景下，忽略对所有因子保持恒定不变的因子，则有

• 如何计算上式中的 和 呢 ？

• 简单假设作为最初的猜测

− 1) 对所有的索引词ki是恒定不变的，通常取为0.5，即

       −

− 2) 不相关文档中的索引词ki的分布可以通过文档集中索引词的分布来估计，即

       −

       − 其中，ni表示包含索引词ki的文档数， N表示集合中的文档总数

• 初始值确定后，根据与查询q相关的大小进行初步排序，取前若干个文档作为相关查询集合

• 之后通过如下方法进行改进(即开始递归计算)

              用V表示概率模型初步检出并经过排序的文档子集

                       − Vi表示V中包含索引词ki的文档数

             改进 和 的过程如下：

                  − 1) 用已经检出的文档中索引词ki的分布来估计

                           − 2) 假定所有未检出的文档都是不相关的来估计

                    即 

• 如此递归重复这一过程，得到理想结果集合

                  对较小的V和Vi上述计算会出现问题，如V=1和Vi=0，可做一些改进：

                           

                            调整因子也可以为ni/N， 即

                          

• 概率模型的算法步骤

− 起始时（只有查询需求，没有检索结果）假设：
（1）对所有索引项概率是常数；
（2）索引项在非相关文档集中的分布近似等于在所有文档集中的分布，即：

• 令V是初始检索结果的子集，有r个，取自检索结果集中前r个文档，这些检索结果是经过概率模型排好顺序的
• 令Vi是V中所有包含索引项ki的那些文档，显然Vi是V的子集；为简单起见，直接用V和Vi表示这些集合中的元素数量
• 修改对概率和的计算方法

• 为保证数值计算的稳定性，常用下列公式计算相似度：

•优点

        •理论上讲，文档按照其与目标集合的相关概率降序排列

•缺点

        •需要最初将文档分为相关和不相关的集合

        •所有权重都是二值的，模型中仍然假设索引项之间是相互独立的