《根据内容检索》PPT课件.ppt

第第9 9章章 根据内容检索根据内容检索 本章目标本章目标 n n 介绍根据内容检索的基本概念。介绍根据内容检索的基本概念。 n n 介绍检索系统的评介方法。介绍检索系统的评介方法。 n n 讨论针对文本数据的根据内容检索问题，讨论针对文本数据的根据内容检索问题， 集中讨论向量空间表示，以及文档中匹配集中讨论向量空间表示，以及文档中匹配 查询的算法、隐含语义索引和文档分类。查询的算法、隐含语义索引和文档分类。 n n 介绍用于对个人偏好建模的自动推荐系统介绍用于对个人偏好建模的自动推荐系统 。 第第9 9章章 根据内容检索根据内容检索 本章目标本章目标 n n 讨论图像检索算法中表示和检索问题。讨论图像检索算法中表示和检索问题。 n n 介绍匹配时间序列和序列的基本概念。介绍匹配时间序列和序列的基本概念。 9.1 9.1 简介简介 n n 传统的数据库查询定义为：查询是一种返回传统的数据库查询定义为：查询是一种返回 精确匹配指定要求的记录集合精确匹配指定要求的记录集合( (或表项集合或表项集合) )的的 操作。例如，查询操作。例如，查询“ “level=MANAGER level=MANAGER AND age30),(30), 所以所以TRECTREC裁判员把他们的裁判范围限裁判员把他们的裁判范围限 制在所有检索系统所返回文档的前制在所有检索系统所返回文档的前 100100篇文档的联合，并假定这个集合篇文档的联合，并假定这个集合 通常已经包含了几乎所有的相关文档通常已经包含了几乎所有的相关文档 。因此，每个裁判者仅需作出几千个。因此，每个裁判者仅需作出几千个 相关性判断，而不是几千万个。相关性判断，而不是几千万个。 9.3 9.3 文本检索文本检索 n n 传统上，一直把对文本信息的检索称为信传统上，一直把对文本信息的检索称为信 息检索息检索(IR)(IR)，互联网搜索引擎的出现使其，互联网搜索引擎的出现使其 成为一个备受关注的课题。成为一个备受关注的课题。 n n 文本由两个基本单位组成，即文档和词条文本由两个基本单位组成，即文档和词条 。 n n 按照按照IRIR惯例，文本查询是由词条集合指定惯例，文本查询是由词条集合指定 的。的。 一、文本的表示一、文本的表示 n n 大多数关于文本检索的研究集中在寻找支大多数关于文本检索的研究集中在寻找支 持如下两个特征的通用表示持如下两个特征的通用表示 : : 1.1.尽可能保留数据语义内容的能力；尽可能保留数据语义内容的能力； 2.2.可以高效的计算查询和文档间的距离。可以高效的计算查询和文档间的距离。 目前的目前的IRIR系统通常依赖于简单的词条匹配和系统通常依赖于简单的词条匹配和 计数技术，即通过词条出现次数向量隐含计数技术，即通过词条出现次数向量隐含 并近似地捕捉了文档语义。并近似地捕捉了文档语义。 n n 假定已经预先定义了要检索的一系列词条假定已经预先定义了要检索的一系列词条 t tj j ,1,1j jT T，然后把每一篇文档然后把每一篇文档DD i i ，1i1iN N 表示为词条向量：表示为词条向量： DD i i =( (d d i i1 1, ,d d i i2,2, d d iTiT ) ) 其中其中d d ij ij 表示第表示第j j个词条在第个词条在第i i篇文档中出现的某篇文档中出现的某 种信息，各个种信息，各个d d ij ij 被称为词条权。被称为词条权。 n n 在布尔表示中，在布尔表示中， d d ij ij 取取1 1或或0 0。在向量空间表。在向量空间表 示中，可以是某个实数值的数字。示中，可以是某个实数值的数字。 n n 下面考虑一个涉及下面考虑一个涉及1010篇文档和篇文档和6 6个词条的简个词条的简 单例子。六个词条是：单例子。六个词条是： t1=t1=数据库，数据库，t2=SQLt2=SQL，t3=t3=索引，索引，t4=t4=回归回归 t5=t5=似然，似然，t6=t6=线性的。线性的。 表表9-29-2为为101066的文档的文档- -词条频率矩阵词条频率矩阵MM。 n n 文档间的距离尺度采用余弦距离：文档间的距离尺度采用余弦距离： n n 这是两个向量夹角的余弦这是两个向量夹角的余弦( (等价于把它们标等价于把它们标 准化为单位长度后的内积准化为单位长度后的内积) )，因此它反映了，因此它反映了 两个向量的词条分量的相对分布相似性。两个向量的词条分量的相对分布相似性。 该距离尺度在该距离尺度在IRIR试验中特别有效。同样地试验中特别有效。同样地 ，我们也可以使用其它距离尺度，如欧氏，我们也可以使用其它距离尺度，如欧氏 距离。距离。 n n 下图是表下图是表9-29-2中的文档中的文档- -词条频率矩阵的像词条频率矩阵的像 素形式距离矩阵。上图是欧氏距离矩阵，素形式距离矩阵。上图是欧氏距离矩阵， 下图是余弦距离矩阵。下图是余弦距离矩阵。 n n 较亮的方块表示两篇文档比较接近，较暗较亮的方块表示两篇文档比较接近，较暗 的地方表示不相近。的地方表示不相近。 n n 对于欧氏距离，白色对应两篇文档间的距对于欧氏距离，白色对应两篇文档间的距 离为离为0 0；黑色对应最大距离。；黑色对应最大距离。 n n 对于余弦距离，较亮的像素对应于较大的对于余弦距离，较亮的像素对应于较大的 余弦值余弦值( (较小的角度较小的角度) )；较暗的像素对应于较；较暗的像素对应于较 小的余弦值小的余弦值( (较大的角度较大的角度) )。 n n 在两种距离矩阵中都可以清楚的看出存在在两种距离矩阵中都可以清楚的看出存在 两个文档簇，一类是关于数据库的文档，两个文档簇，一类是关于数据库的文档， 另一类是关于回归的文档，图中的两个颜另一类是关于回归的文档，图中的两个颜 色较淡的方块区域。色较淡的方块区域。 n n 从图中可见，余弦距离更好的区分了两个从图中可见，余弦距离更好的区分了两个 组。组。 n n 在欧氏距离中，文档在欧氏距离中，文档3 3和文档和文档4(4(数据库簇中数据库簇中 ) )到文档到文档5(5(另一篇数据库文档另一篇数据库文档) )的距离比到的距离比到 文档文档6,86,8和和9(9(关于回归的文档关于回归的文档) )的距离还要的距离还要 远。导致这一现象的原因就是文档远。导致这一现象的原因就是文档3 3和和4(4(以以 及及6,86,8和和9)9)与文档与文档5 5相比更靠近原点。相比更靠近原点。 n n 余弦距离发挥了基于角度距离的优点，更余弦距离发挥了基于角度距离的优点，更 强调各个词条的相对分布，因此产生的区强调各个词条的相对分布，因此产生的区 分更加明显。分更加明显。 n n 上例的一个推广，对于具有上例的一个推广，对于具有N N篇文档的篇文档的T T个个 词条的集合，我们可以构造一个词条的集合，我们可以构造一个N NTT的矩的矩 阵。通常这个矩阵是非常稀疏的。比如上阵。通常这个矩阵是非常稀疏的。比如上 面提到的面提到的TRECTREC文档群大约仅文档群大约仅0.03%0.03%的单的单 元是非零的。元是非零的。 n n 在文本检索系统时，出于对词条在文本检索系统时，出于对词条- -文档矩阵文档矩阵 稀疏性的考虑，原始的文档稀疏性的考虑，原始的文档- -词条矩阵被表词条矩阵被表 示为一种倒排文件结构示为一种倒排文件结构( (而不是直接表示为而不是直接表示为 矩阵形式矩阵形式) )，也就是按照，也就是按照T T个词条来索引文个词条来索引文 件，每个词条件，每个词条t t j j 指向一个指向一个N N个数字的列表，个数字的列表， 这些数字描述了每篇文档中出现该词条的这些数字描述了每篇文档中出现该词条的 情况情况( (d d ij ij , ,j j固定固定) )。 二、匹配查询和文档二、匹配查询和文档 n n 也可以使用与文档相同的基于词条的表征也可以使用与文档相同的基于词条的表征 来表达查询。实际上，可以把查询本身当来表达查询。实际上，可以把查询本身当 作一篇文档来表示，只不过是通常查询仅作一篇文档来表示，只不过是通常查询仅 包含很少的词条。包含很少的词条。 n n 在向量空间中，可以把查询表示为一个权在向量空间中，可以把查询表示为一个权 向量。词条没有出现时权值为向量。词条没有出现时权值为0 0，词条在查，词条在查 询出现时，用户可以指定权值，以表示每询出现时，用户可以指定权值，以表示每 个词条的相对重要性个词条的相对重要性( (权值限定在权值限定在0 01 1之间之间 ) )。 n n 令令Q=(qQ=(q 1 1 , ,q,q T T ) )为查询权向量。最简单的为查询权向量。最简单的 形式，权值要么为形式，权值要么为1 1要么为要么为0 0。下面二值模。下面二值模 式的例子，考虑三个查询，每个都是由一式的例子，考虑三个查询，每个都是由一 个词条组成的，分别是个词条组成的，分别是“ “数据库数据库” ” ，“ “SQLSQL” ”， “ “回归回归” ”。根据前面例子，可以把这三个查询根据前面例子，可以把这三个查询 表达为三个向量表达为三个向量：(1,0,0,0,0,0)(1,0,0,0,0,0)、 (0,1,0,0,0,0)(0,1,0,0,0,0)和和(0,0,0,1,0,0)(0,0,0,1,0,0)。利用余。利用余 弦距离在表弦距离在表9-29-2所示的数据中匹配这三个查所示的数据中匹配这三个查 询，得到最相近的文档，分别是询，得到最相近的文档，分别是d d2 2、d d3 3和和 d d9 9。 n n 更一般的情况，是如何设置匹配查询中权更一般的情况，是如何设置匹配查询中权 值，以提高检索的性能。许多值，以提高检索的性能。许多IRIR文献有相文献有相 关的报导。关的报导。 n n 已经证明一种被称为已经证明一种被称为TF-IDFTF-IDF加权的特殊加加权的特殊加 权模式在实践中特别有效。权模式在实践中特别有效。TF(term TF(term frequency)frequency)代表词条频率，表代表词条频率，表9-29-2中的文中的文 档档- -词条示例矩阵就是以词条示例矩阵就是以TFTF的形式表示的。的形式表示的。 n n 然而，如果一个词条在文档集合中的很多然而，如果一个词条在文档集合中的很多 文档中频繁出现，那么利用文档中频繁出现，那么利用TFTF代表权进行代表权进行 检索的判断力就很小了，也就是它会提高检索的判断力就很小了，也就是它会提高 查全率但是查准率可能很差。文档频率倒查全率但是查准率可能很差。文档频率倒 数数-IDF(inverse-document-frequency)-IDF(inverse-document-frequency) 权可以提高判别力。权可以提高判别力。 n n IDFIDF定义为：定义为：log(log(N N/ /n n j j ) )，式中，式中N N为文档总为文档总 数，数，n n j j 为包含词条为包含词条j j的文档数量。的文档数量。 n n IDFIDF权偏向于仅在很少文档中出现的词条，权偏向于仅在很少文档中出现的词条， 也就是说它是有判别力的。采用对数形式也就是说它是有判别力的。采用对数形式 是使这个权对文档总数是使这个权对文档总数N N不特别敏感。不特别敏感。 n n TF-IDFTF-IDF权就是特定词条在特定文档中的权就是特定词条在特定文档中的TFTF 权和权和IDFIDF权的乘积。表权的乘积。表9-29-2中的文档矩阵所中的文档矩阵所 产生的产生的IDFIDF权是：权是： (0.105,0.693,0.511,0.693,0.357,0.6(0.105,0.693,0.511,0.693,0.357,0.6 93)93)。由此可得。由此可得TF-IDFTF-IDF文档文档- -词条矩阵词条矩阵( (即即 把表把表9-29-2中的中的TFTF权乘以对应的权乘以对应的IDFIDF权权) )，如，如 表表9-39-3所示。所示。 n n 在文档中匹配查询的经典方法是：在文档中匹配查询的经典方法是： 把查询表示为词条向量，把查询表示为词条向量，1 1表示词条出现在表示词条出现在 查询中，查询中，0 0表示不出现；表示不出现； 利用向量分量的利用向量分量的TF-IDFTF-IDF权把文档表示为词权把文档表示为词 条向量；条向量； 使用余弦距离尺度按照文档到查询的距离来使用余弦距离尺度按照文档到查询的距离来 排列