装备采办知识搜索引擎关键技术研究

胡欣杰, 龚 波, 苏俊杰, 王 琳

(装备学院信息装备系,北京101416)

装备采办知识搜索引擎关键技术研究

胡欣杰, 龚 波, 苏俊杰, 王 琳

(装备学院信息装备系,北京101416)

研究并设计了装备采办知识搜索引擎系统结构,包括搜索模块、索引模块、检索模块、查询扩展模块和结果聚类模块。就装备采办知识管理搜索关键技术查询扩展模块和结果聚类模块,提出了相似性度量的渐进直推式支持向量机(similarity measurement progressive tranductive support vector machine,SMPTSVM)查询扩展模型,以及基于人工免疫算法的搜索引擎结果聚类算法。实验结果表明,该模型和算法提高了搜索结果的查全率、查准率及搜索结果的平均聚类精度。

装备采办;查询扩展;支持向量机;聚类

1 问题的提出

随着装备采办知识管理系统内部知识的爆炸式增长,采办工作人员势必会淹没在知识海洋中,如何帮助装备采办人员快速、准确地从浩瀚的知识资源中寻找真正所需的信息,成为装备采办知识管理系统建设的主要目标之一,对装备采办实施知识管理已成为我军提高采办效益的必然选择。装备采办知识管理系统能够实现对知识的有效组织、管理和应用,而知识搜索引擎作为知识管理系统中的核心组成,是采办人员获取知识、学习知识的重要工具,有效提高了知识的使用效率。因此研究具有良好知识搜索性能的装备采办知识管理系统具有较大的军事意义和实际应用价值[1]。

搜索引擎作为一种信息检索技术,能够以一定的策略在信息资源中搜集、发现信息,对信息进行理解、提取、组织和处理,并为用户提供检索服务,从而起到信息导航的作用。一个高效的装备采办知识搜索引擎能够促进系统内部知识的流转,加快装备采办人员查找信息的速度,对提高装备采办工作效率具有重要意义。

2 装备采办知识搜索引擎系统结构

装备采办知识搜索引擎为知识汇聚、知识发现、知识聚类、知识门户的构建等提供支持,通过搜索引擎技术完成知识管理。知识搜索引擎建立在明确的知识来源基础之上,根据用户的身份与请求,回馈最准确恰当的知识,为特定用户提供搜索服务[2-3]。装备采办知识搜索引擎系统主要由搜索模块、索引模块、检索模块、查询扩展模块和结果聚类模块组成,系统框架结构如图1所示。

图1 装备采办知识搜索引擎系统结构

搜索模块搜集系统内部的网页资源和知识库中的内容,并将获取的网页资源存储在文件数据库中;索引模块是对收集的文件进行分析,提取其中的重要信息,并针对这些信息建立索引数据库;检索模块提供了用户与系统进行交互的接口,通过接口,用户提交查询请求,检索模块对该请求进行解析处理,将处理后的查询请求提供给索引子系统,在索引数据库中查找相关信息,并根据一定的相关度算法对查询到的结果进行相关度排序,返回搜索结果;查询扩展模块根据初次检索返回的结果进行查询重构,解决用户“词不匹配”问题,提高搜索结果的查全率和查准率;结果聚类模块根据返回结果之间的相似性进行划分,将内容相近的结果划分为一类并用标签标志,用户根据标签在相应类别中查找,缩短了信息查找时间。

查询扩展模块和结果聚类模块是本系统关键技术,帮助用户快速定位所需信息,提高搜索引擎性能。本系统所实现的查询扩展模块,提出了相似性度量的渐进直推式支持向量机(SMPTSVM)查询扩展模型,结果聚类模块提出基于人工免疫算法的搜索引擎结果聚类算法,实验和仿真结果表明提高了搜索结果的查全率、查准率及搜索结果的平均聚类精度。

3 关键技术研究

3.1 SMPTSVM查询扩展模型

装备采办知识搜索查询扩展模块是根据初次检索返回的结果重新构建查询,实现词匹配,提高搜索结果的查全率和查准率。在本系统的查询扩展模块中,提出了SMPTSVM查询扩展模型,并通过实验验证了其有效性。SMPTSVM查询扩展模型扩展了相似性度量的PTSVM(progressive tranductive support vector machine)模型,引入了渐进直推式支持向量机的概念。

基于支持向量机的查询扩展模型将信息检索中的查询扩展看作1个分类问题,采用分类模型将候选词项分为“相关”和“不相关”2类,将标记为“相关”的词项加入到原始查询中,以解决词的不匹配问题。然而查询扩展与普通的分类问题相比又有其特殊性,不能够用普通的SVM(support vector machine)模型来解决查询扩展问题。根据查询扩展具体应用背景,基于SMPTSVM的查询扩展模型应主要解决以下2个问题：样本的向量表示和目标函数的定义。

3.1.1 SMPTSVM查询扩展模型算法[4-7]

SMPTSVM算法在标记无标签样本时综合了周围样本和通过分类模型计算的标签值对其的影响,使标签值的确定更加准确,减少了标签的重置率。基于SMPTSVM的查询扩展方法如下。

步骤1 由多次搜索结果的特征值构建(query,word)特征向量;

步骤2 随机选取n个(query,word)样本进行人工标记,将相关的样本标记+1,不相关的样本标记-1,并选择m个未标记样本(m≫n);

步骤3 按上述描述的方法对SMPTSVM分类模型进行训练,得到分类效果较优的分类函数f;

步骤4 在索引库中,按查询query进行初次检索,以返回的前K篇文档为扩展词项来源;

步骤5 对返回结果i进行去噪、分词处理,过滤掉不符合条件的词项,对剩余词项构建(query,word)形式的表示向量;

步骤6 利用步骤3训练所得的分类函数f计算每个(query,word)向量的标签值label,并将label=+1的结果存入结果推荐矩阵;

步骤7 若i＜K,返回步骤5继续执行,否则跳到步骤8;

步骤8 根据结果推荐矩阵中total的值,将total值最大的前j个词项加入到原始查询中构成新的查询newquery。

3.1.2 实验设计及结果分析

装备采办知识搜索引擎是基于装备采办知识管理系统的信息检索系统,原型系统设计了3个查询集进行测试,每个查询集合包括10个查询, 3个查询集合如表1所示。

表1 查询集合

其中Query1包含1个关键词,Query2包含2个关键词,Query3中包含3个关键词。

实验采用查全率和查准率作为评价标准。将本文提出的SMPTSVM与标准的SVM方法、局部上下文分析的查询扩展方法进行了比较。选择初始检索后返回的前10篇文档作为相关文档集,然后根据各种算法的选择策略来评估相关文档集中的关键词,选出得分最高且没有在初始查询中出现的20个关键词来重构查询,并进行二次检索。由于在返回结果中,人们往往更关注排名靠前的结果,因此实验选取每次查询返回的前50篇文档,采用人工评判的方式分别统计3种方法在各查询集合上的查全率和查准率,3种方法的查询性能量化对比结果如表2所示。

表2 查询性能对比

从3种方法在不同查询集合上的对比可以看出,本文提出的基于SVM的查询扩展模型与其他2种方法相比查全率和查准率都有了明显的提高,具有更优的检索性能。实验结果表明,与传统查询扩展方法相比,搜索结果的查全率提高了6.67%,查准率提高了6.81%。

3.2 基于人工免疫算法的搜索引擎结果聚类算法

装备采办知识管理搜索引擎的搜索结果聚类模块,针对现有算法自适应差的缺点,将人工免疫思想引入搜索结果聚类过程,构造了基于人工免疫算法的搜索结果聚类方法,采用自生长、自组织的进化策略得到树状拓扑结构的抗体种群,通过该种群获得的聚类中心能够较好地拟合搜索结果在向量空间中的分布形状,提高了算法的聚类精度及运行效率。

目前常用的聚类算法有：划分聚类方法、层次聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法、K-Means算法等。与K-Means算法原理相同,本文利用人工免疫思想改进的聚类算法也是基于K-Nearest准则的聚类,该算法主要分为2个步骤：构造树状拓扑结构的抗体种群;选取记忆抗体作为整个抗原种群的码书(codebook),然后采用K-Nearest准则对搜索结果进行聚类。具体方法为,首先从搜索引擎结果中提取出有效的特征向量,并采用树状种群拓扑结构,采用自生长、自组织的种群进化策略对特征向量进行有效聚类。通过自适应的进化迭代,抗体由单一个体逐渐进化为一定规模的种群,其中的个体可以通过对种群拓扑结构的解析划分到不同的聚类。

基于人工免疫算法的搜索引擎结果聚类过程如下。

步骤1 根据迭代结束后生产的抗体种群,通过上述代码得到每个类别的初始聚类中心。

步骤2 用值在(0,1)之间的随机数初始化隶属度矩阵U,使其满足如下约束条件。

步骤3 判断停止条件,若满足则输出聚类结果,将搜索结果根据隶属度矩阵划分到相应的类别中;否则转至步骤4。

步骤4 根据式(1)更新隶属矩阵U。

其中：m为可调节参数,用来控制算法柔性。

步骤5 根据式(2)计算新的聚类中心,返回步骤3。

在搜索结果聚类过程中,由高效的人工免疫算法生成的初始聚类中心能够很好拟合结果向量在空间中的分布形状,可以减少聚类过程的迭代次数,聚类效果明显优于K-Means这类随机初始化聚类中心的方法。

1)实验设计。设计8个独立的查询词{query1=“合同”,query2=“项目管理”,query3=“装备”,query4=“采办”,query5=“维修保障”,query6=“研制”,query7=“信息化”,query8=“装备科研”}进行实验。对于每个查询词,选取返回结果的前100项作为实验数据,搜索返回结果经过预处理后建立向量空间模型,分别采用本文提出的人工免疫聚类算法以及K-Means算法进行对比实验。人工免疫算法的参数如表3所示。

表3 实验采用的参数值列表

对于每个参与实验的算法,比较该算法生成的聚类结果与人工分类得到的聚类结果的相似度,采用平均聚类精度Jacp作为衡量算法准确度的指标,Jacp计算公式如下[5,8-9]：

式中：k是算法生成的聚类个数;Pj是第j个聚类的准确率,即在该聚类中与采用人工方式判断一致的结果数占人工分类总数目的比重。对比结果如图2所示。

图2 2种算法在8个独立查询词上的平均查准率对比

2)结果分析。从图2对比结果可以看出,与K-Means聚类算法相比,基于人工免疫的聚类算法在8个查询词上的平均聚类精度得到明显的提高,前100项返回结果的平均聚类精度达到72%左右。特别是在query3、query4、query5和query6上,本文算法体现出明显的优越性。而KMeans聚类算法在query7上也有较高的平均聚类精度,但在query6上平均聚类精度仅有50%左右,这是由于K-Means选取的聚类中心具有随机性,有时候并不能很好的体现数据的真实分布情况,导致了聚类性能的不稳定。人工免疫聚类算法通过多次抗原刺激构造的抗体种群,能够较好地拟合搜索结果在真实数据空间的分布形状,从而保证了下一步聚类的有效性,因此聚类效果较为稳定。

4 结束语

本文以装备采办信息化训练与研究平台为背景,主要围绕装备采办知识管理系统和知识搜索引擎相关技术进行研究。知识搜索引擎作为装备采办知识管理系统的一种基础服务,对加速系统内知识的流转、共享和创新具有重要的作用,可以有效提高装备采办工作效率。

References)

[1]战竹杰,白凤凯.装备采办知识管理研究[J].装备指挥技术学院学报,2010,21(1)：35-38.

[2]U.S.Department of Defense.Quadrennial defense review report[R/OL].[2011-02-10].http：//defense.com/products/ w/win-t-pop.ht.

[3]王沙聘,高学东,赵澄谋.新军事变革：武器装备采办中的知识意识[J].现代情报,2007(3)：209-211.

[4]彭新俊,王翼飞.双模糊渐进直推式支持向量机算法[J].模式识别与人工智能,2009,22(4)：560-566.

[5]张选平,蒋宇,袁明轩.一种基于概念的信息检索查询扩展[J].微电子学计算机,2006,23(4)：110-114.

[6]沈新宇.基于直推式向量机的图像分类算法研究与应用[D].北京：北京交通大学,2007：33-36.

[7]李盼池,许少华.支持向量机在模式识别中的核函数特性分析[J].计算机工程与设计,2005,26(2)：302-304.

[8]DASGUPTA D.Advances in artificial immune systems[J]. IEEE Computational Intelligence Magazine,2006,1(4)：40-49.

[9]冯栋梁.基于人工免疫原理的聚类问题研究[D].哈尔滨：哈尔滨工程大学,2008：50-53.

(编辑：李江涛)

Research on the Key Technology of Equipment Procurement Knowledge Searching Engine

HU Xinjie, GONG Bo, SU Junjie, WANG Lin

(Department of Information Equipment,Equipment Academy,Beijing 101416,China)

This paper researches and designs the equipment procurement knowledge searching engine system structure.The system structure has five modules,including scouting module,indexing module,searching module,inquiring extension module and clustering module.About extend module and clustering module,it proposes similarity measurement progressive tranductive support vector machine(SMPTSVM)inquiring extension model and search engine results clustering algorithm based on artificial immune algorithm.The experimental results show that this method can improve the recall ratio,precision and the average clustering precision of the search results.

equipment procurement;inquiring extension;support vector machine;clustering

TP 393

2095-3828(2014)02-0090-04

ADOI10.3783/j.issn.2095-3828.2014.02.021

2013-05-08

部委级资助项目

胡欣杰(1963-),女,教授.主要研究方向：装备信息系统.