剑客
关注科技互联网

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere…

当我们想要理解大型网络数据时,搜索和分析是主要的 手段。为实现快速的搜索分析,一个广泛使用的方法是特征描述子(FDs)。特征描述子常用来描述某些重要的数据属性,然后根据这些属性计算数据元素之间的相似性分数。这篇文章[1]提出一系列经过验证的特征描述子,描述矩阵视图中的特征,以此来引导用户探索分析大型网络数据。这个工作主要的挑战包括:

  • 矩阵视图中存在哪些有趣的特征模式?
  • 如何有效的描述这些特征?
  • 怎么评估视图在某个特征下的相似度?

在这篇文章中,他们主要分析矩阵视图中的6种特征(如图1所示)[2]。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图1. (a)对角线块特征,表示网络中全连接子图;(b)非对角线块特征,表示网络中的二部图结构;(c)星型特征,表示网络中星型结构;(d)条带特征,对应网络中的路径。(e)和(f)是算法伪影,不能反映网络中的任何特征

为了描述这些特征,他们从图像处理的相关文献中收集了27种特征描述子。此外,作者们还根据矩阵特征的特点,设计了3种特征描述子。图2展示了初始集合中的30种特征描述子。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图2. 初始集合中的30种特征描述子

为了测试这些特征描述子的效果,他们根据两种准则设计了基准数据集(如图3所示)。第一个准则是特征变式,用于分析特征描述子能够识别哪些类型的变式。文中涉及的变式主要有特征的大小,数量以及位置。另一个准则是特征弱化,主要用于分析特征描述子对噪音的敏感程度。在这里,噪音主要指矩阵视图中随机分布的黑色色块(black cell)。文章主要涉及三种特征弱化策略,分别是随机交换方块(cell),随机交换行列和随机添加黑色方块。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图3. 5种特征在特征变式和特征弱化下的结果

为评估特征描述子的性能,他们提出了4种评估准则,分别是特征响应能力(pattern response),特征变异识别度(pattern variability),特征敏感度(pattern sensitivity)以及特征辨别度(pattern discrimination)。

特征响应能力,主要用于评估特征描述子在有噪音的情况下,识别特征的能力。为此,他们训练了一个随机森林分类器,分析每个特征描述子识别每种特征的准确率和召回率。图4展示了评估结果。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图4. 特征响应能力评估结果。蓝色越深,表示响应能力越强,说明特征描述子对相应的特征具有越强的响应能力。

特征变异识别度,主要用于分析特征描述子对特征变异的敏感程度。敏感度高,表示该特征描述子只能识别某种状态下的特征。在这里,作者们只考虑基于特征变式的图片,不考虑添加了特征弱化的基准数据。他们通过计算了特征描述子描述同个特征不同变式下的向量之间的欧拉距离,分析这些距离的标准平方差,评估特征描述子的特征变异识别度(图5)。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图5. 特征变异识别度。颜色越深表示越敏感。因此,方块颜色浅或白色,表示这个特征描述子对相应的特征具有很好的识别能力

特征敏感度,用于分析特征描述子对不同特征弱化方法和弱化程度的敏感度。在相同弱化方法下,他们计算得到同个描述子描述同个特征不同弱化程度下的向量,然后分析这些向量之间的欧拉距离,继而分析该描述子在识别某个特征时,对不同弱化程度的敏感度。特征描述子对随机交换方块的敏感度如图6所示。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图6. 对随机交换方块的敏感度评估结果。颜色越深,表示敏感度越低,说明该特征描述子在特征弱化的情况下,也具有很好的识别能力。

特征辨别度,用于分析特征描述子区分不同特征的能力。在这里,针对同个特征描述子,他们计算了描述子描述不同特征的向量。针对同个特征,他们获取了相应向量之间的中值。随后,他们计算了这些中值向量之间的欧拉距离,并绘制了图7。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图7. 箱形图(box plot view),描述特征辨别度的评估结果。中位数大,表示同个描述子描述不同特征的向量之间欧拉距离大,说明该描述子具有比较好的特征区别能力。

根据上述四种规则的评估结果,作者们总结了图8表格。表格中的颜色与评估准则一一对应,蓝色表示特征响应能力;红色是特征变异识别度;棕色是特征敏感度。每个矩形块中的黑点表示作者们对这些描述子性能的主观描述。三个黑点表示性能好,排序高;没有点表示性能差。根据这个表格,作者们最后选了六种特征描述子(黑框标注的描述子)。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图8. 根据四种评估结果总结的特征描述子性能汇总表。

接下来,我将介绍两种使用场景来说明特征描述子在引导用户探索大型网络数据中的作用。在第一个使用场景中,作者们设计了一个系统(如图9所示)支持用户从4313个矩阵图片中搜索与某一特征相似的图片。用户可以绘制任意的特征。然后系统会计算特征描述子描述绘制图片的向量和图片库中每张图片之间的向量之间的欧拉距离。之后,根据距离的大小,将相似的图片进行排序,返回給用户。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图9. 基于特征描述子的系统http://magnostics.dbvis.de/#/sketch/

在第二个使用场景中,他们想要分析动态图随时间的变化情况。在这里,他们分析的是脑部区域连接数据。他们用BLOCK特征描述子分析不同时间步数据中存在的群簇状态;用HARALICK描述子分析不同时间步数据中的噪音。为了分析群簇和噪音随时间的变化情况,他们计算了相邻时间步同个描述子的描述向量之间的距离,并绘制了图10。在图中,红色线是BLOCK的描述结果;蓝色线是HARALICK的描述结果。我们可以发现,在时间步6到时间步9之间,红色线的值很高,这个现象说明此时网络中的群簇结构在发生比较剧烈的变化;时间步11到时间步14之间,蓝色线的值比较高,说明这段时间内,网络中的噪音变化比较大。

Magnostics:基于图片搜索有趣的矩阵视图引导网络探索(Magnostics: Image-based Search of Intere...

图10. 采用特征描述子分析动态图的变化情况。

总的来说,这篇文章介绍了若干个经过验证的特征描述子,用于描述矩阵图片中的特征。同时,通过两个使用场景,他们尝试说明使用特征描述子,从大型网络数据中搜索具有某些特征的网络,可以有效的引导用户分析探索这些数据。

我认为,当数据量很大时,单纯的依靠用户通过交互理解数据是很困难的。为此,结合图片处理方法,快速获取满足要求的视图,协助用户分析理解数据是个不错的方法。但是,很多情况下,用户并不清楚数据中存在哪些有趣的特征,并不具备通过搜索,分析数据的能力。

References:

[1] Behrisch, Michael, et al. “Magnostics: Image-based Search of Interesting Matrix Views for Guided Network Exploration.” IEEE Transactions on Visualization and Computer Graphics 23.1 (2016): 31-40.

[2] M. Behrisch, B. Bach, N. H. Riche, T. Schreck, and J.-D. Fekete. Matrix Reordering Methods for Table and Network Visualization. Computer Graphics Forum, 2016. doi: 10.1111/cgf.12935

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址