一种非完全的散点图去重叠算法  

Incomplete Overlapping Removal Algorithm for Scatterplots

作　　者：赵颖[1] 秀昱宏 唐涛[1] 文陈飞宇 陈晓慧[2] 尤旸 周芳芳[1] ZHAO Ying;XIU Yu-Hong;TANG Tao;WEN Chen-Fei-Yu;CHEN Xiao-Hui;YOU Yang;ZHOU Fang-Fang(School of Computer Science and Engineering,Central South University,Changsha 410083,China;School of Data and Target Engineering,Information Engineering University,Zhengzhou 450002,China;Mininglamp Technology,Beijing 100020,China)

机构地区：[1]中南大学计算机学院,湖南长沙410083 [2]信息工程大学数据与目标工程学院,河南郑州450002 [3]明略科技集团,北京100020

出　　处：《软件学报》2023年第2期945-963,共19页Journal of Software

基　　金：国家重点研发计划(2018YFB1700403);国家自然科学基金(61872388,62072470)。

摘　　要：散点图中数据点重叠现象会严重影响可视分析效率.现有散点图去重叠算法主要通过调整部分数据点的位置来完全去除重叠,但普遍存在画布面积增长、轮廓保持不自然、迭代时间较长等问题.认为完全去除重叠是非必须的,通过实验发现:用户能够在散点图有轻微重叠的情况下,快速、准确地完成数据点选取和区域密度估计等可视分析任务.因此,提出了一个非完全的散点图去重叠算法,该算法通过结合虚拟点临时占位、Voronoi网格划分、数据点选择性移动和重叠率快速计算等方法,实现分布紧凑、轮廓自然、高效迭代的散点图去重叠效果.通过客观实验和主观实验评估了算法性能.实验结果表明,该算法在移动距离、面积增长、形状保持、正交顺序、邻域保持这5个客观指标和形状相似性、类簇稳定性这2个主观指标上都优于现有算法.Data point overlapping frequently occurs in scatterplots,resulting in visual clutters to interfere visual analysis.Some overlapping removal algorithms have been proposed to remove data point overlapping completely,however,they have some common shortcomings,mainly including the increasing of canvas size,distortion of data distribution,and dissatisfaction of time consumption.This work proposes that the complete removal of data point overlapping is non-essential,while slight overlapping is acceptable in some data analytical scenarios.Therefore,an incomplete overlapping removal algorithm is designed for scatterplots.First,the algorithm generates virtual data points in the blank areas in a scatterplot by using a semi-random generation method.Second,the algorithm uses a Voronoi diagram to divide each data point into an irregular grid,and then moves data points to grid centers to reduce the rate of data point overlapping and maintain the natural contour of data distribution.At last,the algorithm iteratively runs the step of Voronoi meshing and data point moving until that the rate of data point overlapping reaches a preset threshold.A series of objective and subjective experiments are conducted to evaluate the performance of the proposed algorithm and reference algorithms.The results show that users can quickly and accurately accomplish visual analysis tasks,including data point selection and regional density estimation,in scatterplots with a slight data point overlapping.The results reflect that the proposed algorithm is superior to all of the reference algorithms in the objective and subjective indicators.

关 键 词：可视化 可视分析 散点图 高维数据 降维投影 去重叠 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]