2018年春季学期视觉计算实验室第9周论文研读预告

时间: 2018年5月3日上午9:30
地点: 四川大学望江校区视觉计算实验室
研读人员: 韦东鑫、朱浩天
研读内容:
[1] Lam H, Tory M, Munzner T. Bridging From Goals to Tasks with Design Study Analysis Reports[J]. IEEE Transactions on Visualization & Computer Graphics, 2017, PP(99):1-1.

[2] Michael Laszlo and Sumitra Mukherjee, A Genetic Algorithm Using Hyper-Quadtrees for Low-Dimensional K-means Clustering, IEEE Transactions on Pattern Analysis & Machine Intelligence, Vol.28, No.4, April 2006.

论文[1]简介:

可视化研究人员与从业者在进行可视化系统设计与评估时所遇到的共同难题是:难以将系统用户提出的问题与用户可能进行的系统操作抽象化,换句话说就是很难用领域无关(domain-agnostic)的描述语言来描述问题与操作。

传统的抽象方法更像是一种自底向上方法:该方法将整个分析流抽成一个个低阶分析步骤(low-level analysis step),然后迭代地将各个分析步骤组成不同的高阶分析目标(high-level analysis goal),理论上该方法应该有效,可实质上该方法存在耗时、耗力、难度大等不足。

论文作者设计出一种自顶向下的抽象方法,该方法的核心思想是:将分析流分片为一个个不同的可操纵分析单元(manageable unit),每个单元配有一个具体的高阶分析目标,再将不同单元向下细分为一个个不同的低阶分析步骤,每一个步骤对应一个低阶可视化任务,这样便能够实现拉近目标与任务的任务。

在这样的思想下:论文作者通过对2009-2015年IEEE InfoVis上数百篇论文进行分析,制作出一个框架,框架中包含9个高阶分析目标,按照2个类型进行分类,依据该框架,可以帮助可视化研究人员有效地缩减高阶目标与低阶任务之间的差距,将用户提出的难题与进行的操作抽象化,削弱用于描述难题与操作的语言中所存在的领域特定性(domain-specific)。

---1

图 1 文献分析流程

在介绍框架之前,可首先从图一中观察论文作者对287篇InfoVis论文进行分析并最终制作出框架的整个流程。

论文作者之所以只选择InfoVis论文进行分析,主要考虑到VAST与SciVis上的相关文献较少,因此依据数量因素选择了InfoVis。随后不断地设置规则一步步地简化、分析、抽象化,最后得到了一个包含2个坐标轴,9个分析目标的框架。

---1-1

图 2 框架展示

如图2所示,框架中包含2个坐标轴,表现为图2表中的行列,其中行包含Explore、Describe、Explain、Confirm,用于表示4种主要的大分析目标,每一个大分析目标含有一至多个小分析目标,每一小分析目标中都会有一个Input、一个output用于描述该目标的输入输出。

以Discover Observation为例:该目标的输入为原始数据,可将原始数据假设为一场球赛中的该类行为(如进攻、防守、得分情况等等);该目标的输出为一个Observation(从原始数据中发现的有趣现象,比如某个球员的某一次进球)。

论文中会对框架中的每一个分析目标举例进行说明,帮助读者更好地理解框架的整体结构。

论文[2]简介:

K-means算法由于其计算效率高被广泛应用在聚类问题上。但k均值对于初始点的选择非常敏感,且可能会收敛于明显低于全局最优值的分区。

遗传算法(GA)通过模拟自然界进化的过程,使用每个染色体存储一组基因,由这些基因共同确定染色体对下一代繁殖或以其他方式贡献的适应性或可能性。遗传算法虽已经被研究用于寻找最优分割,但其计算代价太高,常常无法使用。

为了解决这样的问题,作者构造了一种超四叉树结构的染色体;通过模拟遗传过程,使用点的位置为基因赋值,根据SSE计算基因的适应度,经过多代演化后得到适应性最强的k个中心。

通过在多个真实数据集和模拟数据集上进行测试,通过与已知最优解和J-means的结果比较,作者的遗传算法均能在较小的计算代价下得到已知最优值的数据集的全局最优解,并为大型模拟数据集找到了较好的解决方案。

由于现阶段,实验室多位学长学姐都在处理路径规划、区域划分相关的问题;本次研读,将以四叉树和遗传算法的概念为入口,为大家介绍论文作者如何巧妙的设计了四叉树结构的染色体,并用其解决低维数据的最优分割问题。
21

图 3 使用四叉树的两种子区域划分