对Web上已发布的数据集建立语义关联关系, 是迅速普及关联数据应用、发现并重用已有数据的一个方便快捷的办法。目前, 越来越多的网络资源正在向着数据网络 (Web of Data, 即Web中可被机器理解的语义数据) 方向前进[ 1], 图书情报界如美国国会图书馆、OCLC, 大型媒体公司如BBC、纽约时报等都纷纷试水关联数据, 大量传统网页上的数据正在被自动半自动地转换成关联数据, 英国政府也已大规模提供语义网 (关联数据) 信息服务, Web上的关联数据集越来越多, 根据关联数据的四原则, 数据一般使用RDF数据模型[ 2], 而数据之间的关联关系一般用“RDF链接”来表示[ 3, 4], 数据集中RDF链接的丰富程度是数据集质量的评价标准之一, RDF链接越多, 关联数据集的价值越高[ 5]。不同发布方发布的关联数据集中有很多可以建立RDF链接的三元组, 由于发布时无法统一考量而未实现关联, 一些可以自动发现数据之间关联关系并生成RDF链接的关联发现工具应运而生, SILK[ 6]就是一种关联发现框架, 由柏林自由大学的Christian Bizer及其研究小组的两位助手与Google的工程师Julius Volz共同合作开发, 目的是为了发现不同来源的关联数据集之间的关联关系, 并同时让数据发布者在自己的数据和Web上的数据之间生成RDF 链接。通过SILK框架, 来自不同关联数据集中RDF数据之间的关联关系可以被机器自动发现并以机器可理解的方式将这些关联关系表达出来, 在原本相互割裂的数据集之间建立起相互关联的桥梁, 可以极大地丰富Web上数据集之间的语义联系, 使数据产生更大的使用价值。
包括SILK框架在内, 用于发现和生成RDF链接的其他关联发现工具包括LinQuer与GANT等[ 7]。与SILK相比较, 这两者都只能按批次处理数据, 而SILK有单机版和服务器版, 更为灵活, 可以随需求而变化[ 8], SILK的关联规则描述语言 (Silk Link Specification Language, SILK-LSL) 可供开发人员自定义并配置对何种数据源进行关联、关联的条件以及需要进行的处理等。与SILK框架类似的还有LIMES[ 9]和R2R[ 10]框架, 这两者各有所长, LIMES框架在比较效率上较SILK更佳, 但实现复杂; R2R框架则需要熟悉R2R语言和编写R2R映射程序等, 对于开发人员的要求相对较高。与之相比, SILK框架支持大数据处理和服务端部署以及具有图形化界面的SILK工作台, 因此拥有更加丰富的应用场景和潜力。三种重要关联发现框架的比较如表1所示:
SILK关联发现框架的核心是关联发现引擎, 所有的SILK框架内的组件都依赖这个组件进行运作, 用SILK-LSL语言写成的关联规则描述文件是关联发现引擎工作的依据, 它定义了发现数据间关系的规则, 供关联发现引擎读取。
[ 12].
SILK-LSL是一种结构化的声明式语言, 用于指定SILK在哪些数据集之间发现RDF 链接, 一个典型的SILK-LSL文件如下: .
< ?xml version=" 1.0" encoding=" utf-8" ?>
< Silk>
< Prefixes…/>
< DataSources…/>
[< Blocking…/> ].
< Interlinks…/>
[< Outputs…/> ].
< /Silk>
其结构上是一个标准的XML文件, 根元素为: < Silk> < /Silk> 。子元素包括: .
(1) Prefixes: 指定数据集的前缀, 如< Prefixes> < Prefix id=" rdf" namespace=" http://www.w3.org/1999/02/22-rdf-syntax-ns#" /> < /Prefixes> 。
(2) DataSources: 数据源定义, 指定需要接入获取的本地或者远程SPARQL Endpoint。
(3) Blocking: 数据项分块, 在一般的比较中, 两个数据集如果各包含m和n个数据项, 则需要进行的比较运算是m×n的数量级。而数据项分块以后, 则可以大大降低这个数量级。如对于唱片的信息进行比较, 一般比较的数量级是m×n, 而如果按照唱片公司来分组, 两个数据集分别分为100组: 100i=0mi和100i=0ni, 则分块后运算数量级降低为: 100i=0, j=0mi×nj。
(4) Interlinks: 关联规则定义, 其主要结构包括: .
①LinkType: 生成的RDF Links 类型。
②SourceDataset、TargetDataset: 源数据集与目标数据集。
③LinkageRule: 关联规则, 分为输入、变形、比较、聚合4种类型。
(5) Filter: 用于过滤生成的链接, 可以指定每一个数据项返回最高置信度的N个链接, 如< Filter threshold=" 0.7" limit=" 1" /> 。
(6) Outputs: 指定输出RDF Links的格式和位置。
13]
.作为SILK框架的核心, SILK 关联发现引擎起着最重要的作用。其数据流图如图1所示, 从数据源中获取数据, 并对其进行分簇处理, 进行比较和发现关联, 最后过滤结果并进行输出。
.在这个过程中, 核心的处理流程是Blocking与Link Generation两个阶段。Blocking技术有效地降低了运算开销, 大大提高了处理的性能和效果; Link Generation则运用数据挖掘等相关技术, 应用不同的相似度算法等, 计算出两个数据项之间的差异程度, 并以此作为计算后续阶段置信度的依据。
(1) 分块技术 (Blocking)[ 13].
在大数据时代, 关联发现框架用于进行大数据集之间的关系发现, 但是其中有很多的数据项比较是不必要的或明显不符合相关规则的, 这部分比较将会浪费大量的计算资源。因此, 许多降低这些浪费的方法被提出, 最著名的就是分块技术。但是, 分块技术通常都需要进行配置, 且经常因为错误分块而导致的重新计算。
而在SILK框架中采用的是一种新的分块技术, 这项技术是为不同的实体进行映射到一个多维索引表中去, 如图2所示, 通过经度纬度和名称标签, 将不同的地点映射到一个三维索引表中去。映射到索引表中的每一个实体都保留了原本的距离, 因此原本相关程度高的实体在索引表中的位置也会非常临近。
.分块技术通过不同的相似度算法进行聚合, 因此可以在任意的关联规则下执行, 如字符串距离计算、地理位置相似度计算、时间日期相似度计算等。通过这种聚类方式避免了传统分块方式所导致的错误。
SILK框架中, 分块技术分为三个阶段: .
①索引生成: 在每一个相似度算法中, 都要通过一系列在欧几里得空间中定义的向量组创建索引, 不同的索引方式将会决定每一个实体所需要的向量个数。同时, 向量空间的维数则由数据类型决定, 如纯数值域只需要一维向量来标识距离, 而空间点坐标需要经纬度二维向量来标识距离。
②索引聚合: 这个阶段中, 所有在索引生成阶段生成的不同索引将会被整合进一个符合索引中去。这样不同的实体在保留原有的相对距离的同时又拥有相同的索引向量, 如图3所示。将二维的距离向量索引与一维的字符串向量进行索引聚合, 会生成一个三维的索引空间。
.③比较对生成: 通过前一阶段生成的索引, 可以确定哪些实体对存在潜在的关联。随后这些生成的比较对将会通过关联规则进行评估计算, 并得出最后的结果, 以确定是否增加关联链接。
(2) 链接生成 (Link Generation) .
链接生成是SILK关联发现引擎最重要的阶段, 通过数据挖掘等相似度计算, 对于生成的不同的比较对进行计算, 以确定最后的置信度。对于每一个比较对将会计算相似度, 相似度的值区间可以认为是一个百分数[ 17]。
在这个过程中, 最关键的是关联规则 (Linkage Rule)[ 18]。在SILK框架中, 关联规则分为4部分: 路径输入, 从一个实体的指定RDF路径中获取值, 如?movie/rdfs: label; 变形, 将一个数值类型进行转换处理, 如lowerCase; 比较, 将两个输入的值以用户指定的方式进行距离计算, 并返回置信度; 聚合, 将不同算法得出的置信度进行聚合, 返回最后的结果。
①路径输入 (Path Input) .
路径输入阶段指定了哪些实体的属性值将会被抽取并进行比较。在路径输入中, 可以通过在数据集中已经定义好的变量名加路径来获取不同的属性值, 其中可以使用的操作符如表2所示:
不同的数据集可能有不同的编码或其他格式, 通过变形处理, 可以在比较前将这些格式进行统一处理, 以返回正确的比较结果格式。SILK支持的变形处理提供了丰富的处理方式对数据进行清洗, 如表3所示:
比较阶段, 两个经过处理后的输入将会通过用户定义的距离计算方法和阈值进行比较运行, 以得到结果。输出的结果为0则为相同, 超过0则为不完全相同, 如图4所示, 在0至阈值之间的结果将会产生一个正分, 否则将会是负分。因此, 对于阈值的选择将会影响最后结果的准确程度。
.比较阶段采用的相似度算法主要分为: .
1) 基于字符的距离计算: 从字符层面对两个字符串进行比较, 通常对字母拼写错误等有较好的效果, SILK支持的算法如表4所示:
3) 其他用途的距离计算如表6所示:
聚合阶段需要将不同的多个置信值处理为一个单值。因为大多数情况下, 确定两个实体是否相同, 并不会简单比较一个属性值。在SILK中, 聚合处理的类型如表7所示。有些算法可以支持加权, 使得所得的置信结果更加精确和可靠。
通过使用SILK 工作台可以非常方便地对各种数据源进行发现。本文以SILK 工作台为工具, 简述如何利用SILK工作台对DBpedia的Settlement与LinkedGeoData中的City之间进行关系发现。
首先启动SILK Workbench并用浏览器访问首页, 新建项目, 并添加项目中需要的前缀, 如dbpedia: http://dbpedia.org/ontology/, dc: http://purl.org/dc/terms/等。
然后配置数据源, 分别配置DBpedia与LinkedGeoData的数据源, 还可以配置并修改一些常用的参数, 包括页大小、重试计数、重试间隔等。
随后添加关联任务, 配置源和目标数据源, 如图5所示, 分别选择之前已经配置好的前缀, 并配置相关的限制语句, 在链接类型中, 默认为owl: SameAs类型。
.在添加好关联任务后, 可以打开编辑关联规则, SILK Workbench提供了可视化的关联规则编辑器, 可以让用户方便地编辑关联规则, 如图6所示:
.左边栏分别显示了3.2节中的4类组件, 包括当前源和目标数据源实体的各属性值与变形、比较、聚合组件。右侧窗口为编辑窗口, 通过鼠标点选, 将左侧的内容拖放到右侧区域中, 不同的组件用不同的颜色进行标识。
此关联任务完整的关联规则分别将两个数据源中Label的英文名称与默认名称进行Levenshtein距离计算, 随后通过聚合组件取两者的最大值进行处理。同时, 通过wgs84地理位置距离计算, 将最后的结果进行平均值聚合处理, 以得到最后的置信值, 如图7所示:
.当配置完成以后, 可以运行关联任务, 查看最终的结果, 如图8所示:
.除了可以实时查看已经发现的关联, 还可以查看每一步关联规则的结果、置信度。在图8中, 迪拜的名称匹配度为100%完全相同, 而地理位置信息计算结果为99.2%的置信度, 最后平均得到99.6%的置信度。可以认为, 在DBpedia中的“Dubai”可以与LinkedGeoData中的“node31248510”添加owl: SameAs链接。
最后, 如果对于关联任务的执行结果没有疑问, 且关联规则配置无需进行再次修改, 则可以再次执行关联任务, 并选取之前配置好的输出任务, 将结果输出到指定位置。输出的形式同样可以进行配置, 本例中输出格式为N3, N3文件的默认输出位置为操作系统当前用户主目录的SILK目录下的output文件夹。
SILK框架的优点在于通过提供不同的组件应用于不同的场景, 包括单机与大数据环境均可使用, 且SILK 提供自带的SILK 工作台方便用户使用并简化了操作步骤与复杂度, 包括自动生成SILK-LSL文件; 通过图形化的关联规则编辑器进行编辑; 可视化的结果评估窗口, 使用户可以快速调整和改进关联规则; 提供了REST API[ 23]供用户集成并调用, 进一步拓展了SILK的应用环境。同时, SILK引擎中所采用的分块技术等也极大地提高了效率。SILK官方列出了SILK单机版和大数据版利用分块技术和不利用分块技术运行的对比表。在DBpedia与LinkedGeoData中建立owl: sameAs链接时, 利用了两个数据源的子集, 分别包含105 000与59 000条数据, 测试环境分别为SILK单机版: Intel Core2Duo E8500 处理器、8GB 内存; SILK大数据版: 亚马逊 Elastic MapReduce Cluster, 包含10个亚马逊的云计算机 (Amazon EC2) 。在没有应用分块技术时, 总的执行比较次数超过了60亿次; 而应用分块技术以后, 分块技术将城市按照名称划分为50个分簇, 随后得到的结果如表8所示:
从表8可以发现, 利用分块技术与大数据版可以大大降低运行的时间, 提高效率, 且生成的链接数丢失率相比无分块技术不超过1%。
而SILK框架也有一些不足之处, 它对计算资源的要求较高, 在一些普通配置的计算机上可能会发生启动时间较长、部分操作响应较慢的问题。同时, SILK在处理数据时, 需要首先将数据源的内容缓存到本地, 在缓存的过程中, 受网络环境、数据源影响较大, 且数据缓存无法主动释放, 可能会导致Java虚拟机内存溢出。还有包括对国内的部分主流浏览器如IE浏览器的兼容性不足, SILK内置的相似度算法多不支持汉字字符等问题。
相信在关联数据、语义网技术不断发展的过程中, SILK框架通过与大数据、数据挖掘等相关领域的技术进行结合, 会在用户研究应用的过程中提供更好的技术支撑与保障。