一种基于局部敏感哈希策略的实例匹配方法

摘要

一种基于局部敏感哈希策略的实例匹配方法。解决语义网中快速提取两个数据集间描述相同事物实例的难题，本发明提出了一种新颖的通过局部敏感哈希来进行实例匹配的方法，该方法包括：重要的谓语选择；匹配不同数据集间的重要谓语；根据匹配的谓语提取候选实例对；提炼候选集得到实例匹配结果。

主权项

一种基于局部敏感哈希策略的实例匹配方法，解决语义网中快速提取两个数据集间描述相同事物实例的难题；Linked Data是语义网的一个具体实现，以RDF三元组作为基础数据模型；RDF三元组是由主语、谓语和宾语组成的描述事物特征的框架，数据集中的实例由多个RDF三元组组成；Linked Data中包括大量的数据集，而且任何人都能在其上发布新的数据集，但新发布的数据集需要与现存数据集存在链接数据，即把描述相同事物的实例标记出来，该实例匹配方法能够在用户不了解数据集的情况下快速提取匹配的实例对；所述实例匹配方法详细步骤如下：第1、根据谓语的覆盖率和辨别率找到重要谓语第1.1、计算谓语的覆盖率；谓语覆盖率是谓语在整个数据集所有实例中出现的频率；第1.2、计算谓语的辨别率；谓语辨别率是从数据集中辨别出某一个实例的能力；第1.3、计算重要谓语；重要谓语是指数据集中谓语覆盖率和谓语辨别率都大于各自指定阈值的谓语；第2、匹配不同数据集间的重要谓语得到候选谓语对；第2.1、汇总同一数据类型的谓语；对第1.3步得到的重要谓语进行分类，谓语的类型是由RDF宾语的类型决定，将谓语类型划分为四种，包括string，URI，数值和日期，对同一类型的谓语进行汇总，两两组成一个谓语对；第2.2、计算每个谓语对匹配的置信度；对第2.1步中每一个类型的所有谓语对分别计算其匹配的置信度，将谓语的所有宾语放在一个集合中，然后分别计算宾语间的Jaccard距离，也就是谓语对匹配的置信度；第2.3、筛选候选谓语对；通过阈值来筛选所有谓语对，只有当匹配对的置信度高于阈值时，该匹配对才能加入到候选谓语匹配对进入接下来的步骤中；第3、根据局部敏感哈希策略提取候选实例对第3.1、构建实例的向量空间模型；对RDF三元组的宾语进行分词，以词语ID作为特征值，这些特征用向量的方式来表达，将整个数据集转化为一个实例ID对应一个特征向量v的向量空间模型；第3.2、局部敏感哈希处理；采用基于Jaccard距离的局部敏感哈希函数族，随机产生n个哈希函数，对第3.1步的每个实例ID计算得到其签名向量，签名向量汇总在一起，整个数据集就转化为一个最小哈希签名矩阵，然后通过行条化处理得到候选实例对；第4、实例匹配设置实例匹配相似度的阈值，利用谓语匹配的置信度采用加权平均的方式计算实例匹配的相似度，大于相似度阈值的实例对即为最终的实例匹配结果。