短文本相似度（共6篇）
短文本相似度 篇1
0 引言
中文实体是中文文本中名词性词汇或短语的统称, 本文处理的中文实体, 包括电影、电视剧、电视节目、软件应用、电子游戏和歌曲的名称, 在互联网上常用短文本描述。一般认为, 短文本是长度不超过200个字符的文本[1], 具有词语稀疏、语义离散和用词随意等特点[2]。实体的定义通常由实体描述短文本给出, 实体描述短文本间的相似度即是对应的实体间相似度。短文本间相似度计算是近年来自然语言处理的研究热点之一, 被广泛应用于信息检索、反作弊系统、智能问答系统、智能推荐系统、文本自动分类、机器翻译中。
文本间相似度计算方法大多通过统计分词后文本的词频信息, 将文本建模为向量, 利用向量间余弦相似度、Jaccard相似度等方法计算文本相似度。文本间相似度也可以通过文本分类来近似。文本间相似度计算方法通常只考虑文本中单个词语的统计特性而没有考虑文本整体的语义特性, 并在处理短文本时会生成稀疏的高维向量, 容易出现语义漂移问题。
本文利用《知网》的语义知识资源和概念网络, 针对短文本特点, 提出了短文本间语义相似度部分和短文本分类部分相结合的实体描述短文本间相似度计算方法。
1 相关工作
1.1《知网》
《知网》是一个以汉语和英语的词语所代表的概念为描述对象, 以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库[3]。词语的语义在《知网》中通过一个或多个概念来描述, 而每一个概念由义原来描述。义原是《知网》中最小的、不可再分割的语义单位, 《知网》作者用1 600多个义原对8万多个中文词汇进行描述, 义原的上下位关系为所有义原建立起一个包含多个子树的多层义原网络[4]。
1.2 基于《知网》的文本间语义相似度计算
义原间相似度的计算方法可以分为两类:基于节点之间路径长度的方法和基于节点之间共有信息大小的方法[5]。基于节点之间路径长度的方法需要计算两个节点在义原网络上的最短距离, 基于节点之间共有信息大小的方法需要计算两个节点最近的共同祖先节点含有的子节点个数。许多学者已经在义原间相似度的问题上做了大量的研究, 如刘群[4]、李峰[5]、吴健[6]、Dekang Lin[7]、Resnik[8]、江敏[9]等。词语间相似度可由义原间相似度合成。
在文本间相似度计算方面, 文献[10]通过统计出两个直接义原集合间的共有信息和差异信息来计算集合间的相似度, 并把该方法引进到词语间和句子间相似度的计算中去。文献[11]基于向量空间模型, 计算关键词的语义相似度并采用最大权匹配方法计算两个文本向量间的相似度。文献[12]强调了除第一独立义原以外其它义原的独立性, 用两个文本中实词间的相似度构成特征矩阵, 递归删除最大元素所在行、得到词语最大组合序列进而计算句子间相似度和段落间相似度。文献[13]在词语间相似度中加入了主要义原对次要义原的抑制因素。
1.3 短文本间语义相似度计算
由于短文本具有词语稀疏和语义离散的特点, 其中包含的信息量有限。通过文本间相似度计算方法得到的短文本间相似度偏差较大。现有的短文本间语义相似度计算方法大多需要构建知识库或利用已有的知识库, 这些方法的普适性普遍较差。
2 实体描述短文本语义相似度计算方法概述
本文从短文本间语义相似度和短文本分类两个部分出发计算实体描述短文本间相似度, 并将两部分相似度的平均值作为实体描述短文本间相似度计算的最终结果。
短文本间语义相似度部分首先根据《知网》义原网状结构中的义原节点深度、义原子节点数量、义原节点间最短路径长度等信息计算义原间相似度, 再通过较小语义单位间相似度计算较大语义单位间相似度, 逐步计算义项、词语和短文本间相似度。
短文本分类部分将短文本分解为义原向量, 再从分解为义原向量的网络语料中抽取特征义原, 训练一个朴素贝叶斯分类器, 并通过两篇短文本的分类结果计算两者之间的相似度。
3 短文本间相似度计算方法的语义相似度部分
3.1 义原间相似度计算
本文分别采用基于节点之间路径长度的方法和基于节点间共有信息大小的方法计算义原间相似度。基于节点之间路径长度的方法以李峰[5]等人的公式为基础:
其中, S1和S2表示两个义原, distance (S1, S2) 表示两个义原在《知网》义原网状结构上的最短路径长度, depth1和depth2是两个义原在义原网状结构中各自所在的层次, 即义原深度, α是一个调节参数, 代表Sim值为0.5时两个义原的最短路径长度。这个公式利用义原之间的上下位关系, 以两个义原在义原网络上的路径长度作为义原间相似度计算的基础。
本文发现, 在利用公式 (1) 进行义原间相似度计算时, 义原深度较浅的叶节点义原参与的相似度计算结果普遍偏低, 而义原深度较深的非叶节点义原参与的相似度计算结果普遍偏高。由于《知网》的义原形成的是一个网状结构而不只是一颗义原树, 义原的绝对深度不能直接反映其相应的具体程度。本文提出”义原相对深度”的概念来表达义原的具体程度, 义原相对深度可以通过义原深度和义原所在树深度计算:
其中, depth1是义原在义原网状结构中的深度, length (treeof (S1) ) 是义原S1所在的子树中, 经过S1的根节点-叶节点路径的最短长度。
本文提出基于节点之间路径长度的公式:
这个公式可以平衡”event|事件”树等深度较大的树对相似度计算的影响, 使位于深度较小的树深层的义原也可以获得较大的相似度值。
本文在Dekang Lin[7]的公式基础上引入义原相对深度, 得到基于共有信息的义原间相似度计算公式:
其中, p (S) 表示两个义原最近公共父节点的子节点个数与其所在义原树中所有节点个数的比, p (S1) 和p (S2) 是两个义原连接的节点个数与其所在义原树中所有节点个数的比。deep (S1) 和deep (S2) 表示两个义原用 (2) 式计算得到的相对深度。
本文将 (3) 式和 (4) 式结果的平均值作为义原间相似度计算的结果。
3.2 义项间相似度计算和词语间相似度计算
《知网》中用于描述一个实词义项的特征结构可以分为四个部分[4]:第一独立义原描述式、其它独立义原描述式、关系义原描述式和符号义原描述式。
两个义项间的整体相似度可以表示为:
其中, βi (1≤i≤4) 是用于调节四个部分权重的参数, 且β1+β2+β3+β4=1。
不同义项包含的各类义原对描述义项起到的贡献不同。《知网》中不同词语所对应的义原数量差别很大, 如果将四个部分的权重参数βi (1≤i≤4) 设置为常数, 会导致一定程度的偏差。
本文根据参与义项间相似度计算的两个义项的义原分布情况, 为其动态设置权重:
其中, ci (1≤i≤4) 是两个义项中四种义原的合计数量。
计算两个词语间的相似度时, 本文把相应的义项两两结合, 形成一个完全二分图, 计算二分图每条边上两个顶点间的相似度, 取相似度的最大值作为两个词语间的相似度。
3.3 短文本间相似度计算
本文用词语间相似度计算短文本间相似度, 采用文献[12]的方法, 建立起一个相似度特征矩阵, 并通过词语间相似度的最大组合序列计算文本间相似度。
在计算短文本间相似度时, 本文统计《知网》中所有词语的tf-idf值, 利用参数来降低与高逆文本频率词、单字词和多义项词相关的相似度计算结果:
其中, c1、c2、c3分别是用于降低高逆文本频率词、单字词和多义项词参与的词语相似度的参数。整句相似度由各集合加权平均得到。
4 短文本相似度计算方法的短文本分类部分
本文将实体描述短文本分解为义原向量, 根据短文本的义原分布情况为其分类, 再根据分类结果计算实体描述短文本间相似度。短文本语义相似度方法和短文本分类方法输出的相似度平均值即是实体描述短文本间相似度的最终结果。
4.1 用义原向量描述短文本
短文本分类部分用义原向量来表示短文本。本文采用文献[14]提出了将文本根据义原系数分解为义原向量的方法, 并结合文献[15]的概念排歧方法。系统设计如图1所示。
4.2 特征抽取和模型训练
为了得到一篇短文本属于各个分类的概率并保持较高的计算效率, 本文选择朴素贝叶斯分类器来为实体描述短文本分类。研究将每个实体的描述短文本按4.1的方法整理为义原向量。考虑到非叶节点义原的表意模糊, 本文从义原向量中删除所有非叶节点义原。
生成义原向量之后, 本文需要在叶节点义原中抽取出n个适用于分类的义原作为分类特征。文献[16]提出了四种特征抽取方法:文档频率、信息增益、CHI统计和互信息。本文选择信息增益 (IG) 法、χ2统计量 (CHI) 法和互信息 (MI) 法作为特征选择的方法。当一个义原的信息增益、CHI值和互信息均大于特定阈值时, 这个义原作为表达文本的特征。
本文将每个文本表示为一个n维特征向量, X={x1, x2, …, xn}, 其中xi表示文本中对应义原的出现次数, 以九类电影简介信息生成的特征向量作为训练集, 建立朴素贝叶斯分类模型。
4.3 相似度计算
本文通过朴素贝叶斯分类模型, 计算两篇短文本属于每一个类别ci的后验概率P (ci|X) , 并将其整理为向量形式:Y1= (c1first, p1first, c1second, p1second) 和Y2= (c2first, p2first, c2second, p2second) 。
其中, cfirst为特征向量在朴素贝叶斯分类器中后验概率最高的分类, pfirst为其所对应的后验概率, csecond为特征向量在朴素贝叶斯分类器中后验概率次高的分类, psecond为其所对应的后验概率。通过向量Y1和Y2计算短文本间相似度的方法如表1所示。
5 实验及结果分析
本文的实验建立在百度知识图谱数据分析竞赛任务一, 即实体相似度计算的基础之上, 并以其评测结果为基准。百度知识图谱数据分析竞赛给出的数据集包括11 463组实体属性数据和8 001组实体间相似度数据。参与实验的实体描述文本平均长度约为159字。
本文用8 001组实体间相似度数据进行训练并通过机器学习得到相似度计算模型, 再用来为1 991组测试数据进行打分。本文方法给出的相似度评分Sc将与百度给出的人工标注结果Sm进行对比, 计算相似度评分向量 (Sc1, Sc2, …, Sc1991) 和标注结果 (Sm1, Sm2, …, Sm1991) 的欧氏距离, 最终测试结果表示为:
短文本间语义相似度计算公式 (7) 的参数设置如表2所示。
为了证明方法的有效性和短文本分类部分的必要性, 本文对短文本间语义相似度的计算结果和两种方法结合后的计算结果分别进行测试, 测试结果如表3所示。
两种方法的综合结果得到了较小的D值, 证明短文本分类方法有效地提高了实体描述短文本相似度计算的准确率。
6 结束语
本文提出了基于分类和语义网的实体间相似度计算方法, 利用《知网》的语义网络资源, 提出了自己的义原间相似度、词语间相似度、短文本间相似度表达式;并将短文本分解为义原向量, 根据短文本的义原频率分布训练文本分类器, 再通过分类结果计算两个文本间的相似度, 最后在实验中分析验证了模型的有效性。
短文本相似度 篇2
关键词：向量空间模型,广义向量空间模型,正交特征项,《知网》,文本语义相似度
文本相似度计算是信息检索, 文本分类, 机器翻译等众多领域的核心技术。随着信息化技术的进一步应用和发展, 人们对文本信息的处理能力要求越来越高, 作为文本处理的基础技术, 文本相似度计算已经成为学者研究的一个热点。
文本相似度的计算方法主要分两类, 一类是基于统计的方法, 另一类则是基于语义理解的方法。统计方法中最具有代表的有向量空间模型 (vector space model, VSM) [1]和广义向量空间模型 (general vector space model, GVSM) [2,3]。
GVSM改善了VSM中文本特征项之间相互正交的假设。另外, Jorg Beck[4]提出了基于主题的向量空间模型 (topic-based vector space model, TVSM) , TVSM中无需特征项之间正交并且灵活的处理特征项的相似度。程玉柱等[5]提出一种组件频率模型 (component frequency model, CFM) , 其中文本被表示为以组件为特征项的空间向量。基于统计的方法得到了广泛的使用, 但这些方法大都基于词频而缺乏语义信息。基于语义理解的方法, 通常使用某种知识库来计算文本中词语的相似度[6—8], 从而进一步计算句子和文本相似度。袁晓峰[9,10]引入深度和区域密度对《知网》义原的相似度进行计算, 并在此基础上实现对词语相似度的计算。白秋产等[11]利用《知网》的义原将文本表示成一种概念向量, 但是由于义原之间并不是正交关系, 该模型仍然没有解决特征项正交的假设, 同时使用一个义原代表词语存在丢失语义的问题, 例如使用义原“软件”表示特征项“病毒”明显丢失了语义信息。
现在在GVSM的基础上, 将文本表示为《知网》义原空间中的向量, 并通过义原的相似度实现文本相似度的计算, 为文本语义相似度的计算提供了一种新的思路。通过对比实验表明, 现提出的算法在文本语义相似度计算方面相对VSM和GVSM有所提高。
1 向量空间模型
向量空间模型是G.Salton等在20世纪70年代提出的, 其思想是把文本特征项看作N维空间中的一个向量, 利用特征项向量表示文本, 通过计算文本向量的夹角判断文本之间的相似度。VSM中, 一般选取词语作为特征项, 每个特征项由其在文本中出现的频率TF (term frequency) 与逆文本频率IDF (inverse document frequency) 被赋予一定的权值[12]。文本向量表示如下
ti表示特征项ti对应的空间向量, a、b表示文本向量, m为的特征项的个数, wai、wbi为特征项在文本中的权重, 权重由TF-IDF所确定, 并进行归一化处理, W (t, d) 表示特征项t在文本d中的权重, ft (t, d) 为特征项t在文本d中出现次数, N为文本总数, n1为文本集中包含t的文本数。文本相似度表示如下
VSM中假设特征项ti之间是正交的单位向量, 所以式 (4) 可以化简为
VSM中特征项正交的假设, 并没有考虑到自然语言中词语之间的语义相似性和相关性。广义向量空间模型 (GVSM) 对特征项正交的假设进行了改进。在GVSM中特征项表示为空间中一组独立非正交的单位向量。文本空间是由特征项向量生成的子空间, 特征项的权重采用与VSM相同的方法, 文本向量的相似度表示如下:
式 (7) 中, cosω表示两个特征项夹角的余弦值即特征项的相似度。文本相似度计算的关键问题就是特征项相似度的计算。S.K.M.Wong等[2]利用布尔代数中的最小项, 将特征项的共现 (co-occurrence) 模式用2m小项集合表示, 并将最小项与一个2m维空间的基一一对应, 将文本向量和特征项向量映射到最小项表示的2m空间中, 再通过向量的夹角计算文本相似度。Farahat等[13]在GVSM模型的基础上提出, 使用文档特征项矩阵的协方差矩阵计算特征项的相似度。这两种特征项相似度的计算都是利用文本集中特征项的共现信息, 对于语料的依赖很大, 不易于拓展。
2《知网》
《知网》[14]是我国著名机器翻译专家董振东先生历经十年创建的一个知识系统。它含有丰富的词汇语义知识。在《知网》中有两个主要的概念:“概念”与“义原”。“概念”是对词语语义的一种描述。每个词语可以表达几个“概念”。“概念”是由一种“知识表示语言”描述的, 这种“知识表示语言”所用的词汇就是“义原”。“义原”是描述一个“概念”的最小意义单位。《知网》试图用一系列的“义原”来对每一个“概念”进行描述。
义原作为描述概念的基本单位, 相互之间又存在复杂的关系。《知网》中一共描述了义原的8种关系, 义原之间组成了一个复杂的网状结构。不过, 义原关系中最重要的还是上下位关系。根据义原的上下位关系, 所有的“基本义原”组成了一个义原层次体系 (如图1) 的树状结构, 这也是进行义原相似度计算的基础。
3 义原向量空间
《知网》中, 义原是表示概念的基本单位, 利用GVSM的思想, 将义原看做N维空间中一组线性独立非正交的单位向量。义原空间是由义原向量生成的子空间。义原向量表示如下。
式 (8) 中, j表示N维空间的基, εi为义原在j方向的投影。所以两个义原向量的内积就是它们夹角的余弦, 即相似度:
3.1 义原相似度的计算
义原的相似度计算[9, 15—17]是根据义原在层次结构中的最短距离和深度。距离越大义原的相似度越小, 深度越大义原信息量越大, 相似度也越大。义原相似度计算公式如下:
dis (p1, p2) 为在义原层次结构中的最短距离, depth为义原在层次结构中深度, α表示深度的权重系数。
3.2 概念, 词语, 文本的义原向量
《知网》中, 概念是由一组义原通过一种形式化语言进行描述的。通过对概念的义原描述式进行分析, 将其分为三部分:
(1) 独立义原描述式:使用基本义原或者具体词直接对概念进行描述。
(2) 关系义原描述式:用“关系义原=基本义原”或者“关系义原= (具体词) ”或者“ (关系义原=具体词) ”来描述。
(3) 符号义原描述式:用“关系符号基本义原”或者“关系符号 (具体词) ”加以描述概念。
在独立义原描述式中, 第一个义原描述式代表概念的主要意思, 具有较高权重, 因此将独立义原描述式又细分为第一独立义原和其他独立义原两部分。
本文中的义原为空间向量, 因此概念是由义原向量的线性组合表示。根据以上对概念组成的划分, 概念向量应该由四部分义原向量组成, 每部分的权重根据义原表达式的重要程度而定。概念向量表示如下
P1到P4定义如下
(1) P1表示概念S的第一独立义原描述式对应的义原向量。因为第一独立义原由唯一的一个义原或者词语表示, 所以P1由唯一的义原向量或者词语向量表示, β1为该部分义原向量的权重系数。
(2) P2表示概念S的其他独立义原描述式对应的义原向量。由除第一独立义原外的其他独立义原或者词语的义原向量进行线性相加表示, β2为该部分义原向量的权重系数。
(3) P3表示概念S的关系义原描述式对应的义原向量。由关系义原与它描述的独立义原或者词语的义原向量进行线性相加表示, β3为该部分义原向量的权重系数。
(4) P4表示概念S的符号义原描述式对应的义原向量。由描述符号所描述的独立义原或者词语的向量相加表示, β4为该部分义原向量的权重系数。
S表示概念向量, βi表示每部分义原向量的权重系数, np表示概念中包含义原向量的个数, εw表示概念向量中对应义原向量的系数。
词语通常包含不止一个概念, 所以词语的向量表示为所包含的概念向量的加权平均, 如下
式 (12) 中, W表示词语向量, nsw为词语W包含概念的个数, Sj表示W的一个概念, nw表示词语向量中义原的个数。利用特征项的TF-IDF权重, 文本向量表示如下:
式 (13) 中, ndw为D中特征项的个数, wi为特征项Wi的权重, 通过式 (3) 计算, nd为文本向量中包含义原的数目。利用文本义原向量, 相似度可以表示如下:
4 实验
通过文本聚类实验来对比本文提出的方法PVSM与VSM以及GVSM。分类文本选择搜狗实验室提供的中文文本分类语料库, 从中选取6类长短不同的文本各150篇作为实验数据。每类文本中选取50篇文本作为VSM和GVSM的训练文本, 100篇作为聚类文本。通过对使用F-度量值来对比三种模型的优异, F-度量值是一种结合查准率和召回率的平衡指标。设ni是类别i的文本数目, nj是聚类j的文本数目, nij是聚类j中隶属于类别i的文本数目, 则查准率p (i, j) 、查全率r (i, j) 和F-度量值F (i, j) 分别定义为:[18]
实验参数α、βi的确定参考文献[15—17]中对概念相似度的计算实验, 并在实验中根据效果进行调整。具体设置如下α=1.6β1=0.5, β2=0.2, β3=0.17, β4=0.13。
引入特征项权重计算公式
选取特征项集合。tt表示特征项在训练文本集中出现的总次数, 值越大说明其表示文本能力越强, ti表示特征项出现在训练集合类别的个数, 数目越大说明特征项表征该类别的能力越弱, td表示特征项出现的文本数目, 其值越大, 表明特征项表示文本类别的能力越弱。根据权重的大小选取前N词语作为特征项。通过使用K-means聚类算法, 实验结果如图2~图4。
通过对三种算法查全率, 查准率和F-度量值的对比, 本文提出的算法在文本集3、4、5、6上都优于VSM和GVSM, 但在文本集1、2上却不如VSM和GVSM。通过分析发现, 文本集1与2主题分别是军事, 旅游。这两类文本中, 具有明显的高频特征项词语, 例如“武器”、“旅游”等。对于这种特征项明显的文本集, VSM和GVSM比较适合。文本集合3、4分别对应生活杂谈, 小说电影文化, 文本的内容范围很广不具有明显特征项, 这时PVSM算法较为有效。而在文本集5, 6医疗健康、科技中PVSM效果与GVSM接近, 优于VSM, 这两类文章中具有一些常用的特征词但不像1, 2文本集中那么明显。综上可知, 基于《知网》义原向量空的PVSM模型在语义相似度计算方面优于GVSM与VSM, 但在具有明显特征项的文本集中不如GVSM和VSM高效。《知网》中词语, 概念, 义原都是已知的, 因此义原的相似度, 概念和词语的义原向量表示都可以事先计算, 在计算文本相似度时直接使用, 无需训练语料, 相比VSM和GVSM应用范围更广。
5 结束语
短文本相似度 篇3
随着Internet的迅猛发展,Web上的网页数目呈现出爆炸性增长趋势。网页是一种半结构化的数据,在主题型网页中,除了主题内容外,网页还包括网页噪声,噪声内容是指网页中与其应用目的不相符的内容,如广告、版权、导航信息等。如何准确、高效地提取网页的正文信息早已成为网络信息应用和研究领域的一个重要课题。
2 相关研究
国内外对网页信息提取已经进行了大量的研究工作。网页提取方法主要有:基于包装器的方法、基于网页源码特征的方法及基于页面结构树的方法。
包装器[1](Wrapper)抽取方法,它基于信息模式识别的知识,包装器可以通过分析网页的源代码来手工编写。文献[2]介绍的XWR AP系统中的包装器采用了半自动化的方法来获取规则。
基于网页源码特征的方法是直接从网页HTML源码中寻找网页正文区域。文献[3]提出了一种基于区域分块的微内容类网页正文提取[4]技术,利用网页区域分块技术与HTML的结构特征,实现正文提取方法。
基于页面结构树的方法是利用解析器将页面解析成树,分析树的结构特点完成信息抽取。文献[5]提出一种从页面获取正文信息并正确分段的方法。
文章提出了一种网页标题与文本相似度的主题网页正文信息抽取方法。
3 一种基于标题与文本相似度的网页正文提取技术
3.1 基本概念
STU-DOM[6]树:向DOM树的某些结点添加描述语义的属性,生成的DOM树称之为STU-DOM树。
Shingle算法[7]:该算法将文本视为词项序列,将固定长度的相邻词项视为一个Shingle,从而将文本转化为Shingle集合加以表示,通过对比两个文本的Shingle集合匹配程度来识别两者是否内容上相似。
Dice[8]系数:是一种集合相似度度量函数,通常用于计算两个样本的相似度值s。
其中X和Y表示标题和文本的词汇单元集合。
3.2 算法描述
文章实现的网页正文信息提取分为4个步骤:HTML解析、生成STU-DOM,剪掉正文周围噪音,正文提取。
步骤1:HTML解析
本步骤是将网页文档解析成DOM树的过程。本算法采用nekohtml+xerces实现网页文档的解析。
步骤2:生成STU-DOM
本步骤是将DOM树转化为STU-DOM树的过程。
网页设计者们在开发网站的时候,常用<table>、<div>标签进行页面区域初步划分。给DOM添加语义信息时,计算<table>、<div>块的语义信息是块中非链接文字总数(字符数)、链接总数、标点符号句号数目、段落标记<p>和<br>的数目。
步骤3:剪掉正文周围噪音
统计分析大量的HTML文档发现,网页中包含的一些明显的噪音信息主要有如下特点:
3.2.1 与主题无关的块总是含有大量无关链接和极少非链接文字,针对这种类型的块,通过文字链接密度(Local Correlativity(STU-i))值来达到剪枝效果。
其中,STUCij表示STUi的第j棵子树,Link Count(STUi)是STUi的linkcount属性值,其值为它所有的子树中链接数之和,Content Length(STUi)是STUi的contentlength属性值,其值为它所有的子树中非链接文字的字符数之和。通过训练得到阈值为Lm,如果Local Correlativity(STUi)大于Lm的块,则判定为噪音。
3.2.2 与主题无关的块总是<table>、<div>标签中文字密度低的结点,这种类型的块中只包含文字,而且文字数量较少。
3.2.3<style>、<script>等HTML标签对应的节点。
3.2.4 与主题无关的块中标点符号句号、段落标记数目较少。
步骤4:正文提取器
第一步,首先从STU-DOM树种提取网页标题“title”,接着过滤掉标题中的中英文标点符号,尤其要过滤掉标题中的空格和回车符号,用Shingling算法对网页标题进行切分,生成词汇单元集合,Title_Words。
Title_Words=(TW1,TW2,…,TWn)
第二步,提取剪枝后的STU-DOM树种的<table>、<div>标签中的文本节点,对节点文本去掉分隔符,比如句号、逗号等等。在切分之前,对中英文的标点和数字进行统一化处理,然后应用Shingle算法进行切分,生成文本词汇单元集合Content_Words。
Content_Words=(CW1,CW2,…,CWm)
统计出Title_Words与Content_Words的交集。
考虑到标题与文本节点经过Shingle算法进行切分后2个集合大小之间的差异,我们对Dice系数进行了改进。
s越大,说明相似度就越大。
对于s小于给定阈值的节点,需考虑文本节点的上下文相关度c Similary,如果当前节点的相邻的兄弟节点c Similary的值为true,则可以设定当前节点的is Extract值为1。对于满足一定阈值的节点直接提取,同时标记该节点的上下文相关度c Similary的值为true。
3.3 实验结果
为了对网页正文提取方法进行验证,从网易上下载的一个网页进行测试如图1所示。经过实验评估后,Lm取值为0.05,文字密度值取值为30,句号数目、段落标记<p>和<br>的数目为0,取Shingle的长度为2,r(A,B)阈值α取值为0.001时网页去噪效果好。
提取结果如图2所示。
使用北大天网实验室为全国搜索引擎与网上信息挖掘研讨会中文网页分类测评提供的网页训练集YQ-CCT-2006-03,共分为8个类别,分别为教育,计算机,娱乐,时尚,法律,财经,军事,体育。从网页训练集选取电脑、时尚、娱乐3个类别中共150篇文档及从网易、新浪上下载50篇文档进行网页正文提取测试。测试结果如图3所示。
由图3可知阈值α取值越接近0网页提取的准确率越高,同时含有的网页噪音也越多,取0时网页噪音最多,取1时准确率几乎为0。r(A,B)阈值α取值为0.01时,该抽取方法准确率达到90%以上,网页噪声几乎为0。
4 结束语
随着互联网的迅猛发展,许多研究如信息检索、数据挖掘等由传统领域转到了Web上。面对充满了噪音的网页,如何快速、有效去除网页上的噪音对于提高信息检索、网页分类、用户感兴趣挖掘和个性化信息推荐的研究效果至关重要。实验结果显示,文章提出的方法,有效去除网页噪音,保留了正文内容。
摘要：主题型网页标题是网页正文内容的高度概括,利于标题与正文相似性之间的关系,提出了基于标题与文本相似度的网页正文提取算法。该算法首先把网页解析成DOM树,再生成STU-DOM,接着对STU-DOM进行粗剪枝。对剪枝后的语义树通过Shingle算法对网页标题与节点文本进行切分,生成标题和节点文本词汇单元集合,利用改进后的Dice系数计算标题与文本的相似性实现网页正文提取。实验结果表明,该抽取方法准确率达到90%以上,具有可观的实用价值。
关键词：网页去噪,DOM,STU,Shingle,Dice
参考文献
[1]刘冬兰.Deep Web数据抽取中自适应包装器问题研究[D].济南:山东大学,2013.
[2]Liu,L.,Pu,C.etal.XWRAP:An XML2enable Wrapper Construction Sy stem for the Web Information Source[C].In:proceedings of the 16th IEEE International Conference on Data Engineering,2000:611-620.
[3]申晨,周辉.基于区域分块的微内容类网页正文提取技术[J].海南大学学报自然科学报,2013,31(1):31-36.
[4]Rahman A R,Alam H,Hartono R.Content Extraction from Html Documents[C]//Proc.of the 1st International Workshop on Web Document Analysis.Seattle,USA:[s.n.],2001:7-10.
[5]周建,汤进,罗斌.基于DOM结构树的网页正文信息分段方法[J].计算机与现代化,2013,10:229-232.
[6]莫卓颖.基于语义DOM的网页信息抽取[D].桂林:广西师范大学,2012.
[7]马成前,毛许光.网页查重算法Shingling和Simhash研究[J].计算机与数字工程,2009,37(1):15-17.
短文本相似度 篇4
信息检索是企业管理信息系统中常见却又重要的功能之一,其基本功能是根据用户输入的相关专业的检索条件,从企业数据库中检索出用户所感兴趣的数据。检索关键字是构造检索条件的必须过程之一。信息检索系统所要解决的核心问题就是:提高检索关键字集合的规范性与完备性;确定每次检索所需要的信息全集,并随着系统运行时间的增加,不断提高这种计算的准确性。本文将通过对文本相似度计算及相关分类算法,达到检索关键字集合规范性及完备性的提高的目的。
1企业终端用户信息检索的特点
1.1信息检索关键字一般要求及预处理的目的
信息检索关键字从用户角度而言,是通过信息检索工具定位被检索主体的一些字、词或词组、短句的集合[1];从系统角度而言,检索关键字是被检索主体显著特征的综合体现;从系统的设计角度来看,检索关键字是检索算法的输入参数。一次信息检索过程的执行,及最终检索结果的获得能否顺利完成,或者说用户能否通过输入既定的检索关键字获得自己需要的数据信息,检索关键字的规范性、完备性至关重要。
所谓关键字的规范性是指关键字能否体现与之对应的被检索主体的典型特征。所谓关键字的完备性是指能体现被检索主体某一典型特征的关键字可能不只一个,比如对某一设备的检修历史记录而言,“设备巡检”及“设备巡更”就代表相同的意义,而这两个关键字对企业用户来说,都是标准的专业语言,所以,若某个被存储的数据中只有“设备巡更”关键字,而没有“设备巡检”关键字,但用户输入“设备巡检”作为检索关键字时,该用户将得不到期望的数据资料。为此,为了提高数据检索的准确性,输入的检索关键字的集合在经过系统的处理后应该具有完备性,即通过一定的算法,将与关键字所表述意义一致或相近的标准关键字加入到检索关键字集合中,进一步达到提高检索准确性的目的。
1.2企业用户检索信息的特点
企业级用户在完成信息检索时,其检索行为具有如下特点:
被检索主体的规范性:企业级信息检索,被检索的最小对象是存储在数据库表中具有规范数据结构的记录,这一基本特点区别于互联网搜索引擎。因此,在构造好检索关键字及确定了检索范围后,可以通过标准化的SQL语言,对数据进行搜索,获得用户所需要的数据信息。
检索关键字数量的有限性:限于企业终端用户岗位及专业的限制,其在某岗位长期的工作过程中,所使用的用于信息检索的关键字的集合中元素的数量是有限的,据不完全统计,对于每个终端用户,其常用的检索关键字也就几十个甚至只有十几个。其实,就互联网络搜索引擎的使用而言,对于一般的网络用户,由于个人工作、爱好、生活的因素的决定性作用,其日常所使用的关键字的集合也是有限的,一般不会无限制扩大(每个人都可留心统计一下自己使用关键字的情况)。
关键字的规范性:企业信息检索系统的用户,由于其工作上的要求,一般会熟悉自己所从事的工种及与之对应的专业,因此,其与其工作对应的信息是,所输入到检索系统中的关键字的规范程度还是比较高,口语化、随意性的比例不会很大。
关键字的完备性:其实,无论是企业用户还是一般的用户进行信息检索时,都不会从主观上考虑构造完备的检索关键字的集合(那样确实是很繁琐的事情),因此,为实现系统检索信息的准确性,扩充关键字集合,使其完备性获得较大的提高,是信息检索系统必须完成的工作之一。
检索范围的不确定性:此处所谓的不确定性具体来说应该是检索范围的不精确性,当然,如果把检索范围定义为全数据库系统,那检索范围肯定是确定的,但这样每次完成检索肯定要耗费大量的时间。因此,对于每次具体的信息检索功能之前,与检索关键字集合对应的被检索主体所潜在的数据范围是不确定的,系统必须根据既定的字典信息、以往的检索历史等,对检索对象所在的尽可能小的数据全集进行初步的计算,并通过系统不断运行,积累相关的数据,不断提高这种计算的准确性。
2检索关键字预处理
检索关键字是企业信息检索系统工作过程中构造检索条件的必须过程之一。在通常情况下,由于用户输入检索关键字的随意性较大,使得检索关键字的集合存在不规范、不完备等诸多对检索不利的因素存在,为了提高检索的准确性,并提高检索速度,就必须对用户输入的检索关键字进行预处理,使检索关键字满足较为精确信息检索的需要。检索关键字的预处理过程如图1所示。
在检索关键字预处理过程中,用户首先通过输入界面的检索关键字输入框,输入检索关键字字符串。一个这样的字符串包含多个关键字,关键字之间以空格或预设定的符号分隔。在系统接收该检索字符串后,通过一个相关算法,将字符串分解为若干关键字,并形成集合。在获得输入关键字集合后,由前文分析可知:
输入关键字集合具有不规范性、不完备性等缺点,因此必须通过后继相关处理,使该集合具有规范性及完备性。在系统内部,即系统安装及初始化过程中,系统安装人员针对企业的不同专业、不同工种已预定义了规范的关键字字典(工种及专业人员进行信息检索时所需关键字的特点在前文已分析,因此规范、完备的专业关键字字典的数量不会很庞大)。在系统运行过程中,输入关键字集合中的每个关键字,都会与规范关键字集中的每个关键字进行相似度匹配,当相似度满足预设定的阀值要求后,就将该关键字加入规范关键字集。如此循环,直到所有的输入关键字被处理完成为止,最后获得组成相似集。
在关键字规范工作完成以后,就要进行检索范围的确定。事实上,在企业级计算机应用系统中,关键字和被检索目标—表之间的存在多对多的映射关系,即一个关键字可以在多个表的数据字段中出现,同时一个表的数据字段中一般也会包含多个可能的关键字。基于以上原因,如何确定一次信息检索过程中所涉及的表的集合,成为影响检索速度、检索精度的重要问题。在企业信息检索系统中,通过KNN算法,确定关键字组成相似集中每个关键字所属的规范关键字子集,规范关键字子集由系统根据对检索结果的分析动态刷新,并与被检索对象—表之间形成映射关系,因此可以通过关键字组成相似集获得检索目标的集合。
在获得关键字相似集及检索目标集后,可以构造检索条件并执行,最后获得检索结果集。
3 文本相似度与关键字组成相似集计算算法的提出
3.1 文本相似度
所谓文本的相似度,是指文本在组成或含意上相近的程度。在本文中,文本的相似度确指用户输入的某关键字与标准关键字集合中某关键字的相似度(下文中将用关键字相似度代替文本相似度)。
对于信息检索所使用的关键字,因为专业及业务的制约,一般是比较规范的、标准的。在关键字的使用上,书面及学术词语的使用是基本要求,因此,在企业信息检索系统中,关于关键字相似度的计算,考虑更多的是组成上的相似度。
现在已经有很多相似度计算模型被提出,例如:[2]向量空间模型VSM、字符串相似度模型、文档结构相似度模型,还有国内学者提出来的一些方法:基于属性论来计算文本相似度的方法、基于汉明距离的文本相似度计算方法等等。目前主流的是VSM。在VSM中,文本空间被看作是一组无序词条向量所组成的向量空间,把文本和查询式表示成以词条为分量的向量,根据词频tf以及逆文本频率idf,来计算该向量中各个分量的权值。当文档被表示为文档空间向量后,就可以用向量之间的距离计算公式来计算查询向量和被检索文档之间的相似度。另外还有广义向量空间模型,隐性语义索引模型和以属性理论为基础的属性重心剖分模型等方法。
以上这些方法,它们都不外乎利用欧氏空间,微分几何中单纯形等概念,把文本与查询式描述成空间中的向量,再在向量空间中定义诸如内积等运算,由此来定量地描述文本与查询式之间的相似度。但是,不管上述那一种方法,都要求向量空间内的词条是正交的,所以在获得文档的特征向量前,都要进行消歧、词规范化等预处理。这些过程通常是比较繁琐和复杂的,而且不一定能得到好的效果。
基于此,该文提出如下关键字组成相似度计算算法。
3.2 关键字组成相似度计算算法[3,4]的提出
(1) 基本定义
① 关键字组成相似度。设有关键字组成集合Kx={x1,x2,…,xn}及Ky={y1,y2,…,ym},及K=Kx∩Ky={K1,k2,..,kQ},其中1≤Q≤min(m,n)且K1,k2,…,kQ排列次序同其在Kx和Ky中出现的次序一致。Len(K)=Q,称max(Q)为关键字Kx和Ky的组成相似度,记做MD(Kx,Ky)。
关键字的组成相似度MD(Kx,Ky)实质上就是组成关键字Kx的元素(字)依次在组成Ky的元素(字)集合中所出现的最大个数。
② 组成匹配矩阵。设有m×n阶矩阵MM,其中将Kx中的组成元素xj依次同Ky中的组成元素yi比较,若xj=yi,则MM[i][j]=1,否则MM[i][j]=0,称MM为关键字Kx和Ky的组成匹配矩阵。匹配矩阵MM中包含关键字组成集合Kx和Ky的所有匹配信息。
称MM中所有从第i行到第m行(1≤i≤m),第j列到第n列(1≤j≤n)的元素依照其在MM中的元素排列所构成的矩阵为关键字Kx和Ky的一个组成匹配子阵,记做MM(i)(j)。组成匹配子阵中包含着关键字Kx从第i个组成元素开始的子列及Ky从第j个组成元素开始子列的匹配信息。
关键字的组成相似度的计算过程,实质上就是依据某种规则在组成匹配矩阵中进行搜索的过程。
(2) 匹配矩阵的性质
性质1 设xj、xr∈Kx,yi、yz∈Ky,且j≤r,i≤z。若xr=yz,则MM[q][r]=1必出现在匹配子阵MM[i][j]中。此性质从组成匹配矩阵的定义中可以直接得出。
性质2 在匹配子阵MM(i)(j)(1≤i≤;1≤j≤n)中,对元素MM[p][q]=1(1≤p≤m;1≤q≤n),若p,q满足以下性质,则MM[p][q]是起始搜索点:
A:p=i或q=j;
B:MM[p-1][q-1]=0(p>i,q>j)。
在组成匹配子阵MM(i)(j)中,若MM[p-1][q-1]=1,则从MM[p-1][q-1]开始搜索所得到的组成相似度可定大于从MM[p][q]开始搜索所获得的相似度。故满足条件B的组成元素是起始搜索点。
性质3 在匹配子阵MM(i)(j)中,(1≤i≤m;1≤j≤n),对于元素MM[p][q]=1(i≤p≤m;j≤ q≤n),若p、q满足以下性质,则MM[p][q]是一次搜索结束点。
A:p=m或q=n;
B:MM[p+1][q+1]=0(p<m;q<n);
(3) 关键字组成相似度计算算法(搜索算法)
依据关键字组成匹配矩阵的性质,设计相似度计算算法如下:
算法输入:关键字组成匹配矩阵MM
算法输出:关键字组成相似度
算法步骤:
① 定义起始搜索节点结构,如图2所示。
② 令MD=0,起始节点队列头指针SH;P=SH,i=1,j=1;
③ 得到匹配子阵MM(i)(j)的所有起始搜索节点SSk,令SSK→MD=MD(1≤k),并插入起始搜索点队列,i=P→Row,j=P→Col。
④ i=i+1,j=j+1,P→MD=P→MD+1,直到MM[i][j]成为搜索结束点。
⑤ MD=max(MD,P→MD),P=P→lpNext。
⑥ 若P非空,则转第3步,否则输出MD,算法结束。
(4) 关键字组成相似度计算
将用户输入的关键字逐个规范关键字集合中的关键字比较,获得每个用户输入关键字与规范关键字的匹配矩阵,在此基础上运用关键字组成相似度计算算法获得用户输入关键字与规范关键字的相似度,通过设定相似度阀值,将相似度大于或等于阀值的规范关键字从规范关键字集合中提取出来,即获得与用户输入关键字集合相对应的规范关键字子集,简称组成相似集(SSS,Structure Simulate Set)。该关键字子集首先是规范的,其次具有完备性,因此从检索条件的角度确保了检索准确性。
在应用关键字组成相似度计算算法时,应该注意以下几个问题。
① 关键字组成相似度计算算法实质是对关键字匹配空间的搜索,其时间复杂度与匹配阵的规模(m×n)成比例关系,因此,当关键字较长时,计算的时间开销比较大,因此算法有待进一步优化。
② 获得的规范关键字子集的完备性,与系统预定义的规范关键字的集合的元素数量有很大关系,数量越大,则得到的集合的完备性越高。因此,检索关键字的规范集的定义及输入需要专业人士完成。
③ 检索关键字的规范子集获得后,可以结合SQL语句的相关运算如“like”运算,实现更强的检索匹配。
3.3 算法优化
以上算法[7]的实质,是通过穷举方式,在匹配矩阵MM中遍历状态空间树,所以是间及空间开销较大,通过对算法的分析,得到以下性质,用于算法的优化。
性质4 在以MM(i)(j)(1≤i≤m,1≤j≤n)为起始节点的一次搜索过程中,若MM=min(m,n),则搜索过程结束。
性质5 在得到匹配子阵MM(i)(j)(1≤i≤m,1≤j≤n)起始节点的过程中,若MD(i)(j)的一个搜索起始点MM(p)(q)(i≤p≤m,j≤q≤n)已包涵在起始搜索点队列中,设SSk是队列中对应起始搜索点,则会有以下情况出现:
如MM(p)(q)→MD≤SSk→MD,则MM(p)(q)不插入起始搜索点队列中。
如MM(p)(q)→MD≥SSk→MD,则令SSk→MD=MM(p)(q)→MD,MM(p)(q)不插入起始搜索点队列中。
根据性质5对算法进行改进,达到了对空间搜索树的剪枝目的,减少了算法对空间搜索树的遍历规模,在时间及空间上加快了算法的执行速度。
性质6 若以MM(i)(j)(1≤i≤m,1≤j≤n)为顶点,采Z形扫描得到匹配子阵MM(i)(j)的起始搜索点,将起始搜索点插入队列时,如按MD由大到上的顺序插入,则在一定程度上可以缩短算法搜索时间。
性质7 设线性序列L1={X1,X2,…,XK},L2={Y1,Y2,…,YK},其中X1,X2,…,XK,Y1,Y2,…,YK也是线性序列,且在匹配过程中,存在Xi同 Yi( l≤i≤m)的匹配对应关系,
则
性质8 设线性序列L1={ X1,X2,…,Xm },L2={Y1,Y2,…,Yn},其中X1,X2,…,Xm,Y1,Y2,…,Yn,也是线性序列,且在匹配过程中,存在Xk( l≤k≤m)同 Yh( l≤k≤n)的一一对应匹配关系G对,则
根据性质7,性质8,可将较长线性序列L1和L2的匹配过程,分解为若干子序列的匹配过程,从而降低了空间搜索树的规模,极大地加快了算法的执行速度。
在算法设计过程中,可以定义匹配矩阵节点结构同搜索起始点结构一致,此时,搜索起始点队列可以“蕴涵在匹配矩阵”中,以进一步减小算法空间复杂度。
以上性质因为证明过程比较复杂,限于篇幅,这里不再赘述。
4 结束语
根据匹配矩阵及搜索算法的性质,对算法改进后,算法的运行速度进一步提高,应用相似度算法对文件及数据库记录进行了相似度计算,取得了良好效果。
参考文献
[1]黄炜.发电企业信息检索系统
[2]苏振魁.基于公共子串的文本相似度计算模型.计算机科学,2007;34(10)
[3]黄炜,费洪晓,张伟.线性序列相似度的计算.铁道学院学报,2002;20(3):105—106
[4]张振亚.基于余弦相似度的文本空间索引方法研究.计算机科学,2005;(9):160—163
[5] Tan Songbo.Neighbor weighted K-nearest neighbor for unbalancedtext corpus.Expert Systems with Applications,2005;28(4):667—671
[6] Hwang W J,Wen K W,Fast K N N.Classification algorithm based onpartial distance seareh.Electron Lett,1998;34(21):2062—2063
短文本相似度 篇5
关键词：组卷,遗传算法,相似性检索,小生境算法,对比实验
网络化教育以其高速快捷和大信息量被广大学习者认可，而网络化考试作为网络化教育的主要组成部分之一[1]，成为研究者们热衷的课题，其中研究点之一就是智能组卷系统。智能组卷系统应用人工智能、机器学习理论，根据学习者的需求和考试试卷的特点建立数学模型，再依靠计算机强大计算能力“智能”地找到学习者的特点和需求，使计算机不断向智能化、人性化的方向迈进，在教育领域更加体贴的为学习者服务[2]。
近年来不断有学者对考试智能组装试卷的方法进行研究和探索[3]。而如何更准确地利用计算机智能的产生出具有针对性的、难度适中的、范围准确的考试试卷就成为了网络化考核之中又一个重要的研究环节。本文提出了将试题文本作为组卷参数之一的改进模式，通过对相似试题文本的排除达到遗传算法中早熟现象的免疫[4]。同时增加考试试卷的多样性。其次，提出遗传算法框架模式并研究遗传算法中适应度函数对函数收敛速度的影响。最后对研究算法进行测试，并对结果进行了实现。
1 遗传算法在组卷中的应用
1.1 目标函数及适应度函数
实际应用中，可能不会需要上述如此多的约束条件，比如只需要约束试卷的难度与题型分布，或者难度与知识点的分布等，对每一方面都做到完好的满足可能要花费很长的组卷时间，甚至组不出满足要求的试卷，这时需要在一定程度下放宽对组卷的约束要求。并且对于不同的约束条件，其容忍的误差也会有所不同。因此需要设定目标函数为：F=(X1,X2,...,Xn)。其中：X1为组卷需求中第i项约束条件取值变量；F为目标函数值，而X1,X2,...,Xn全部取到需求点时即为F的极值。适应度函数则由F的目标函数映射为非负、极大函数，以满足遗传算法中优胜劣汰的思想。
分析可以得出，如果组卷人指定了组卷的n个约束条件后，且约束条件相互独立，组卷算法中遗传算法的适应度函数就是一个n+1维单峰值最优化问题了。在n维度的自变量中，靠近要求的点的函数值越接近极值；再加上前面所要求的约束条件对函数值的贡献不同的因素则可以采用加权离差的方法来表示函数的自变量，则有：
式中：Wi表示第i项约束条件的权重，Wi与约束条件的重要性成正比，且满足;di为用户定义的第i项约束目标值；x为题库内试题选取。
目标函数为：
对于多点的复合条件，如题型设定与知识点设定，则选取分条件值。也可以通过分段编码来更高效地实现其中之一。对于遗传算法来说，将目标函数反转取得适应度函数的方法有：
在这种情况下，cmax存在多种选择方法，它可以是一个合适的输入值，也可以采用迄今为止进化过程中g(x)的最大值，但cmax最好与群体无关。由于参数cmax需事先预估，不可能精确，其结果常常使适应度函数不灵敏；但优点是计算量小，运算简单，线性函数也保证了收敛的规则性，在二维约束条件下其适应度函数为：
在这种情况下，适应值函数由于在极值附近高速上升，在轮盘赌的选择条件下收敛速度会大幅上升，但若速度过快的话也会导致早熟现象。
1.2 编码设计
用遗传算法进行求解问题时，必须在目标问题实际表示与遗传算法染色体结构之间建立联系，即确定编码和解码运算。在组卷系统中，二进制编码方式是以长度为N的二进制串表示选择题目数，N为题库中试题数量，二进制串中1的个数和为n，即组卷试题数量。
针对二进制编码的不足，本文采用实数编码、题型分割的编码方式进行个体组建。这种编码方式见图1。
这种编码方式中应注意的是在同一编码段即同一题型内不应出现重复试题。而对于小规模题库来说由于遗传算法的随机选择性，取得重复试题的概率会变大，去重的工作也会加大，故而实数编码比较适用于大规模试题库抽取试题量相对较小试卷的组卷情况。
1.3 组卷体系结构
如图2所示，组卷的体系结构要求抽象出组卷和遗传算法两种接口。图中：Assemble接口是组卷接口抽象出进行组卷和取得试题的方法；Generable是适应度接口，抽象出测试函数评估方法；Generation是遗传算法接口，抽象出遗传算法过程；Individual是遗传算法个体类。这种设计方法的好处是：
(1）抽象出组卷接口，其他模块可以直接关心接口方法而不必担心内部实现。
(2）通过适应度计算接口将遗传算法与组卷模块分离化。
(3）遗传算法接口的不同实现可以完成不同编码方式、不同进化方式甚至遗传算法防早熟优化措施的实现类共存和对比，使组卷模块做到可扩展且易使用，同时，对算法的对比研究也提供了良好的平台。
2 组卷系统中的遗传算法研究
2.1 早熟现象的克服方法
遗传算法过程中种群在选择算子的作用下，优秀模式大量增加，低劣模式会迅速减少，整个群体向好的方向进化，但是在选择算子的作用下，群体丧失了多样性[5]，群体进化中后期导致优秀个体的缺失即早熟现象。
本文以小生境算法为基础策略进行早熟现象的克服。基于这种小生境的遗传算法，可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题[6]。
它的实现方法是：首先两两比较种群中个体之间的海明距离，如果个体间距离在指定的距离L内，即两个个体具有一定的相似程度[7]；则再比较二者的适应度大小，并对适应度低的个体增加惩罚值，使其适应度大大降低。以此保证种群空间内L距离内的个体只有一个适应度较高的个体更具有竞争性，而那些适应度较低的且受到惩罚的再选择过程中就极容易被淘汰。在种群空间中，优秀的个体距离会大于L，这样便保证了种群的多样性。
2.2 文本相似度计算方法
组卷过程中的另一个重要问题是组卷过程中出现重复性或相似性试题的问题。研究中尝试利用基础向量检索模型进行研究，使时间效率和算法复杂度都做到最简单。
定义在向量模型中，二元组(ki,dj)的权重Wi,j为非二元正数。并且，在查询语句中的索引词也赋予权重。令Wi,q为二元组(ki,q)的权重，其中。之后，查询向量定义为q=(W1,a,W2,a,...,Wt,a)。其中t为系统中索引词的总数量。文档dj的向量定义为：
因此，文档dj与查询语句q可以被表示为t维空间向量。向量模型根据向量之间的关系来判断文档dj与查询语句间的相似度。而这种关系通常也可以被定量地表示出来。
判断两文档的相似度可以通过将两文档的向量数量积相乘并除以两向量模得到向量余弦值，从而判断向量夹角。余弦值越大说明向量夹角越小，向量代表的文档越相似。进一步，判断整个文档集A也可以通过对特征词矩阵与其转置矩阵数量积相乘并除以对应行内向量模来得到整个文档内的相似度矩阵。
文档特征向量的构造整体流程如图3所示。
为了提高组卷时间效率，暂不考虑引入分词算法，而是直接切字分析。这里只面对分解完毕的特征词词组，并按照向量模型对特征词词组进行相似性比较。之后，利用停用词表，将考试中可能会频繁出现的词语过滤，其中包括助词、连词以及本次考试涉及到的知识点的常用词语。
在特征词抽取后，即可以将试题文本建立向量模型，利用相似性公式将抽取的试题进行相似性比较，两文本特征向量内容如图4所示。
如图4所示，Sym为特征词编码，W表示特征词在向量中的权重。设定每个向量各一个指针，判断两指针位置的特征词编码大小，小的特征词指针向后移动，若两个指针对应特征词相同，则进行权值相乘并累加，如图中所示i指针将向后移动，之后i,j指针所指特征字编码相等则相乘。当一个特征向量指到向量尾部时，向量乘法结束，分别除以两向量的模。
2.3 文本相似度控制
设计相似性检索调整组卷模型如下：
(1）适应度满足要求，产生试卷S。
(2）设定检测池P（线性表），令P=S中的所有试题。
(3）对P中试题进行两两重复检测和相似性检测，记录试题i在此试卷中的几何平均相似度，其中P为测试池中试题数量，并对重复试题进行标记。若无重复试题，跳转到步骤（6）；清空池P；对标记的试题和平均相似度高于设定阈值Simi>T1的试题集T′进行步骤（4），若所有试题都已执行完，重复步骤（3）。
(4）对T′中试题t，从试题库中查询试题m，要求试题m的约束条件与试题t相同。
(5）分析m与t的相似度Simmt，若相似度小于阈值|Simmt|<T2，将m加入池P，从T′中删去t，转到步骤（4）。
(6）若P≠S，跳转到步骤（2）；否则结束。
改进的组卷算法流程如图5所示。
3 结果分析与系统实现
3.1 实验结果分析
首先对比一般随机算法与遗传算法的收敛情况，测试实例中题库有400道试题，具有难度、区分度和认知程度的三项定量约束指标，定性其范围均为1～5，从中根据策略抽取10道试题，使试题参数的算术平均值满足约束条件。表1给出了基本遗传算法运行100次的平均命中代数与理论上随机抽取的速度对比。
由于遗传算法具有并行性，每代种群中设定为40个个体，即可以认为每代遗传算法测试了40次，这样也可以看出其收敛的速度。
小生境算法的收敛性适用于多峰值函数，以ShufferF6函数进行测试，其为减函数并最佳收敛于(x,y,z)的（0,0,-0.5）点，通过种群数量为400，交叉概率为0.7，变异概率为0.05的遗传计算1 000次，若进化100代仍未能抽取到（0,0）点则算法不能收敛，选取x,y值范围[-5,5]，分析排挤机制的小生境算法的平均收敛性，如表2所示。
经过计算分析，小生境排挤算法能极大地增强全局收敛的能力，并且在一定程度上提高算法的收敛速度。在组卷的实际应用中，多峰值的函数主要出现在诸如知识点分布以及不同多认知水平设计上，但更多情况是单峰适应度函数；在这种情况下还是需要对适应度，种群及其他遗传算子进行控制来避免早熟。
针对相似度算法，抽取试题库中的试题进行相似度计算，并对改进的组卷算法进行时间计算，分析平均时间[8]。经过计算，相似度算法模块能够比较有效地查询出文字上相似的试题，并加以排除。
对算法时间效率进行检测，测试用例为500道试题库中，利用交叉概率为0.7，变异概率为0.05，种群规模为400，适应度函数为线性函数的遗传算法，从中抽取10,20,40,100道试题组装试卷的时间模型，测试机器参数为：Core2 2.26,2 GB RAM，每组测试50次，并计算平均时间，融入相似性计算后的组卷算法时间效率见图6。
从图6中可以看出，在抽取试题较少时，相似性试题检测基本不会占用组卷时间，随着试题抽取量的上升，相似度检测会耗费较多的时间，但是仍不会占用大量时间。
3.2 系统实现
依照实际应用，采用B/S方式，利用Struts,Hibernate框架进行Web搭建，完成试题、试卷的管理，考试信息的管理，资源共享处理功能，组卷功能的实现以及安全策略的实现[9]。根据J2EE架构方案，设计四层架构模式进行实现，自下而上分别是Database,Dao/Model，业务逻辑层和表示层。利用MVC架构进行数据控制。利用工厂模式设计数据库访问接口，利用不同方式实现多种数据库的访问。同时，本系统利用QTI统一测试标准，搭建模块式设计，使与学习系统的其他部分松耦合、接口化，从而使考试部分能够高效地为学习者服务，提供标准化、科学化的考试服务平台。
4 结论
本文从现有的智能组卷技术出发，分析了组卷过程中涉及的经典测试理论和项目反应理论的信息参数和评价参数。利用小生境排挤机制和调整遗传算子的办法避免了组卷算法中早熟现象的发生。建立了向量空间查询模型，并对研究结果进行了实验对比和分析，最终依照实际应用，建立了一套高效的、智能的、符合用户测试需求的组卷系统。分析实验结果表明，利用文本相似度改进遗传算法实现的组卷系统具有较高的实用价值。随着人工智能与语言技术的进步，更为准确、高效的文本分析将会被应用于组卷算法中，从而产生更为人性化的测试试卷。这也将成为本课题下一步的研究重点。
参考文献
[1]周国文.基于XML的试题库自动组卷系统[D].长春:吉林大学,2013.
[2]王一萍,曲伟建,潘海珠.一种基于粒子群优化的组卷算法[J].兵工自动化,2009,28(2):39-42.
[3]田涛.在线考试系统设计与实现[D].成都:电子科技大学,2013.
[4]边霞,米良.遗传算法理论及其应用研究进展[J].计算机应用研究,2010,27(7):2425-2429.
[5]郭小磊.基于自适应遗传算法的组卷系统的设计与实现[J].电脑开发与应用,2010,23(8):67-68.
[6]华洁,崔杜武.基于个体优化的自适应小生境遗传算法[J].计算机工程,2010,36(1):194-196.
[7]齐畅,王冬霞,韩颖.多种遗传算法在函数优化方面的性能比较分析[J].辽宁工业大学学报(自然科学版),2013,33(5):290-293.
[8]王旭阳,万里.信息检索中语义相似度算法研究[J].计算机工程与应用,2012,50(10):124-127.
短文本相似度 篇6
文本相似度是表示两个或多个文本之间匹配程度的一个度量参数。相似度越大，说明文本相似程度越高，反之就越低。在文本聚类、Web智能检索、问答系统、网页去重、自然语言处理等很多领域，文本相似度的有效计算是解决问题的关键。目前使用最多并且最为成功的文本表示模型是向量空间模型VSM。向量空间模型的基本思想是以向量来表示文本:[W1,W2，…，Wn]，其中Wi为第i个特征项的权重，一般选择词作为特征项。文本相似度计算的大致步骤为:首先，将待进行相似度计算的文本进行分词操作，分词后的文本由特征词构成;然后，统计特征词词频，构造特征词词典;之后，依据特征词词典，利用文本相似度计算公式进行文本的相似度计算。传统的文本相似度计算公式由于没有对文本间相同的特征词进行统计，有时可能会产生计算结果不准确的问题。本文为解决这个问题，提出了一种改进的基于向量空间文本相似度计算方法，其正确性和有效性得到了实验证明。
1 传统的基于向量空间的文本相似度计算方法
在比较两个文本相似度时，一般采用传统的基于向量空间的相似度计算公式Cosine[1]:
其中D1与D2为需要进行相似度计算的文本。a1k表示文本D1中的第k个特征词的词频，a2k表示文本D2中的第k个特征词的词频。
该相似度计算公式实际是两向量夹角的余弦函数，也是VSM文本分类中常用的度量公式:两个向量越靠近，则相似度数值越接近1，越分开则越接近0。它不考虑向量的绝对长度，着重从方向上考虑它们之间的关系。如图1所示。
通常来说，如果两篇文本所有的特征词都相同，则两篇文本的文本相似度为1;如果没有一个特征词是相同的，则其相似度为0。一般情况下，这种方法能够判断出文本间的相似程度，但是由于该方法没有对文本间相同的特征词进行统计，有时可能导致计算结果不准确的问题。以表1为例，该表显示了D1到D5五个文本的特征词频。表中D4、D5在10个特征词中只有一个共有特征词W1，说明D4与D5不相似;但是根据式(1)，它们之间的相似度为0.96，这与实际差别较大。在文本相似度计算中，类似情况的出现可能会给最终结果造成一定的干扰，使其不够准确，因此考虑对该文本相似度算法进行改进。
2 改进的文本相似度计算方法
两个文本的特征词相互覆盖情况在一定程度上反映了两者的相似性。如表1中的D1与D2相互覆盖的特征词有W2、W4、W6、W7、W9，而D1与D3相互覆盖的特征词有W1、W8，由于D1与D2相互覆盖的特征词比D1与D3相互覆盖的特征词数多，通过直观的比较，可以看出前二者的相似程度比后二者的要大。考虑到两个文本相同的特征词数量在一定程度上反映了两者的相似性，这里对传统的相似度计算公式进行改进，引入两个文本的覆盖程度这个衡量参数。我们对式(1)进行改进如下:
其中，D1与D2为需要进行相似度计算的文本。a1k表示文本D1中的第k个特征词的词频，a2k表示文本D2中的第k个特征词的词频。nD1D2表示文本D1与D2的共有特征词个数，Min(nD1,2)是取D1、D2所含特征词数较少的那个文本中的特征词数。nD1D2/Min(nD1,2)取值范围为[0,1]，用于衡量D1、D2两个文本的相互覆盖程度。如果文本D1的特征词都不在文本D2中出现，那么D1、D2的相互覆盖率为0;如果文本D1的特征词都在文本D2中出现了，那么D1、D2的相互覆盖率为1。b∈N，它能够放大相似度结果，使其更加直观，具体取值参照最终的相似度计算结果，当所得相似度超过1时，取相似度为1。
式(2)在式(1)基础上增加了乘积项nD1D2/Min(nD1,2)(新公式中b只是用于放大相似度计算结果，因此这里不加分析)，相似度计算结果相比式(1)有以下改进:
(1)对文本相似度差异进行了优化
利用传统的文本相似度计算公式对表1中的D4、D5进行相似度计算，所得相似度为0.96，考虑到两个文本之间只有一个相同的特征词W1，这个结果显然是不合理的。而D4、D5的相似度在新算法下为0.32，这个结果比起原始算法所得的0.96显然要更精确一些。
(2)有效减少相似度低的文本干扰
乘积项nD1D2/Min(nD1,2)的取值范围为[0,1]，相对来说，它使两篇文本的相似度缩小了一些，这样能够有效减小干扰，使结果更准确。如果两篇文本相似度比较大的话，通过该参数的引入，其相似度的下降幅度并不是很大;如果两篇文本相似度较低的话，那么通过该参数的引入，其相似度的下降幅度将会变大，使部分非同类文本可以被排除在近邻之外。当然，根据Simnew的文本相似度的排序和根据Sim的相似度排序不会改变文本间的相似度趋势，因此能够充分利用该参数减小其他相似度低的文本的干扰，更准确地找到最相似文本。表2所示为10个15维的文本向量，利用Simnew和Sim分别计算这10个文本向量与“文本向量1”的相似程度，结果如图2所示。
从图2中可以看出，编号为4、8的这两个文本与文本1计算的Sim值相对较小，即这两个文本与文本1的相似度较小。新的算法没有改变曲线的变化趋势，但是却明显地降低了4、8这两个文本向量的Sim值，这说明改进后的算法能够有效地减少相似度低的文本的干扰。
3 改进算法的系统实现
本文将改进的文本相似度计算方法用于科研项目立项申报系统中，设计并实现了基于该算法的相似项目查询子系统。该子系统能够快速、准确地检索到同类别项目中有无项目与新申报的项目相似，并设定阈值，通过两两计算项目文本的相似度，找到相似度高于阈值的项目，一定程度上杜绝了项目重复申报的现象。
图3为子系统的结构图。系统流程为:首先，通过统计各项目文本的特征词，生成词典;然后将待比较的项目文本进行分词[2,3]操作后，利用词典统计词频，生成向量空间向量[4];之后与同类别项目中其余项目文本的向量空间向量进行相似度计算，选出相似度高于预定阈值的项目文本，即可以得到最终的计算结果。
本文选用从网络上搜集到的400个项目文本作为实验用文本，对这些文本进行分词操作，并对文本进行编号。查找前100个相似度高于0.85的项目文本，将查找结果保存在．txt类型文件中，如图4所示。
可以看到，系统精确地查找出了前100个文本中相似度高于0.85的文本对。对所有400个文本相似度查找耗时不到1秒，可见无论是在分类速度还是效果上，都达到了较高的应用水平。
4 结语
针对传统的基于VSM的文本相似度计算算法，由于没有对文本间相同的特征词进行统计，从而导致有时计算结果不准确的问题，本文提出了一种改进的文本相似度计算算法。改进算法充分考虑到了文本间相同特征词对文本相似度的影响，有效减少相似度低的文本干扰。仿真实验和系统运行结果验证了新算法的有效性和准确性。
摘要：通过分析传统的基于向量空间模型(VSM)文本相似度计算算法存在的不足,提出一种改进的文本相似度计算算法。改进算法充分考虑到了文本间相同特征词对文本相似度的影响,有效减少了相似度低的文本干扰。仿真实验和系统运行结果验证了改进算法的有效性和准确性。
关键词：向量空间,文本相似度,特征词,覆盖度
参考文献
[1]张霞,王建东,顾海花.一种改进的页面相似性度量方法[J].计算机工程与应用,2010,46(19):141-144.
[2]岳晓光,等.基于.NET的中文分词系统设计与实现[J].微计算机信息,2010,26(4-3):214-216.
[3]张华平.计算所汉语词法分析系统ICTCLAS[EB/OL].2002-08-16.http://www.n lp.org.cn/project/project.php?proj_id=6.
【短文本相似度】推荐阅读：