一种基于随机森林改进的实体解析方法

摘要

本发明提供了一种基于随机森林改进的实体解析方法，包括以下步骤：S1：提供一个包括k个决策树的随机森林F，提供若干个字符串Bi；S2：执行修剪步骤包括：S2.1：从k个决策树中提取m个决策树Tm，分别使用Tm执行每一个字符串Bi，得到输出Cm；S2.2：建立集合I＝C1∩C2∩...∩Cm；S3：执行验证步骤包括：S3.1：建立集合J＝(C1∪C2∪...∪Cm)\(C1∩C2∩...∩Cm)；S3.2：从随机森林F中提取n个决策树Rn，使用Rn执行集合J，以生成集合Kn；S4：随机森林F输出结果为I∪K1∪K2∪...∪Kn。本发明通过将执行每一个决策树分解为在修剪步骤中执行树的子集，然后在验证步骤中执行剩余的树，通过树的重用计算简化执行决策树集，以大幅缩短时间。

权利要求

1.一种基于随机森林改进的实体解析方法，其特征在于，包括以下步骤：S1：提供一个包括k个决策树的随机森林F，其中k＝1，2...N；提供若干个字符串Bi，其中i＝1，2...N；并执行如下训练步骤：S1.1：给定若干个样本数据表Ai，其中i＝1，2...N；

S1.2：从Ap表中随机选择一组Xp元组，从Aq表中随机选择与所述Ap表可能匹配的一组Xq元组，将所述Xp与所述Xq配对组成样本S，其中：p∈i，q∈i，p≠q；

S1.3：检查所述Ap表与所述Aq表的模式，创建一组特性，使用所述特性将所述样本S中的元组对转换为特征向量；

S1.4：使用S1.3中的所述特征向量训练所述随机森林F；

S2：执行修剪步骤，所述修剪步骤包括：S2.1：从所述k个决策树中提取m个决策树T1，T2...Tm，分别使用所述T1，T2...Tm执行每一个所述字符串Bi，得到输出C1，C2...Cm，所述m为正确解析所需要的最小的决策树数量，所述正确解析为所述随机森林F将所述字符串Bi正确解析为实体；

S2.2：建立集合I＝C1∩C2∩...∩Cm；

S3：执行验证步骤，所述验证步骤包括：S3.1：建立集合J＝(C1∪C2∪...∪Cm)\(C1∩C2∩...∩Cm)；

S3.2：从所述随机森林F中提取n个决策树R1，R2...Rn，使用所述R1，R2...Rn执行所述集合J，以生成集合K1，K2...Kn，且其中S4：所述随机森林F输出实体解析结果为I∪K1∪K2∪...∪Kn。

2.根据权利要求1所述的一种基于随机森林改进的实体解析方法，其特征在于，S3.2中，(R1，R2...Rn)∪(T1，T2...Tm)＝随机森林F。

3.根据权利要求1所述的一种基于随机森林改进的实体解析方法，其特征在于，S1.2中，在所述Aq表中构建反向索引，使用所述反向索引快速查找所述Aq表中与所述Xp元组共享x个符号的元组，组成Xq元组，其中x≥2。

4.根据权利要求2所述的一种基于随机森林改进的实体解析方法，其特征在于，S2中，在执行前对所述k个决策树进行修剪。

说明书

一种基于随机森林改进的实体解析方法

技术领域

[0001] 本发明涉及数据处理技术领域，尤其是涉及一种基于随机森林改进的实体解析方法。

背景技术

[0002] 在数据集中，数据所指向的现实世界中的对象，一般称之为实体。对于同一实体，在不同甚至同一数据集中，可能存在多种不同的表现或描述形式，当将多个不同来源的数
据集进行合并以分析处理时，这些对于同一实体的描述则会混杂在一起，造成一定程度的
重复现象。实体解析，就是对数据集中的多种不同的描述进行识别、连接，确定哪些描述映
射于现实世界中的同一实体的过程。实体解析是数据预处理过程中的一个重要步骤，主要
用于解决数据的重复冗余等质量问题。

[0003] 目前的实体解析是指不同的数据对同一个事物即实体可能会有不同的描述(这里的描述包括数据格式、表示方法等)，但它们通常在描述存储的过程中可能会出现排版或者
错别字等错误，增加我们数据处理解析的时间并且容易造成匹配的冗余无法精准的得到我
们想要的数据集。

发明内容

[0004] 本发明的目的在于提供一种基于随机森林改进的实体解析方法，能够通过随机森林对字符串与实体的匹配进行相似度的连接，提高对数据集匹配的准确性和效率，克服现
有的实体解析技术的不足。

[0005] 本发明提供的一种基于随机森林改进的实体解析方法，包括以下步骤：

[0006] S1：提供一个包括k个决策树的随机森林F，其中k＝1，2...N；提供若干个字符串Bi，其中i＝1，2...N；并执行如下训练步骤：

[0007] S1.1：给定若干个样本数据表Ai，其中i＝1，2...N；

[0008] S1.2：从Ap表中随机选择一组Xp元组，从Aq表中随机选择与所述Ap表可能匹配的一组Xq元组，将所述Xp与所述Xq配对组成样本S，其中：p∈i，q∈i，p≠q；

[0009] S1.3：检查所述Ap表与所述Aq表的模式，创建一组特性，使用所述特性将所述样本S中的元组对转换为特征向量；

[0010] S1.4：使用S1.3中的所述特征向量训练所述随机森林F；

[0011] S2：执行修剪步骤，所述修剪步骤包括：

[0012] S2.1：从所述k个决策树中提取m个决策树T1，T2...Tm，分别使用所述T1，T2...Tm执行每一个所述字符串Bi，得到输出C1，C2...Cm，所述m为正确解析所需要的最小的决策树数
量，所述正确解析为所述随机森林F将所述字符串Bi正确解析为实体；

[0013] S2.2：建立集合I＝C1∩C2∩...∩Cm；

[0014] S3：执行验证步骤，所述验证步骤包括：

[0015] S3.1：建立集合J＝(C1∪C2∪...∪Cm)\(C1∩C2∩...∩Cm)；

[0016] S3.2：从所述随机森林F中提取n个决策树R1，R2...Rn，使用所述R1，R2...Rn执行所述集合J，以生成集合K1，K2...Kn，且其中

[0017]

[0018] S4：所述随机森林F输出实体解析结果为I∪K1∪K2∪...∪Kn。

[0019] 进一步地，S3.2中，(R1，R2...Rn)∪(T1，T2...Tm)＝随机森林F。

[0020] 进一步地，S1.2中，在所述Aq表中构建反向索引，使用所述反向索引快速查找所述Aq表中与所述Xp元组共享x个符号的元组，组成Xq元组，其中x≥2。

[0021] 进一步地，S2中，在执行前对所述k个决策树进行修剪。

[0022] 本发明通过减少需要匹配的候选对的数量，缩小样本，然后通过缩小的样本训练随机森林，以缩短时间，通过将执行每一个决策树分解为在修剪步骤中执行树的子集，然后
在验证步骤中执行剩余的树，通过树的重用计算简化执行决策树集，以再次缩短时间，精简
数据、精确解析结果。

附图说明

[0023] 为了更清楚地说明本发明具体实施方式或现有技术中的技术方案，下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的
附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前
提下，还可以根据这些附图获得其他的附图。

[0024] 图1为本发明的实体解析流程示意图；

[0025] 图2为传统的实体解析流程示意图；

具体实施方式

[0026] 应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常
理解的相同含义。

[0027] 需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式
也包括复数形式，此外，还应当理解的是，当在本说明中使用术语“包含”和/或“包括”时，其
指明存在特征、步骤、操作、器件、组件和/或它们的组合。

[0028] 下面将结合实施例对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技
术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范
围。

[0029] 实施例1：

[0030] 本发明提供的一种基于随机森林改进的实体解析方法，包括以下步骤：

[0031] S1：提供一个包括k个决策树的随机森林F，其中k＝1，2...N；提供若干个字符串Bi，其中i＝1，2...N；

[0032] 对随机森林F执行训练步骤；

[0033] S1.1：给定若干个样本数据表Ai，其中i＝1，2...N；

[0034] S1.2：从Ap表中随机选择一组Xp元组，从Aq表中随机选择与Ap表可能匹配的一组Xq元组，将Xp与Xq配对组成样本S，其中：p∈i，q∈i，p≠q；S1.2中，在Aq表中构建反向索引，使
用反向索引快速查找Aq表中与Xp元组共享x个符号的元组，组成Xq元组，其中x≥2。

[0035] S1.3：检查Ap表与Aq表的模式，创建一组特性，使用特性将样本S中的元组对转换为特征向量；

[0036] S1.4：使用S1.3中的特征向量训练随机森林F。

[0037] 例如，S1.1中，给定两个样本数据表A1和A2，S1.2中，从A1表中随机选择一组X1元组，从A2表中随机选择与A1表中可能匹配的一组X2元组，将X1与X2配对组成样本S。S1.3中，通
过检查A1表和A2表的模式，创建一组特性，创建该特性的方法，例如，如果检测到属性city属
于string类型，则就会创建许多使用字符串相似性度量的特性，举例：edit dist(A1.city，
A2.city)，jaccard 2gram(A1.city，A2.city)。

[0038] S2：执行修剪步骤，修剪步骤包括：

[0039] S2.1：从k个决策树中提取m个决策树T1，T2...Tm，分别使用T1，T2...Tm执行每一个字符串Bi，得到输出C1，C2...Cm；

[0040] S2.2：建立集合I＝C1∩C2∩...∩Cm；

[0041] S3：执行验证步骤，验证步骤包括：

[0042] S3.1：建立集合J＝(C1∪C2∪...∪Cm)\(C1∩C2∩...∩Cm)；

[0043] S3.2：从随机森林F中提取n个决策树R1，R2...Rn，使用R1，R2...Rn执行集合J，以生成集合K1，K2...Kn，且其中

[0044]

[0045] S4：随机森林F输出实体解析结果为I∪K1∪K2∪...∪Kn。

[0046] 如图1所示：例如，S1中，随机森林F包括3个决策树，分别为T1、T2和R1，S2中，提供两个字符串B1和B2，在B1和B2上执行T1、T2，得到输出C1和C2，则S3中，建立集合I＝C1∩C2，则I是
由T1和T2预测匹配的所有对组成，可以作为随机森林F输出的一部分，则S4中，建立集合J＝
(C1∪C2)\(C1∩C2)，则S5中，使用R1执行集合J，以生产集合K，所以显然K也匹配随机森林F，
所以随机森林F的输出是I∪K，任何其他对(既不在I中也不在J中)都不能被T1和T2预测匹
配，因此不能与随机森林F匹配。

[0047] 另外，S2中，集合J往往比较小，因此，将树T3应用于J中往往比将其应用于原始的字符串B1和B2集合要快得多。当F很大时，比如10棵树，节省的时间非常可观。假设在这种情
况下，我们需要至少5棵树来匹配F，然后我们可以在B1和B2上应用6棵树来得到集合I和J，然
后将剩下的4棵树应用到相对较小的集合J上，前者即树的修剪，后者即树的验证。

[0048] 具体为：考虑一个由10棵树组成的森林F，其中至少有5棵树必须匹配才能使F匹配。然后修剪步骤执行6棵树来产生一组对J，在修剪过程中考虑一对p1∈J与4棵树匹配。然
后，只要剩下的4棵树中的一棵与p1匹配，我们就可以将p1声明为匹配；考虑一对p2∈J在剪
枝时只与一棵树匹配，当剩下的4棵树中的一棵预测p2不匹配时，我们就可以宣布p2不匹
配。

[0049] 所以，在S2中，m个决策树T1，T2...Tm执行过程即修剪过程；S5中，R1，R2...Rm的执行过程即验证过程，验证过程可以简化数据处理解析的时间。

[0050] S3.2中，S3.2中，(R1，R2...Rn)∪(T1，T2...Tm)＝随机森林F。充分利用随机森林F中的所有树，使解析结果更准确。

[0051] S2.1中，所述m为正确解析所需要的最小的决策树数量，所述正确解析为所述随机森林F将所述字符串Bi正确解析为实体。当修剪步骤使用能够保证正确解析的最少的决策
树数量m，则验证步骤使用剩余的决策树数量n，此时明显的，对于缩短解析时间的效果是最
大的，因为修剪步骤需要执行所有的字符串，而验证步骤只需要执行修剪后的集合J。

[0052] S2中，在执行前对k个决策树进行修剪。应用树的子集进行修剪，修剪作用是为了避免过拟合，之后用剩余的树应用J进行验证。

[0053] 实施例2：

[0054] 本实施例中，考虑匹配两组名称，这两组名称同时包含长名(例如Graphene Nanospheres)和短名(例如Golf Ball)。通过执行随机森林F的修剪和验证对两组字符串B1
和B2进行匹配获取想要的字符串。

[0055]

[0056]

[0057]

[0058] 为了匹配两组字符串B1和B2，我们学习随机森林F，然后在B1和B2上执行F。本发明执行过程在于，我们将F的执行分为两个步骤：修剪和验证。以下描述如何有效地执行这两
个步骤。

[0059] 假设随机森林F有k棵树，其中至少需要dk/2e树以便F匹配。那么显而易见，剪枝步骤至少执行(bk/2c+1)个树时，任何不由该步骤输出的字符串对都不能是匹配的。

[0060] 如图2所示，假设随机森林F只在三棵树中至少有两棵树输出同一对时，才输出一对(即声明它是匹配的)。简单地说，我们可以在两组字符串B1和B2上执行F，方法是执行B1和
B2上的每个树Ti以获得输出Ci，然后输出出现在至少两个树的输出中的所有对(参见图2)，
这是比较耗时的一种方法。

[0061] 如图1所示，本发明的优点是只执行两个树，比如在B1和B2上执行T1、T2，以获得输出C1和C2(参见图1)。集合I＝C1∩C2由T1、T2预测匹配的所有对组成，因此可以作为随机林F
输出的一部分立即输出。

[0062] 修剪步骤的实施过程为：集合J＝(C1∪C2)\(C1∩C2)，由仅由一棵树(T1或T2)预测匹配的所有对组成。很容易看出，我们只需要将剩下的树R1应用于集合J，设K是J中R1预测匹
配的对的集合，显然任何这样的对也是随机森林F的匹配，因为它正好由两棵树(T1或T2，以
及R1)匹配。因此，随机林F的输出为I∪K(见图1)。任何其他配对(即I和J中的配对)都不能
由T1和T2预测匹配，因此不能与F匹配。

[0063] 验证步骤的实施过程为：集合J往往相对较小，因此，将树R1应用于J往往比将其应用于字符串B1和B2的原始集合快得多，当F较大时(例如10棵树)，这种时间节省是非常显著
的；假设在这种情况下，我们至少需要五棵树来匹配F。然后我们可以将六棵树应用于B1和B2
以获得集合I和J(即修剪步骤)，然后将其余四棵树应用于相对较小的集合J(即验证步骤)。

[0064] 在验证步骤中，假设在之前的剪枝步骤中执行修剪Tm树产生一组对J，则需要考虑如何对J执行剩余的树：使U为在集合J上执行的剩余的树的集合，类似于在修剪步骤中执行
树的方式，这里可以简单地使用上面的优化过程来生成一个计划P，该计划P以组合方式执
行U中的所有树(即重用计算)，但是更好的解决方案是按顺序应用树，以避免将U中的所有
树应用于J中的所有对。

[0065] 综上，本发明通过训练包含k个决策树的随机森林，输入引用集合内的字符串，执行随机森林中的决策树构建新的集合I，J，利用集合I，J构建随机森林的输出，完成引用集
合与现实实体的匹配，并且在对随机森林的执行过程中，可以利用构造的集合J对匹配进行
验证。

[0066] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依
然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进
行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术
方案的范围。