ConcaveCubes: 支持基于聚类的大规模地理数据可视化 (ConcaveCubes: Supporting Cluster-based Geographical Visualization in Large Data Scale)

城市数据越来越容易获取,且规模不断扩大。现有的信息可视化方法在处理大规模数据时,需要占用大量的存储空间,交互时间过长,并且会由于渲染过多的图元而加重用户的认知负担。

已有的一些工作,提出基于数据立方体的数据结构,预计算可能的数据聚集的聚合值,从而提高运算速度。但是这些工作都只关注于支持热力图形式的可视化。热力图可以展现密度信息,保留离群点,但是不能很好地支持地理语义信息的展示。[1]中作者提出的方法,可以应对大规模的地理数据可视化,并且保留地理语义信息。

基于聚类的可视化

聚类

使用聚类的好处是不需要计算每一个数据点,只需要计算聚类的统计信息。同时,Tobler地理学第一定律指出距离更近的事物比距离远的更相关。因此,该工作按照地理远近进行聚类。

作者们将地理相关数据中的属性分为4类:地理相关属性,附加地理相关属性,地理无关属性,附加地理无关属性,并假设用户希望对地理无关属性和地理相关属性相同的元素进行按照地理位置远近的聚类。聚类的方法是首先按照地理无关属性进行聚集,再按照地理相关属性进行聚集。最后对每个聚集,使用层次DBScan进行层次聚类。

可视化设计

作者提出2种地图形式:基于气泡图的地图形式和基于边界的地图形式。其中,气泡图可以提供颜色和大小两个通道,但是被气泡包围的点不一定代表实际属于这个类。而边界地图可以精确地保证数据点落在所属的聚类对应的多边形之中。同时,还提供折线图和柱状图的多维数据可视化视图,以用于观察聚类在某些属性上的聚合值。

交互方面支持缩放和平移,过滤,精度控制和高亮、关联等操作。

图1. 基于聚类地图的界面

构建基于边界的聚类地图算法

需求

基于边界的地图,对聚类对应的图形有以下要求:

  1. 两个聚类对应的边界没有重叠
  2. 减少边界的复杂性
  3. 减少边界内部的空白区域
  4. 避免调参数

方法

算法步骤如下:

  1. 进行Delauney三角化;
  2. 去除多余边,包括:端点分属不同聚类的边,位于多边形内部的边,以及2个端点的度都为1的边;
  3. 消除非Jordan边界,若∠p’pp”的三个点不在闭合的环上,则称其为外角,取一个聚类中的最小外角∠p’pp”,连接p’p”,去除内部边,重复该步骤,直到不存在外角。

消除非Jordan边界的示意图如下所示:

图2. 非Jordan边界的两种情况。左:单独的边;右:2个环

时间复杂度

对n个点的数据集,Delauney三角化的复杂度为O(nlogn),去除边的复杂度为O(n),消除非Jordan边界的复杂度O(s),s<<n,所以总复杂度为O(nlogn)。

ConcaveCubes:基于聚类的数据立方体索引

建立ConcaveCubes

为了适应大规模数据,作者们提出了ConcaveCubes这一数据结构来存储聚类的统计信息。首先介绍构建ConcaveCubes的整体流程。如下图所示:

图3. ConcaveCubes构建流程图

需要用户对数据进行预处理,指定维度的分类和顺序,指定地理语义如何映射;随后,按照指定顺序对数据进行聚集;对每个聚集的数据子集计算层次聚类;对聚类结果,进行边界计算和统计值计算。

最后得到的ConcaveCubes如下图所示:

图4. ConcaveCubes的结构示意图

在这一结构中,相同聚类中的数据存储在相近的位置,并被进行索引。与其它工作的不同之处在于它没有使用四叉树对空间进行划分,而是使用地理语义进行划分,如国家-省-市的方式。

ConcaveCubes索引的操作

初始时,根据当前地图视图的范围、用户选定的维度和聚类层次,读取相应的聚类数据;

  • 对缩放和平移:计算当前地图视图范围包含的聚类,与原范围对应的聚类集合进行集合求差操作,根据结果进行重新渲染;
  • 对过滤:由于用户会选取不同的条件,如同时选取3个房间的房子和别墅,会造成聚类结果的边界重叠,此时需要检测边界的重叠并对边界进行合并;
  • 对粒度的控制:对应于ConcveCubes中的不同的聚类层次。

实验

作者们对现实的房产数据、社交媒体数据和模拟的人口数据进行实验,发现尽管它的构建时间比已有的工作长,但是内存占用要小得多。

根据收集到的用户实际的查询,对它们计算查询时间,发现虽然比已有工作稍长,但全部少于100ms。

从可视化结果看,作者们提出的聚类地图视图可以更好地保持地理语义信息。

结论

这篇论文提出了基于数据立方体的数据结构,ConcaveCubes;基于聚类的地图视图和多维数据视图;以及有效计算聚类边界的新颖算法,可以保持地理语义信息,支持用户探索大规模地理数据。

参考文献

[1] M. Li, F. Choudhury, Z. Bao, H. Samet, and T. Sellis, “ConcaveCubes: Supporting Cluster-based Geographical Visualization in Large Data Scale”, Computer Graphics Forum, 2018.

评论关闭。