第9章根据内容检索

第9章根据内容检索本章目标介绍根据内容检索的基本概念。介绍检索系统的评介方法。讨论针对文本数据的根据内容检索问题，集中讨论向量空间表示，以及文档中匹配查询的算法、隐含语义索引和文档分类。介绍用于对个人偏好建模的自动推荐系统。第9章根据内容检索本章目标讨论图像检索算法中表示和检索问题。介绍匹配时间序列和序列的基本概念。9.1简介传统的数据库查询定义为：查询是一种返回精确匹配指定要求的记录集合(或表项集合)的操作。例如，查询“[level=MANAGER]AND[age30]”，返回的结果是有具有重要职务的年轻雇员的列表。但在数据分析时，所感兴趣的是更一般的但不很精确的查询。例如，假设已知一个患者的人口统计学信息(比如年龄性别等等)、血液和其他常规检查的结果，以及生物医学方面的时间序列、X-光和图像。为了辅助对这个患者进行诊断，医生希望了解医院数据库中是否包含类似的患者，如果有类似的患者，那么他们的诊断、治疗方法和最终结果如何？这个问题的难点在于如何根据不同的数据类型(多元变量、时间序列和图像数据)来判断各个患者间的相似性。这类问题采用精确匹配是行不通的，因为数据库中不可能存在各项指标完全匹配的患者。因此，需要解决的是在数据库找出和指定查询或指定对象最相似的k个对象的各种技术问题。可以把这种形式的检索看是交互式的数据挖掘，因为用户直接参与了探索数据集的过程—指定查询并解决匹配过程得到的结果。如果数据集是根据内容批注的，那么检索问题就简化为标准的数据库索引问题，如果数据库没有被预先索引，我们仅有要寻找目标Q(查询模式)的一个实例，根据这个查询模式Q，我们要推论出数据集中哪些其他对象和它相近。这种检索方法被称为根据内容检索(retrievalbycontent)，它的最著名应用是在文本中检索。在文本检索中，查询模式Q通常是很短的(查询词汇列表)，然后在很大的文档集合匹配这个模式。这类问题由三个基本部分组成：1.如何定义对象间的相似尺度；2.如何实现高计算效率的搜索算法(对于给定的相似尺度)；3.如何在检索过程中融入用户的反馈并进行交互。本章主要讨论第一和第三个问题，第二个问题通常是一种索引问题(一个好的索引可以极大提高效率)。在下面的分析中，我们使用“相似”这个词，又使用“距离”这个词。对应的是相似尺度最大化和距离尺度最小化，其他章节的相似度和相异度。根据内容检索需要解决的几个问题：1.如何客观地评估特定检索算法的性能。2.如何决定用以计算相似尺度的表示。例如，通常用颜色、纹理和相似特征来地、表示图像；用单词的出现次数来表示文本。9.2检索系统的评价一、评价检索性能的困难之处在分类和回归中，总能以一种客观的方式来评判模型的性能。然而，对于根据内容检索来说，评价一个特定算法或技术的性能要复杂和棘手的多。主要的难点是检索系统的最终性能尺度是由检索出的信息对用户的实用性来决定的。检索是一种以人为中心的交互过程，这给评价检索性能带来了很大困难。首先我们假定相对一个特定的查询，可以把对象标记为相关或不相关。换句话来说，对于任一个查询Q，我们假定存在一个二值分类标签的集合，该集合对应数据中的所有对象，指出哪个对象是相关的，哪个是不相关的。最后我们假定已经以某种方式为每个对象附加标签(假定是以一种比较客观并与人类判相一致的方式)。基于这些假定，就可以把检索问题看作一种特殊形式的分类问题—类标签依赖于查询Q，也就是，“对于查询Q相关还是不相关”，然后相对Q来估计数据库中对象的类标签。检索分类的特点：1.分类变量的定义是由用户掌握的(用户定义查询Q)，因此每次运行系统时都可能变化。2.主要目标不是分类出数据库的所有对象，而是返回与用户查询最相关的对象。二、查准率对查全率假定我们在一个独立的检验数据集上评价一个指定检索系统相对特定查询Q的性能。检验数据中的对象已经被预先分类为相对于查询Q是相关还是不相关。假定这个检验数据集没有被这个检索算法使用过，我们可以把检索算法想象为就是要对这个数据集中的对象作出分类(按照相对于查询Q的相关性)。如果这个算法是使用距离尺度(数据集中的每个对象相对于Q的距离)来排列对象集合的，那么这个算法通常具有一个阈值参数T。算法将返回KT个对象—和查询对象Q的距离小于T的KT个对象的有序列表。通过改变T来改变检索系统的性能。假定对于有N个对象的检索数据集合，检索系统返回了KT个可能相关的对象，那么可以用表9-1来归纳这个算法的性能。表9-1中，实验中已经标记出了各文档相关还是不相关(相对于查询Q)。列对应于真实情况，行对应于算法对文档的判断。TP，FP，FN，TN分别对应于真的正，假的为正，假的为负和真的为负，其中正负是指算法所给出的分类是否相关。理想的检索算法将产生FP=FN=0的对角矩阵。其中:N=TP+FP+TN+FN(对象总数)KT=TP+FP(返回对象的数量)TP+FN是相关对象的总数。查准率：TP/(TP+FP)(行)查全率：TP/(TP+FN)(列)存在着这样一个问题：当KT增大时(提高阈值将返回更多的对象分类为相关)，查全率上升(极限情况，可以返回所有对象，查全率为1)，然而查准率会下降。如果使用不同的阈值T来运行检索算法，那么会得到一系列(查全率，查准率)的点对。反过来使用这些点对描出这个特定检索算法(相对于查询Q、特定的数据集、以及数据标签)的查全率-查准率曲线，如图9-1所示。图9-1是三种假想查询算法的查全率-查准率曲线。由图可见，在大多数情况下，难以判断哪一种算法有绝对优势，因此不能完全根据查全率-查准率曲线来判定一个算法就比另一个算法更好。尽管如此，这些曲线对于在一定操作条件范围内评价检索算法的相对、绝对性能还是有价值的。三、查准率和查全率的实践应用查准率-查全率评价在文本检索中一直特别流行。文本检索会议(TREC)就是查准率-查全率评价试验的一个大型例子。在这项试验中使用几个G字节大小的文本文档数据集合，大约是由一百万个独立的文档(对象)组成的，平均每个文档有500个术语索引。主要问题是如何评价相关性，特别是如何决定相关文档总数以计算查全率。如果使用50个不同查询，那么就需要每个人工裁判员给出5千万个分类标签!由于TREC会议的参展系很多(30),所以TREC裁判员把他们的裁判范围限制在所有检索系统所返回文档的前100篇文档的联合，并假定这个集合通常已经包含了几乎所有的相关文档。因此，每个裁判者仅需作出几千个相关性判断，而不是几千万个。9.3文本检索传统上，一直把对文本信息的检索称为信息检索(IR)，互联网搜索引擎的出现使其成为一个备受关注的课题。文本由两个基本单位组成，即文档和词条。按照IR惯例，文本查询是由词条集合指定的。一、文本的表示大多数关于文本检索的研究集中在寻找支持如下两个特征的通用表示:1.尽可能保留数据语义内容的能力；2.可以高效的计算查询和文档间的距离。目前的IR系统通常依赖于简单的词条匹配和计数技术，即通过词条出现次数向量隐含并近似地捕捉了文档语义。假定已经预先定义了要检索的一系列词条tj,1≤j≤T，然后把每一篇文档Di，1≤i≤N表示为词条向量：Di=(di1,di2,…,diT)其中dij表示第j个词条在第i篇文档中出现的某种信息，各个dij被称为词条权。在布尔表示中，dij取1或0。在向量空间表示中，可以是某个实数值的数字。下面考虑一个涉及10篇文档和6个词条的简单例子。六个词条是：t1=数据库，t2=SQL，t3=索引，t4=回归t5=似然，t6=线性的。表9-2为10×6的文档-词条频率矩阵M。文档间的距离尺度采用余弦距离：这是两个向量夹角的余弦(等价于把它们标准化为单位长度后的内积)，因此它反映了两个向量的词条分量的相对分布相似性。该距离尺度在IR试验中特别有效。同样地，我们也可以使用其它距离尺度，如欧氏距离。TkTjkikTkjkikjicddddDDd121),(下图是表9-2中的文档-词条频率矩阵的像素形式距离矩阵。上图是欧氏距离矩阵，下图是余弦距离矩阵。较亮的方块表示两篇文档比较接近，较暗的地方表示不相近。对于欧氏距离，白色对应两篇文档间的距离为0；黑色对应最大距离。对于余弦距离，较亮的像素对应于较大的余弦值(较小的角度)；较暗的像素对应于较小的余弦值(较大的角度)。在两种距离矩阵中都可以清楚的看出存在两个文档簇，一类是关于数据库的文档，另一类是关于回归的文档，图中的两个颜色较淡的方块区域。从图中可见，余弦距离更好的区分了两个组。在欧氏距离中，文档3和文档4(数据库簇中)到文档5(另一篇数据库文档)的距离比到文档6,8和9(关于回归的文档)的距离还要远。导致这一现象的原因就是文档3和4(以及6,8和9)与文档5相比更靠近原点。余弦距离发挥了基于角度距离的优点，更强调各个词条的相对分布，因此产生的区分更加明显。上例的一个推广，对于具有N篇文档的T个词条的集合，我们可以构造一个N×T的矩阵。通常这个矩阵是非常稀疏的。比如上面提到的TREC文档群大约仅0.03%的单元是非零的。在文本检索系统时，出于对词条-文档矩阵稀疏性的考虑，原始的文档-词条矩阵被表示为一种倒排文件结构(而不是直接表示为矩阵形式)，也就是按照T个词条来索引文件，每个词条tj指向一个N个数字的列表，这些数字描述了每篇文档中出现该词条的情况(dij,j固定)。二、匹配查询和文档也可以使用与文档相同的基于词条的表征来表达查询。实际上，可以把查询本身当作一篇文档来表示，只不过是通常查询仅包含很少的词条。在向量空间中，可以把查询表示为一个权向量。词条没有出现时权值为0，词条在查询出现时，用户可以指定权值，以表示每个词条的相对重要性(权值限定在0～1之间)。令Q=(q1,…,qT)为查询权向量。最简单的形式，权值要么为1要么为0。下面二值模式的例子，考虑三个查询，每个都是由一个词条组成的，分别是“数据库”，“SQL”，“回归”。根据前面例子，可以把这三个查询表达为三个向量：(1,0,0,0,0,0)、(0,1,0,0,0,0)和(0,0,0,1,0,0)。利用余弦距离在表9-2所示的数据中匹配这三个查询，得到最相近的文档，分别是d2、d3和d9。更一般的情况，是如何设置匹配查询中权值，以提高检索的性能。许多IR文献有相关的报导。已经证明一种被称为TF-IDF加权的特殊加权模式在实践中特别有效。TF(termfrequency)代表词条频率，表9-2中的文档-词条示例矩阵就是以TF的形式表示的。然而，如果一个词条在文档集合中的很多文档中频繁出现，那么利用TF代表权进行检索的判断力就很小了，也就是它会提高查全率但是查准率可能很差。文档频率倒数-IDF(inverse-document-frequency)权可以提高判别力。IDF定义为：log(N/nj)，式中N为文档总数，nj为包含词条j的文档数量。IDF权偏向于仅在很少文档中出现的词条，也就是说它是有判别力的。采用对数形式是使这个权对文档总数N不特别敏感。TF-IDF权就是特定词条在特定文档中的TF权和IDF权的乘积。表9-2中的文档矩阵所产生的IDF权是：(0.105,0.693,0.511,0.693,0.357,0.693)。由此可得TF-IDF文档-词条矩阵(即把表9-2中的TF权乘以对应的IDF权)，如表9-3所示。在文档中匹配查询的经典方法是：●把查询表示为词条向量，1表示词条出现在查询中，0表示不出现；●利用向量分量的TF-IDF权把文档表示为词条向量；●使用余弦距离尺度按照文档到查询的距离来排列文档。表9-4显示了一个简单查询实例，比较了TF和TF-IDF方法。上表中查询包含的词条是“数据库”和“索引”，即Q=(1,0,1,0,0,0)；使用表9-2矩阵；采用余弦距离。如果使用TF矩阵，文档d5是最相近的；使用TF-IDF权，d2是最相近的。