线性代数式检索结果的相似度排序方法

(河北大学 计算机科学与技术学院,河北 保定 071002)

0 概述

作为现代数学的一个重要研究课题,线性代数式广泛应用于各种科技文献,相对于普通公式和文本,线性代数式的结构更复杂。目前主流的搜索引擎多数是针对文本而设计,且部分针对数学公式设计的检索系统也不能十分合理地完成线性代数式的搜索,因此,研究并设计具有线性代数式检索功能的数学公式检索系统具有重要意义。

目前,国内外针对线性代数式检索的研究并不多,而针对普通表达式的研究已取得一些成果,包括MathDex[1]、DLMF Search[2]、LeActiveMath[3-4]、EgoMath[5-7]、MathWebSearch[8-9]、Wikimirs[10-11]等。按照实现方法,可将上述成果分为改进文本搜索的数学检索系统和为数学公式建立专门索引的数学检索系统,前者不支持数学公式内容识别,而后者支持。随着网络数学资源的日渐丰富,用户进行检索时往往会返回大量的检索结果,如何按检索结果与查询公式的相似度由高到低将其进行排序,以缩短查询时间、提升工作效率,是实际应用中面临的挑战。

文献[12]将数学公式用五元组(s,n,r,p,b)表示,利用距离公式计算待查询式和结果式的五元组距离,得出相似度进而完成排序。文献[13]提出一种基于结构相似度的数学检索方法,其将不同形式的数学公式统一成Presentation MathML格式,采用“树编辑距离”方法计算公式之间的相似度。文献[14-15]定义“数据类型层级”“查询覆盖度”“匹配深度”等特征,利用对查询表达式和获取目标表达式的解析树进行递归的相似距离分析,计算其之间的相似度。文献[16-17]设计并实现数学公式检索系统MASE和Lattice-based Math Search,前者采用被动攻击的在线学习分类模型对检索结果进行排序,后者建立数学概念格,在格中完成数学公式的相关排序。文献[10]改进TF-IDF(Term Frequency-Inverse Document Frequency)算法,引入节点所处层次评价指标,计算每个节点的频率和倒排公式频率,完成相似度排序。文献[11]改进文献[10]方法,引入结果表达式中包含的与待查询式相同的节点数目占待查询式节点总数的比例,用其作为评价指标,优化排序结果。文献[18]采用加权算法形成权值分配矩阵,利用快速排序和优化排序对数学公式进行相似度计算。

上述方法为线性代数式检索结果排序提供了思路。由于线性代数式的结构、语法和语义的复杂性,只有选择合理的理论及模型,从多视角研究线性代数式的特征,才能完成线性代数式检索结果的相似度排序。本文将犹豫模糊集理论应用于线性代数式的相似度评价中,提出一种线性代数式检索结果相似度排序方法。在线性代数式的局部属性和整体属性2个方面建立隶属度函数,应用距离相似度公式计算犹豫模糊集之间的距离,完成待查询线性代数式与检索结果式的相似度计算,并最终得到排序结果。

1 线性代数式相似度评价特征

1.1 线性代数式检索模式

线性代数式种类较多,其变形和计算十分丰富,在设计检索系统时,应根据用户的实际需求设计不同的匹配模式。

定义1线性代数式中按照行列规则排列,既相互独立又互有联系的子表达式称为子公式。

定义2Eq为一个m行n列的线性代数查询式,Eq(i,j)(i=1,2,…,m;j=1,2,…,n)为其子公式,Erqt(t=1,2,…,h)为检索结果集合中的h个c行d列线性代数式,Erqt(k,l)(k=1,2,…,c;l=1,2,…,d)为其子公式。

线性代数式的检索功能覆盖了矩阵、行列式和方程组匹配3种模式,它们均是在子式匹配的基础上做了相应的改进。由于在匹配算法的设计时考虑到线性代数式的语法和语义变换问题,因此矩阵匹配结果中除包含与待查询矩阵精确一致,或部分子式包含待查询矩阵子式的矩阵外,还会包含查询式的转置、逆矩阵、增广矩阵和伴随矩阵等变换结果。因此,在矩阵检索结果的相似度评价中,也将查询式的转置、逆矩阵、增广矩阵和伴随矩阵作为相似度评价的因素。类似地,在行列式匹配中涉及转置变换和求值运算,而方程组匹配仅限于子式匹配。

子式匹配是将用户输入的待查询式Eq的子式Eq(i,j)和检索结果集Erqt的子式Erqt(k,l)看作一个独立的数学公式,按行优先原则递归地将Eq(i,j)和Erqt(k,l)进行包含匹配,即要求Eq(i,j)是Erqt(k,l)的一部分或两者完全相同,当包含匹配成功时,将该Erqt(k,l)所对应的Erqt返回给用户。子式匹配原理如图1所示。

图1 子式匹配原理

1.2 评价流程

对线性代数式进行相似度评价的流程分为3个步骤:特征提取,隶属度计算,相似度计算。

图2 线性代数式评价原理

在图2中,一级属性为局部属性{A1,A2,…,Am},二级属性为整体属性{Am+1,Am+2,…,An},每个属性包含一组评价标准,按每个属性所对应的评价标准进行特征提取,首先提取局部属性特征,并代入相应的隶属度函数进行计算,再按相同的原理提取整体属性特征,形成如图2所示的局部犹豫模糊集和整体犹豫模糊集,最后根据针对线性代数式变型的广义犹豫标准距离公式完成公式之间的相似度计算,该公式将在后文中给出详细定义。基于犹豫模糊集的线性代数式评价流程如图3所示。

图3 线性代数式评价流程

1.3 评价属性

本文从局部和整体2个部分进行线性代数式的相似度评价。综合考虑多种因素,定义线性代数式的评价属性如表1所示,其中针对不同的匹配模式,将个别属性设置为1来表示该属性值对该匹配模式的属性评价无影响。

表1 线性代数式评价属性

定义3calla[a,b]表示a与b的相似度。其中a,b表示代数式。

1.3.1 局部属性

线性代数式是多个子公式的组合,子公式的结构、数量、位置和相对位置等都影响着线性代数式之间的相似程度。因此,进行线性代数式相似度评价时需考虑如下属性:

1)结构属性AF

(1)长度标准indlen

按行优先原则考察Eq(i,j)与每一个以其为子式的Erqt(k,l)所包含的运算数和运算符的数目,两者的数目越接近,其相似度就越大。

calla[Eq(1,1),Erq1(1,1)]

(1)

(2)层次标准indlev

图4 线性代数式层次与相似度关系

(3)位置标准indloc

calla[Eq(1,1),Erq1(1,1)]>calla[Eq(1,1),Erq2(2,1)]

(2)

(4)起始位标准indsta

图5 线性代数式起始位与相似度关系

(5)标志位标准indfla

图6 线性代数式标志位与相似度关系

2)运算数属性AO

按行优先原则考察Eq(i,j)与以其为子式的Erqt(k,l)的运算数信息,设Eq(i,j)中包含若干运算数{O1,O2,…,Os1},其中,s1表示Eq(i,j)所包含的运算数个数,考察Om(m=1,2,…,s1)在Erqt(k,l)中出现的次数及重要程度,将其作为一个评价标准indopd。

3)运算符属性AR

按行优先原则考察Eq(i,j)与以其为子式的Erqt(k,l)的运算符信息,设Eq(i,j)中包含若干运算符{R1,R2,…,Rs2},其中,s2表示Eq(i,j)所包含的运算符个数,考察Rn(n=1,2,…,s2)在Erqt(k,l)中出现的次数及重要程度,将其作为一个评价标准indopr。

1.3.2 整体属性

线性代数式在整体角度有其独特的特征,因此,在考察线性代数式间的相似度时应考虑其整体属性,从而得出更准确的测评结果。

1)矩阵变换属性AJ

考虑矩阵A的4种变形:转置变换AT,逆矩阵变换A-1,增广矩阵变换和伴随矩阵变换A*。将Eq和Erqt的矩阵变换信息作为评价标准indjuz。考虑到待查询矩阵与经过上述4种变换后矩阵的相似性,规定相似度排序为:原矩阵>转置矩阵>增广矩阵>逆矩阵>伴随矩阵>普通矩阵。

2)行列式变换属性AD

根据行列式的性质可知:D=DT,即行列式与其转置行列式相等,将行列式是否与原查询式互为转置作为评价标准indhal。

3)行列式的值属性AK

行列式可以进行求值运算,依据行列式的性质进行求值运算时,原行列式可能会发生变化,但其值不变,将行列式的值作为评价标准indkey。

4)规模属性AS

calla(Eq,Erq1)>calla(Eq,Erq2)

(3)

5)相同子表达式数量属性AN

设Eq中包含若干子表达式{N1,N2,…,Ns3},其中,s3为Eq所包含的子表达式个数,将Erqt中每个子表达式Nd(d=1,2,…,s3)出现的个数及其所占的比例作为一个评价标准indnsu。

1.4 犹豫模糊隶属度定义及参数设置

1.4.1 犹豫模糊隶属度定义

定义4长度标准indlen的隶属度函数为:

findlen[Eq(i,j),Erqt(k,l)]=lb(1+indlen)

(4)

定义5层次标准indlev的隶属度函数为:

findlev[Eq(i,j),Erqt(k,l)]=eη·indlev

(5)

其中,indlev为子式Eq(i,j)在Erqt(k,l)中所处的层次,η为层次属性权重系数。

定义6位置标准indloc的隶属度函数为:

(6)

其中,rmin=min(i,k)表示Eq(i,j)和Erqt(k,l)所处行号中较小值,rmax=max(i,k),表示Eq(i,j)和Erqt(k,l)所处行号中较大值,cmin=min(j,l),表示Eq(i,j)和Erqt(k,l)所处列号中较小值,cmax=max(j,l),表示Eq(i,j)和Erqt(k,l)所处列号中较大值。

定义7起始位标准indsta的隶属度函数为:

findsta[Eq(i,j),Erqt(k,l)]=e-μindsta

(7)

其中,indsta为子式Eq(i,j)在Erqt(k,l)中所处的水平位置(规定初始位置为0),μ为起始位属性权重系数。

定义8标志位标准indfla的隶属度函数如表2所示。本文将标志位信息内部做了特殊处理,为区分各行,规定每行第1个子式的主基线标志位为6i,其中,i=1,2,…,表示行号。每行非第1个子式的主基线标志位为0。

表2 标志位g隶属度值

定义9运算数标准indopd的隶属度函数为:

(8)

定义10运算符标准indopr的隶属度函数为:

(9)

定义11矩阵变换标准indjuz的隶属度函数如表3所示。

表3 矩阵不同变换形式的隶属度值

定义12行列式变换标准indhal的隶属度函数为:

(10)

定义13行列式的值标准indkey的隶属度函数为:

(11)

定义14规模标准indsiz的隶属度函数为:

(12)

其中,Rmin=min(m,c)表示Eq和Erqt的行数中较小值,Rmax=max(m,c)表示Eq和Erqt的行数中较大值,Cmin=min(n,d)表示Eq和Erqt的列数中较小值,Cmax=max(n,d)表示Eq和Erqt的列数中较大值。

定义15相同子表达式个数标准indnsu的隶属度函数为:

findnsu[Eq(i,j),Erqt(k,l)]=

(13)

其中,D=m×n表示Eq包含的子式总数,cntq(i,j)表示Eq(i,j)与Erqt(k,l)完全相同的次数,cntrqt(k,l)表示Erqt的子公式总数。

1.4.2 参数设定

隶属度函数参数设定说明如下。

层次属性权重系数η:通过统计数据库中6 352个表达式的节点总数、层次信息以及处于该层的节点个数,并将处于某层的节点个数归一化,利用polyfit函数借助MATLAB软件绘制图像,最终确定η值为-0.113。

起始位属性权重系数μ:通过统计数据库中6 352个表达式的长度信息,找出最小长度、中间长度、最大长度和分布中心长度,统计在[LEN,LEN+10](LEN=最小长度,或中间长度,或最大长度,或分布中心长度)范围内的表达式个数并进行归一化处理,将这4类长度与其加10后的长度进行取平均值处理,利用polyfit函数借助MATLAB软件绘制图像,最终确定μ值为0.56。

根据统计数据库中不同g值所对应的表达式个数占表达式总数的比例,以及不同标志位所代表的典型运算的常见程度,进行g隶属度的取值设定。

综合考虑用户的检索需求及几种不同矩阵的常见性,进行矩阵不同变换形式的隶属度取值设定。

1.5 犹豫模糊集及线性代数式相似度计算

文献[19]提出模糊集概念,之后一些学者又对其进行扩展,相继提出直觉模糊集、Type2型模糊集、模糊多重集等,但在处理决策问题时其模糊不确定性方面存在缺陷,特别是在专家对某对象的某个属性进行评价时出现犹豫的情况。对此文献[20]提出犹豫模糊集的概念,用一个集合的形式给出某一对象属于模糊集的程度,该方法不再需要专家对属性值给定一个误差范围或几个可能值的分布,就可以对决策中的不确定性进行有效刻画,为数学公式检索结果排序提供理论支撑。此后,区间值犹豫模糊集[21]及其相应的一些关联度、距离及相似性测度、算子和相应的决策方法相继被提出[22]。

1.5.1 犹豫模糊集相关概念

定义16设X是一个非空集合,则称式(14)为犹豫模糊集。

E={|x∈X}

(14)

其中,hE(x)称为犹豫模糊元素,是元素x对于集合E的几个可能隶属度的集合,该元素值在[0,1]区间内分布[20]。

定义17设P和Q分别为非空集合X={x1,x2,…,xn}中的2个犹豫模糊集合,则P和Q的广义犹豫标准距离表示为:

(15)

定义18P和Q的相似度表示为:

s(P,Q)=1-dghn(P,Q)

(16)

1.5.2 线性代数式相似度计算

线性代数式相似度计算分为3步:局部特征相似度计算,整体特征相似度计算和公式相似度计算。各步骤具体内容如下:

步骤1设Eq(i,j)和Erqt(k,l)分别对应犹豫模糊集合Hfq(i,j)和Hfrqt(k,l),这2个集合所对应的犹豫模糊元素为Pq(i,j)(Aa)和Prqt(k,l)(Aa),其中Aa表示局部评价属性,且a=1,2,3。根据式(15)得到局部特征犹豫模糊集合的广义犹豫标准距离,再根据式(16)得出2个犹豫模糊集合的相似度。

s(Hfq(i,j),Hfrqt(k,l))=1-dghn(Hfq(i,j),Hfrqt(k,l))=

(17)

设srqt表示最终局部相似度,若同一个Erqt(k,l)有多个相似度值,就取最大值作为其相似度值。对同一个Erqt的每一个子式的最大相似度求平均值,即为Erqt的最终局部相似度。

(18)

步骤2设Eq和Erqt的整体评价属性分别对应的犹豫模糊集合为Hfq和Hfrqt,这2个集合所对应的犹豫模糊元素为Pqw(Aw)和Prqwt(Aw),其中,Aw表示整体评价属性,且w=1,2,3,4,5。考虑到用户的实际需求,每个整体评价标准对检索结果相似度排序的影响程度不同,将式(15)适当变形,得出2个犹豫模糊集的相似度为:

s(Hfq,Hfrqt)=1-dghn(Hfq,Hfrqt)=

(19)

其中,在考虑大量用户检索需求的基础上,经过统计不同整体属性所代表的典型线性代数式与待查询式的逻辑相似性,进而进行θi值的设定(对不同匹配模式的相似度评价没有影响的整体属性对应的θi值设置为0)。例如:当用户检索式为某一矩阵时,用户更想查询出原矩阵及其转置矩阵、增广矩阵、逆矩阵等。基于此,每种匹配模式的整体评价属性所对应的θi值如表4所示。

表4 各类匹配模式整体属性所对应θi值

步骤3将上述2部分相似度取平均值,即得到2个公式的相似度。

(20)

2 线性代数式排序算法

不同匹配模式的排序算法,其原理大致相同,算法步骤如下:

输入LaTeX形式的线性代数查询式

输出LaTeX形式的线性代数结果式排序结果

1)初始化数据表LaForm、SubForm、Whole、NodeInf、OpInf、Rt_end。

2)将待查询式子式的subid、文件名subnam和字符串substr存入表SubForm中,对其进行解析,将特征存入表NodeInf、OpInf。

3)i=i+1,若i>待查询线性代数式的子式总数,执行步骤5),否则执行步骤4)。

4)查询数据库中SubForm表,若数据库中表达式子式的字符串含有该查询式的子式,则对其进行解析,存入表NodeInf、OpInf、Whole,计算局部相似度,存入表NodeInf;否则,算法结束。

5)将待查询式的Eqid、文件名Eqfnam和字符串Eqstr存入表LaForm,对其进行解析,将特征存入表NodeInf、OpInf、Whole。

6)j=j+1,若j>数据库中表达式总数,执行步骤8);否则,执行步骤7)。

7)查询数据库中NodeInf表,并根据Formid在表达式表FORMULA中找到对应表达式,对其进行解析,并将特征存入表LaForm、SubForm、NodeInf、OpInf,计算整体属性相似度,存入表Whole。

8)计算线性代数式的相似度并将最终结果写入表Result_end,并把该表按s_end降序返回给用户。

假设待查询线性代数式的子公式总数为m1,数据库中线性代数公式的总数为n,则数据库中线性代数公式的子公式总数为m2×n,其中m2为数据库中线性代数公式子公式个数的平均值。根据实验数据可知:1≤m1<

表5 检索结果所对应犹豫模糊集合

表6 结果表达式相似度计算结果

3 实验结果与分析

采用C#进行编程,结合SQL2013,应用犹豫模糊集理论进行线性代数式检索及结果排序。由于目前国内外对此方面的研究并不多,相关数据集较少,因此本文选取线性代数课本和网络上相关文献的电子文档,从中提取MathType格式的线性代数表达式并转换成LaTeX形式,再通过解析程序将其存储于数据库中,最终共得到6 352条用于实验的线性代数式数据集。因为本文系统主要针对线性代数式,所以选择与数学检索系统SearchOnMath(http://searchonmath.com/,一个直接查询数学内容的搜索引擎,查询结果包含给定数学公式的网页,并给出其不同的相似性)进行对比,并引入斯皮尔曼秩次相关系数概念用以检验检索结果的合理性,斯皮尔曼秩次相关系数定义如下:

定义19斯皮尔曼秩次相关系数[24]是反映2组变量之间联系密切程度的统计分析指标,适用于2组无序数列相关性大小的计算,其值越大,表示相关性越高。斯皮尔曼秩次相关系数计算公式为:

(21)

其中,di表示2组无序序列按递增或递减排序后,每个数列元素位置变化的差值,n表示2个序列的长度。

表7 待查询线性代数式

表8 排序结果对比

让一组专家对表7中每个查询表达式的检索结果集合进行人工排序,将该排序结果作为评价标准,利用斯皮尔曼秩次相关系数,分别计算本文方法和SearchOnMath方法的排序结果与人工排序结果的相关性,得到如图7所示的相关性比较结果,其中,斯皮尔曼秩次相关系数越高,说明排序结果越符合用户需求。

图7 2种方法与人工排序结果的相关性比较

由图7可以看出,本文方法的排序结果与人工排序结果更接近,因此,本文方法更能满足用户的查询需求。

4 结束语

针对线性代数式的检索及结果排序,本文从多角度分析并归纳线性代数式的特征,利用犹豫模糊集的相关理论建立相应的隶属度函数,对抽象的公式特征进行数量化,从而实现线性代数式的相似度评价,完成线性代数式检索结果的合理排序。对比实验验证了该方法在线性代数式相似度评价上的合理性和有效性。但本文实验在线性代数式的特征选取上还不够全面,评价函数涉及的参数选择还需优化,下一步将对此进行研究。

[1] MINER R,MUNAVALLI R.An approach to mathematical search through query formulation and data normaliza-tion[C]//Proceedings of the 14th Symposium on Towards Mechanized Mathematical Assistants.Berlin,Germany:Springer,2007:342-355.

[2] MILLER B,YOUSSEF A.Technical aspects of the digital library of mathematical functions[J].Annals of Mathematics and Artificial Intelligence,2003,38(1):121-136.

[3] LIBBRECHT P,MELIS E.Semantic search in leactive-math[EB/OL].[2017-09-05].http://www.hoplahup.net/copy_left/Libbrecht-etal-Semant ic-Search-WebALT-06.pdf.

[4] LIBBRECHT P,MELIS E.Methods to access and retrieve mathematical content in active math[C]//Proceedings of 2006 Mathematical Software-ICMS.Berlin,Germany:Springer,2006:331-342.

[5] MISUTKA J,GALAMBOS L.Mathematical extension of full text search engine indexer[C]//Proceedings of the 3rd International Conference on Information and Communication Technologies.Washington D.C.,USA:IEEE Press,2008:1-6.

[7] MISUTKA J,GALAMBOS L.System description:EgoMath2 as a tool for mathematical searching on Wikipedia.org[C]//Proceedings of the 18th Calculemus and 10th International Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2011:307-309.

[8] KOHLHASE M,SUCAN I.A search engine for mathematical formulae[C]//Proceedings of the 8th International Conference on Artificial Intelligence and Symbolic Computation.Berlin,Germany:Springer,2006:241-253.

[9] KOHLHASE M,ANCA S,JUCOVSCHI C,et al.MathWebSearch 0.4,a semantic search engine for mathematics[EB/OL].[2017-09-15].https://www.researchgate.net/publication/216797208_MathWebSearch_04_A_Semantic_Search_Engine_for_Mathematics.

[10] HU X,GAO L C,LIN X Y,et al.WikiMirs:a mathe-matical information retrieval system for Wikipedia[C]//Proceedings of the 13th ACM/IEEE-CS Joint Conference on Digital Libraries.New York,USA:ACM Press,2013:11-20.

[11] LIN X Y,GAO L C,HU X,et al.A mathematics retrieval system for formulae in layout presentations[C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2014:697-706.

[12] SCHELLENBERG T,YUAN B,ZANIBBI R.Layout-based substitution tree indexing and retrieval for mathematical expressions[J].Document Recognition and Retrieval XIX,2012,8297(2):263-271.

[13] KAMALI S,TOMPA F W.Structural similarity search for mathematics retrieval[C]//Proceedings of 2013 Inter-national Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2013:246-262.

[14] ZHANG Q,YOUSSEF A.An approach to math-similarity search[C]//Proceedings of 2014 International Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2014:404-418.

[15] 田学东,张凯歌,周 南,等.一种数学表达式检索结果相关排序算法[J].计算机工程,2017,43(3):204-212.

[16] NGUYEN T T,CHANG K,HUI S C.A math-aware search engine for math question answering system[C]//Proceedings of the 21st ACM International Conference on Information and knowledge Management.New York,USA:ACM Press,2012:724-733.

[17] NGUYEN T T,HUI S C,CHANG K.A lattice-based approach for mathematical search using formal concept analysis[J].Expert Systems with Applications,2012,39(5):5820-5828.

[18] 马惠娟.数学搜索中索引模型研究[D].兰州:兰州大学,2013.

[19] ZADEH L A.Fuzzy sets[J].Information and Control,1965,8(3):338-353.

[20] TORRA V.Hesitant fuzzy sets[J].International Journal of Intelligent Systems,2010,25(6):529-539.

[21] 陈树伟,蔡丽娜.区间值犹豫模糊集[J].模糊系统与数学,2013,27(6):38-44.

[22] 蔡丽娜.区间值犹豫模糊集及其在决策中的应用研究[D].郑州:郑州大学,2013.

[23] XU Z S,XIA M M.Distant and similarity measures for hesitant fuzzy sets[J].Information Sciences,2011,181(11):2128-2138.

[24] KENDALL M,GIBBONS J D.Rank correlation methods[M].New York,USA:Oxford University Press,1990.