支持用户偏好查询的领域概念图模型

高志君，郑俊生，安敬民

(1.大连东软信息学院 计算机学院，辽宁 大连 116023； 2.大连海事大学 信息科学技术学院，辽宁 大连 116026)

0 引 言

传统的概念聚类主要可分为3类，分别是基于语法相似度的概念聚类、基于语义相似度的概念聚类以及基于语用相似度的概念聚类方法[1]。基于语法相似的概念聚类主要是根据词汇间的上下文，判断其语法结构特征，将具有相似语法结构的概念进行聚类，如文献[2]和文献[3]分别改进了传统的语法相似度聚类方法，在文献[2]中，作者提出了一种可在大规模文本数据中识别少量生成概念文本的模型，而文献[3]中将互信息与层次聚类相结合，采用自底向上的方式判断概念间语法特征的相似性，进而实现了概念聚类。基于语义相似度的概念聚类是当前较为通用的一种方法，该方法利用WordNet等语义知识库计算概念间的语义相似度(包括：语义距离、密度和深度等)，并将其融合到K-Means[4]或层次聚类[5]等不同的方法中，以实现概念的语义聚类。如：文献[6,7]使用改进的具有优化聚类中心能力的K-Means方法，并基于设定的阈值进行概念聚类。且在文献[8]中，作者重点考虑了概念在基于语义相似度聚类过程中出现的概念重叠问题，并提出利用图熵理论进行聚类而摒弃了原有选取聚类质心的方法。文献基于语用相似度的概念聚类不同于前者，其重点不在于概念本身的特点，而是关注于不同概念与某一对象的接近程度[9]。如：利用关键字搜索网页资源[10]，获得针对该网页的关键字间的关联关系。

上述方法均已在实践中得到了良好的验证，但都是从某一角度对概念聚类进行研究，仍缺少一种综合考虑概念间语义关系和用户偏好的方法，进一步提高聚类的应用效果。由于当前网络资源等大量的涌现，人们对于本体中概念的查询需求不再局限于领域专家所给出的同领域概念或基于语义知识库的语义相似度计算获得的具有较高关联性的概念，而同时针对用户偏好的查询也有所需求。如用户集U={u1,u2,…,ui,…,un} 和概念集C={c1,c2,…,ci,cj,…,cn}， 用户u1,u2,…,ui等高频次地同时查询概念ci和cj，说明ci和cj间隐含着用户的用户查询偏好。故，将此用户偏好关系数值化并合理地用于补充原有的概念语义关系中，可对原有查询聚类结果进行有益地补充，提高用户查询的查准率和查全率。所以，本文基于此问题，提出了支持用户偏好查询的领域概念图模型，具体的创新点及步骤如下：①从多角度(语义距离、深度和密度及内容)计算概念间的语义相似度，并构建领域概念语义关系图，实现各领域本体(如：医药学、农学、海洋科学及计算机科学技术学等领域)中不同概念间关系的重构(改进了原领域本体中概念关系仅从单一角度考虑的情况)；②利用改进的互信息方法挖掘UGD中隐含的不同概念间的用户偏好关系值；③利用用户针对概念的偏好关系补全步骤①中的语义关系图，以获得支持用户偏好查询的领域概念图模型及本体，使得各领域的研究人员和用户在查询和分析不同领域概念时，能够获得更为准确和全面的概念数据。

1 概念间的语义相似度计算与语义关系图的构建

目前，概念间的语义相似度的计算方法可以在概念间的语义距离[10]，WordNet中深度关系和密度关系[11]或重合度及内容相关度等[12]多个方面上实现。本文从多角度考虑概念ci和cj间的语义关系，并将上述方法的结果进行有效地融合，得到ci和cj间的综合语义相似度，进一步提升结果的准确性。

基于语义距离的相似度计算：

D(ci,cj) 表示WordNet中ci和cj间的语义距离CS(ci,cj) 是ci和cj间的语义相似度，如式(1)计算所得

(1)

这里，a是ci和cj与WordNet中概念集合的平均语义距离。

基于深度的相似度关系计算：

令ci所在的语义树的最大深度分别为Hmax(ci)， 且H(ci) 表示ci在树中的深度，故，结合Hmax(ci) 和H(ci) 的概念ci和cj间相似度HS(ci,cj) 的计算公式如式(2)所示

(2)

基于密度的相似度关系计算：

令n(ci) 是ci对应的语义树中，以ci为根节点的直接子节点数，nmax(T) 则表示ci对应的语义树T中的所有非叶子节点的直接子节点数量的最大值。则ci和cj在WordNet中密度的语义相似度关系PS(ci,cj) 的计算方法，如式(3)所示

(3)

基于语义重合度的相似度关系计算：

若将从节点ci到根节点所经过的节点数记为S(ci)， 则基于语义重合度的ci和cj相似度SS(ci,cj) 的计算如式(4)所示

(4)

基于概念内容信息的相似度关系计算：

本文改进了文献[12]中提出的利用概念信息内容计算概念相似度的方法，考虑到WordNet中概念子节点的空间结构对概念信息内容值的影响，给出式(5)，计算IS(ci,cj)， 其中I(c) 计算方式由文献[12]而得

(5)

为了将上述的概念ci和cj间的语义距离、深度和密度关系以及语义重合度及内容信息方面的相关度进行有效合理的组合，本文使用加权的形式计算ci和cj间的综合语义相似度。考虑到过多的参数设定对最终结果的影响，本文利用主成分分析方法[13,14]分析CS、HS、PS、SS和IS的贡献率，进而动态地求解影响因子，克服了概念间语义相似度计算过多依赖WordNet的问题。

构建矩阵α=(xi1,xi2,xi3,xi4,xi5)T， 且i=1,2,3,4,5。 这里xi是由向量 (CS,HS,PS,SS,IS) 构成。基于主成分分析法将α等价转化为一维矩阵γ=[x′1,x′2,x′3,x′4,x′5]， 即α的主成分表示，并同时计算矩阵的特征值，以获取主成分贡献率 (q1,q2,q3,q4,q5)， 最终得概念间相似度综合计算公式为式(6)

KSIM(ci,cj)=q1x′1+q2x′2+q3x′3+q4x′4+q5x′5

(6)

将KSIM(ci,cj) 用于构建间的语义关系图，如定义1和图1所示。

图1 领域概念语义关系

定义1 令领域概念语义关系图GS=(V,E,η,θ1)，V表示概念集 {c1,c2,…,ci,cj,…,cn}， 表示E是概念节点间的边的集合 {e12,e23,…,eij,…,emn}，eij=；η=KSIM(ci,cj) 是eij的权值，θ1是判断语义关系的阈值，且当η>θ1时，概念ci与概念cj间存在边eij。

2 基于互信息的用户概念查询偏好关系挖掘

互信息[15,16](具体定义及公式参见文献[15,16])是度量不同实体间相关性的主要手段。

首先，本文使用互信息计算不同概念间可能隐含的针对用户偏好的直接交互关系，如定义2所示。

定义2 对于概念集C中任意两个概念ci和cj(i≠j)， 针对用户的查询偏好，ci和cj间的关联关系如式(7)所示

(7)

式中：I(ci,cj) 表示基于用户偏好的概念ci和cj间相关度，且I(ci,cj)∈[0,1]；P(ci) 表示用户查询ci的概率，P(ci,cj) 是ci和cj的联合概率，使用如式(8)和式(9)求得

(8)

(9)

这里，F表示用户查询概念频次总数，F(ci,cj) 是ci和cj同时被查询频次，F(ci) 表示概念ci的查询频次。

例2：如表1给出了用户u在概念集C上的概念查询的UGD记录 {ui,cj}。 由表1可知，F=5， (c1,c2) 即ci和cj同时被查询的次数为2，则F(c1,c2)=2，P(c1,c2)=0.4，I(c1,c2)=0.52， 所以c1和c2同时出现的频次与二者的关联性呈正相关。

表1 用户的查询概念记录

进一步地，若用户多次同时查询ci和ck及cj和ck，而未同时查询或很少同时查询ci和cj，并不一定说明用户对ci或cj的偏好程度较低(因为ci和cj均与ck有着密切的交互关系)，可能是很少有用户同时熟知ci和cj，且这种情况较为普遍，所以挖掘隐含在用户生成数据中的间接概念交互关系能进一步刻画用户查询偏好。本文根据定义2获得的I(ci,ck) 与I(ck,cj)， 计算ci和cj间可能存在间接交互关系，为此，本文给出如下定义3所示的计算方法。

定义3计算。若概念ci,ck和cj满足上述概念间接交互关系，则I(ci,cj)=I(ci,ck)I(ck,cj)， 具体地

I(ci,cj)=I(ci,ck)I(ck,cj)=

(10)

当k不唯一，即k=1,2,…,n时，根据式(5)可知，I(ci,cj) 不唯一，此时本文综合不同的I1(ci,cj)，I2(ci,cj)， …和In(ci,cj)， 利用运算获得最终的I(ci,cj)， 如式(11)所示

I(ci,cj)=I1(ci,cj)I2(ci,cj)…In(ci,cj)

(11)

式中：两个不同概念间的交互关系I(ci,cj) 与I(cj,ci) 是相等的，且I(ci,ck)I(ck,cj)=I(ck,cj)I(ci,ck)，I(ci,cj)∈[0,1]。

3 基于偏好查询的语义关系图补全

GS中缺失的边表明对应节点ci和cj间的语义相似度较低(小于θ1)，所以在用户查询其中某个概念ci时，另一个概念cj应该不能作为相关联概念出现，但这是从语义角度考虑的，如果进一步从语用和用户查询偏好角度考虑，如果用户经常性地同时直接或间接地查询ci和cj，即使二者语义相关度很低，但cj仍应该作为ci的相关概念，同时作为查询结果。这一过程综合了ci和cj的语用和语义关系，进一步满足用户查询需求。本文将上述第1节和第2节中提出领域概念相似度计算方法与用户偏好挖掘方法相结合，首先针对不同领域分别构建领域概念语义关系图GS，其次从获取得到的UGD中挖掘(训练)出用户在不同概念间的查询偏好，并最终利用后者得到的概念间隐含的用户偏好关系补全GS以获得支持用户偏好查询的概念语义关系图GK，用于不同领域中本体的构建以及概念查询。具体地，如算法1所示。

算法1： 基于UGD的领域概念语义关系图补全算法

Input：D： 用户生成数据集UGD片段；GS； 交互关系阈值θ2

Output： 支持偏好查询的领域概念图GK

(1)For eachciinGSdo

For eachcjinGSdo

利用由式(7)计算I(ci,cj); 构建邻接概念；

Ifeij∉E∩I(ci,cj)>θ2

补全eij;

Else

Continue;

End For

End For

(2)For eachciinGSdo

构建ci的邻居节点集Si；

For eachcjinGSdo

IfSi∩Sj≠∅

构建ci和cj的共同邻居节点集，←Si∩Sj;

构建三元组(ci,cj,ck)←{ci}∩{cj}∩{ck∈}

Else

Continue;

End For

End For

(3)For each (ci,cj,ck) do

利用式(10)和式(11)计算I(ci,cj);

IfI(ci,cj)>θ2

补全eij;

Else

Continue;

End For

(4)GK←GS;

(5)ReturnGK;

算法1旨在利用用户查询的生成数据补全概念本身的语义相似度构建的关系图GS。其中，主要时间消耗是在步骤(1)和步骤(2)，对于GS中含有n个概念节点，进行GS中缺失边的直接补全(对应上文的概念间直接交互关系的处理)的时间复杂度为O(n2)(步骤(1))，遍历GS中各个节点并构建其邻居节点的时间消耗可以认为也是O(n2)(步骤(2))，而步骤(3)进行GS中缺失边的间接补全(对应上文的概念间间接交互关系的处理)的时间复杂度为O(m2)(m≪n)，所以算法1的最终时间复杂度是O(n2)。最后对图1进行了更新的结构如图2所示。

图2 支持用户查偏好的领域概念语义关系

4 实验与分析

本文的实验过程是在Windows 10，内存8 GB，2.5 GHz的PC机上进行的，主要使用Microsoft.NET framework和SQL Server 2012 database搭建平台。本文的实验数据选取由全国科学技术名词审定委员会审定公布的领域概念集合作为实验数据集(http：//www.cnctst.cn/)，我们挑选其中24个领域中概念各500，并分配给100个用户，收集他们在一个月内查询记录(UGD)共96 743条。

实验1：本文提出模型中的参数有阈值θ1和θ2，而阈值的设置直接影响本文模型的性能，所以文中首先利用数据集进行参数的设置。将数据集中的60%作为训练集，剩余40%用于测试，结果见表2。由表中结果可知，随着阈值的增大，模型在支持用户查询的正确率在降低，同时消耗的时间代价也在减少，这是因为阈值较小时，构建图模型时对于概念间的关联关系过滤性较弱，图的连通性较强，进而用户的查询结构更多地包含了满足其要求的概念；但同时模型中的概念节点间的边结构复杂，查询时所花费的遍历时间代价相对较高。具体地，当阈值θ1,θ2≤0.6时，模型的正确率变化并不明显，而时间消耗却有明显变化，当θ1,θ2>0.6时，模型正确率开始明显地下降。说明θ1,θ2在0.6附近可使本文模型获得最优的性能表现，最终，本文设置θ1=0.55，θ2=0.6，此时正确率为0.794，消耗时间897 ms。

表2 不同阈值情况下的GK模型的性能表现

实验2：本文根据设定的阈值，以及训练出的GK模型，与现有的相关算法[3,8,10]进行对比，目的是能够在其基础上进一步提升查准率(precision)和查全率(recall)以及F-值，并使用文献[8]中的公式进行计算，如式(12)～式(14)所示。为了在实验过程中验证本文方法与其它方在支持多用户查询时的数据处理能力，本文将数据集分为不等的4组，分别是测试数据总数据量的10%、20%、30%和40%，并依次进行实验。对比方法中涉及到的参数均尽可能与其原文保持一致。查询过程中，本文依据三度影响力理论[17]，只查询路径长度小于等于3的路径上的相关概念(因为路径长度大于3的概念间尽管连通，但是关联性很弱)，具体对比结果如表3、表4及图3所示

(12)

(13)

(14)

这里，N是用户满足用户需求的概念个数，M为用户查询获得的概念个数；A表示概念集C当中所有满足用户查询需求的概念。

通过上述的实验结果不难发现，本文的方法整体上要优于其它3种方法。整体看来，随着实验数据的增加，4种方法的性能均受到了影响，但具体地，本文模型在precision方面，本文方法较文献[8]中的方法依次提高了1.53%、

表3 precision结果对比

表4 recall结果对比

图3 F-值对比

2.76%、6.03%及9.52%；在recall方面，较文献[8]在4组实验中分别提高了1.10%、3.31%、8.19%及10.89%。分析发现，由于数据的增加，其中包含了多个用户查询大量领域概念，文献[3,8,10]中的方法分别是基于语法、语义和语用角度来考量与用户查询概念相关的领域概念，而本文方法则在此基础上考虑了用户查询偏好，能够进一步补充用户的查询需求，所以用户偏好的挖掘在查询过程中起到了积极的作用。

实验3：考虑到支持用户查询的响应时间是反映模型性能的重要评价指标，本文利用实验2中的数据，对4种方法处理数据的响应时间进行对比，结果如图4所示。由图4发现，随着数据量增加，该4种方法的响应时间均是趋于上升，其中文献[8,10]中的方法响应时间增长比例较大，而文献[3]和本文方法的增长比例相对较小，且随着数据量加大，本文方法优势更加明显。原因在于本文提出的方法主要的时间消耗是在构建GK部分，且构建构成是在线下完成的，所以对于线上的查询过程消耗的时间主要花费在利用已有模型进行基于规则的遍历，而另外3种方法的时间消耗主要集中在线上的概念查询(聚类)过程中。

图4 响应时间对比

实验4：为验证本文的可拓展性，本文分别使用数据集的20%、40%、60%以及80%作为训练集，以验证在不同训练集下的GK模型的性能，结果如图5～图7所示。GK模型在使用较低数量的训练集构建时，其性能较低，而随着训练数据集达到40%甚至60%时，GK模型的性能明显提高，且在训练集在50%～60%间，GK模型性能达到最优，当训练集超过60%时，其性能开始下降。分析发现，由于较低的训练集致使构建的GK模型连通性较弱，使得遍历查询达不到预期效果，随着训练集增加，GK模型中概念节点间的关联关系不断建立，其连通性较强；但不断增加训练集，会导致GK中的概念间的关系(边)出现冗余的情况，使得性能降低。

图5 不同训练集下的precision值

图6 不同训练集下的recall值

图7 不同训练集下的F-值

5 结束语

本文主要针对现有概念查询聚类方法中未考虑用户查询偏好的问题，提出了一种支持用户偏好查询的领域概念图模型，全面考虑了概念的语义关系和语用关系在用户查询领域概念过程中的作用，将概念的语义和语用相结合，改进现有的概念语义相似度计算方法，利用综合语义相似度计算方法计算不同概念间的语义关系，并构建对应的关系图；针对用户生成数据，分别考虑概念间的直接交互关系和间接交互关系，使用改进的互信息计算方法挖掘UGD中隐含的用户偏好，并提出了一个基于UGD的领域概念语义关系图补全算法，实现GS的补全，获得GK。最后，本文从多个角度对GK模型进行实验，包括参数影响、precision、recall以及F-值，响应时间以及可拓展性，验证了本文方法整体上优于目前流行的概念聚类方法。因为训练集过大而造成的概念语义关系图中冗余的无用边过多，影响了模型的整体性能，所以下一步工作将专注于消除关系图中冗余边的研究。