大数据技术中图像搜索服务


May 18, 2018

图像识别服务(Image Recognition)是基于大数据和深度学习实现的,可精准识别图像中的视觉内容,包括上千种物体标签、数十种常见场景等,包含场景分类、图像打标等在线API服务模块,应用于智能相册管理、图片分类和检索、图片安全监控等场景。


图的表达能力强、应用广泛,在社交网络、生物数据分析、推荐系统、复杂对象识别和软件代码剽窃检测等领域都起着重要的作用。社会计算一般认为需要考虑社会的结构、组织和活动等社会因素,而所有的社会活动构成了社会网络,其本质上是图的一种表现形式。在社会网络中,可以把用户看作图的顶点,用户之间的关系(如朋友关系)看作图的边。图的广泛应用自然而然使得图搜索成为了工业界和学术界的共同关注点。


图搜索是一种“大数据”时代适应社会计算的搜索方式,虽然对于社会计算目前还没有明确公认的定义,但是大家普遍承认社会计算一般需要考虑社会的结构、组织和活动等社会因素。所有的社会活动构成了社会网络,本质上这是图的一种表现形式,所以图搜索自然而然的就成了工业界和学术界的共同关注点。图搜索在社会计算“大数据”时代将很有可能成为一种统一的面向社会网络的搜索模式,综上表明图搜索是“大数据”时代适应社会计算的重要搜索方式,并起到了极其重要的作用。


图搜索作为近年来逐渐兴起的一种新型搜索技术,为用户获取所需信息提供了一种方便快捷的搜索方式。图搜索的核心关键问题是建立满足新型应用需求的图搜索理论和模型,并提供高效的搜索查询技术,以提高搜索的效率和查询结果的准确性。大数据时代的图搜索理论和技术是目前国际上数据库领域的研究热点之一。


本文将首先介绍图搜索及其应用,然后介绍几类具体的图搜索,目前,图搜索技术中主要包含以下4中搜索方式:


1. 路径搜索


当 前 应 用 广 泛 的 定 位 服 务 ( L o c a t i o n   B a s e d Services)使得交通网络领域也成为图搜索的应用领域之一。下面我们通过交通路线搜索中的一个应用实例来介绍路径搜索。图搜索服务可以根据用户对行程的要求和约束选择合适的路线,提供人们出行的方便。


2. 凝聚子图搜索


凝聚子群原指社交网络整体用户中的一个子集用户群,并且该子集用户群内用户之间满足某种“紧密关系”。根据应用需求的不同,会有不同的“紧密关系”,从而产生不同的凝聚子群。社会网络可以用图来表示,其中图的顶点表示用户,边表示用户之间的关系,比如朋友关系等。这样,我们也称凝聚子群为凝聚子图,相应的我们将从图中搜索凝聚子图的搜索称为凝聚子图搜索。


结合著名的“Padgett's Florentine家族网络图”,可以解释凝聚子图:


这个家族网络包括了15世纪早期意大利佛罗伦萨的16个大家族的婚姻关系网络,其中图的顶点表示家族,并且用家族的姓氏加以标注;边表示一个家族的某个成员和另一个家族的某个成员有着婚姻关系。家族间通过婚姻结合和商业交易结成并巩固家族间政治经济同盟关系,我们利用凝聚子图搜索技术从家族关系数据中找到这些家族同盟体,并研究不同家族同盟间的政治经贸关系,从而更好地了解当时佛罗伦萨的历史状况

1. 关键词图搜索

随着各行各业互联网的覆盖和信息化技术的普及,数据量的增长速度显著加快。怎样在如此大量的信息资源中获取出需要的数据信息,成为当今的一项研究热点。“关键词搜索”(Keyword Search)为用户从数据集中获取相关信息提供了有效的技术支持。由于关键词搜索极其友好的搜索界面,它已经成为事实上的互联网数据信息检索通用机制。关键词图搜索指的是给定一组关键词,从图中查找“满足”该组关键词的子图,并且子图中的顶点满足“一定”的结构约束关系。这样,图上的关键词搜索同时考虑顶点之间结构和包含的内容两类信息,这里通常输入图上的每个顶点都被标示了一组关键词。关键词图搜索的基本要求是找到的子图顶点中包含所有的输入关键词,而结构约束关系的不同导致了不同的搜索方法和技术。以下是三类关键词图搜索:

1) 最小树语义。目前大多数关键词搜索采用最小树语义。查找到的结果是树,所有输入的关键词一定出现在该树的某个顶点中,并且该树的所有边的权重之和最小。

2) R半径Steiner图语义。给定一个半径小于等于r的图G和一组关键词K,如果G中两个顶点u、v均包含输入K中某个关键词,那么u和v之间路径上的点(包含u、v)称为Steiner顶点。实际上Steiner顶点就是与K中的关键词直接或者间接相关的顶点。以Steiner顶点及其相关边构成的G的子图就称为r半径Steiner图。采用这种语义的关键词图搜索输出结果是r半径Steiner图。

3) R-极大团语义。采用这种语义的关键词图搜索输出结果是r-极大团,该方法在图中搜索得到含有关键词的顶点,而且r-极大团顶点集合包含了所有的输入关键词,并且任意两个顶点间距离都不大于r,这样就对搜索结果间关系的紧密程度做了限制。

实际上,由于关键词图搜索中缺少输入关键词之间的结构约束关系,因此需要通过“猜想”关键词之间的拓扑结构,从而形成了各种语义。并且,由于对用户期望的搜索结果进行猜想,搜索的结果就需要结合排序(Ranking)。因此所有的关键词搜索(包括经典的关键词搜索)都需要结合排序技术。

2. 图匹配查询

图匹配查询中,尽管模式图结构都一样,由于“匹配”语义的不同,形成了子图同构、图模拟和强模拟等不同的图匹配查询语言。

1) 图同构(Graph Isomorphism)。要介绍子图同构,需要先介绍图同构(Graph Isomorphism)。给定一个数据图G和一个查询图Q,则Q与G同构当且仅当Q顶点集VQ与G的顶点集VG之间存在一个双射关系f:VQ →VG,使得若图Q中任意两个顶点u和v之间有一条边当且仅当在图G中相应顶点f(u)和f(v)之间有一条边。

2) 子图同构(Subgraph Isomorphism)。给定一个数据图G和一个查询图Q,则Q与G子图同构当且仅当在G中存在一个子图Gs与图Q同构。我们通过推荐系统中的一个应用示例来介绍图匹配,如下图所示:




图中每个顶点代表一个专家,顶点上标签表示其专业方向,顶点之间的边代表两人间的推荐关系,当输入模式图和数据图分别为图中Q和G时,在数据图G中执行基于子图同构的图搜索时,即“匹配”语义定义为子图同构时,结果显示数据图G与查询图Q不是子图同构的,即G中不存在任何子图与Q具有完全相同的拓扑结构。

我们通过调查发现图搜索理论及相关技术在各个领域中有着重要的商业价值。东方金信在图搜索服务方面也开发出属于自己的产品并投入了生产环境,其中包括海盒大数据R语言开发系统SRS,可为R语言环境提供分析挖掘的开发系统界面;海盒大数据分布式数据挖掘系统SHO,集成了多种分布式的挖掘算法,可供用户通过可视化界面进行调用;海盒数据可视化分析系统(SDV),可为用户提供一个网页端的图形化操作界面,通过该界面用户可以进行批量和实时的数据分析展现,实现报表、管理驾驶舱与多种图形的数据展示。

从分析图搜索在当前工业界的应用和学术界的研究发展动态,以及搜索的历史发展两个方面,我们看到了当前大数据时代图搜索的重要性,同时,我们也看到了图搜索所面临的挑战。可以看出,大数据时代图的搜索理论及相关技术是一个亟待研究和解决的内容,具有重要的科学意义和应用价值。