基于奇异值分解的信息检索
仲兆满1，2，高维春1，李元金1
( 1 天津工业大学计算机学院，天津 300160；
2 连云港师范高等专科学校计算机系，江苏 222003）
摘要：针对web信息检索的特点，提出了一种基于奇异值分解和欧氏距离算法的信息检索算
法。该算法能解决传统信息检索搜索时间慢、空间占用量大的问题。实验证明了该算法的有
效性。
关键字：信息检索；奇异值分解；欧氏距离；Salton 向量空间模型
1 引言
随着www在全球范围内的不断普及和应用，www上的信息资源种类及其数量不断扩大，
因此，研究高效的信息搜索方法成了一个非常重要的课题。
信息检索是从任何信息集合中识别和获取所需信息的过程及其所采取的一系列方法和
策略。从原理上看，它包括存储和检索两个方面。信息的存储主要是指对在一定范围内的信
息选择基础上进行信息特征描述、加工并使其有序化，即建立数据库;检索是借助一定的设
备与工具，采用一系列方法与策略从数据库中查找出所需信息 [1] 。
目前信息检索主要有两种方式：基于目录结构的检索和基于关键字的文档检索。基于目
录结构的检索是一种被动的处理方式，用户只能通过系统所提供的分类情况进行检索。缺少
必要的用户交互手段，并不知道用户真正所需要的文章，因此，在许多搜索引擎的实现过程
中，并不提供基于目录的服务。而基于查询串的文档信息检索则属于一种主动的处理方式。
它所完成的任务是接收用户从客户端(主要是浏览器)所提交的信息串，经网络传输后提交相
关的信息检索机制，并将最终的结果按照一定的排序规则排序后传输给用户。这种检索方式
具有较好的用户交互能力。
近年来，不少科研工作者致力于这方面的研究，并成功应用于各种Web的应用中。Salton
等人[2] 提出的向量空间模型( Vector Space Model, VSM)将文档和用户查询式转化为向量形
式，根据向量之间的相似程度对所有返回结果进行排序，并在搜索引擎系统中得到了较为广
泛的应用。但是，随着文档集合的扩充，数据库表的记录的会增大，特征值也会变得很大。
对应的文档向量空间大小的维数会急剧上升，直接影响查快率。
雷景生等人[3]提出了一种改进的向量空间模型。该模型将一篇文档的相关信息从逻辑上
划分为多个相对独立的文本段，按照不同位置的文本段确定相应的索引项权重，并给出了该
模型的相似度计算方法。
刘志为等人[4]提出一种N层向量模型，它能较好地适应文档集合的动态扩充。
-1-
本文针对传统向量空间模型在Web信息检索中存在的缺陷，采用奇异值分解和欧氏距离
算法的信息检索，能够减少文档的维数，提高查找的速度。
2 Salton 向量空间模型的算法
向量空间模型使用以下的一些知识：
在对文本进行处理时，由于一个文本所包含的属性非常多，因此，为了简化文本处理的
计算过程，需要对文本信息进行预处理，通过特征选取的方法，尽可能降低文本处理过程中
的计算量。由于所涉及到的文本向量和词频矩阵非常大，而且单词与单词的依赖性将会使得
文本信息处理无法完成，因此在对文本信息进行处理的过程中，一般都基于单词与单词之间
互相独立的假设来降低文本信息处理的复杂度。同时考虑到文本向量空间过大的问题，需要
对文本信息进行预处理，过滤到一些无关的属性，以降低文本向量空间的维数并减少无关信
息对文本信息处理过程的干扰，使文本信息处理的精度得到提高。常用的预处理方法是特征
选取方法。
定义1 特征项t：也称为索引项，是指出现在文档d中且能够代表该文档性质的基本语
言单位。
定义2 特征项权值Wik：是指特征项tk代表文档di的能力大小。Wik的计算采用特征项频
率tfik和反比频率idfk计算：
wik=tfik+ idfk=tfik *(log2 (N/nk)+1) （１）
其中，tfik表示特征项tk在文档di中出现的频率，N代表文档集合中的文档数量，nk代表在
文档集合中出现特征项tk的文档数目。
从公式(1)可知，tfik越大，wik值越大；同样nk越小，wik值也越大，说明该特征项tk更能
够代表文档d的内容。
定义3 文档向量：设文档集合中共有m个不同的特征项t1，t2，……tm，分别计算文档
di(i=1，……，N)的特征项t1，t2 ，……，tm的特征项权值，由这些特征项权值所构成的向
量( wi1，Wi2，……，wim,.)成为文档d,的向量。
由于特征项t1，t2，……tm互不相同，我们可以将文档向量看作是m维欧氏空间的向量。
这样，文档之间的相似程度通过向量的形式转化为向量之间的数学计算模式，使得在进行文
档归类以及查询匹配过程中的计算过程比较简单、快速。
定义4 相似度：两文档向量之间相似的距离程度记为相似度。文档di、dj相似度定义为
di、dj所对应的文本向量之间的夹角余弦：
-2-
∑∑
∑
=
=
=
=
===
mk
k
ik
mk
k
jk
m
k
jk
ww
w
djdisim
11
1
ik
)()(
* w
cos),(
22
θ (2)
在进行查询匹配时，查询条件QS的向量化过程可采用布尔模型进行：
⎩⎨
⎧
∉
∈=
QSt
QSt
Q
j
j
j 当
当
0
1
即特征向量tj出现在查询条件QS中，则qj为1，否则为0。
利用前述基本知识实现信息检索的算法步骤如下：
第一、构造特征项库：输入文档集合中的特征项，并建立特征项库；
第二、建立文档信息：将文档内容输入数据库，建立文档信息库；
第三、构造文档向量信息库：对每个文档信息依据公式(1)，计算每一个特征项的权值，
并构建相应的文档向量；
第四、查询文档：用户输入查询条件，利用布尔模型得到查询条件的文档向量，再利用
公式(2)与每一个文档向量进行计算得到该查询条件与文档的相似度；
第五、排序输出结果：按照第四步所计算出来的相似度大小排序输出查询结果。
基于向量空间模型的信息检索方法存在着缺陷：
随着数据库表的记录的增大，特征值会变得很大。对应的文档向量空间大小的维数会急
剧上升。比如：对于一个含有100个记录的表来说，其文档向量空间大小的维数达到1000是
很正常的，但如此大或更大维数的向量之间运算的时间复杂度会很高，直接影响查快率。
3 基于奇异值分解和欧氏距离测量的信息检索算法
由于 Salton 向量空间模型算法随着文档向量的增加，占用存储空间和运算量会急剧增
大，所以采用奇异值分解的算法。因为在对文本信息进行处理的过程中，一般都基于单词与
单词之间互相独立的假设来降低文本信息处理的复杂度，所以可以把由 Salton 向量空间模型
算法得到的文档向量转换成 m×n 的矩阵。再对矩阵进行奇异值分解，得到的奇异值向量
是唯一的,它刻画了矩阵数据的分布特征，保留了矩阵的代数本质，因此可以将
奇异值向量作为文档矩阵的代数特征。而奇异值向量将文档向量映射到一个子空间，运算的
时间复杂度和空间复杂度要减少很多。
),...,,( 21 rσσσ
在计算文档向量和查询条件文档之间的相似度时 Salton 向量空间模型算法采用夹角余
弦，在这里采用欧氏距离测量，运算量会减小。
奇异值分解
-3-
引理1 奇异值分解： 对于任一实矩阵Am×n ,秩(A)=r,则存在两个标准正交矩阵Um×m和Vn×n以及对角阵
Dm×n，使得A=UDVT。其中,
,
00
0⎥⎦
⎤⎢⎣
⎡Σ= ×× rrnmD ),,...,,( 21 rrr diag σσσ=Σ × ,),...,,,...,,( 121 mrrmm uuuuuU +× = =×nnV ),...,,,...,,( 121 nrr vvvvv + 。
),...,,...,2,1( nriii == λσ 称为矩阵A的奇异值，λ1≥λ2≥…≥λr≥0,λr+1=λr+2=…=λn=0 是矩阵ATA
和AAT的特征值。 分别是A),...,2,1(, rivu ii = TA和AAT对应于非零特征值 λ i的特征向量。
在λ1≥λ2≥…≥λr的限制下，矩阵的奇异值向量 是唯一的，它刻画了矩阵数据
的分布特征。直观上，可以这样理解奇异值分解，将矩阵A
),...,,( 21 rσσσ
m×n看成是一个线形变换，它将n
维空间的点映射到m维空间，而经过对Am×n进行奇异值分解之后，这种映射被分割成 3 个部
分，分别是Um×m，Dm×n和Vn×n。其中的Um×m和Vn×n都是标准正交矩阵，那么它们对应的线形
变换就相当于分别对m维和n维坐标系中坐标轴的旋转变换。而Dm×n是对角矩阵，在线形变
换中相当于对各个坐标轴进行伸缩变换，由此可见，对矩阵进行奇异值分解之后，只有奇异
值向量构成的对角矩阵保留了矩阵的代数本质。因此可以将奇异值向量作为文档向量矩阵的
代数特征[5，6，7，8]。
用欧氏距离测量文档向量的相似度
测度两个模式之间相似程度的方法很多，其中欧氏距离是实际使用较多的一种。
引理 2 欧氏距离： ( ) ⎥⎦⎤⎢⎣⎡ −∑==−=
n
i
yxyxd ii yx
1
2),(
2
1
（3）
当两个文档向量越相似，两个矢量越相似，距离（3）就越小，反之亦然[8]。
算法实现步骤
根据以上的讨论，提出算法，总结如下：
第一、构造特征项库：输入文档集合中的特征项，并建立特征项库；
第二、建立文档信息：将文档内容输入数据库，建立文档信息库；
第三、构造文档向量信息库：对每个文档信息依据公式(1)，计算每一个特征项的权值，
并构建相应的文档向量；
第四、对每个文档的特征向量进行奇异值分解，得到每个文档的奇异值信息库；
第五、查询文档：用户输入查询条件，利用布尔模型得到查询条件的文档向量，在对其
进行奇异值分解，然后利用欧氏距离公式(3)与每一个文档的奇异值特征进行计算得到该查
询条件与文档的相似度；
第六、排序输出结果：按照第五步所计算出来的相似度大小排序输出查询结果。
4 实验与结果分析
-4-
实验对象
从万方数字化期刊中随机抽取期刊论文 20 篇，得到文档集合的关键字特征项共 50 个。
实验结果及分析
文档向量矩阵
由 Salton 向量空间模型算法得到文档向量。因为在对文本信息进行处理的过程中，一般
都基于单词与单词之间互相独立的假设来降低文本信息处理的复杂度，所以可以把由 Salton
向量空间模型算法得到的文档向量转换成 m×n 的矩阵。结果如下图所示：
文档 1
文档 5
图 1 文档向量矩阵
文档矩阵分解为奇异值向量
文档矩阵经过奇异值分解后，得到对应的奇异值向量如下：
文档 1 的特征值向量：（）
-5-
文档 5 的特征值向量：（，）
测量欧氏距离
在查询条件中先后输入文档 1、文档 2、文档 4、文档 5，进行实验，得到欧式距离结果
如下：
查询条件
距离
文档 1的关键字 文档 2的关键字 文档 4的关键字 文档 5的关键字
与文档 1 的距离
与文档 2 的距离
与文档 3 的距离
与文档 4 的距离
与文档 5 的距离
与文档 6 的距离
与文档 7 的距离
与文档 8 的距离
与文档 9 的距离
与文档 10 的距离
与文档 11 的距离
与文档 12 的距离
与文档 13 的距离
与文档 14 的距离
与文档 15 的距离
与文档 16 的距离
与文档 17 的距离
与文档 18 的距离
与文档 19 的距离
与文档 20 的距离
图 2 欧氏距离表
可见，如果在查询算法可靠的情况下，当查询条件中输入文档 1 的关键字时，文档 1
对应的欧氏距离是最小的。同样当查询条件中输入文档 2 的关键字时，文档 2 对应的欧氏距
离是最小的。从上表的实验结果可以看出，当在查询条件中输入文档 1 的关键字时，得到的
文档 1 欧氏距离在文档集合中排第二；当在查询条件中输入文档 2 的关键字时，得到的文档
2 欧氏距离在文档集合中排第二；当在查询条件中输入文档 4 的关键字时，得到的文档 4 欧
-6-
氏距离在文档集合中排第一；当在查询条件中输入文档 5 的关键字时，得到的文档 5 欧氏距
离在文档集合中排第四。所以当按相似度的大小显示满足一定阈值的一系列文章时，奇异值
分解具有很高的查全率和查准率。
5 结 论
上述实验证明，本文提出的基于奇异值分解和欧氏距离算法的信息检索算法在保证查全
率和查准率的前提下，大幅度的降低了运算量，提高了运算速度。
参考文献
[1]焦玉英,符绍宏.信息检索[M].武汉:武汉大学出版社,2001.
[2]GERARD SALTON，A. WONG and . A Vector space model for information Retrieval.
Communications of the ACM，(11)：613-620.
[3]雷景生,林冬雪,符浅挽. 基于改进向量空间模型的Web信息检索技术研究.计算机工程.2005,.
[4]刘志为. N层向量空间模型在web信息检索中的应用. 微型机与应用.2004年第12期.
[5]史荣昌.矩阵分析.北京：北京理工大学出版社, 153.
[6]屠伯埙.线性代数：方法导引.上海：复旦大学出版社,1986.
[7]Shi RC. Matrix Analysis. Beijing:Beijing Institute of Technology Press, 1996. 149-153(in
Chinese).
[8]Han JW, Kamber M. Data Mining:Concepts and Techniques. Beijing:High Education Press,
2001,38-388.
A Web Information Retrieval Method Based on Singular
Value Decomposition
Zhong Zhao-man1,2, Gao Wei-chun1, Li Yuan-jin1
(1 School of Computer Technology and Automation, Tianjin Polytechnic University, Tianjin
300160；2 Computer Science and Technology department, Lian Yungang Teachers’ college,
LianYungang 222003)
Abstract
Aiming at the feature of web information retrieval, an information retrieval method based on
singular value decomposition and Euclidean distance is proposed in this paper. The traditional
information retrieval has the problems that the searching speed is slow and the searching space is
big. The method we proposed can solve the above problem. The experiment results show that the
method is efficient.
Key words: information retrieval; singular value decomposition; Euclidean distance; Salton
vector space model
-7-
作者简介：
仲兆满，现为天津工业大学计算机技术与自动化学院计算机应用技术专业 2003 级硕士
研究生，连云港师范高等专科学校讲师，主要从事网络安全、数据挖掘等方面的研究。
-8-
Abstract
