引言

知识图谱^[1]的出现为信息获取带来新的转变，它通过为查询词赋予丰富的语义信息建立与现实世界实体的关系，从而帮助用户更快找到所需的信息。关联开放数据(linked open data，LOD)^[2]作为知识图谱结构化数据的主要来源，随着规范化的开放数据发布标准^[3]的逐步统一，可获得的LOD数量在不断增加。实体对齐技术通过建立异构关联数据集实体间的共指链接来进行实体消歧，从而实现高效的信息共享。所以实体对齐技术是实现语义标准化、促进数据集间互操作化的关键技术，也是当前知识图谱构建技术中的研究热点和难点。

实体对齐问题可看作一个二分类问题。现有实体对齐方法主要分为基于模式层和基于实例层两类。基于模式层的实体对齐主要针对本体定义中的概念、属性、命名规则进行度量，且根据是否与匹配数据集构成本体一致又可分为内部和外部两种。内部方法主要依赖于领域内本体定义规则，外部方法主要依赖与外部知识库的模式映射实现对齐。Tummarello等^[4]提出的Sindice查找索引通过一种明确定义的内部属性来推断实体间等价关系；Nikolov等^[5]利用关联数据集中各数据集之间现有的OWL：sameAs链接来推断实体间等同关系；Nath等^[6]提出的Anchor-flood算法利用本体中概念层次关系进行实例聚类进而实现实体互联。

基于实例层的对齐方法根据论证数据来源不同也可以分为内部和外部两种，相同点是都利用多种基于属性的相似度度量函数进行合计度量，算法模型与记录链接^[7]领域的算法较为类似。内部方法主要通过直接对比数据源中相应实体相似度实现，外部方法则是利用OWL的传递性，通过各数据源中现存OWL链接进行聚合作出等价推断。Volz等^[8]提出的Silk系统利用不同相似度匹配方法(如Avg、Max、Min、Euclidean距离等)实现链接发现，进而实现实体对齐；Hu等^[9]针对实体URI提出了一种结合OWL：sameAs、逆函数属性及最大基数的内核函数方法，并通过两阶段的自训练算法来实现数据集实体间的对齐。

上述基于模式层或实例层的方法大多依赖于前阶段的模式匹配结果，易于过滤掉语义异构属性中的重要信息，链接构建存在缺失；同时，关联数据集间实体对齐工作因其本体描述语言(OWL)的多样性及复杂性，使用基于传统方法的数据预处理时间成本较高。本文提出一种基于属性文本语义特征的实体对齐方法(semantic features based entity alignment，SFEA)。在特征向量建模阶段，针对关联数据集中具有语义异构特征的实体属性进行分类，抽取得到非结构化文本的同时保留了一般模式识别方法中易于过滤掉的有价值实体关系信息；同时在分类器生成阶段，结合C4.5算法和改进的可变样本集Adaboost(VS-Adaboost)分类学习算法生成分类器来进行实体对齐关系分类。

1 实体对齐定义

关联数据一般采用resource description framework(RDF)执行逻辑推理^[10]、描述web服务。定义1描述了一个使用RDF三元组定义的关联数据集。

定义1  关联数据集形如式(1)

$ {D_{{\rm{LD}}}} = \left\{ {O, L, R, P, {R_{\rm{F}}}, {P_{\rm{F}}}} \right\} $

(1)

式(1)中O为实例，L为文本信息, R为关系，P为属性，R_F⊆O×R×O是一个由主谓宾三元组表示的、宾语为实例的关系事实，P_F⊆O×R×L是一个由主谓宾三元组表示的、宾语为文本信息的属性事实。

实体对齐通过对比各个异构或同构关联数据集中的实体^[11]来确定它们是否指代同一现实实体。根据定义1，本文中独立于模式的实体对齐方法主要是利用实例层信息，将每一个RDF三元组数据文本看作整体。基于此方法进行的实体对齐可由定义2描述。

定义2(实体对齐(Entity Alignment))  给定数据集

$ \begin{array}{l} {D_{{\rm{L}}{{\rm{D}}_1}}}, {D_{{\rm{L}}{{\rm{D}}_2}}}, {E_{\rm{A}}}\left( {{D_{{\rm{L}}{{\rm{D}}_1}}}, {D_{{\rm{L}}{{\rm{D}}_2}}}} \right) = \left\{ {\left( {{a_i}, {b_j}, {\rm{sim}}\left( {{a_i}, } \right.} \right.} \right.\\ \left. {\left. {{b_j}} \right)} \right)|{a_i} \in {D_{{\rm{L}}{{\rm{D}}_1}}}, {b_j} \in {D_{{\rm{L}}{{\rm{D}}_2}}}, \left( {{a_i}, {b_j}} \right) \in {D_{{\rm{L}}{{\rm{D}}_1}}} \times {D_{{\rm{L}}{{\rm{D}}_2}}}, \\ \left. {{\rm{sim}}\left( {{a_i}, {b_j}} \right) \in \left[{0, 1} \right]} \right\} \end{array} $

其中，sim(a_i, b_j)为表述实体a_i和b_j语义相似度的数值，通过判断sim(a_i, b_j)与阈值ε的大小关系进而判定实体间是否有指代一致的等同关系。

2 基于属性文本语义特征的实体对齐(SFEA)方法 2.1 SFEA方法框架

本文提出的SFEA方法通过分析、抽取实体对属性特征建模得到特征向量，再采用有监督的机器学习分类方法训练生成分类器，进而将实体关系进行有效分类，通过将等同和不等同两类映射到两个不同标号的类来实现实体对齐。即找到一个分类器C_l, 将非对齐实例分到-1类中，将对齐实例分到1类中。SFEA方法框架如图 1所示。

SFEA方法主要实现步骤如下。

1) 数据预处理。针对给定数据集中三元组数据包含的丰富文本信息，在文本抽取过程中使用MapReduce框架建立key-value对，并进行排序获得有价值的文本信息。对每一实体抽取独立于模式的属性文本信息后，按类别赋予不同权重并筛选出候选实体对集合，降低计算复杂度。

2) 特征向量建模。对数据预处理阶段抽取得到的文本信息，选用合适的特征相似度计算函数生成特征向量。

3) 分类学习。标注已有对齐关系作为训练数据，使用C4.5算法迭代生成并测试基分类器，并通过改进的VS-Adaboost算法更新样本集规模，得到平衡总分类器，进而实现数据集实体对齐。

2.2 数据预处理

数据预处理包括数据标准化抽取及分区索引建立。

1) 数据标准化抽取

本文数据标准化抽取工作中通过轻量级JavaScript object notation(JSON)技术解析RDF三元组数据^[12]得到JSON字符串，再提取(key，value)集并分类。具体属性文本信息抽取过程中，将待对齐的实体对看作一系列非结构化的字符串的组合，根据不同属性中文本描述特征的不同抽取下列几类数据。

(1) l_label类：实例名称等标识性的词语通过<rdf:label>属性识别。

(2) l_property类：实例属性中进行文本描述。

(3) l_value类：实例属性值中的文本描述。某一属性值含义由于描述词语数量的不同存在差异，所以将属性值的文本抽取根据词语数量的不同抽取为l_single、l_short、l_long 3类。

(4) 针对三元组实例可能存在多样性数据信息，抽取l_date、l_number、l_link作为补充。

2) 分区索引建立

由定义2可知，对于各自包含|A|和|B|个实例的数据集来说，实体对齐过程中要处理的实例对的个数是|A|×|B|，这对于本来就拥有百万级数据的数据集来说工作量十分巨大，通过设计高效的索引技术可以避免数据集规模较大带来的计算复杂度问题，因此进行筛选预处理是很有必要的。本文通过为描述数据集中实体的关键词设置倒排索引(inverted value)筛选得到候选相似对齐实例集$\mathscr{F} $，其中关键词的获得是在文本信息抽取中通过tokenizer()方法得到的。

2.3 特征匹配

为保证数据评估的可靠性，本文选用多种相似形函数来构建实体属性特征向量并计算实体间相似关系。在此过程中采用MapReduce并发处理模型框架能在筛选有效信息的同时，最大程度保证候选实体对的完整性、降低计算复杂度。

相似度特征计算方法为：以数据预处理结果为输入，分别使用MapReduce计算框架的Map()、Reduce()过程提取文本特征项，生成特征向量。在提取文本特征项过程中，选用具有较好类别区分能力的TF-IDF统计方法度量字、词重要性及相似程度，并结合三元组数据的文本语义标签特征，针对不同类别文本选用合适的度量方法得到特征向量e_i(p₁, (p₁), p₂, (p₂), …, p_n, (p_n))。

由于文本特征存在区别，分别选用式(2)~(6)5大类度量函数计算各个维度上的向量值(范围[0, 1])。

1) 属性标签文本(l_single、l_short、l_long、l_label)由于含有较多文本描述，适用于余弦相似度核函数SimCos()，通过计算描述词的TF-IDF值(F_tf-idf())得到其特征值，计算公式如式(2)

${\rm{SimCos}}\left( {{T_1},{T_2}} \right) = \\ \frac{{\sum\limits_{{t_i} \in {T_1}, {t_j} \in {T_2}} {\left[{{F_{{\rm{tf-idf}}}}\left( {{t_i}} \right) \times {F_{{\rm{tf-idf}}}}\left( {{t_j}} \right)} \right]} }}{{\left[{\sum\limits_{{t_i} \in {T_1}} {{F_{{\rm{tf-idf}}}}{{\left( {{t_i}} \right)}^2}} } \right] \times \left[{\sum\limits_{{t_j} \in {T_2}} {{F_{{\rm{tf-idf}}}}{{\left( {{t_j}} \right)}^2}} } \right]}} $

(2)

2) 短描述属性(l_single、l_short、l_label)中常含关键词，适用于逆文档频率度量函数SimIdf()，公式如式(3)

$ {\rm{SimIdf}}\left( {{T_1},{T_2}} \right) = \\ \frac{{\sum\limits_{{t_i} \in {T_1}, {t_j} \in {T_2}} {\left[{{F_{{\rm{idf}}}}\left( {{t_i}} \right) \times {F_{{\rm{idf}}}}\left( {{t_j}} \right)} \right]} }}{{\left[{\sum\limits_{{t_i} \in {T_1}} {{F_{{\rm{idf}}}}{{\left( {{t_i}} \right)}^2}} } \right] \times \left[{\sum\limits_{{t_j} \in {T_2}} {{F_{{\rm{idf}}}}{{\left( {{t_j}} \right)}^2}} } \right]}} $

(3)

3) 对于短描述特性，为更好权衡单个词汇的重要性，进一步使用字逆文档频率函数SimTopidf ()计算，公式如式(4)

$ \begin{array}{l} {\rm{SimTopidf}}\left( {{T_1}, {T_2}} \right) = \\ \frac{{\sum\limits_{w \in {W_1} \cap {T_2}} {{F_{{\rm{idf}}}}\left( w \right)} + \sum\limits_{w \in {W_2} \cap {T_1}} {{F_{{\rm{idf}}}}\left( w \right)} }}{{\sum\limits_{w \in {W_1}} {{F_{{\rm{idf}}}}\left( w \right)} + \sum\limits_{w \in {W_2}} {{F_{{\rm{idf}}}}\left( w \right)} }} \end{array} $

(4)

4) 由于对每一实例仅抽取一个label属性，而且label中的描述词对于对齐与否的判断较为重要，所以对于l_label属性的度量适用计算Levenshtein相似度(S_levenshtein(l_label^a, l_label^b))的度量函数SimEdit()及SimCount()，计算公式如式(5)、(6)

$ {\rm{SimEdit}}\left( {l_{{\rm{label}}}^{\rm{a}}, l_{{\rm{label}}}^{\rm{b}}} \right) = 1-\frac{{{S_{{\rm{levenshtein}}}}\left( {l_{{\rm{label}}}^{\rm{a}}, l_{{\rm{label}}}^{\rm{b}}} \right)}}{{\max \left( {\left| {l_{{\rm{label}}}^{\rm{a}}} \right|, \left| {l_{{\rm{label}}}^{\rm{b}}} \right|} \right)}} $

(5)

$ {\rm{SimCount}}\left( {l_{{\rm{label}}}^{\rm{a}}, l_{{\rm{label}}}^{\rm{b}}} \right) = \frac{{1-{2^{-\left| {\left\{ {w|w \in l_{{\rm{label}}}^{\rm{a}} \cap w \in l_{{\rm{label}}}^{\rm{b}}} \right\}} \right|}}}}{{1-{2^{ - \left( {\left| {l_{{\rm{label}}}^{\rm{a}}} \right| + \left| {l_{{\rm{label}}}^{\rm{b}}} \right|} \right)/2}}}} $

(6)

另外，l_single一般是ISBN类极具标识性的字符，l_short中少量词的出现对实例对齐与否的判断起着较关键的作用，所以l_single、l_short、l_long在特征向量的相似度计算中应赋予较高权重。

2.4 VS-Adaboost分类学习 2.4.1 二分类问题

假设两实例对(p₁, p₂)和(q₁, q₂)，特征相似度向量分别用μ、y表示，u₆=ν₆=0.3，u₅=0.1, ν₅=0.5。若p₁和p₂分别是由一些长文本和短文本组成的，而q₁和q₂可能是由同领域内的一些长文本构成的，那么只根据u₅＜ν₅并不能判定q₁、q₂为同一现实实体的可能性大于p₁、p₂，也就是说它们之间的关系并不是线性可分的。

特定领域的关联数据集^[13]具有丰富的上下文语义关系，特征相似度向量的维度之间也包含隐含关系，因此本文选择决策树中的C4.5算法生成基分类器^[14]，并在训练中迭代更改样本集规模、优化分类器性能；另外待处理的关联数据集数据量较大、实体个数较多是实体对齐的关键问题，因此神经网络、支持向量机等具有复杂内核的学习模型并不适用于此场景，因此本文提出了一种有监督的可变样本集VS-Adaboost算法训练模型来优化学习模型、生成训练数据集。二分类学习过程总体流程如算法1所示。

算法1  二分类学习算法

输入 正训练数据集P，负训练数据集N，候选集$\mathscr{F} $，基分类器M，迭代次数N，可变样本影响因子f_P, f_N

1) 初始化

S_L=| $\mathscr{F} $|;

S_P=|P|;

S_N=|N|;

2) 将P、N作为训练数据使用C4.5算法及VS-Adaboost训练M，得到总分类器M′

3) int n=0; //迭代计数

4) while n < N do

  S_P=S_P×f_P;

  S_N=S_N×f_N;

  if i=1

    P=L_i; //使用L中第一个S_D作为新的正训练数据

  else

    N=L_i; //其余作为负训练数据

  n=n+1;

 end while

输出  $ \mathscr{F}$中的有序列表L

2.4.2 总分类器生成

C4.5算法将信息增益率函数作为分类标准，避免了对多重取值属性的选择。该方法使用有放回的方法进行抽样，生成差异性较大、准确性较高的基分类器, Adaboost算法通过不断迭代更新样本权重来更新样本集，进而得到分类器权重，最后得到总分类器M′。M′训练生成流程如算法2所示。

算法2  VS-Adaboost分类算法

输入 训练样本集{(x₁, y₁), (x₂, y₂), …}, C4.5分类器

1) σ_i¹=w(i), i=1, …, m//初始化样本权值

2) for t=1, …，T //迭代次数

  ${d^t} = {w^t}/\sum\limits_{i = 1}^m {w_i^t} $//产生分布

  λ_t:X→[0, 1] //基于分布d^t调用C4.5得到

  ${\phi _t} = \sum\limits_{i = 1}^m {d_i^t\left| {{\lambda _i}\left( {{x_i}} \right)-{y_i}} \right|} $//λ_t的误差率

  ψ_t=ϕ_t/(1－ϕ_t)//计算新误差

  σ_i^t+1=σ_i^t×ψ_t//更新

end for

输出

$ \mathit{\boldsymbol{M'}}\left( x \right) = \left\{ \begin{array}{l} 1\;\;\;\;\;\sum\limits_{t = 1}^T {\left( {\log \frac{1}{{{\psi _t}}}} \right){\lambda _t}\left( x \right) \ge \frac{1}{2}\sum\limits_{t = 1}^T {\left( {\log \frac{1}{{{\psi _t}}}} \right)} } \\ 0 \end{array} \right. $

3 实验与结果分析 3.1 实验设置

实验条件设置为：VMware Workstation 12 Pro；系统Oracle_Linux_7u2_64bi；jdk版本jdk-8u77-linux-x64；Hadoop版本Hadoop1.2.1；控制台XShell5；虚拟机为1个master、3个node，每台机器配置均为2G+20G。

实验数据取自British Museum(BM)、Amsterdan Museum(AM)、DBpedia^[15](DB)和New York Times(NY)4个LOD数据集，数据集信息如表 1所示。

以DBpedia为对齐标准，与其他3个数据集分别进行两两实验，由于AM、NY中已存在与DBpedia的owl：sameAs链接，将已有链接作为训练数据进行分类器的学习，从而进行AM-DB、NY-DB两组实验，最后根据已有标注数据进行BM-DB上的实验。

3.2 评估方法

使用精确率(p)、召回率(r)与F1测度(F_1-m)作为分类结果的评价标准，计算公式如式(7)~(9)：

$ p = \frac{{{P_1}}}{{{P_1} + {N_1}}} $

(7)

$ r = \frac{{{P_1}}}{{{P_1} + {N_2}}} $

(8)

$ {F_{1-{\rm{m}}}} = 2 \times \left( {\frac{{pr}}{{p + r}}} \right) $

(9)

其中，P₁为实验中被分类器正确标记的对齐数据；P₂为被正确标记的非对齐数据；N₁为实验中被分类器错误标记的非对齐数据；N₂为实验中被分类器错误的标记对齐数据。

另外在索引构建的实验过程中，发现候选对筛选的召回率是不完美的(为0.9)，这意味着最大可实现分类的F_1-m严格低于100%。因此相应的F_1-m只是悲观估计，分类器不可能完全错误地标记所有遗漏的匹配对。因此本文使用加权悲观F-Measure(F_m)公式(10)来估计真实F_1-m。

$ {F_{\rm{m}}} = \frac{{100{F_{1-{\rm{m}}}}}}{{{F_{\max }}}} $

(10)

3.3 结果分析

为了对比本文算法(VS-Adaboost)与其他算法之间的性能差异，实验中同时使用RiMOM框架进行对齐链接生成。在使用VS-Adaboost方法分类学习过程中，通过多组实验，得到最佳迭代次数为7时分类器效果最佳(可避免过拟合现象)。最终实验结果如表 2所示。

由表 2可知，3组实验中基于VS-Adaboost算法的实体对齐方法在召回率与F_1-m测度值上均比RiMOM方法有一定程度的提高，从而可以有效发现模式匹配中易于过滤掉的链接关系，提高召回率；但准确度方面，在BM-DB实验中有错误分类的情况出现，原因可能是缺乏较为充分、有效的标注训练数据。整体来说利用本文方法可以在较少人工干预前提下实现对关联数据集中数据实例的高效链接。

4 结论

(1) 通过分析关联数据的属性语义特征，应用独立于模式的匹配算法将属性值信息看做纯文本信息，可以发现在模式匹配中被排除的隐含对齐信息。

(2) 利用大规模并行MapReduce框架处理文本特征，为处理大规模结构化数据集上的实体对齐问题带来新的可能；同时在保证数据完整性的前提下，利用一种有监督的机器学习算法降低了对齐过程的计算复杂度。

(3) 经过验证发现本文方法在存储空间方面所需缓冲存储空间大约仅为40 M左右，这为处理高数量级数据及带来更多可能，同时可以极大保证等同链接构建的质量，在未来知识图谱构建中有着广泛前景。