基于RANSAC潜在语义分析的专家库检索

摘要：随着信息技术的发展，对信息的检索和利用越来越显示出其重要的作用。在知识产权专家库的应用中，由于信息表达的差异化和碎片化，信息检索的准确率和有效率都有待提高。将潜在语义检索方法应用于专家库系统中，可以大大提高检索的准确率和有效率，并且可以避免数据库以及外围系统的重复更新，极大地节约了开发和维护的成本，具有十分重要的实际意义。该文结合RANSAC以及潜在语义检索算法给出了一种适用于专家库信息检索的搜索算法。实验结果表明，该方法在实践中取得了预期的效果。

关键词： RANSAC；潜在语义分析；奇异值分解；聚类分析

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）05- 1141-03

Expert Database Retrieval Based on RANSAC and LSA Algorithm

CAI Jia-cheng

（Suzhou Intellectual Property Rights Center， Suzhou 215104， China）

Abstract： With the development of information technology the retrieval and use of information becoming more and more important. In the case of experts in intellectual property library， because of the differentiation and fragmentation of information expression， accuracy and efficiency of information retrieval is not good enough for us. By applying LSA technology to Municipal Intellectual Property expert database retrieval system can improve the accuracy and efficiency of retrieval results. It can also avoid needless updating of database and retrieval system which greatly save the cost of development and maintenance of the retrieval system. In this paper we introduced an expert database retrieval method based on RANSAC and LSA. The experimental results show that this method gets the expected effectiveness.

Key words：RANSAC；latent semantic analysis （LSA）；singular value decomposition （SVD）；cluster analysis

1 概述

近年來，随着互联网技术的发展，信息化已经渗透到企业与政府部门的各个重要环节。苏州知识产权专家库作为专家信息的存储与检索平台，为政府各部门进行知识产权专家信息检索，知识产权预警以及知识产权相关项目评审提供了统一化的信息搜集和过滤支持。在庞大的知识产权库中，由于录入人员、时间、方式的多样化，特别是随着时间的推移会出现一些新兴的领域以及新兴名词，导致对专家所擅长的领域以及兴趣方向描述方式不尽相同。而对于专家库录入界面进行规约化的做法会大量耗费重复开发的人力物力，并且不能做到一劳永逸。而引入基于潜在语义的搜索方法，有助于对数据库中各种专家信息进行聚类和分析，并且提取统一化的关键词作为出口。从而无需对以前的数据进行重复的整理或者反复改变既有系统的录入方式并调整数据库结构，从而大大节约了管理与维护成本。

本文，根据知识产权专家相关特征量大相似表述多，并且在实际应用中对搜索精度和效率的特别要求设计了基于层次化特征潜在语义空间的聚类方案来增加搜索准确度，通过使用RANSAC方法提高了搜索速度。从而实现了对专家信息检索在精度和效率上的需求。

2 基于潜在语义的专家库检索算法

2.1 RANSAC算法

专家库中的数据特征，具有数量庞大，但是特征方向性明显，同时包含散乱噪声的特点。为了提高精确度与后期计算速度，该文使用了RANSAC算法对数据进行预处理。噪声环境下的鲁棒性估计算法，常用的有M-估计器、最小二乘和RANSAC（Random Sample Consensus）方法。而由Fishler和Bolles在1981年提出的RANSAC算法被认为是最好、也是使用最广泛的方法，它甚至能处理50%噪声情况下的数据 [1]。RANSAC算法利用一小部分数据作为内点得到初始值，然后根据初始值统计数据集中所有的内点。这种估计方法使其能最大限度地减少噪声及外点的影响。但这也使得算法精确性和收敛速度受初始参数值的影响很大。要提高RANSAC算法性能，必须建立一个良好的初始参数值估计方法。

2.2 潜在语义分析

潜在语义分析 （Latent Sereantic AnMysis，LSA）是一种用于自动地实现知识提取和表示的理论和方法，它通过对大量的文本集进行统计分析，从中提取出词语的上下文使用含义，是一种通过建立概念空间的方式来获得对词语和文档的语义理解和语义联系[2]。它通过统计方法，提取并量化这些潜在的语义结构，进而消除同义词、多义词的影响，提高文本表示的准确性。LSA思想最初应用于文本信息检索领域，有效地解决了同义词和多义词的问题，随着应用领域的不断拓展，LSA在信息过滤、信息分类、聚类、交叉语言检索、信息理解、判断和预测等众多领域中得到了广泛的应用[3，4]。

2.3 算法基本思想

基于RANSAC的潜在语义搜索算法的主要思想是，在原始的文档矩阵基础上，对数据先进行RANSAC处理，得到新的数据矩阵。在此基础上使用SVD提取特征向量，最后通过词频信息对特征进行层次化分类。具体算法流程如下：

1）生成词-文档矩阵X。从专家库，专家特长字段抽取原始文本并按照既定的自然语言分割标记如：标点空格斜杠等自动筛选出关键词，并将抽取的关键词生成关键词矩阵X。

2） 使用RANSAC算法对原始矩阵X进行处理获得精简数据集R。对高维度海量的关键词矩阵进行预处理，运用RANSAC算法对原始数据矩阵进行精简，排除关键词矩阵中孤立的、低效益的特征点。此算法不管是在数据量，还是在空间维度上，都能对原始数据进行精简，同时还能有效排除孤立的噪声数据。

3） 对新数据集进行SVD分解提取主成分得到特征矩阵T。RANSAC简化、降维处理，大大减少了提取主成分的时间，同时也使得矩阵特征矩阵T中的特征区分度更高、更为明显。

矩阵的奇异值分解：这里，R为初始矩阵，设r为m*n实矩阵，且n阶方阵[RTR]的非0特征值的算术平方根为矩阵X的奇异值。则：

[R=T×S×TD] （1）

其中，[Tm×r=（t1，t2，…，tr）]为正交矩阵，其中[t1，t2，…，tr]為R的左奇异向量，并且是[RRT]的特征向量；

[Sr×r=diag（σ1，σ2，…，σr）] （2）

[Sr×r]为对角矩阵，[σ1，σ2，…，σr]为X的所有奇异值，并满足以下关系：[σ1≥σ2≥…≥σr>0]； [Dn×r=（d1，d2，…，dr）]为正交矩阵，其中[d1，d2，…，dr]为R的右奇异向量，并且是[RTR]的特征向量。

设定k值，保留[σ1，σ2，…，σk]，同时只保留T和D的前k列，得到原矩阵的近似矩阵R。

[R=T×S×DT] （3）

4）对各个特征向量进行相似度分析，并使用词频信息对其进行分类。根据专家库具体应用的特点与需求，使用词汇与词汇的关进进行相似度分析，并进行聚类，生成相似度聚类矩阵E。最后使用词频权重算法对其进行加权变换形成最终特征空间。

对上一步得到的近似矩阵R进行正向乘法。[R^' R'T=T'S'D'T?D'S'T T'T]，这里，[S'=S'T，D'D'T）=I]，因此：

[R' R'T=T' S' I?S'T'T）=T'S'2 T'T] （4）

其中，矩阵[R' R'T]的第i行第j列表明了词汇i和词汇j的相似程度。

求解（4）所得到的特征矩阵可称之为相似度聚类矩阵E。矩阵E所描述的相似关联度，仅与原始文档数据中关键词关联信息相关。而在实际专家库检索应用中，各关键词存在不同的重要级别。如：与物联网关联更多的，应该是传感器与嵌入式技术，而与软件技术或者工业设计关联度较弱。每一个特征词汇对文档的贡献度不尽相同。故本文使用词频权重对相似度特征矩阵进行权重赋值。这里采用了直接而简单的词频权重：

[ajk=fjk] （5）

由于专家库的应用需求，该文中的权重由两部分构成：局部权重和和全局权重。局部权重记作LW（i，j），全局权重记作GWT（i，j）。经过权重分配后的相似度聚类矩阵可表示为[f?E]。

5） 最后，根据原有矩阵的截断奇异值进行近似计算，即计算矩阵[RK|A]的奇异值分解，其中：[RK=TK SK DTK]为原矩阵的截断奇异值矩阵，A为新增数据集。并通过SVD-Updating算法更新数据库。

3 实验及分析

本文方法在市知识产权据专家数据库上进行了一系列测试，其命中率和查准率如表1所示：

表1 搜索对比表

[特征值＼&测试用例＼&本文方法＼&传统检索＼&感兴趣数据＼&本文方法＼&传统检索＼&检索结果＼&命中结果＼&检索结果＼&命中结果＼&命中率＼&查准率＼&命中率＼&查准率＼&单关键词＼&地理信息＼&62＼&58＼&58＼&58＼&62＼&94%＼&93%＼&100%＼&93%＼&计算机科学＼&105＼&100＼&65＼&62＼&100＼&95%＼&100%＼&95%＼&88%＼&GIS＼&62＼&62＼&20＼&20＼&62＼&100%＼&100%＼&100%＼&32%＼&多关键词＼&计算机科学，GIS＼&167＼&160＼&85＼&85＼&170＼&95%＼&94%＼&100%＼&50%＼&语义表述＼&地理信息，计算机技术专家＼&52＼&50＼&0＼&0＼&60＼&100%＼&83%＼&0＼&0＼&计算机资深

专家＼&54＼&52＼&0＼&0＼&57＼&100%＼&91%＼&0＼&0＼&]

从以上实验数据分析可以得到如下结论：

1）对于单关键词的中文检索，在精确含义词汇检索中本文方法与传统方法差异不大，而在广义或者模糊含义词汇的检索中，该文方法能够检索出更多有价值的信息，查准率更高；

2）对于单关键词的英文检索，只能检索到包含相同英文字母的信息，不能获得其真实本意不能查到相关中文信息，其命中率和查准率都比较低，而本文方法则能够取得较为满意的结果；

3）对于多特征中英文混合检索，仅仅靠关键词匹配的传统检索搜索出的结果不能令人满意，而本文方法同样达到了比较高的准确率，结果令人满意；

4）对于语义方式表述的特征样本，该文方法能够检索出有价值的数据，并且查准率较高，而相反在传统检索方法中，由于没有出现直接关键词，故无法获得检索结果。

参考文献：

[1] Bartoli Adrien， A Random Sampling StrategyFor Piecewise Planar Scene Segmentation[J]. Computer Vision and Image Understanding， 2007， 105（1）： 42-59.

[2] 叶昭辉，杨高峰，杨岳湘.一种基于潜在语义分析的中文网页自动摘要方法[J].广西大学学报：自然科学版，2012，37（2）：342-345.

[3] 蔡嘉诚.潜在语义索引技术在知识产权专家库中的研究与应用[D].苏州大学硕士论文，2010.04.

[4] 杨文清.基于Web文档库的中文全文检索技术与实现[D].南京大学计算机科学与工程系硕士论文，1998.

[5] Ishii，Murai，Yamada.Text Classification by combining Grouping[J]，LSA and KNN，Computer and Information Science，July 2006：148-154.

[6] Sudarsun.S，Venkatesh Prabhu.G Sathish Kumar.V.Role of weighting on TDM in Improvising PerformanceofLSA on TbXt Data[C]，Annual India Conference，2006，Sept.2006：1-6.

[7] 余正涛，樊孝忠，郭剑毅，等.基于潜在语义分析的汉语问答系统答案提取[J].计算机学报，2006，29（10）：1889-1893.

[8] 盖杰，王怡，武港山.基于潜在语义分析的信息检索[J].计算机工程，2004（30）.

[9] 戚涌，徐永红，刘凤玉.基于潜在语义标引的Web文档自动分类[J].计算机工程与应用，2004（22）：28-31.