基于WordNet的因素空间算法在搜索引擎中的应用

2020-10-27郑文良关世杰尹安琪刘旭东

沈阳理工大学学报 2020年3期

郑文良，关世杰，尹安琪，刘旭东

(1.沈阳理工大学 a.发展规划处，b.信息科学与工程学院，沈阳 110159；2.营口职业技术学院机电工程学院，辽宁营口 115002)

随着大数据时代的到来，信息数据优势已经渗透到政府、企业以及高校等各个行业，数据的及时性与准确性已成为提升本行业的利器，数据分析在制定决策的过程中作用日益显著。如何在海量检索数据中提高语义相关性，已成为一个重要课题。本研究在基于P2P技术的分布式搜索引擎架构基础上[1]，在应用层Search Pocket模块引入了基于WordNet语义关系的因素空间展开与收拢算法，可大幅提高检索的准确性。

1 基于P2P技术的分布式搜索引擎的架构

基于P2P技术的分布式搜索引擎系统主要由智能代理服务器(Intelligent Agent Server)和检索系统Search Pocket组成。智能代理服务器可为检索用户提供信息注册，Search Pocket为检索系统的核心部分，包括应用层、控制层和数据层。其中，应用层为用户上传检索信息的部分；控制层采用分级B-tree结构，将检索的信息由多维空间上的相似度度量问题转化成在一维度量空间上的间隔问题；数据层则对关键节点进行取舍[1]。

2 因素之间的关系分析

2.1 因素之间的运算

当对一个本体进行分析时，可以从与其相关的因素进行考察，即本体o与因素f相关，且本体与因素之间的映射关系用f(o)表示。与因素相关的概念如下。

概念1子因素：若因素g是因素f的真子集，记作f>g，如果X(g)是X(f)的真子集空间，即存在着非空的集合Y，使X(f)=X(g)*Y，称g是f的子因素，记作f≥g。

Ф表示一种空状态，则对于任一状态x，都有(x，Ф)=(x)。

概念2因素的析取：若因素h是因素f和因素g的析取因素，记作h=f∧g，如果X(h)是X(f)与X(g)的公共子空间，Y是X(f)与X(g)的公共子空间，则Y一定是X(h)的子空间。如果X(g)是{x(ft)}(t∈T)的最大公共子空间，则因素g是{ft}(t∈T)因素族的析取，记作g=∧t∈Tft。

概念3因素的合取：若因素h是因素f和因素g的合取，记作h=f∨g，如果X(f)和X(g)是X(h)的子空间，并且空间中的最小者。如果{x(ft)}(t∈T)是X(g)的子空间，并且是空间中最小的因素，则因素g称为因素族{ft}(t∈T)的合取，记作g=∨t∈Tft。

概念4因素的减法：若因素f与g之差是因素h，记作h=f-g，如果(f∧g)∨h=f。若f∨g存在，则

X(f∨g)=X(f-g)×X(f∧g)×X(g-f)

(1)

2.2 基于WordNet的语义关系分析

在进行相似度分析时，可通过类相似度进行构造语义空间，空间向量中的每个元素都表示类与类之间的相似度。在机器学习的过程中，本研究引入了WordNet为本体类构造层次化相似度。在WordNet中一个基本的语义概念包含多个同义词，构成同义词集合，这些集合通过语义关系联系在一起，形成一个个词汇网络。名词网络中的层次主要体现的是蕴含关系，如上位关系与下位关系、整体与部分关系、继承关系等。词与词之间的距离越近，则两者之间的语义关系就越相似。在样本学习中，对已知类别和未知类别可以抽取其在WordNet中的最小公共上位子集，使用路径长度计算每个物体与上位子集中所有类的相似度，这些相似度所组成的向量是层次化语义嵌入向量[2]。可以通过以下三个公式进行相似度的计算。

simjc=2×IC(mscs(c1,c2))-IC(c1)-IC(c2)

(2)

(3)

simpath=minp∈pth(c1,c2)len(p)

(4)

式中：c1、c2表示两个不同的类别标签；mscs表示c1、c2的公共父节点；IC(c)表示信息量，常用的IC值计算模型为IC=-logp(c)，p(c)表示c出现的概率；pth(c1，c2)表示c1和c2之间的路径集合；len表示路径长度。

3 因素空间的展开与收拢

因素空间的展开与收拢是WordNet上下位关系的一种，不同的语义进行因素空间的展开后得到的下位词不同。本研究根据WordNet给出的例子(如图1所示)，对因素空间的展开与收拢进行阐述[3-4]。

图1 WordNet示意图

3.1 因素空间的展开

因素空间的展开是因素合取得一种算法，根据因素的上下位关系将因素空间进行展开，具体定义如下：

概念5因素空间的展开：现有因素g、因素f、因素s分析样本o，样本与因素之间的映射关系用A(o)表示，因素合取可表示为A(o)→g+f+s。分析样本时，增加分析视角的维度，将多个因素相结合，使综合程度加大，考虑的范围更广，使问题思考的更加全面，多个因素在决策过程中共同发挥作用。

如：property展开后为magnitude；magnitude展开后有size、volume、dimension、degree、extent；将size展开后得到circumference、largeness、smallness、distance；将dimension 展开后得到height、length、width；将length展开后得到longness、shortness。将因素根据上下位进行展开后，因素更加具体，上位因素包含下位因素。本研究采用自上而下树状结构的层次聚类算法，如图2所示。

图2 层次聚类算法的结构

给定的数据集样本X=(x1，x2，…，xm)，在层次聚类时首先对数据进行初始化处理，数据集中每个数据样本在初始时是单独的一个簇；接着计算出两个样本簇之间的距离，将距离相近的两个簇进行合并后得到一个新的簇；再计算新的簇之间的距离，直到将所有的簇归为同一类。层次聚类与其他聚类算法相比不需要预先设置聚类的类别数量。层次聚类的终止取决于所设置的类别之间的阈值，不同的阈值可以得出不同的聚类结果。通过聚类算法对因素空间中的因素和属性进行聚类[5]。

3.2 因素空间的收拢

因素空间的收拢是因素减约的一种算法，具体定义如下。

概念6 因素空间的收拢：对于给定的因素fj及其所取的转态su，记，

(5)

如果[su]中结果因素g具有相同的状态活等级tu，使

[tu]={ui|g(ui)=tu}⊇[su]

(6)

则称[su]是因素fj的一个决定类。所有决定类的合集称为该因素fj对结果的决定域。

因素fj的决定域所占行数h与表的行数(即全体对象个数)m之比称为其对结果的决定度，记作

d(fj)=h/m

(7)

因素空间的收拢是把视角的维度减少，进行语义降维，提取出关键因素，确保对结果有重要影响的因素进入经验推理系统，影响不大的因素在决策的过程中自动地被舍弃。在因素约减过程中确保重要因素不被约减掉的同时降低了算法的时间的复杂度，推进了算法的进程[3]。其过程是因素空间展开过程的逆过程，具体执行过程如：将highness和lowness进行收拢后得到height，将circumference、largeness、smallness、distance进行收拢后得到size。将下位因素进行收拢后得到上位因素，因素更加具有概括性。

4 基于WordNet的相似度计算

基于WordNet的相似度计算是基于上位词层次结构中相互连接的概念之间的最短路径在0～1范围的打分。无路径返回0，同义词与自身比较返回1。

利用WordNet提供的接口函数，从WordNet的同义词集(synet)、属类词(class word)和意义解释(sense explanation)三个集合中抽取候选同义词，然后进行特征提取，计算出feature(SW)。

feature(SW)={{Ws}，{Wc}，{We}}

(8)

式中：{Ws}为WordNet中概念W的所有的同义词；{Wc}为WordNet中概念W的所有的相关的属类；{We}为WordNet中概念W的解释中所有的实词。

根据上面对词汇语义特征的描述，两个概念之间的相似度可以通过计算其在三个不同意义特征空间中的距离来得到。距离越小，相似度越大。根据意义相似度就可以容易的计算出WordNet中两个词语之间的相似度[3]。

意义相似度：

(9)

式中：No(SW)为W意义的顺序，如，the first sense=1，the second sense=2等；IDF(wi)为从WordNet中训练得到的构建WordNet时出现某个wi的文档的个数；Ks为同义词特征的权重；Kc为类属特征的权重；Ke为意义解释的权重；QU为出现wi的指标集；QV为出现wj的指标集。

词语相似度的计算公式为

(10)

式中：|SW1|是W1的词义的个数；|SW2|是W2的词义的个数。

5 结果分析

本研究采用了NLTK(Natural Language Toolkit，自然语言工具包)，即Python的第三方库，可以很方便的完成很多自然语言处理的任务，包括分词、词性标注、命名实体识别及句法分析。语料库调用NLTK语料库。可以查看一个单词的同义词集(synet)，描述为一个三元组(单词.词性.序号)。

将因素空间展开与收拢算法嵌入到Search Pocket模块中，在模拟参数(表1)的网络中进行测试[1]，随机抓取400篇网页，得到相关度计算准确率为90%(表2)。