9.3 文本检索
三、隐含语义索引
?上面所介绍的都是将文档表示为 T维词条权
向量的。但用户可能提出的查询中的词条
不在用在索引文档的词条中。
?例如，从词条相似性的角度来看，词条
“数据挖掘”和“知识发现”设有什么直
接的共同点。然而，从语义角度来看，这
两个词条有很大的相同点。
?因此，在提出一个包含其中之一的查询，那
么应该考虑包含另一个的文档。解决方法是：
预先创建一个把语义相关词条连接在一起的
知识库 (同义词典或本体集 )。然而，这样的
知识库存在固有的主观性，因它取决于从何
种角度来把词条和语义内容联系起来。
?隐含语义索引 (latent semantic
indexing)(LSI)— 一种可选的有趣又有价值的
方法。该方法不是仅使用词条出现信息，而
是从文本中提取出隐藏的语义结构信息。
?实际上,LSI采用 T维词条空间中前 k个主成
分来近似原始的 T维词条空间，使用 N× T的
文档 -词条来估计这个方向。
?主成分方法的直观解释是，由原始词条的加
权组合所构成的单个向量可以非常好的近似
由 大得多的向量集合所起的效果。于是可以
把原来的 N× T大小的文档 -词条矩阵简化为
N× k的矩阵 (k<<T),
?对于固定的查全率，和前面讨论的向量空间
方法相比,LSI可以提高查准率。
?对表 9-2中的矩阵 M计算奇异分解式 (SVD)。
?目标是，找一个分解式 M=USVT。式中 U是
一个 10× 6的矩阵，它的每一行是相对特定
文档的权向量,S是每个主成分方向特征值
的 6× 6对角阵,6× 6的矩阵 VT的各列提供
了数据的新共轭基，被称为主成分方向 。
?S矩阵的对角线元素是 (协方差矩阵对应 …),
λ1,…,λ n={77.4,69.5,22.9,13.5,12.1,4.8}
可见，前两个主成分捕捉了数据中的主要变
化，和直觉一致。
?当使用两个主成分时，那么二维表征所保
留的变化比例 0.925，信息丢失仅 7.5%。
925.0/)( 6 1 22221 ?? ? ?i i???
?如果我们在新的二维主成分空间来表示文
档，那么每篇文档的系数对应于 U矩阵的前
两列 (两个主成分对应的特征向量，即新的
文档权值 ),
?这两列可看作新的伪词条，其作用相当于
原来 6个词条的线性组合。
?看一下前两个主成分方向可以得到的信息
(新共轭基 ),
V1=(0.74,0.49,0.27,0.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的词
条向量最大，因此离原最远。
?从图可看出，文档间的角度差异显然是相
似性的一个有用指标，因为回归和数据库
文档在平面上是围绕两个不同的角度聚成
簇的。
?主成分方法的应用例子,
考虑一个新的文档 D1，词条“查询”在该
文档
?中出现 50次，另一个文档 D2，包含词条
,SQL”50次，两且两篇文档都不包含其他
的词条。如果直接使用关键字表示，这两
个文档不会被认为是相似的，因为它们没
有包含相同的词条。
?然而，如果使用两个主成分词条来表示这
两篇文档，并把它们投影到这个空间中，
那么正如图 9-3所示，二者都被投影到“数
据库”方向，尽管它们都 仅包含和数据库
有关的三个词条中的一个。
?从计算的角度来看，直接计算主成分向量
(例如求解相关矩阵或协方差矩阵的特征值 )
通常要么是计算上不可行，要么是数值上
不稳定。实践中，可以使用特别适合高维
稀疏矩阵的 SVD技术来估计 PCA向量。
四、文档和文本分类
?上面的讨论可以看出使用词条向量来表示
文档为文档分类提供了一种自然框架。
?有了这一框架对于预先有标签的文档我们
可以使用有指导分类技术，对于没有标签
的文档我们可以使用无指导学习 (聚类 )框架。
?典型词条向量的维数都是非常高的，基于
这一事实，高维空间中的准确性和高效性
通常是选择分类器的首要标准。
?对于文档表示来说，像一阶贝叶斯分类器
这样的分类模型或者是加权线性组合可工
作得很好。
?在文档分类这一领域还有很多有趣的问题
可以探讨，例如认为每篇文档属于多个主
题 (类 )而不是仅属于某个类是有意义的。因
此在分类时不再限于各个类是相互排斥的
这一通用框架。一种简单的方法是为每个
类分别训练一个二值分类器，此方法仅当
类别总数较少时是可行的。
9.4 对个人偏好建模
一,相关性反馈
?文本检索系统比其他数据挖掘算法更具有
交互性。特别是，提出特定查询 Q的用户可
能愿意反复使用算法进行一系列不同的检
索尝试，并通过为返回的文档标记出相关
与否来给算法提供用户反馈。
?在这方面,Rocchio算法应用的特别广泛。
算法的基本思想,
?从根本上讲相关性是以用户为中心的，也
就是，如果用户可以 (理论上 )看到所有的文
档，那么原则上他可以把所有文档分成两
个集合，相关的 R和不相关的 NR。如果给
定了这两个集合，那么可以证明最佳查询
(利用向量模型 )为,
?其中 D代表文档的词条向量表示，它的标签
(用户作出的 )是已知的。
??
??
??
NRDRD
o p t i m a l DNRDRQ
11
?在实际应用中，一般一个用户不会把数据
库中所有文档都标上分类标签。相反，用
户是从一个特定查询 Qcurrent开始的，可以把
这个查询看作是相对 Qoptimal次优的。算法使
用这个初始查询返回文档的一个较小子集，
然后用户把该子集的文档标记为相关 R’和不
相关 NR’。 Rocchio算法按下面的方式来提
炼查询,
??
??
???
''
''
NRDRD
c u r r e n tn e w DNRDRQQ
???
?该算法使查询朝着相关文档的均值向量靠
近，并远离不相关文档的均值向量。参数 α、
β和 γ是正的常数 (启发式选取 )，它们控制着
新查询对最近标记文档的敏感性 (相对于当
前查询向量 Qcurrent)。
?不断重复这个过程，把新的查询 Qnew与文
档集合进行匹配，然后让用户再一次标记
文档。
?原则上讲，如果每一次迭代所作的标签是
一致的，那么 Qnew会逐步逼近 Qoptimal。
?实验证据表明，利用用户反馈确实提高了
查准率 -查全率性能。然而，在实际应用时
还有一些细节问题需要确定，比如显示给
读者的文档数量；使用的相关文档和非相
关文档的相对数量；选取非相关文档的方
法等等。
二、自动推荐系统
9.5 图像检索
?随着图像和视频数据集合在的不断增加，
人们对图像检索的兴趣也日益浓厚。
?手工对图像进行注释具有浪费时间、主观
性强等缺点，而且可能因为注释者的看法
不同而丢失图像的某些特征。
?一幅图像可能要使用一千个词来描述,但是
到底使用哪一千个单词却不是简单的问题,
?因此，开发高效而又准确的算法来根据内
容对图像数据库进行查询是很有必要的。
比如，检索系统允许用户提交这样的查询
“找出和这幅图像最相近的 K幅图像”或者
“找出和这组图像属性最匹配的 K幅图像”。
一、图像理解
?图像数据查询是非常困难的任务。从某种
意义上来说寻找彼此相似的图像等价于求
解图像理解问题，也就是从图像数据中抽
取语义信息。
?在这方面人类非常出色，然而，关于模式
识别和计算机视觉的几十年研究已经表明，
要用计算机算法来“复制”人类在视觉理
解和识别方面的能力是极端困难的。
?举例来说，婴儿可以很快学会要任何背景
下辨别各种动物，比如各种大小、颜色、
体型的狗，而这种完全无约束的识别问题
超出了目前任何视觉算法的能力。因此，
目前的大多数图像检索算法还仅依赖于相
当低级的可视提示。
二、图像表示
?为了便于检索，可以把原始的像素数据抽
象为特征表示，通常是以类似色彩和纹理
这样的原语来表示图像特征。
?类似于文本表达方式，仍然采用数据矩阵
格式来表示图像，每一行代表一幅特定的
图像；每一列代表一个图像特征。这样的
特征表示通常比直接的象素测量值对缩放
和平移变化更有效。
?原始的像素数据被简化为标准的 N× p数据
矩阵，在这个矩阵中每一幅图像被表示为
特征空间中的一个 p维向量。
?通过计算图像局部化子区域的特征可以粗
略的引入空间信息。例如，我们可以计算
一幅 1024× 1024像素图像的每个 32× 32子
区域的颜色信息。这样便可以在图像查询
中使用粗略的空间约束，比如“寻找中央
主要为红色，四周为蓝色的图像”。
?应用于图像的根据内容检索系统的一个著
名商业实例是 IBM开发的 根据图像内容查询
(QBIC)系统。该系统允许用户交互式的查
询图像和视频数据，查询的依据可以是图
像实例、用户输入的草图、颜色和纹理模
式、对象属性等等。允许对景物、对象以
及视频帧序列或者是这些的任意组合进行
查询。
?QBIC系统使用了多种特征以及多种和距离
有关的尺度用于检索,
◇ 相对整幅图像进行空间平均的三维颜色特
征向量，采用欧氏距离尺度。
◇ K-维颜色直方图，直方图的柱位可以使用
像使用 K-平均这样的基于划分聚类算法来
选取。采用马氏 (Mahalanobis)距离尺度来
表征颜色相关性。
◇ 衡量粒度 /比例、方向性和对比度特征的三
维纹理向量。采用加权的欧氏距离尺度来
计算距离，权的缺省值为各个特征方差的
倒数。
◇ 20-维的对象形状特征，比如区域、圆度、
离心率、轴方向、各种矩等等。采用欧氏距
离来计算相似性。
三、图像查询
?和文本数据的情况相同，用于抽象表示图像
的方法决定了支持何种类型的查询和检索操
作。特征表示提供了一种表示查询的语言。
有两种形式来表示查询。
?一种方法：通过样例查询，在这种样例中，
我们既可以为要寻找的目标提供一个图像样
例，也可以勾画出感兴趣图像的形状。
接下来便计算样例图像的特征向量，然后再把
计算出的查询特征向量和数据库中预先计算
出的特征向量进行匹配。
?另一种方法：直接以特征表征表达查询，比
如, 寻找这样的图像,50%的区域为红色，
并且包含具有特定方向和粒度特征的纹理, 。
?表示图像和查询的特征向量形式与用于文本
检索的向量空间表示非常相似。一个主要差
异是图像特征通常是一个实数，而词条向量
中的词条分量通常是某种形式的加权计数，
代表了这个词条在文档中出现的频繁程度。
?不过，这两种问题都是根据内容检索的问题，
这一共同特征决定了用于文本检索的很多技
术也适应于图像检索应用。
9.6 时间序列和序列检索
?在时间序列和序列数据集合中高效而又准确
的定位有意义模式的问题对于很多应用都有
重要意义，比如复杂系统的诊断和监控、生
物医学数据分析以及对科研和商业时间序列
的探索性数据分析。这样例子包括,
◇找出这样的顾客：他们相对时间的消费模式
和给定的消费特征相似；
◇在复杂的实时监控和故障诊断系统中，搜索
出与当前异常传感器信号相似的以前实例；
◇在蛋白质序列中进行有噪声子串的匹配。
?和二维图像数据相比，可以把序列数据看作
是一维的。时间序列数据是相对时间测量出
来的一系列观察结果，因此可以用时间变量 t
来索引观察值。
?序列数据的概念比时间序列数据的概念更广，
因为序列数据不一定是时间的函数。例如，
在计算生物学中，蛋白质是以其在蛋白质序
列中的顺序位置来索引的。
一、时间序列数据的全局模型
?传统的时间序列建模技术 (比如统计方法 )主
要是建立在全局线性模型基础上的，典型的
例子是 Box-Jenkins自回归模型族，该方法
把当前值 y(t)模拟成过去值 y(t-k)的加权线性
组合，再加上一个额外的噪声项,
?式中 αi是加权系数,e(t)是时间 t的噪声 (通常
被假定为均值为零的高斯函数 )。
?
?
???
k
i
i teityty
1
)()()( ?
?Box-Jenkins方法的一个重要贡献是，如果
在时间序列中存在可识别的系统性非平稳分
量 (比如某种趋势 )，那么很多情况下可以把
这个不平稳分量删除使这个时间序列变成平
稳的形式。例如，像国内生产总值和道琼斯
指数这样的经济指标中包含着固有的上升趋
势 (总体而言 )，通常要在建模前将这种趋势
删除。
?对于非平稳性比较复杂的情况，另一种有用
方法是假定这个信号是相对时间局部平稳的。
?非线性的全局模型对上面公式进行了推广，
比如可以允许 y(t)非线性地依赖过去值,
其中 g(.)是非线性的。
?从数据挖掘的角度来看，如果我们假定这样
的全局模型充分地描述了潜在的时间序列，
那么我们就可以使用模型参数 (比如上面的
各个权 )作为表示数据的基础，而不使用原
始数据本身。
)()()(
1
teitygty
k
i
i ???
??
?
? ?? ?
?
?
?通过把时间序列表示为参数向量，把序列问
题转化为本章前面所介绍的文本和图像的方
法，便可以在参数向量空间中定义相似性尺
度、在这个空间中定义根据内容检索的查询。
二、时间序列的结构和形状
?考虑一个实数值时间序列的子序列
Q=[q(t),…q(t+m)],和一个长得多的归档时
间序列 X=[x(t),…,x(T)],前者称为查询序列。
?我们的目标是在 X中找到和 Q最相似的一个
子序列。
?现实情况下,X可能是由许多单个的时间序
列组成的，但是为了简单，我们假定它们已
经被合成一条长的序列。并且假定 X和 Q都
是使用相同采用时间间隔测量的。
?上一节所讲的一般方法仅描述一个时间序列
的全局特征，根本没有提供对局部形状的描
述，比如峰值等。通常，全局模型平均了这
些局部的结构特征。然而，对于很多时间序
列来说，用结构特征来描述它们会更自然。
?两种查询方法,
◆第一种：在整个 X数据中序列化在扫描查询
Q，顺着 X每次把查询 Q移动一个时间点，同
时计算出每个时间点的距离尺度。该方法的
主要特点是，①开销大。②其焦点集中在低
层次的数据采样点，而不是高层次的结构特
征，比如峰值、高原、走势和波谷等。③直
接计算欧氏距离也对查询 Q和数据 X中的微
小岐变异常敏感。
◆ 第二种：先局部化地估计查询 Q和归档 X的
基于形状特征，然后在较高层次上进行匹配。
其特点是，①具有计算优势，因为抽象实质
上是一种压缩数据，可以把信号的很多无关
细节都忽略掉。②它可以以一种适合于人类
解释的形式提取结构化的信息。
?第二种技术的一个典型实例是用分段线性化
的片段来逼近信号。然后把分成段的序列表
示为局部参数化的曲线列表，而后便 可以 直
接根据参数描述计算结构特征。 可以 使用概
率模型把期望的形状和变化性按这些特征进
行参数化。 可以 把在数据档案 X中匹配 Q的问
题表达为这样的一个搜索问题：给定 Q的概
率模型，在 X中搜索局部区域使这个区域中
数据的似然最大化。
?第二种技术对于用局部统计模型不易处理的
信号类型这种表示特别有用，比如包含暂态、
阶跃函数、趋势和其他各种类似某一形状模
式的不稳定信号。
三、隐含语义索引
?上面所介绍的都是将文档表示为 T维词条权
向量的。但用户可能提出的查询中的词条
不在用在索引文档的词条中。
?例如，从词条相似性的角度来看，词条
“数据挖掘”和“知识发现”设有什么直
接的共同点。然而，从语义角度来看，这
两个词条有很大的相同点。
?因此，在提出一个包含其中之一的查询，那
么应该考虑包含另一个的文档。解决方法是：
预先创建一个把语义相关词条连接在一起的
知识库 (同义词典或本体集 )。然而，这样的
知识库存在固有的主观性，因它取决于从何
种角度来把词条和语义内容联系起来。
?隐含语义索引 (latent semantic
indexing)(LSI)— 一种可选的有趣又有价值的
方法。该方法不是仅使用词条出现信息，而
是从文本中提取出隐藏的语义结构信息。
?实际上,LSI采用 T维词条空间中前 k个主成
分来近似原始的 T维词条空间，使用 N× T的
文档 -词条来估计这个方向。
?主成分方法的直观解释是，由原始词条的加
权组合所构成的单个向量可以非常好的近似
由 大得多的向量集合所起的效果。于是可以
把原来的 N× T大小的文档 -词条矩阵简化为
N× k的矩阵 (k<<T),
?对于固定的查全率，和前面讨论的向量空间
方法相比,LSI可以提高查准率。
?对表 9-2中的矩阵 M计算奇异分解式 (SVD)。
?目标是，找一个分解式 M=USVT。式中 U是
一个 10× 6的矩阵，它的每一行是相对特定
文档的权向量,S是每个主成分方向特征值
的 6× 6对角阵,6× 6的矩阵 VT的各列提供
了数据的新共轭基，被称为主成分方向 。
?S矩阵的对角线元素是 (协方差矩阵对应 …),
λ1,…,λ n={77.4,69.5,22.9,13.5,12.1,4.8}
可见，前两个主成分捕捉了数据中的主要变
化，和直觉一致。
?当使用两个主成分时，那么二维表征所保
留的变化比例 0.925，信息丢失仅 7.5%。
925.0/)( 6 1 22221 ?? ? ?i i???
?如果我们在新的二维主成分空间来表示文
档，那么每篇文档的系数对应于 U矩阵的前
两列 (两个主成分对应的特征向量，即新的
文档权值 ),
?这两列可看作新的伪词条，其作用相当于
原来 6个词条的线性组合。
?看一下前两个主成分方向可以得到的信息
(新共轭基 ),
V1=(0.74,0.49,0.27,0.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的词
条向量最大，因此离原最远。
?从图可看出，文档间的角度差异显然是相
似性的一个有用指标，因为回归和数据库
文档在平面上是围绕两个不同的角度聚成
簇的。
?主成分方法的应用例子,
考虑一个新的文档 D1，词条“查询”在该
文档
?中出现 50次，另一个文档 D2，包含词条
,SQL”50次，两且两篇文档都不包含其他
的词条。如果直接使用关键字表示，这两
个文档不会被认为是相似的，因为它们没
有包含相同的词条。
?然而，如果使用两个主成分词条来表示这
两篇文档，并把它们投影到这个空间中，
那么正如图 9-3所示，二者都被投影到“数
据库”方向，尽管它们都 仅包含和数据库
有关的三个词条中的一个。
?从计算的角度来看，直接计算主成分向量
(例如求解相关矩阵或协方差矩阵的特征值 )
通常要么是计算上不可行，要么是数值上
不稳定。实践中，可以使用特别适合高维
稀疏矩阵的 SVD技术来估计 PCA向量。
四、文档和文本分类
?上面的讨论可以看出使用词条向量来表示
文档为文档分类提供了一种自然框架。
?有了这一框架对于预先有标签的文档我们
可以使用有指导分类技术，对于没有标签
的文档我们可以使用无指导学习 (聚类 )框架。
?典型词条向量的维数都是非常高的，基于
这一事实，高维空间中的准确性和高效性
通常是选择分类器的首要标准。
?对于文档表示来说，像一阶贝叶斯分类器
这样的分类模型或者是加权线性组合可工
作得很好。
?在文档分类这一领域还有很多有趣的问题
可以探讨，例如认为每篇文档属于多个主
题 (类 )而不是仅属于某个类是有意义的。因
此在分类时不再限于各个类是相互排斥的
这一通用框架。一种简单的方法是为每个
类分别训练一个二值分类器，此方法仅当
类别总数较少时是可行的。
9.4 对个人偏好建模
一,相关性反馈
?文本检索系统比其他数据挖掘算法更具有
交互性。特别是，提出特定查询 Q的用户可
能愿意反复使用算法进行一系列不同的检
索尝试，并通过为返回的文档标记出相关
与否来给算法提供用户反馈。
?在这方面,Rocchio算法应用的特别广泛。
算法的基本思想,
?从根本上讲相关性是以用户为中心的，也
就是，如果用户可以 (理论上 )看到所有的文
档，那么原则上他可以把所有文档分成两
个集合，相关的 R和不相关的 NR。如果给
定了这两个集合，那么可以证明最佳查询
(利用向量模型 )为,
?其中 D代表文档的词条向量表示，它的标签
(用户作出的 )是已知的。
??
??
??
NRDRD
o p t i m a l DNRDRQ
11
?在实际应用中，一般一个用户不会把数据
库中所有文档都标上分类标签。相反，用
户是从一个特定查询 Qcurrent开始的，可以把
这个查询看作是相对 Qoptimal次优的。算法使
用这个初始查询返回文档的一个较小子集，
然后用户把该子集的文档标记为相关 R’和不
相关 NR’。 Rocchio算法按下面的方式来提
炼查询,
??
??
???
''
''
NRDRD
c u r r e n tn e w DNRDRQQ
???
?该算法使查询朝着相关文档的均值向量靠
近，并远离不相关文档的均值向量。参数 α、
β和 γ是正的常数 (启发式选取 )，它们控制着
新查询对最近标记文档的敏感性 (相对于当
前查询向量 Qcurrent)。
?不断重复这个过程，把新的查询 Qnew与文
档集合进行匹配，然后让用户再一次标记
文档。
?原则上讲，如果每一次迭代所作的标签是
一致的，那么 Qnew会逐步逼近 Qoptimal。
?实验证据表明，利用用户反馈确实提高了
查准率 -查全率性能。然而，在实际应用时
还有一些细节问题需要确定，比如显示给
读者的文档数量；使用的相关文档和非相
关文档的相对数量；选取非相关文档的方
法等等。
二、自动推荐系统
9.5 图像检索
?随着图像和视频数据集合在的不断增加，
人们对图像检索的兴趣也日益浓厚。
?手工对图像进行注释具有浪费时间、主观
性强等缺点，而且可能因为注释者的看法
不同而丢失图像的某些特征。
?一幅图像可能要使用一千个词来描述,但是
到底使用哪一千个单词却不是简单的问题,
?因此，开发高效而又准确的算法来根据内
容对图像数据库进行查询是很有必要的。
比如，检索系统允许用户提交这样的查询
“找出和这幅图像最相近的 K幅图像”或者
“找出和这组图像属性最匹配的 K幅图像”。
一、图像理解
?图像数据查询是非常困难的任务。从某种
意义上来说寻找彼此相似的图像等价于求
解图像理解问题，也就是从图像数据中抽
取语义信息。
?在这方面人类非常出色，然而，关于模式
识别和计算机视觉的几十年研究已经表明，
要用计算机算法来“复制”人类在视觉理
解和识别方面的能力是极端困难的。
?举例来说，婴儿可以很快学会要任何背景
下辨别各种动物，比如各种大小、颜色、
体型的狗，而这种完全无约束的识别问题
超出了目前任何视觉算法的能力。因此，
目前的大多数图像检索算法还仅依赖于相
当低级的可视提示。
二、图像表示
?为了便于检索，可以把原始的像素数据抽
象为特征表示，通常是以类似色彩和纹理
这样的原语来表示图像特征。
?类似于文本表达方式，仍然采用数据矩阵
格式来表示图像，每一行代表一幅特定的
图像；每一列代表一个图像特征。这样的
特征表示通常比直接的象素测量值对缩放
和平移变化更有效。
?原始的像素数据被简化为标准的 N× p数据
矩阵，在这个矩阵中每一幅图像被表示为
特征空间中的一个 p维向量。
?通过计算图像局部化子区域的特征可以粗
略的引入空间信息。例如，我们可以计算
一幅 1024× 1024像素图像的每个 32× 32子
区域的颜色信息。这样便可以在图像查询
中使用粗略的空间约束，比如“寻找中央
主要为红色，四周为蓝色的图像”。
?应用于图像的根据内容检索系统的一个著
名商业实例是 IBM开发的 根据图像内容查询
(QBIC)系统。该系统允许用户交互式的查
询图像和视频数据，查询的依据可以是图
像实例、用户输入的草图、颜色和纹理模
式、对象属性等等。允许对景物、对象以
及视频帧序列或者是这些的任意组合进行
查询。
?QBIC系统使用了多种特征以及多种和距离
有关的尺度用于检索,
◇ 相对整幅图像进行空间平均的三维颜色特
征向量，采用欧氏距离尺度。
◇ K-维颜色直方图，直方图的柱位可以使用
像使用 K-平均这样的基于划分聚类算法来
选取。采用马氏 (Mahalanobis)距离尺度来
表征颜色相关性。
◇ 衡量粒度 /比例、方向性和对比度特征的三
维纹理向量。采用加权的欧氏距离尺度来
计算距离，权的缺省值为各个特征方差的
倒数。
◇ 20-维的对象形状特征，比如区域、圆度、
离心率、轴方向、各种矩等等。采用欧氏距
离来计算相似性。
三、图像查询
?和文本数据的情况相同，用于抽象表示图像
的方法决定了支持何种类型的查询和检索操
作。特征表示提供了一种表示查询的语言。
有两种形式来表示查询。
?一种方法：通过样例查询，在这种样例中，
我们既可以为要寻找的目标提供一个图像样
例，也可以勾画出感兴趣图像的形状。
接下来便计算样例图像的特征向量，然后再把
计算出的查询特征向量和数据库中预先计算
出的特征向量进行匹配。
?另一种方法：直接以特征表征表达查询，比
如, 寻找这样的图像,50%的区域为红色，
并且包含具有特定方向和粒度特征的纹理, 。
?表示图像和查询的特征向量形式与用于文本
检索的向量空间表示非常相似。一个主要差
异是图像特征通常是一个实数，而词条向量
中的词条分量通常是某种形式的加权计数，
代表了这个词条在文档中出现的频繁程度。
?不过，这两种问题都是根据内容检索的问题，
这一共同特征决定了用于文本检索的很多技
术也适应于图像检索应用。
9.6 时间序列和序列检索
?在时间序列和序列数据集合中高效而又准确
的定位有意义模式的问题对于很多应用都有
重要意义，比如复杂系统的诊断和监控、生
物医学数据分析以及对科研和商业时间序列
的探索性数据分析。这样例子包括,
◇找出这样的顾客：他们相对时间的消费模式
和给定的消费特征相似；
◇在复杂的实时监控和故障诊断系统中，搜索
出与当前异常传感器信号相似的以前实例；
◇在蛋白质序列中进行有噪声子串的匹配。
?和二维图像数据相比，可以把序列数据看作
是一维的。时间序列数据是相对时间测量出
来的一系列观察结果，因此可以用时间变量 t
来索引观察值。
?序列数据的概念比时间序列数据的概念更广，
因为序列数据不一定是时间的函数。例如，
在计算生物学中，蛋白质是以其在蛋白质序
列中的顺序位置来索引的。
一、时间序列数据的全局模型
?传统的时间序列建模技术 (比如统计方法 )主
要是建立在全局线性模型基础上的，典型的
例子是 Box-Jenkins自回归模型族，该方法
把当前值 y(t)模拟成过去值 y(t-k)的加权线性
组合，再加上一个额外的噪声项,
?式中 αi是加权系数,e(t)是时间 t的噪声 (通常
被假定为均值为零的高斯函数 )。
?
?
???
k
i
i teityty
1
)()()( ?
?Box-Jenkins方法的一个重要贡献是，如果
在时间序列中存在可识别的系统性非平稳分
量 (比如某种趋势 )，那么很多情况下可以把
这个不平稳分量删除使这个时间序列变成平
稳的形式。例如，像国内生产总值和道琼斯
指数这样的经济指标中包含着固有的上升趋
势 (总体而言 )，通常要在建模前将这种趋势
删除。
?对于非平稳性比较复杂的情况，另一种有用
方法是假定这个信号是相对时间局部平稳的。
?非线性的全局模型对上面公式进行了推广，
比如可以允许 y(t)非线性地依赖过去值,
其中 g(.)是非线性的。
?从数据挖掘的角度来看，如果我们假定这样
的全局模型充分地描述了潜在的时间序列，
那么我们就可以使用模型参数 (比如上面的
各个权 )作为表示数据的基础，而不使用原
始数据本身。
)()()(
1
teitygty
k
i
i ???
??
?
? ?? ?
?
?
?通过把时间序列表示为参数向量，把序列问
题转化为本章前面所介绍的文本和图像的方
法，便可以在参数向量空间中定义相似性尺
度、在这个空间中定义根据内容检索的查询。
二、时间序列的结构和形状
?考虑一个实数值时间序列的子序列
Q=[q(t),…q(t+m)],和一个长得多的归档时
间序列 X=[x(t),…,x(T)],前者称为查询序列。
?我们的目标是在 X中找到和 Q最相似的一个
子序列。
?现实情况下,X可能是由许多单个的时间序
列组成的，但是为了简单，我们假定它们已
经被合成一条长的序列。并且假定 X和 Q都
是使用相同采用时间间隔测量的。
?上一节所讲的一般方法仅描述一个时间序列
的全局特征，根本没有提供对局部形状的描
述，比如峰值等。通常，全局模型平均了这
些局部的结构特征。然而，对于很多时间序
列来说，用结构特征来描述它们会更自然。
?两种查询方法,
◆第一种：在整个 X数据中序列化在扫描查询
Q，顺着 X每次把查询 Q移动一个时间点，同
时计算出每个时间点的距离尺度。该方法的
主要特点是，①开销大。②其焦点集中在低
层次的数据采样点，而不是高层次的结构特
征，比如峰值、高原、走势和波谷等。③直
接计算欧氏距离也对查询 Q和数据 X中的微
小岐变异常敏感。
◆ 第二种：先局部化地估计查询 Q和归档 X的
基于形状特征，然后在较高层次上进行匹配。
其特点是，①具有计算优势，因为抽象实质
上是一种压缩数据，可以把信号的很多无关
细节都忽略掉。②它可以以一种适合于人类
解释的形式提取结构化的信息。
?第二种技术的一个典型实例是用分段线性化
的片段来逼近信号。然后把分成段的序列表
示为局部参数化的曲线列表，而后便 可以 直
接根据参数描述计算结构特征。 可以 使用概
率模型把期望的形状和变化性按这些特征进
行参数化。 可以 把在数据档案 X中匹配 Q的问
题表达为这样的一个搜索问题：给定 Q的概
率模型，在 X中搜索局部区域使这个区域中
数据的似然最大化。
?第二种技术对于用局部统计模型不易处理的
信号类型这种表示特别有用，比如包含暂态、
阶跃函数、趋势和其他各种类似某一形状模
式的不稳定信号。
