基于层次搜索的潜在语义索引方法研究，本文主要内容关键词为：语义论文,索引论文,层次论文,方法论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
［分类号］G354.2
1 潜在语义索引方法及其不足
潜在语义分析方法是一种概念检索方法，该方法能有效解决单纯词形匹配方法中天然存在的同义和多义两大问题。但是，对于大型的词汇——文本矩阵而言，该方法中的关键步骤——奇异值分解技术（SVD）所需耗费的巨大计算成本成为其应用的瓶颈。实验表明，大量的LSA 处理时间都用在了计算截短的大型稀疏词汇——文本矩阵的奇异值分解上。总结一下，LSA／SVD的关键性问题主要有以下三点：
●词条——文本矩阵的SVD计算时间代价。SVD算法的时间代价是O（N[2]K[3]），，其中N是单词数和文本数的乘积，K是LSA空间的维数（K值一般在100—300），N随着文本数和单词数的增加迅速地增长，这就使得SVD算法不太适合于大规模动态变化的数据集。
●根据词频生成的词汇——文本矩阵是具有大量零值的稀疏矩阵。利用传统的SVD计算方法计算效率不高，时间较长， 需要研究适合于大规模稀疏矩阵的特定SVD方法。
●研究表明，SVD对于小型同主题数据集效果明显， 而对于大型多主题的数据集而言，基于SVD的信息检索效果就不理想了。
2 基于层次搜索的潜在语义索引方法设计
2.1 层次搜索方法介绍
层次搜索是基于图论的信息检索模型，每个检索词和文本都表示为一个无向图的顶点。这个图等价于该图的对称矩阵
，其中A是原始的词汇——文本矩阵。图的每条边设定权值，这样超过一定阈值的文本被选为与查询相关的文本。由于使用了加权方法，我们将层次搜索分为简单层次搜索和加权层次搜索两种。下面简单介绍一下简单层次搜索的计算方法。
2.2 简单层次搜索方法
为说明这一算法，我们举下面一个小的西文文本标题集为例，它由5 个文本和10个词汇组成（见图1）。
首先，我们要对这一文本标题集进行处理，通过停用词表抽取出文本标题中有实词意义的词汇，有时还会用到去枝技术（stemming），即将同根词合并为一个词汇，此例中未用到。
随后，即可生成一个10×5的词汇——文本矩阵
，其中a[,ij]表示词i在文本标题j中出现的次数。该矩阵的转秩矩阵A[T]如下：
因为该词汇——文本矩阵A＝是由文本集直接建成的，即表示为初始矩阵。给出查询式“infant food”，向量q可表示为q＝[1010000000]，其中q[,i]表示查询中第i个词汇的频数。图2表示简单层次搜索的过程。
图2 简单层次搜索文本集的过程
如图2所示，查询式“infant food”（由T[,1]和T[,3]组成）定义为层1。第2层包括所有包含T[,1]和T[,3]的文本，即D[,1]、D[,3]和D[,5]。第3层由所有出现在D[,1]、D[,3]和D[,5]文本中的词汇组成。每个词汇只能出现在它第一次访问的层中。同样，第4层包括所有层3中列出的词汇和文本，并且它们之前未出现过。总体来说，层次搜索寻找从查询到其相关文本的路径，这个过程可看成将词汇和文本从初始矩阵到分层聚类的分类过程。
每个奇数层是一组词汇，每个偶数层是一组文本。在第3层有3个文本与查询相关，而在第4层找到了所有4篇文本（D[,2]加上第2层的3篇文本）。我们可以在任何文本层形成这个查询的新的词汇——文本矩阵。例如在第2层，词汇T[,1]和T[,3]只和D[,1]、D[,3]、D[,5]相关，因此，关于查询式“infant food”在第2 层可生成词汇——文本矩阵B＝
A[T]＝
这个2×3的特定词汇——文本矩阵一定是初始的10×5的词汇——文本矩阵的子集。
由于SVD的计算成本与稀疏矩阵中非零元素数目相关， 因此子矩阵中非零元素数与原始词汇——文本矩阵中非零元素数之比可用于评价SVD计算量的减少程度。行和列的减少也可作为评价标准。
2.3 新方法的设计思路
针对LSI的问题和层次搜索的特点，我们设计了一种针对大型多主题数据集、融合信息检索和信息过滤的新型算法，其思路是引入图论中比较成熟且计算成本低的算法——层次搜索方法。该方法首先对原始的词汇——文本矩阵进行信息过滤，缩小其规模，但保留其中主要的语义关系，然后再对过滤后的新词汇——文本矩阵进行LSA计算。其宗旨是要在信息过滤阶段保持高的查全率， 在信息检索阶段保证高的查准率，最后达到很好的检索效果。下面我们通过试验来进一步验证该方法的效果。
3 中文文本实例研究
我们选用中国期刊网中的《计算机工程》和《计算机工程与应用》两本计算机领域核心期刊中2003年至2004年的论文作为文本数据来源。在选择样本时，我们以“信息检索”主题进行筛选，并以此编制关键词表，模拟层次搜索和潜在语义分析技术，并比较两者的优劣。
因后面评价检索效果的需要，我们采用标准样本模式，它是由词汇集、文本集和正确的检索结果三部分组成的。在本次试验中，我们设计了“Web 信息检索”查询式，并给出了正确答案为D1—D6。
3.1 对样本进行LSI计算步骤及结果分析
3.1.1 词汇——文本矩阵构建初始化 该样本集的文本数为35篇，索引词汇数为69个。以词汇T在文本D的标题中出现的频次作为矩阵X的元素X[,ij]的值，可得到69×35的中文样本“词汇——文本”矩阵。
3.1.2 查询数据初始化 根据索引词汇在提问式q[,1]中出现的频次，可得69×1的提问式矩阵Xq1。
3.1.3 对原始样本进行LSI分析 运用MATLAB中函数svd的运算，得分解后的矩阵：T,S,D。为建立一个二维的语义空间，在计算结果中取S最大的2个奇异值（即第1、第2个），相应地，取T的前2列，D的前2列，得矩阵T[,2]、S[,2]、D[,2]。
3.1.4 检索结果分析 在对原始词汇——文本矩阵进行LSA后，设定阈值为0.9，我们检索到以上12篇文本，即D[,t]＝12，对比我们的标准答案为D1—D6，即D[,r]＝6，我们得到此次检索的文本中正确的是D1、D5、D6，即D[,r]＝3。
参照有关查全率和查准率的计算公式，我们得到下面的结果：
查全率R[,0]∶R[,0]＝D[,r]／N[,r]＝50％；查准率P[,0]∶P[,0]＝D[,r]／D[,t]＝25％。表1中列出了原始词汇——文本集的一些特点。
表1 原始词汇文本集的特征
*注：密度即为词汇——文本矩阵中非零元系数目的百分比，计算公式为：密度＝非零元素数目／（词汇数×文本数）。
3.2 用新方法对样本进行计算及结果分析
运用简单层次搜索对原始词汇——文本矩阵进行过滤，由层1和层2构成新的词汇——文本子矩阵，它们由3个词汇（Web、信息、检索）和25个文本（D1、D3、D5、D6、D7、D8、D9、D10、D12、D13、D16、D19、D20、D21、D22、D23、D24、D25、D26、D29、D30、D31、D32、D34、D35）组成。然后再对简单层次搜索后的3×25的新词汇——文本矩阵进行LSA计算，得出最后的结果（见表2）。
表2 经过简单层次搜索后的子矩阵的参数
实验表明，层次搜索技术针对每个特定的查询过滤出了足够小的子集（指的是既保留主要的语义关系，又要使子集的规模最小），大大降低了后续的SVD 计算成本，达到了很好的效果。
3.3 两种方法比较分析
3.3.1 LSI与“LS＋LSI”成本比较 我们设定查询式为“Web信息检索”，采用LSI和LS＋LSI两种方法对原始的词汇—文本集进行信息检索。表3比较了这两方法的成本差异。
表3 经过简单层次搜索后的子矩阵的参数
原始矩阵简单层次搜索简单层次搜索＋LSI
文本数35 25 4
词汇数69 3 3
非零元素数目 172 3211
密度7.12
42.67 91.67
3.3.2 LSI与“LS＋LSI”查全率和查准率比较 表4从检索结果的角度比较这两种方法的差别。
表4 基于查询式“Web信息检索”的查全率和查准率比较
LSA简单层次搜索简单层次搜索＋LSA
查全率(%)5066.775
查准率(%)25 16 75
4 结语
使用层次搜索技术（包括简单层次搜索和加权层次搜索）作为预处理的手段，首先进行信息过滤，再配合LSA进行信息检索，可以显著地提高查全率和查准率，有时甚至可以达到100％的完美效果，由此可得层次搜索技术是一项有效的技术，配合LSI使用可以达到理想的检索效果。
收稿日期：2006—01—12修回日期：2006—03—10本文起止页码：36—38
标签：自然语言处理论文; 信息检索论文; lsi论文; SVD论文; 语义分析论文; 矩阵分解论文; 文本分类论文; 文本分析论文; 矩阵论文;