基于预聚类的潜在语义分析模型文献检索研究

云南民族大学学报：自然科学版，２０１５，２４（３）：２５７—２６０　ｄｏｉ：１２．３９６９／ｊ．ｉｓｓｎ．１６７２—８５１３．２０１５．０３．０１９　ＣＮ５３—１１９２／Ｎ　ＩＳＳＮ　１６７２—８５１３　

ｈｔｔｐ：／／ｘｂ．ｙｎｎｉ．ｅｄｕ．ｃａ　

基于预聚类的潜在语义分析模型文献检索研究　和晓萍，李　迪，王米利，马学松，周卫红　（云南民族大学数学与计算机科学学院，云南昆明６５０５００）　

摘要：提出一种基于预聚类的潜在语义文献检索算法．首先，对待检索文档集进行预聚类．在潜在语义　分析方法的基础上采用ｋ—ｍｅａｎｓ聚类算法，寻找出各聚类簇的中心，董；其次，在检索时，通过计算查询　向量与各聚类簇中心点的相似度来进行检索．此方法有效解决了现有潜在语义文献检索算法在检索　时需耗费大量时间计算查询向量与各文本向量之间的相似度的不足．另外还针对文献检索的特点，重　新给出特征权重计算方法．实验结果表明，该方法缩短了检索的时间，提高了检索的效率．　关键词：潜在语义分析；文献检索；奇异值分解；　一ｍｅａｎｓ　中图分类号：ＴＰ３９１．３　文献标志码：Ａ　文章编号：１６７２—８５１３（２０１５）０３—０２５７—０４　

传统的经典信息检索模型主要有布尔模型、向量空间模型和概率模型¨］．其基本原理都是关键词的机　器匹配，即基于关键词的检索．通过用索引词来表示文档和用户查询，检索时通过用户查询和文档间字、词的　匹配来实现．但由于参与匹配的字、词具有同义和多义的特点，若不考虑上下文的约束，会对检索的查准率和　查全率造成严重的影响．　针对传统检索模型中同义词和多义词的现象，１９８８年Ｄｕｍａｉｓ等＿２　提出了基于潜在语义分析的检索模型，　

该方法有效解决了单纯的关键词匹配方法中的一词多义和多词一意的现象．在此基础上，盖杰等　提出了基于　潜在语义分析的文本信息检索算法；卢健等Ｈ　分析了基于潜在语义分析的信息检索方式，并在中文样本上进行　了验证；余正涛等　提出了一种基于潜在语义分析的汉语问答系统答案提取，并验证该方法的效果优于向量空　间模型；瞿琳琳等　开发了一个基于潜在语义分析的有关地理知识的智能检索系统；刘博等［　提出了一种基于　用户反馈的潜在语义信息检索模型；陈燕虹等　提出一种针对农业主题垂直搜索引擎的改进的潜在语义检索　模型．这些方法进一步将潜在语义分析应用到中文信息检索中，取得了较好的检索效果．　盖杰等　采用的方法主要是通过采用潜在语义分析的方法构造语义空间，或通过优化潜在语义分析方　法的缺点，提高检索的准确率．但在检索的过程中，由于查询向量需与每个文本向量进行相似度的计算，这需　要耗费大量的时间，针对这一问题，本文提出一种基于预聚类的潜在语义文献检索算法，采用预聚类的方法　对文档集进行预处理，检索时，查询向量就只需与聚类中心点进行相似度计算，从而避免了查询向量与每个　文本向量分别进行相似度计算，从而提高检索的效率．　

１　基础理论　１．１潜在语义分析　潜在语义分析（１ａｔｅｎｔ　ｓｅｍａｎｔｉｃ　ａｎａｌｙｓｉｓ，ＬＳＡ）的原理是假设词语之间存在某种联系，使用统计方法来提　取这种隐含的潜在语义联系，从而有效、准确的表示文本信息　８］．潜在语义分析是利用奇异值分解ＳＶＤ（ｓｉｎ—　ｇｕｌａｒ　ｖｅｃｔｏｒ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ），来发现文档中词与词之间的关联关系．　奇异值分解定理：　Ａ＝　ｖＴ　（１）　

收稿日期：２０１４—０６—０３．　基金项目：国家民委科研项目（１２ＹＮＺＯ０８）；云南省教育厅科学研究基金（２０１２Ｙ３１５）；云南民族大学青年基金（１１ＱＮ０８）　作者简介：和晓萍（１９８９一），女，硕士研究生．主要研究方向：数字图像处理与模式识别．　通信作者：周卫红（１９６９一），男，博士研究生，副教授，硕士生导师．主要研究方向：图像处理与模式识别．　２５８　云南民族大学学报（自然科学版）　第２４卷　式中，矩阵Ａ是一个ｍ×／＇ｔ的矩阵，矩阵Ｕ是ｍ×ｒ大小的正交矩阵，矩阵∑是ｒ×ｒ的对角线矩阵，矩阵　是ｒ　×ｎ大小的正交矩阵．其中，ｒ是矩阵Ａ的秩，且ｒ＜＜ｍｉｎ（ｍ，ｎ）．且有：　Ｕ＝　Ｖ＝Ｊ　（，　为ｎ阶单位矩阵）．　ＬＳＡ在对矩阵Ａ进行奇异值分解后，从分解得到的奇异值矩阵　中选取　个最大的奇异值，对矩阵进　行降维处理（　＜＜ｒ）．即取　、’，的前　个列和　的前　行　列进行奇异值分解的反运算，构建Ａ的　一秩近　似矩阵Ａ　：　Ａ　＝Ｕ　（２）　其中矩阵　和　均为正交矩阵．Ａ　为原词汇一文档矩阵Ａ的近似矩阵，它保留了原始矩阵Ａ中的重要信　息和文本间的关联，并且剔除了噪声　Ｊ．　１．２　ｋ—ｍｅａｎｓ聚类　一ｍｅａｎｓ算法是一种基于划分的经典聚类算法，该算法的相似度评价指标是通过距离来衡量的Ｈ。。“］．　在本文中采用的是基于余弦相似度的　一ｍｅａｎｓ算法对原始矩阵的相似矩阵进行聚类．具体步骤如下：　１）随机选取　个文本作为初始聚类中心点；　２）利用余弦相似度计算公式，计算每个文本与这些中心文本的相似度，并根据最大相似度原则重新对　相应样本进行划分；相似度的计算公式如下：　

∑ｄｉ　×ｄ　ＣＯＳ　ｆ＝ｓｉｍ（ｄ　，　ｆ）＝—　ｍ＝二ｌ＝—　：　＝＝　（３）　

√　√　其中，ｄ　、ｄ　为不同的文本向量．如果２个向量的夹角越小，它们的相似度就越大，反之，夹角越大，它们的相　似度就越小．　３）最后重新计算每个簇中文本的均值作为新的簇中心点．　

２基于预聚类的潜在语义文献检索的算法描述　针对现有的潜在语义检索方法检索时，需耗费大量时间计算查询向量与每个文本向量间的相似度，本文　提出采用预聚类的方法对其加以改进，在对文档集进行预处理时，在潜在语义分析的基础上应用基于余弦相　似度的聚类算法，将文档集中的文档划分为不同的聚类簇，并得到不同聚类簇的中心点；在检索时，直接计算　查询向量与各聚类中心的相似度，进行检索．流程图如下所示：　

｝　计算查询向　对蠢　Ｈ　攀　卜　对矩阵　进行Ｈ对　ｌ　量与聚类中　Ｈ返器　｛　ＳＶＤ分解，构　造近似矩阵　心的相似度　

ｌ　文档集的预聚类处理　：　：　检索过程　Ｌ…一…一…一一一…一…一一…一…一一一…一ｊ　Ｌ一一…一…一一…一一…　

图１基于预聚类的潜在语义检索结构图　

２．１文档集的预聚类处理　１）文档预处理．首先采用分词工具对文本集中的文本进行分词处理，然后根据停止词表去除停止词．　２）词汇～文档矩阵的构建．对预处理得到的词汇进行权重计算，选择适当的阀值获取特征词，构建词汇　

一文档向量空间矩阵Ａ用于奇异值分解．由于文献中在不同位置的词汇其对文本的重要程度也不同，所以　针对文献的这一特点，本文重新给出一种基于位置权值（加　）的权重计算公式：　／＾，　、　＝　×　ｄ×　ｌ。　＝　×ｌｏｇ２Ｉ　１　Ｔ＋０．０１　ｌ×　ｌ。　（４）　

＼，　／　其中　为特征值词频，即某个特征项ｉ在文本中出现的次数　为倒排文档频率．　＝ｌｏｇ　（Ｎ／ｎ　＋０．Ｏ１）；位　

置权重　的取值为：标题３，摘要和尾段２，其他正文１．　３）奇异值分解．对上一步中得到的词汇一文档矩阵进行奇异值分解，得到左奇异值矩阵ｕ、右奇异值矩　阵　和对角矩阵　，选取适当的截断值Ｋ对分解得到的矩阵进行截取，本文采用文献［１１］中宋涛提出的选　第３期　和晓萍，李迪，王米利，等：基于预聚类的潜在语义分析模型文献检索研究　２５９　择使用奇异值递减过程中速度的拐角点作为ｋ值，最后采用公式（２）对其进行重构，得到矩阵Ａ的相似矩　阵Ａ　．　４）聚类．对相似矩阵Ａ　进行聚类，本文采用基于余弦相似度的ｋ—ｍｅａｎｓ聚类算法，具体步骤如１．２节　所述．　２．２　检索过程　１）相似度计算．对查询语句进行预处理，生成查询向量ｇ．采用如下公式分别计算查询向量鼋与各聚类　中心点的相似度，根据计算所得的相似度大小值，选择与查询向量ｇ相似度最大的簇．　ｋ　∑ｑ　×ｃ　

ＣＯＳ　＝ｓｉｍ（ｑ，ｃ）＝　＝　．　（５）　

√　ｇ　√　。ｃ　

其中，向量垡为查询向量，ｃ为聚类中心．　２）检索．计算查询向量与上一步中选定的簇中的元素的相似度，并根据相似度大小，对簇中的文献进行　排序，返回给用户．　

３实验及分析　３．１评价指标　本文采用查全率（ｐｒｅｃｉｓｉｏｎ）和查准率（ｒｅｃａｌ１）作为检索效果的评估指标．　查全率＝　鬻　；　

查准率＝　．　３．２实验结果及分析　由于实验条件有限，在本文实验中，仅以“计算机”、“民族”、“经济”、“科学”、“生态”、“文化”、“政治”、　“教育”为初始关键词在知网上进行查询，从返回的结果中选择相关文献各２０篇作为实验数据．　１）采用中科院的汉语分词系统ＩＣＴＣＬＡＳ５０＿Ｗｉｎｄｏｗｓ＿３２一Ｃ对所选的实验数据进行分词处理，利用停止　词表去除停止词，采用公式（４）对剩余的词汇进行权重计算，选择其权重值最大的１０个词汇作为文本的特　征词，构建原始词汇一文本矩阵Ａ．　２）然后对词汇一文本矩阵Ａ进行奇异值分解，由于奇异值递减过程中速度的拐角点为３０，所以截断值　ｋ＝３０，利用公式（２）重构词汇一文本矩阵，得到矩阵Ａ　．　３）再利用基于余弦相似度的ｋ—ｍｅａｎｓ聚类算法对矩阵Ａ　按列向量进行聚类，这里我们将其分为ｌ８　类，并计算出各聚类簇的中心点．　４）最后假设查询关键词ｑｌ＝（计算机网络，网络故障，　网络维护），ｑ２＝（民族文化传承，教育），ｑ３＝（文化贸易，文　化产业），ｑ４＝（区域经济，经济增长），ｑ５＝（科学发展，创　新），ｑ６＝（教育改革，社会转型），转换为查询向量，利用公式　（５）计算查询向量与各聚类簇中心点的相似度．　５）通过计算得出查询向量留１与簇Ｃ４相似度最大，查询　向量ｇ２与簇ｃ２相似度最大，查询向量ｇ３与簇ｃ５相似度最　大，查询向量　与簇Ｃ１２相似度最大，查询向量留５与簇ｃ８　

表１　检索的查全率和查准率　

相似度最大，查询向量留６与簇ｃ７相似度最大，最后再分别对簇Ｃ４、ｃｆ２、Ｃ５、Ｃ１２、Ｃ８、Ｃ７中各元素与口１、ｇ２、　ｇ３、　、ｇ５、窜６进行相似度计算，按相似度从大到小排序，输出结果．　从表１中可以看出，本文提出的检索方法具有较高的查全率和查准率．同时，在实验的过程中发现，该方　法的检索结果与聚类的结果有着直接的关系，必须保证聚类的准确率和召回率．　在实验中，通过假设查询向量来计算检索的时间，传统的潜在语义检索方法的平均检索时间为０．０３３　Ｓ，