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

1、9.3 文本检索,三、隐含语义索引 上面所介绍的都是将文档表示为T维词条权向量的。但用户可能提出的查询中的词条不在用在索引文档的词条中。 例如，从词条相似性的角度来看，词条“数据挖掘”和“知识发现”设有什么直接的共同点。然而，从语义角度来看，这两个词条有很大的相同点。,因此，在提出一个包含其中之一的查询，那么应该考虑包含另一个的文档。解决方法是：预先创建一个把语义相关词条连接在一起的知识库(同义词典或本体集)。然而，这样的知识库存在固有的主观性，因它取决于从何种角度来把词条和语义内容联系起来。 隐含语义索引(latent semantic indexing)(LSI)一种可选的有趣又有价值的方

2、法。该方法不是仅使用词条出现信息，而是从文本中提取出隐藏的语义结构信息。,实际上，LSI采用T维词条空间中前k个主成分来近似原始的T维词条空间，使用NT的文档-词条来估计这个方向。 主成分方法的直观解释是，由原始词条的加权组合所构成的单个向量可以非常好的近似由大得多的向量集合所起的效果。于是可以把原来的NT大小的文档-词条矩阵简化为Nk的矩阵(kT)， 对于固定的查全率，和前面讨论的向量空间方法相比，LSI可以提高查准率。,对表9-2中的矩阵M计算奇异分解式(SVD)。,目标是，找一个分解式M=USVT。式中U是一个106的矩阵，它的每一行是相对特定文档的权向量，S是每个主成分方向特征值的66

3、对角阵， 66的矩阵VT的各列提供了数据的新共轭基，被称为主成分方向。 S矩阵的对角线元素是(协方差矩阵对应): 1, n=77.4,69.5,22.9,13.5,12.1,4.8 可见，前两个主成分捕捉了数据中的主要变化，和直觉一致。 当使用两个主成分时，那么二维表征所保留的变化比例0.925，信息丢失仅7.5%。,如果我们在新的二维主成分空间来表示文档，那么每篇文档的系数对应于U矩阵的前两列(两个主成分对应的特征向量，即新的文档权值)：,这两列可看作新的伪词条，其作用相当于原来6个词条的线性组合。 看一下前两个主成分方向可以得到的信息(新共轭基)： V1=(0.74,0.49,0.27,0

4、.28,0.18,0.19) V2=(-0.28,-0.24,-0.12,0.74,0.37,0.31) 这两个方向是原来6维词条空间中数据最分散(具有最大方差)的方向。每方向更突出前两个词条(查询,SQL)：实际上这是描述和数据库有关文档的方向。,第二方向突出了后三个词条回归、似然和线性，这是描述和回归有关文档的方向。图9-4以图形方式说明了这一点(将上面数据用图表示)。,当把文档投影到由前两个主成分方向所决定的平面量，两个不同组的文档分布在两个不同的方向上。注意文档2几乎落在文档1上，使其有点模糊。文档5和文档10的词条向量最大，因此离原最远。 从图可看出，文档间的角度差异显然是相似性的一

5、个有用指标，因为回归和数据库文档在平面上是围绕两个不同的角度聚成簇的。 主成分方法的应用例子： 考虑一个新的文档D1，词条“查询”在该文档,中出现50次，另一个文档D2，包含词条“SQL”50次，两且两篇文档都不包含其他的词条。如果直接使用关键字表示，这两个文档不会被认为是相似的，因为它们没有包含相同的词条。 然而，如果使用两个主成分词条来表示这两篇文档，并把它们投影到这个空间中，那么正如图9-3所示，二者都被投影到“数据库”方向，尽管它们都 仅包含和数据库有关的三个词条中的一个。,从计算的角度来看，直接计算主成分向量(例如求解相关矩阵或协方差矩阵的特征值)通常要么是计算上不可行，要么是数值上

6、不稳定。实践中，可以使用特别适合高维稀疏矩阵的SVD技术来估计PCA向量。,四、文档和文本分类 上面的讨论可以看出使用词条向量来表示文档为文档分类提供了一种自然框架。 有了这一框架对于预先有标签的文档我们可以使用有指导分类技术，对于没有标签的文档我们可以使用无指导学习(聚类)框架。 典型词条向量的维数都是非常高的，基于这一事实，高维空间中的准确性和高效性通常是选择分类器的首要标准。,对于文档表示来说，像一阶贝叶斯分类器这样的分类模型或者是加权线性组合可工作得很好。 在文档分类这一领域还有很多有趣的问题可以探讨，例如认为每篇文档属于多个主题(类)而不是仅属于某个类是有意义的。因此在分类时不再限于

7、各个类是相互排斥的这一通用框架。一种简单的方法是为每个类分别训练一个二值分类器，此方法仅当类别总数较少时是可行的。,9.4 对个人偏好建模,一、相关性反馈 文本检索系统比其他数据挖掘算法更具有交互性。特别是，提出特定查询Q的用户可能愿意反复使用算法进行一系列不同的检索尝试，并通过为返回的文档标记出相关与否来给算法提供用户反馈。 在这方面，Rocchio算法应用的特别广泛。算法的基本思想：,从根本上讲相关性是以用户为中心的，也就是，如果用户可以(理论上)看到所有的文档，那么原则上他可以把所有文档分成两个集合，相关的R和不相关的NR。如果给定了这两个集合，那么可以证明最佳查询(利用向量模型)为：

8、其中D代表文档的词条向量表示，它的标签(用户作出的)是已知的。,在实际应用中，一般一个用户不会把数据库中所有文档都标上分类标签。相反，用户是从一个特定查询Qcurrent开始的，可以把这个查询看作是相对Qoptimal次优的。算法使用这个初始查询返回文档的一个较小子集，然后用户把该子集的文档标记为相关R和不相关NR。Rocchio算法按下面的方式来提炼查询：,该算法使查询朝着相关文档的均值向量靠近，并远离不相关文档的均值向量。参数、和是正的常数(启发式选取)，它们控制着新查询对最近标记文档的敏感性(相对于当前查询向量Qcurrent)。 不断重复这个过程，把新的查询Qnew与文档集合进行匹配，

9、然后让用户再一次标记文档。 原则上讲，如果每一次迭代所作的标签是一致的，那么Qnew会逐步逼近Qoptimal。,实验证据表明，利用用户反馈确实提高了查准率-查全率性能。然而，在实际应用时还有一些细节问题需要确定，比如显示给读者的文档数量；使用的相关文档和非相关文档的相对数量；选取非相关文档的方法等等。 二、自动推荐系统,9.5 图像检索,随着图像和视频数据集合在的不断增加，人们对图像检索的兴趣也日益浓厚。 手工对图像进行注释具有浪费时间、主观性强等缺点，而且可能因为注释者的看法不同而丢失图像的某些特征。 一幅图像可能要使用一千个词来描述,但是到底使用哪一千个单词却不是简单的问题.,因此，开发

10、高效而又准确的算法来根据内容对图像数据库进行查询是很有必要的。比如，检索系统允许用户提交这样的查询“找出和这幅图像最相近的K幅图像”或者“找出和这组图像属性最匹配的K幅图像”。 一、图像理解 图像数据查询是非常困难的任务。从某种意义上来说寻找彼此相似的图像等价于求解图像理解问题，也就是从图像数据中抽取语义信息。,在这方面人类非常出色，然而，关于模式识别和计算机视觉的几十年研究已经表明，要用计算机算法来“复制”人类在视觉理解和识别方面的能力是极端困难的。 举例来说，婴儿可以很快学会要任何背景下辨别各种动物，比如各种大小、颜色、体型的狗，而这种完全无约束的识别问题超出了目前任何视觉算法的能力。因此

11、，目前的大多数图像检索算法还仅依赖于相当低级的可视提示。,二、图像表示 为了便于检索，可以把原始的像素数据抽象为特征表示，通常是以类似色彩和纹理这样的原语来表示图像特征。 类似于文本表达方式，仍然采用数据矩阵格式来表示图像，每一行代表一幅特定的图像；每一列代表一个图像特征。这样的特征表示通常比直接的象素测量值对缩放和平移变化更有效。,原始的像素数据被简化为标准的Np数据矩阵，在这个矩阵中每一幅图像被表示为特征空间中的一个p维向量。 通过计算图像局部化子区域的特征可以粗略的引入空间信息。例如，我们可以计算一幅10241024像素图像的每个3232子区域的颜色信息。这样便可以在图像查询中使用粗略的

12、空间约束，比如“寻找中央主要为红色，四周为蓝色的图像”。,应用于图像的根据内容检索系统的一个著名商业实例是IBM开发的根据图像内容查询(QBIC)系统。该系统允许用户交互式的查询图像和视频数据，查询的依据可以是图像实例、用户输入的草图、颜色和纹理模式、对象属性等等。允许对景物、对象以及视频帧序列或者是这些的任意组合进行查询。,QBIC系统使用了多种特征以及多种和距离有关的尺度用于检索： 相对整幅图像进行空间平均的三维颜色特征向量，采用欧氏距离尺度。 K-维颜色直方图，直方图的柱位可以使用像使用K-平均这样的基于划分聚类算法来选取。采用马氏(Mahalanobis)距离尺度来表征颜色相关性。 衡

13、量粒度/比例、方向性和对比度特征的三维纹理向量。采用加权的欧氏距离尺度来计算距离，权的缺省值为各个特征方差的倒数。,20-维的对象形状特征，比如区域、圆度、离心率、轴方向、各种矩等等。采用欧氏距离来计算相似性。 三、图像查询 和文本数据的情况相同，用于抽象表示图像的方法决定了支持何种类型的查询和检索操作。特征表示提供了一种表示查询的语言。有两种形式来表示查询。 一种方法：通过样例查询，在这种样例中，我们既可以为要寻找的目标提供一个图像样例，也可以勾画出感兴趣图像的形状。,接下来便计算样例图像的特征向量，然后再把计算出的查询特征向量和数据库中预先计算出的特征向量进行匹配。 另一种方法：直接以特征

14、表征表达查询，比如“寻找这样的图像，50%的区域为红色，并且包含具有特定方向和粒度特征的纹理”。 表示图像和查询的特征向量形式与用于文本检索的向量空间表示非常相似。一个主要差异是图像特征通常是一个实数，而词条向量中的词条分量通常是某种形式的加权计数，代表了这个词条在文档中出现的频繁程度。,不过，这两种问题都是根据内容检索的问题，这一共同特征决定了用于文本检索的很多技术也适应于图像检索应用。,9.6 时间序列和序列检索,在时间序列和序列数据集合中高效而又准确的定位有意义模式的问题对于很多应用都有重要意义，比如复杂系统的诊断和监控、生物医学数据分析以及对科研和商业时间序列的探索性数据分析。这样例子

15、包括： 找出这样的顾客：他们相对时间的消费模式和给定的消费特征相似； 在复杂的实时监控和故障诊断系统中，搜索出与当前异常传感器信号相似的以前实例； 在蛋白质序列中进行有噪声子串的匹配。,和二维图像数据相比，可以把序列数据看作是一维的。时间序列数据是相对时间测量出来的一系列观察结果，因此可以用时间变量t来索引观察值。 序列数据的概念比时间序列数据的概念更广，因为序列数据不一定是时间的函数。例如，在计算生物学中，蛋白质是以其在蛋白质序列中的顺序位置来索引的。,一、时间序列数据的全局模型 传统的时间序列建模技术(比如统计方法)主要是建立在全局线性模型基础上的，典型的例子是Box-Jenkins自回归

16、模型族，该方法把当前值y(t)模拟成过去值y(t-k)的加权线性组合，再加上一个额外的噪声项： 式中i是加权系数，e(t)是时间t的噪声(通常被假定为均值为零的高斯函数)。,Box-Jenkins方法的一个重要贡献是，如果在时间序列中存在可识别的系统性非平稳分量(比如某种趋势)，那么很多情况下可以把这个不平稳分量删除使这个时间序列变成平稳的形式。例如，像国内生产总值和道琼斯指数这样的经济指标中包含着固有的上升趋势(总体而言)，通常要在建模前将这种趋势删除。 对于非平稳性比较复杂的情况，另一种有用方法是假定这个信号是相对时间局部平稳的。,非线性的全局模型对上面公式进行了推广，比如可以允许y(t)

17、非线性地依赖过去值： 其中g(.)是非线性的。 从数据挖掘的角度来看，如果我们假定这样的全局模型充分地描述了潜在的时间序列，那么我们就可以使用模型参数(比如上面的各个权)作为表示数据的基础，而不使用原始数据本身。,通过把时间序列表示为参数向量，把序列问题转化为本章前面所介绍的文本和图像的方法，便可以在参数向量空间中定义相似性尺度、在这个空间中定义根据内容检索的查询。 二、时间序列的结构和形状 考虑一个实数值时间序列的子序列Q=q(t),q(t+m)，和一个长得多的归档时间序列X=x(t),x(T)，前者称为查询序列。,我们的目标是在X中找到和Q最相似的一个子序列。 现实情况下，X可能是由许多单

18、个的时间序列组成的，但是为了简单，我们假定它们已经被合成一条长的序列。并且假定X和Q都是使用相同采用时间间隔测量的。 上一节所讲的一般方法仅描述一个时间序列的全局特征，根本没有提供对局部形状的描述，比如峰值等。通常，全局模型平均了这些局部的结构特征。然而，对于很多时间序列来说，用结构特征来描述它们会更自然。,两种查询方法： 第一种：在整个X数据中序列化在扫描查询Q，顺着X每次把查询Q移动一个时间点，同时计算出每个时间点的距离尺度。该方法的主要特点是，开销大。其焦点集中在低层次的数据采样点，而不是高层次的结构特征，比如峰值、高原、走势和波谷等。直接计算欧氏距离也对查询Q和数据X中的微小岐变异常敏感。,第二种：先局部化地估计查询Q和归档X的基于形状特征，然后在较高层次上进行匹配。其特点是，具有计算优势，因为