论文部分内容阅读
[摘 要] 针对传统信息检索搜索时间慢、空间占用量大的问题，提出了一种基于奇异值分解和欧氏距离算法的信息检索算法。该算法降低了信息检索时间复杂度和空间复杂度，实验证明了该算法的有效性。
[关键词] 信息检索 奇异值分解 欧氏距离 Salton向量空间模型
随着因特网上信息资源种类及数量不断扩大，研究高效的信息检索方法成了一个非常重要的课题。信息检索就是借助一定的设备与工具，采用一系列方法与策略从数据库中查找出所需信息。基于查询串的文档信息检索接收用户从浏览器提交的信息串，经网络传输后提交相关的信息检索，并将最终结果按照一定排序规则排序后传输给用户，这种检索方式具有较好的用户交互能力。
近年来很多科研工作者致力于基于关键字的文档检索领域方面研究，并成功应用于各种Web应用中。Salton等人提出的向量空间模型将文档和用户查询转化为向量形式，根据向量之间的相似程度对所有返回结果进行排序，并在搜索引擎系统中得到了较为广泛的应用。
一、利用Salton向量空间模型实现信息检索的算法
第一，构造特征项库。输入文档集合中的特征项，并建立特征项库；
第二，建立文档信息。将文档内容输入数据库，建立文档信息库；
第三，构造文档向量信息库。对每个文档信息依据公式(1)，计算每一个特征项的权值，并构建相应的文档向量；
第四，查询文档。用户输入查询条件，利用布尔模型得到查询条件的文档向量，再利用公式(2)与每一个文档向量进行计算得到该查询条件与文档的相似度；
第五，排序输出结果。按照第四步所计算出来的相似度大小排序输出查询结果。
定义1 特征项t:是指出现在文档d中且能够代表该文档性质的基本语言单位。
定义2 特征项权值Wik:是指特征项tk代表文档di的能力大小。Wik的计算采用特征项频率tfik和反比频率idfk计算。
wik=tfik+idfk=tfik *(log2 (N/nk)+1) 公式（１）
其中，tfik表示特征项tk在文档di(i=1，……，N)中出现的频率，N代表文档集合中的文档数量，nk代表在文档集合中出现特征项tk的文档数目。
定义3 文档向量:设文档集合中共有m个不同的特征项t1，t2，……tm,分别计算文档di(i=1，……，N)的特征项t1，t2，……,tm的特征项权值,由这些特征项权值所构成的向量(wi1,wi2,……,wim,.)成为文档di的向量。
由于特征项t1，t2，……tm互不相同，可以将文档向量看作是m维欧氏空间的向量。这样，文档之间的相似程度通过向量的形式转化为向量之间的数学计算模式，使得在进行文档归类以及查询匹配过程中的计算过程比较简单、快速。
定义4 相似度:两文档向量之间相似的距离程度记为相似度。文档di、dj相似度定义为di、dj所对应的文本向量之间的夹角余弦：
公式(2）
在进行查询匹配时，查询条件QS的向量化过程可采用布尔模型进行：
即特征向量tj出现在查询条件QS中，则Qj为1，否则为0。
二、问题提出
利用传统向量空间模型可以定量计算查找字符串和数据库字符串的相似程度，但随着数据库表记录的增大，特征值变得很大，对应文档向量的维数急剧上升，严重影响查找效率。
三、基于奇异值分解的信息检索算法
奇异值分解通过数据降维方法发现高维数据之间的潜在关系，得到的奇异值向量(σ1，σ2，…，σr)是惟一的,它刻画了矩阵数据的分布特征，保留了矩阵的代数本质，因此可以将奇异值向量作为文档矩阵的代数特征。而奇异值向量将文档向量映射到一个子空间，提高了运算效率，因此可以将奇异值向量作为文档向量矩阵的代数特征。
引理1 奇异值分解:对于任一实矩阵Am×n,秩(A)=r,则存在两个标准正交矩阵Um×m和Vn×n以及对角阵Dm×n，使得A=UDVT。其中,,=diag(σ1,σ2,…,σr),Um×m=(u1,u2,…,ur,ur+1,…,um),Vn×n=(V1,V2,…,vr,vr+1,…,vn)。
称为矩阵A的奇异值，λ1≥λ2≥…≥λr≥0,λr+1=λr+2=…=λn=0是矩阵ATA和AAT的特征值。ui,vi(i=1,2,…,r)分别是ATA和AAT对应于非零特征值λi的特征向量。
在Salton向量空间模型实现信息检索算法的第三步构造文档向量信息库之后，对每个文档特征向量进行奇异值分解，然后在文档查询时，对查询条件的文档向量也要进行奇异值分解，然后利用欧氏距离计算奇异值分解后的文档特征向量与查询条件的文档向量的相似度，最后排序输出结果。
四、实验与结果分析
从万方数字化期刊中随机抽取期刊论文20篇，得到文档集合的关键字特征项共50个。
由Salton向量空间模型算法得到文档向量。因为对文本信息处理过程中，一般基于单词与单词之间互相独立的假设来降低文本信息处理的复杂度，所以把文档向量转换成m×n的矩阵。结果如下图所示：
文档矩阵经过奇异值分解后，得到对应的奇异值向量如下：
文档1的特征值向量:（1.4862）
文档5的特征值向量:（2.1478，0.5503）。
在查询条件中先后输入文档1、文档2、文档4、文档5，进行实验，得到欧式距离结果如下：
可见，如果在查询算法可靠的情况下，当查询条件中输入文档1的关键字时，文档1对应的欧氏距离是最小的。同样当查询条件中输入文档2的关键字时，文档2对应的欧氏距离是最小的。从上表的实验结果可以看出，当在查询条件中输入文档1的关键字时，得到的文档1欧氏距离在文档集合中排第二；当在查询条件中输入文档2的关键字时，得到的文档2欧氏距离在文档集合中排第二；当在查询条件中输入文档4的关键字时，得到的文档4欧氏距离在文档集合中排第一。所以当按相似度的大小显示满足一定阈值的一系列文章时，奇异值分解具有很高的查全率和查准率。
五、结论
上述实验证明，本文提出的基于奇异值分解和欧氏距离算法的信息检索算法和传统算法相比，在保证查全率和查准率的前提下，大幅度的降低了运算量，提高了运算效率。
参考文献：
[1]焦玉英 符紹宏:信息检索[M].武汉:武汉大学出版社,2001
[2]GERARD SALTON A. WONG and C.S.YANG. A Vector space model for information Retrieval. Communications of the ACM 1975.18(11):613～620
[3]雷景生 林冬雪 符浅挽:基于改进向量空间模型的Web信息检索技术研究[J].计算机工程，2005,1.vol31
[4]刘志为:N层向量空间模型在web信息检索中的应用[J].微型机与应用，2004年第12期
[5]史荣昌:矩阵分析[M].北京:北京理工大学出版社,1996.149～153
[6]屠伯埙:线性代数:方法导引[M].上海:复旦大学出版社,1986.
[7]Shi RC.Matrix Analysis[M].Beijing:Beijing Institute of Technology Press, 1996.149～153(in Chinese)
[8]Han JW, Kamber M. Data Mining:Concepts and Techniques[M]. Beijing:High Education Press, 2001,38～388
[关键词] 信息检索 奇异值分解 欧氏距离 Salton向量空间模型
随着因特网上信息资源种类及数量不断扩大，研究高效的信息检索方法成了一个非常重要的课题。信息检索就是借助一定的设备与工具，采用一系列方法与策略从数据库中查找出所需信息。基于查询串的文档信息检索接收用户从浏览器提交的信息串，经网络传输后提交相关的信息检索，并将最终结果按照一定排序规则排序后传输给用户，这种检索方式具有较好的用户交互能力。
近年来很多科研工作者致力于基于关键字的文档检索领域方面研究，并成功应用于各种Web应用中。Salton等人提出的向量空间模型将文档和用户查询转化为向量形式，根据向量之间的相似程度对所有返回结果进行排序，并在搜索引擎系统中得到了较为广泛的应用。
一、利用Salton向量空间模型实现信息检索的算法
第一，构造特征项库。输入文档集合中的特征项，并建立特征项库；
第二，建立文档信息。将文档内容输入数据库，建立文档信息库；
第三，构造文档向量信息库。对每个文档信息依据公式(1)，计算每一个特征项的权值，并构建相应的文档向量；
第四，查询文档。用户输入查询条件，利用布尔模型得到查询条件的文档向量，再利用公式(2)与每一个文档向量进行计算得到该查询条件与文档的相似度；
第五，排序输出结果。按照第四步所计算出来的相似度大小排序输出查询结果。
定义1 特征项t:是指出现在文档d中且能够代表该文档性质的基本语言单位。
定义2 特征项权值Wik:是指特征项tk代表文档di的能力大小。Wik的计算采用特征项频率tfik和反比频率idfk计算。
wik=tfik+idfk=tfik *(log2 (N/nk)+1) 公式（１）
其中，tfik表示特征项tk在文档di(i=1，……，N)中出现的频率，N代表文档集合中的文档数量，nk代表在文档集合中出现特征项tk的文档数目。
定义3 文档向量:设文档集合中共有m个不同的特征项t1，t2，……tm,分别计算文档di(i=1，……，N)的特征项t1，t2，……,tm的特征项权值,由这些特征项权值所构成的向量(wi1,wi2,……,wim,.)成为文档di的向量。
由于特征项t1，t2，……tm互不相同，可以将文档向量看作是m维欧氏空间的向量。这样，文档之间的相似程度通过向量的形式转化为向量之间的数学计算模式，使得在进行文档归类以及查询匹配过程中的计算过程比较简单、快速。
定义4 相似度:两文档向量之间相似的距离程度记为相似度。文档di、dj相似度定义为di、dj所对应的文本向量之间的夹角余弦：
公式(2）
在进行查询匹配时，查询条件QS的向量化过程可采用布尔模型进行：
即特征向量tj出现在查询条件QS中，则Qj为1，否则为0。
二、问题提出
利用传统向量空间模型可以定量计算查找字符串和数据库字符串的相似程度，但随着数据库表记录的增大，特征值变得很大，对应文档向量的维数急剧上升，严重影响查找效率。
三、基于奇异值分解的信息检索算法
奇异值分解通过数据降维方法发现高维数据之间的潜在关系，得到的奇异值向量(σ1，σ2，…，σr)是惟一的,它刻画了矩阵数据的分布特征，保留了矩阵的代数本质，因此可以将奇异值向量作为文档矩阵的代数特征。而奇异值向量将文档向量映射到一个子空间，提高了运算效率，因此可以将奇异值向量作为文档向量矩阵的代数特征。
引理1 奇异值分解:对于任一实矩阵Am×n,秩(A)=r,则存在两个标准正交矩阵Um×m和Vn×n以及对角阵Dm×n，使得A=UDVT。其中,,=diag(σ1,σ2,…,σr),Um×m=(u1,u2,…,ur,ur+1,…,um),Vn×n=(V1,V2,…,vr,vr+1,…,vn)。
称为矩阵A的奇异值，λ1≥λ2≥…≥λr≥0,λr+1=λr+2=…=λn=0是矩阵ATA和AAT的特征值。ui,vi(i=1,2,…,r)分别是ATA和AAT对应于非零特征值λi的特征向量。
在Salton向量空间模型实现信息检索算法的第三步构造文档向量信息库之后，对每个文档特征向量进行奇异值分解，然后在文档查询时，对查询条件的文档向量也要进行奇异值分解，然后利用欧氏距离计算奇异值分解后的文档特征向量与查询条件的文档向量的相似度，最后排序输出结果。
四、实验与结果分析
从万方数字化期刊中随机抽取期刊论文20篇，得到文档集合的关键字特征项共50个。
由Salton向量空间模型算法得到文档向量。因为对文本信息处理过程中，一般基于单词与单词之间互相独立的假设来降低文本信息处理的复杂度，所以把文档向量转换成m×n的矩阵。结果如下图所示：
文档矩阵经过奇异值分解后，得到对应的奇异值向量如下：
文档1的特征值向量:（1.4862）
文档5的特征值向量:（2.1478，0.5503）。
在查询条件中先后输入文档1、文档2、文档4、文档5，进行实验，得到欧式距离结果如下：
可见，如果在查询算法可靠的情况下，当查询条件中输入文档1的关键字时，文档1对应的欧氏距离是最小的。同样当查询条件中输入文档2的关键字时，文档2对应的欧氏距离是最小的。从上表的实验结果可以看出，当在查询条件中输入文档1的关键字时，得到的文档1欧氏距离在文档集合中排第二；当在查询条件中输入文档2的关键字时，得到的文档2欧氏距离在文档集合中排第二；当在查询条件中输入文档4的关键字时，得到的文档4欧氏距离在文档集合中排第一。所以当按相似度的大小显示满足一定阈值的一系列文章时，奇异值分解具有很高的查全率和查准率。
五、结论
上述实验证明，本文提出的基于奇异值分解和欧氏距离算法的信息检索算法和传统算法相比，在保证查全率和查准率的前提下，大幅度的降低了运算量，提高了运算效率。
参考文献：
[1]焦玉英 符紹宏:信息检索[M].武汉:武汉大学出版社,2001
[2]GERARD SALTON A. WONG and C.S.YANG. A Vector space model for information Retrieval. Communications of the ACM 1975.18(11):613～620
[3]雷景生 林冬雪 符浅挽:基于改进向量空间模型的Web信息检索技术研究[J].计算机工程，2005,1.vol31
[4]刘志为:N层向量空间模型在web信息检索中的应用[J].微型机与应用，2004年第12期
[5]史荣昌:矩阵分析[M].北京:北京理工大学出版社,1996.149～153
[6]屠伯埙:线性代数:方法导引[M].上海:复旦大学出版社,1986.
[7]Shi RC.Matrix Analysis[M].Beijing:Beijing Institute of Technology Press, 1996.149～153(in Chinese)
[8]Han JW, Kamber M. Data Mining:Concepts and Techniques[M]. Beijing:High Education Press, 2001,38～388