一种基于马尔可夫聚类的实体间关系消解方法

摘要

本发明提供一种基于马尔可夫聚类的实体间关系消解方法，包括：计算K个实体中任意两个实体之间的语义相似度；根据实体间的语义相似度构造赋权图G；构造状态转移矩阵M；在状态转移矩阵M上执行马尔科夫聚类算法，得到多个关系簇；其中，每个簇代表一系列语义相近似的实体。本发明提供的基于马尔可夫聚类的实体间关系消解方法具有以下优点：提出了融合词法和语义的相似度计算方法，然后给出了基于马尔科夫图聚类的关系聚类方法。该方法与层次聚类方法相比，聚类纯度指标有了一定提高，还具有计算过程简单快速的优点。

说明书

技术领域

本发明属于实体间关系消解技术领域，具体涉及一种基于马尔可夫聚类的实体间关系消解方法。

背景技术

近年来，随着互联网、云计算等IT技术的不断发展，网络数据快速增长，网络大数据给传统的信息处理方式带来了挑战。故需要构建一个知识库存放静态知识，其中，静态知识包括命名实体以及实体间关系，命名实体包括人、地点、机构等，实体间关系则多种多样，例如父母、同学、同事等等。关系消解就是对不同的实体关系的同义性进行判定，将同义不同名的实体关系对齐，并映射到相同的标签，关系消解可以提升知识库整体数据质量，方便后续计算，如利用实体间关系进行推理、发掘实体间隐含关系等。

关系消解实际是短文本的合并，现有的短文本合并方法主要有两类：一类是基于聚类的关系消解方法，即：通过聚类算法将语义相似的短语聚合到同一簇中，达到关系消解的目的。另一类方法是基于分类的关系消解方法，分类算法需要事先确定短语的种类，然后对每一类短语准备训练数据，通常需要大量人工标注，提取每类关系的特征，包括词语本身特征、上下文特征等，然后训练分类器再利用分类器将关系打上标签，最后达到合并的目的。

由于分类算法具有以下缺陷：分类算法必须预先确定或估计出最终关系的种类，然后才能进行特征提取模型训练，而当有新型关系出现时则无法处理了；另外，分类方法容易出现过拟合现象，对不同数据集有不同的分类效果。而聚类算法具有不需要大量人工标注、易于实施的优点，因此，聚类算法为一种更具发展前景的关系消解方法。

然而，现有技术中出现的各类基于聚类的关系消解方法，普遍具有聚类纯度较低、聚类过程较复杂等不足。

发明内容

针对现有技术存在的缺陷，本发明提供一种基于马尔可夫聚类的实体间关系消解方法，可有效解决上述问题。

本发明采用的技术方案如下：

本发明提供一种基于马尔可夫聚类的实体间关系消解方法，包括以下步骤：

步骤1，当需要对K个实体进行关系消解时，将K个实体分别记为P₁、P₂…P_K；计算K个实体中任意两个实体之间的语义相似度；

步骤2，根据实体间的语义相似度构造赋权图G；赋权图G的构造方法为：

步骤201，预设置相似度过滤系数θ；

步骤202，实体P₁、P₂…P_K作为聚类元素，形成节点；

步骤203，将任意两个节点用边相连，形成初始赋权图G；

步骤204，对于任意的一条边，记为La，假设其为实体P_i和实体P_j之间的边，均进行以下处理：

边La的权重即为步骤1计算得到的实体P_i和实体P_j之间的语义相似度，记为P_ij；

判断语义相似度P_ij的值是否小于相似度过滤系数θ，如果不小于，则保留边La；如果小于，则去除边La；

步骤205，由此形成最终的赋权图G；

步骤3，根据步骤205形成的赋权图G，构造状态转移矩阵M；其中，状态转移矩阵M的维数为赋权图G的节点数，即：状态转移矩阵M为K行K列的矩阵；状态转移矩阵中任意一个元素Q_ij，i为行数，j为列数，元素Q_ij的值采用以下规则：

如果i等于j时，元素Q_ij的值统一等于1；

如果i不等于j时，判断赋权图G中实体P_i和实体P_j之间是否存在边，如果存在，则令元素Q_ij的值等于实体P_i和实体P_j之间边的权重；如果不存在，则令元素Q_ij的值等于0；

步骤4，在状态转移矩阵M上执行马尔科夫聚类算法，得到多个关系簇；其中，每个簇代表一系列语义相近似的实体。

优选的，步骤1具体包括以下步骤：

步骤101，对于需要计算语义相似度的任意两个实体，分别记为实体P_i和实体P_j；首先判断实体P_i和实体P_j是否均属于《同义词词林》中的基本词语，如果是，则执行步骤102；否则，执行步骤103；

步骤102，实体P_i和实体P_j在《同义词词林》中均存在对应的编码，采用义项相似度计算方式计算实体P_i和实体P_j之间的语义相似度，即：

步骤1021，《同义词词林》中收录的每个词语对应一个5级编码，共8位，其中，第1级用大写英文字母表示；第2级用小写英文字母表示；第3级用二位十进制整数表示；第4级用大写英文字母表示；第5级用二位十进制整数表示；第8位为标记位，标记位采用三种标记符，分别是“＝”、“#”、“@”，其中“＝”代表相等、同义；“#”代表不等、同类，属于相关词语；“@”则表示独立，在词典中既没有相关词，也没有同义词；

步骤1022，读取到实体P_i的编码和实体P_j的编码，判断是否属于第一种情况，其中，第一种情况为：如果实体P_i的编码和实体P_j的编码的第1位到第7位完全相同，第8位均为“#”时，代表实体P_i和实体P_j是同类词语，但意思不相同，此时，令实体P_i的编码和实体P_j的语义相似度为0.5；如果不属于第一种情况，继续判断是否属于第二种情况，其中，第二种情况为：如果实体P_i的编码的第8位为“@”，和/或如果实体P_j的编码的第8位为“@”，此时，令实体P_i的编码和实体P_j的语义相似度为0；如果也不属于第二种情况，则继续判断是否属于第三种情况；其中，第三种情况为：实体P_i的编码和实体P_j的编码的第1位到第7位不完全一致，只有部分相同，则通过以下公式计算实体P_i和实体P_j的语义相似度：

sim(P_i,P_j)＝0.2×(i-1)；公式(1)

其中，sim(P_i,P_j)代表实体P_i和实体P_j的语义相似度；i的取值为[1,5]，代表实体P_i的编码和实体P_j的编码在第i层开始不同；

步骤103，利用分词工具分别对实体P_i和实体P_j进行分词并去除虚词，得到实体P_i分词后的词序列为Seq1＝a₁a₂a₃......a_x，得到实体P_j分词后的词序列为Seq2＝b₁b₂b₃......b_y；其中，实体P_i和实体P_j分词后所得到的词序列中的各个词属于《同义词词林》中的基本词语；

判断x是否等于y，如果等于，则执行步骤104；否则，执行步骤105；

步骤104，按公式2计算实体P_i和实体P_j的语义相似度:

其中，sim(a_i,b_j)按公式1计算；

步骤105，设x小于y，则从Seq2的y个分词中选择出x个分词，假设共有h种选择方式，由此得到h个序列2子序列，对于每1个序列2子序列，均采用公式2计算Seq1与序列2子序列之间的语义相似度，由此共得到h个语义相似度；h个语义相似度中的最大值即为最终计算得到的实体P_i和实体P_j的语义相似度。

优选的，步骤4具体包括以下步骤：

步骤401，对状态转移矩阵M进行一次随机游走，得到新的状态转移矩阵；然后，使用松弛系数τ对新的状态转移矩阵进行规格化，使每列的和为1，由此得到新的状态转移矩阵M’；

步骤402，判断状态转移矩阵M和新的状态转移矩阵M’的差别是否小于一定阈值，如果小于，则执行步骤403；否则，令M＝M’，继续执行步骤401；

步骤403，使用新的状态转移矩阵M’更新步骤2构造的赋权图G，其更新方法为：采用新的状态转移矩阵M’的相近度值更新赋权图G对应边的权重，并且，当更新后的边权重值低于相似度过滤系数θ时，删除对应边，由此得到新赋权图G；

步骤404，使用广度优先遍历方法计算新赋权图G的每个连通分支，每个连通分支即是一个关系簇。

本发明提供的基于马尔可夫聚类的实体间关系消解方法具有以下优点：

本发明可以快速，简单的计算短语相似度，最终可得到高质量聚类结果。

附图说明

图1为本发明提供的基于马尔可夫聚类的实体间关系消解方法的整体流程图；

图2为本发明提供的两个实体间语义相似度的计算流程图；

图3为本发明提供的马尔科夫聚类算法流程图。

具体实施方式

为了使本发明所解决的技术问题、技术方案及有益效果更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

本发明提出一种基于马尔可夫聚类的实体间关系消解方法，通过在不同规模数据集上实验，证明此方法与传统层次聚类方法相比，在聚类结果簇数相同时，纯度有明显提升。

本发明采用的技术方案是：首先计算实体集合中任意两个实体之间的语义相似度，然后将实体(聚类元素)作为点，实体间的相似度作为两节点之间的边构造赋权图，基于马尔科夫聚类算法生成多个含相似关系的簇，解决关系融合的问题。如图1所示，具体步骤包括：

步骤1，当需要对K个实体进行关系消解时，将K个实体分别记为P₁、P₂…P_K；计算K个实体中任意两个实体之间的语义相似度；

如图2所示，步骤1具体包括以下步骤：

步骤101，对于需要计算语义相似度的任意两个实体，分别记为实体P_i和实体P_j；首先判断实体P_i和实体P_j是否均属于《同义词词林》中的基本词语，如果是，则执行步骤102；否则，执行步骤103；

本步骤中，任意两个实体之间的语义相似度的计算需要参考《同义词词林》。《同义词词林》是梅家驹等人于1983年编纂而成，这本词典不仅包含了一个词语的同义词，也包含了一定数量的同类词，即广义的相关词。哈尔滨工业大学利用众多词语相关资源,完成了一部具有汉语大词表的同义词词林扩展版。同义词词林扩展版收录词语近7万条,全部按意义进行编排。本发明的实体之间的语义相似度计算使用的是同义词词林扩展版本。

《同义词词林》按照树状层次结构把所有收录的词条组织到一起，把词汇分成大、中、小三类，小类下有很多词群，词群又进一步分成若干行。《同义词词林》共提供了5级编码,第1级用大写英文字母表示；第2级用小写英文字母表示；第3级用二位十进制整数表示；第4级用大写英文字母表示；第5级用二位十进制整数表示。如“Aa01C01＝众人 人人 人们”，称Aa01C01是“众人”的一个义项，具体编码如下表所示。

上表中的编码位是从左到右排列，第8位的标记有三种，分别是“＝”、“#”、“@”，其中“＝”代表“相等”、“同义”；“#”代表“不等”、“同类”，属于相关词语；“@”则表示“独立”，表示它在词典中既没有相关词，也没有同义词。

由于汉语词语在不同语境下有不同语义，所以在《同义词词林》中一个汉语词语可能对应多种不同编码，称词语的每种编码方式为词语的一个义项。

实体之间语义相似度的计算分为义项相似度的计算和短语相似度的计算。当实体P_i和实体P_j均属于《同义词词林》中的基本词语时，执行步骤102，步骤102即为义项相似度的计算，义项相似度计算，主要是对两个实体的编码进行比较；否则，执行步骤103，步骤103即为短语相似度的计算，也就是说，《同义词词林》只是包含了基本词语的义项，而很多常见名词性短语在《同义词词林》中没有，此时采用步骤103的方法计算两个实体间语义相似度。

步骤102，实体P_i和实体P_j在《同义词词林》中均存在对应的编码，采用义项相似度计算方式计算实体P_i和实体P_j之间的语义相似度，即：

步骤1021，《同义词词林》中收录的每个词语对应一个5级编码，共8位，其中，第1级用大写英文字母表示；第2级用小写英文字母表示；第3级用二位十进制整数表示；第4级用大写英文字母表示；第5级用二位十进制整数表示；第8位为标记位，标记位采用三种标记符，分别是“＝”、“#”、“@”，其中“＝”代表相等、同义；“#”代表不等、同类，属于相关词语；“@”则表示独立，在词典中既没有相关词，也没有同义词；

步骤1022，读取到实体P_i的编码和实体P_j的编码，判断是否属于第一种情况，其中，第一种情况为：如果实体P_i的编码和实体P_j的编码的第1位到第7位完全相同，第8位均为“#”时，代表实体P_i和实体P_j是同类词语，但意思不相同，此时，令实体P_i的编码和实体P_j的语义相似度为0.5；如，义项“Ab04A03#”有两个词语“女婴”、“男婴”，二者是同类词语，但是意思不完全一致，这种情况下，，将二者相似度记为0.5。

如果不属于第一种情况，继续判断是否属于第二种情况，其中，第二种情况为：如果实体P_i的编码的第8位为“@”，和/或如果实体P_j的编码的第8位为“@”，此时，令实体P_i的编码和实体P_j的语义相似度为0；

也就是说，当实体编码第8位为“@”，表明此义项是独一无二的，没有同义词，将这个义项和其他任何义项的相似度记为0；

如果也不属于第二种情况，则继续判断是否属于第三种情况；其中，第三种情况为：实体P_i的编码和实体P_j的编码的第1位到第7位不完全一致，只有部分相同，则通过以下公式计算实体P_i和实体P_j的语义相似度：

sim(P_i,P_j)＝0.2×(i-1)；公式(1)

其中，sim(P_i,P_j)代表实体Pi和实体Pj的语义相似度；i的取值为[1,5]，代表实体P_i的编码和实体P_j的编码在第i层开始不同；

例如：

Ad03A01＝本地人当地人土著土人土著人

Ad03A02＝村里人全村人

Ad03A03@家里人

以计算“本地人”的义项“Ad03A01”和“村里人”的义项“Ad03A02”的相似度为例，因为两个义项在第5级出现不同，所以sim(Ad03A01,Ad03A02)＝0.2×(5-1)＝0.8。

在一词多义的情况下，以两个词最相近的义项的相似度作为两个词的相似度；，例如，词语“认真”有两种意思，即可以形容人做事情认真仔细，也可以形容某人对于某事当真、信以为真，“认真”在《同义词词林》中有两个义项，分别是：Ee27A01和Gb14A04，所以在计算时使用最相似的义项之间的相似度作为两个词的相似度；如果某个词语没有在《同义词词林》中出现，则它与任何其他词语的相似度都记为0。

步骤103，利用分词工具，例如，可以为ICTCLAS分词工具，分别对实体P_i和实体P_j进行分词并去除“的”“地”“得”等虚词，得到实体P_i分词后的词序列为Seq1＝a₁a₂a₃......a_x，得到实体P_j分词后的词序列为Seq2＝b₁b₂b₃......b_y；其中，实体P_i和实体P_j分词后所得到的词序列中的各个词属于《同义词词林》中的基本词语；

判断x是否等于y，如果等于，则执行步骤104；否则，执行步骤105；

步骤104，按公式2计算实体P_i和实体P_j的语义相似度:

其中，sim(a_i,b_j)按公式1计算；

公式(2)的两个词序列Seq1,Seq2必须是等长的，a_i,b_i是两个分词。

步骤105，设x小于y，则从Seq2的y个分词中选择出x个分词，假设共有h种选择方式，由此得到h个序列2子序列，对于每1个序列2子序列，均采用公式2计算Seq1与序列2子序列之间的语义相似度，由此共得到h个语义相似度；h个语义相似度中的最大值即为最终计算得到的实体P_i和实体P_j的语义相似度。

本步骤可描述为：对实体P_i和实体P_j进行分词分别得到两个长度不同的词序列时，取序列元素个数较小值进行排列的枚举，并利用公式2计算两个序列的相似度(序列元素个数相等)，这些相似度的最大值即为实体P_i和实体P_j的语义相似度。

例如，对实体A和实体B使用ICTCLAS分词工具进行分词，得到实体A的词序列SeqA＝{sa₁,sa₂,...,sa_m}和实体B的词序列SeqB＝{sb₁,sb₂,...,sb_n}，取length＝min(length(SeqA),length(SeqB))，分别从SeqA和SeqB中取出length个词，枚举这些排列，根据计算两个排列的相似度，这些相似度的最大值即为实体A和实体B的相似度。

步骤2，根据实体间的语义相似度构造赋权图G；赋权图G的构造方法为：

步骤201，预设置相似度过滤系数θ；

步骤202，实体P₁、P₂…P_K作为聚类元素，形成节点；

步骤203，将任意两个节点用边相连，形成初始赋权图G；

步骤204，对于任意的一条边，记为La，假设其为实体P_i和实体P_j之间的边，均进行以下处理：

边La的权重即为步骤1计算得到的实体P_i和实体P_j之间的语义相似度，记为P_ij；

判断语义相似度P_ij的值是否小于相似度过滤系数θ，如果不小于，则保留边La；如果小于，则去除边La；

步骤205，由此形成最终的赋权图G；

也就是说，当两个元素间的相似度为0或者小于相似度过滤系数θ时，其在图中对应的节点之间没有边相连。否则，这两个元素对应的点之间存在一条边，其权重等于二者的相似度。

通过设定相似度过滤系数θ对相似度矩阵M的数据做过滤，可以有效降低噪声，因为有些关系如“儿子”和“兄弟”肯定是不同的关系，但是通过步骤1相似度的计算方法，两者相似度并不会等于0，即在图上“儿子”和“兄弟”两个节点之间会产生一条边，虽然这条边权重不高，但是还是会给步骤4)中马尔科夫聚类算法带来干扰，所以通过设定过滤系数直接把一些较低的相似度去掉，可以有效提升结果质量。

步骤3，根据步骤205形成的赋权图G，构造状态转移矩阵M；其中，状态转移矩阵M的维数为赋权图G的节点数，即：状态转移矩阵M为K行K列的矩阵；状态转移矩阵中任意一个元素Q_ij，i为行数，j为列数，元素Q_ij的值采用以下规则：

如果i等于j时，元素Q_ij的值统一等于1；

如果i不等于j时，判断赋权图G中实体P_i和实体P_j之间是否存在边，如果存在，则令元素Q_ij的值等于实体P_i和实体P_j之间边的权重；如果不存在，则令元素Q_ij的值等于0；

步骤4，在状态转移矩阵M上执行马尔科夫聚类算法，得到多个关系簇；其中，每个簇代表一系列语义相近似的实体。

步骤4具体包括以下步骤：

步骤401，对状态转移矩阵M进行一次随机游走，得到新的状态转移矩阵；然后，使用松弛系数τ对新的状态转移矩阵进行规格化，使每列的和为1，由此得到新的状态转移矩阵M’；

步骤402，判断状态转移矩阵M和新的状态转移矩阵M’的差别是否小于一定阈值，如果小于，则执行步骤403；否则，令M＝M’，继续执行步骤401；其中，可以假设阈值条件为||M-M'||²＜0.05。

步骤403，使用新的状态转移矩阵M’更新步骤2构造的赋权图G，其更新方法为：采用新的状态转移矩阵M’的相近度值更新赋权图G对应边的权重，并且，当更新后的边权重值低于相似度过滤系数θ时，删除对应边，由此得到新赋权图G；

步骤404，使用广度优先遍历方法计算新赋权图G的每个连通分支，每个连通分支即是一个关系簇。

对于步骤4，解释如下：

马尔科夫聚类算法是一种基于图的聚类算法，它将聚类对象看成是一个有向图或无向图，目标是将图内点聚成若干簇，使得一个漫游者从簇内的某个点“出发”，那么到达同一簇内点的概率大于到达簇外点的概率。通过在图上进行随机游走过程，就可以发现在图的某些区域边是比较密集的，可以聚成一簇。马尔科夫聚类算法通过计算马尔科夫链达到在图上进行随机游走的过程。

马尔科夫算法主要有两个过程，分别是扩展和膨胀，这两个过程都是对状态转移矩阵进行操作，记一个状态转移矩阵为M，M的维数就是图中点的个数，M不一定是对称矩阵，M中的每一列表示某一时刻从某一个点出发，下一时刻到达其余点各自的概率。

扩展过程是模拟随机游走过程，即取正整数e，对当前状态转移矩阵自乘e次，得到新的状态转移矩阵，这一过程相当于在原状态转移矩阵上进行了一次e步的随机游走。例如一个只有两个定点的图，状态转移矩阵状态转移矩阵中第i列、第j行的元素表示如果漫游者当前从顶点i出发，则下一时刻出现在顶点j的概率，状态转移矩阵的每列的和为1，假设旅行者在第0时刻从顶点1出发，则第2时刻，它仍然出现在顶点1的概率是0.6*0.6+0.4*0.2＝0.44，同理可以得到它出现在其他顶点的概率，此时状态转移矩阵

膨胀过程是一个矩阵规则化过程，是对状态转移矩阵的各列进行规则化，其处理公式如公式(3)所示：

${\left(M^{*}\right)}_{pq}={\left(M_{pq}\right)}^{\tau }/\underset{i=1}{\overset{k}{\Sigma }}{\left(M_{iq}\right)}^{\tau }---\left(3\right)$

其中，M是状态转移矩阵，M^*是规格化得到的矩阵。τ是松弛系数，k是M的行数，p是行下标，q是列下标，公式(3)的作用是把转移矩阵的列进行规格化得到规格化矩阵M^*。例如当τ＝2时，向量经过公式(3)规格化的结果是

本发明提供的基于马尔可夫聚类的实体间关系消解方法具有以下优点：提出了融合词法和语义的相似度计算方法，然后给出了基于马尔科夫图聚类的关系聚类方法。该方法与层次聚类方法相比，聚类纯度指标有了一定提高，还具有计算过程简单快速的优点。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视本发明的保护范围。