PKU Visualization Blog

在可视数据分析中，分析者需要用视觉观察数据，寻找有趣而未知的模式。在降维的投影的语境下，希望降低人的认知开销，让机器事先找到有趣的投影。为此，就需要量化定义投影的质量，在许多工作中都给出了各自的视觉效果度量（visual quality measure），这些度量都希望能够模仿人类知觉的准则。

本文只考虑到二维散点图的投影，在二维散点图的视觉效果度量的相关工作中，一般来说，这些视觉效果度量，或者说可分性度量，希望散点图中不同类的中心距离比较大，或者希望在不同范围中根据类标签计算出的熵比较小。不失一般性，本文只讨论数据的类别标签只有两种的情况。

图1. 左侧是视觉效果较好（可分性好，分析者可能更感兴趣）的散点图（投影）；右侧是视觉效果较差（可分性差，分析者可能不感兴趣）的散点图（投影）

上面两张图片是文中考虑的散点图的例子。

在这个工作中，作者提出了一个统一的构造视觉效果度量的流程，即将视觉效果度量分成三步:

1. 定义邻域（neighborhood），对散点图中每个点计算邻域，将原来的散点图转化成点的邻近关系图。

2. 定义类纯度（class purity），对每个点或整个散点图的邻域计算类纯度。

3. 如果第2步类纯度的定义是针对一个点的，则需要对所有散点或者一个特定类的散点，计算这些点的邻域类纯度的均值，作为散点图的视觉效果度量。如果第2步类纯度的定义是针对整个散点图的，则这个类纯度就是最后整个散点图的视觉效果度量。

按这样的一个流程，可以将所有此前有关二维散点图的视觉效果度量的计算进行拆分，从而进行归类。更重要的是，通过先前已有的对邻域的度量方法，对类纯度的度量方法，可以组合出非常多的新的视觉效果度量。本文中，作者就通过挑选不同的邻域定义，不同的类纯度定义，不同的求平均方法，组合出了2002种不同的度量方法。并且其中最好的一种方法能够显著优于此前的工作中给出的最好的方法。

这样的流程之所以合理，就在于当一组散点可分性好时，各类的类内分散程度会较小，类间分散程度会较大，因此一个点的“邻域”内，一般都是与自己同类的点，即“纯度”较高。

在第一步中的邻域定义，还可以细分为硬边界邻域（hard neighborhood）和软边界邻域（soft neighborhood）。硬边界邻域是指，对于一个点，所有点中只有一个特定的子集是他的邻域；软边界邻域是指，对于一个点，所有其他点都在他的邻域中。

注意到，有一些方法其实不是特别符合文中这个流程。比如LDA中，既没有显式定义邻域，也没有显式定义类纯度。在这个流程下，LDA的邻域定义可以勉强算成是软边界邻域，但是他的类纯度定义确实就无法合适地进行归类。很多在邻域定义方面被归为软边界的方法在类纯度定义方面都难以归类，因为这些方法中往往是把这两步糅合起来做，因此后文在通过三个步骤的不同组合生成新的度量方法时，在邻域定义中只考虑硬边界的邻域定义。

在硬边界邻域定义中，文中提到了11种方法，其中前5种不带人为设置的参数，后6种包含人为设置的参数。

第1种定义是Delaunay Graph，他不带参数。这种定义是，将原来的散点图做成Voronoi图，做出来的图中，如果一个点所在的网格和另外一个点的所在的网格相邻，则这两个点相互是neighbor，即相互出现在对方的neighborhood中。

第2种定义是Gabriel Graph，他不带参数。这种定义是，如果以两个点连线作为圆的直径的两端，作出一个圆，这个圆内不存在任何点，则这两个点相互是neighbor。

第3种定义是Relative Neighbor Graph，他不带参数。这种定义是，如果两个点p、q，找不到另外一个点r，使得按欧氏距离，rp和rq都比pq短，则p、q相互是neighbor。

第4种定义是Minimun Spanning Tree，他不带参数。这种定义是，将原来的散点图中每个散点作为图的一个结点，构建一个完全图，找这个完全图的一个最小生成树，这个树上相邻的结点相互是neighbor。

第5种定义是Sphere-of-Influence Graph，他不带参数。这种定义是，如果点p的最近邻是点x，点q的最近邻是点y，如果按欧氏距离，pq比px+qy小，则p、q相互是neighbor。

第6种定义是ε-Ball Graph，他带一个参数ε。这种定义是，如果按欧氏距离pq小于ε，则p、q相互是neighbor。

第7种定义是K-Nearest Neighbor Graph，他带一个参数K。这种定义是，如果所有点中距离p最近的K个点中有q，则q是p的neighbor，但反之不一定。

第8种定义是K-Nearest Center of Gravity，他带一个参数K。这种定义是，对于点p如果所有点中，选择一个点q1能使得点集{p,q1}的重心最接近p，则将q1加入点集。接下来如果选择一个点q2能使得点集{p,q1,q2}的重心最接近p，则将q2加入点集。以此类推，一直这样加到第K个结点qK，则q1,q2,…,qK都是p的neighbor，但反之不一定。

第9种定义是Circle-based β-Skeleton Graph，他带一个参数β。这种定义是，对于p、q，如果任意其他点r，都能使得∠prq＜π(1+β)/2，则p、q相互是neighbor。

第10种定义是α-Shape，他带一个参数α。将原来的散点图做成Voronoi图，做出来的图中，如果一个点所在的网格和另外一个点的所在的网格相邻，并且这两个点的欧氏距离小于等于2/α，则这两个点相互是neighbor。

第11种定义是γ-Observable Neighbor Graph，他带了一个参数γ。对于点p、q，如果线段pq的γ分点γp+(1-γ)q的除了q以外的点中的的最近邻是p，则q是p的neighbor，但反之不一定。

需要注意的是，在第一步生成邻近关系图时，如果使用的neighborhood的定义是K-Nearest Neighbor Graph或者K-Nearest Center of Gravity或者γ-Observable Graph，则若q是p的邻居，q不一定是p的邻居，也就是说得到的邻近关系图是一个有向图。对于这个有向图，有三种进一步处理的方法，第1种是维持原样，第2种是将所有有向边全都作为双向边，第3种是删除所有的单向边。

在第二步的类纯度定义中，文中提到6种方法。其中前4种定义是基于neighborhood的，后2种定义是基于不同的类别的连通成分的。需要注意的是，前4种定义是针对单个点的，因此后续需要第3步进行求平均，而后2种定义直接针对整个散点图，因此之后不需要进行求平均。

第1种定义是Class Proportion。对于一个点，他的所有neighbor中与他类别标签相同的点所占的比例作为这个点处的类纯度。

第2种定义是Class Entropy。对于一个点，他的所有neighbor加上他自己，对所有这些点根据类别标签计算信息熵，作为这个点处的类纯度。

第3种定义是Majority Vote。对于一个点，他的所有neighbor中，如果与他类别标签相同的点的比例，比其他任意一种类别标签的点的比例都大，则这个点的类纯度为1，否则为0.

第4种定义是Weighted Vote。对于一个点p，他的每个neighbor按自己的类别标签对p的类别标签进行投票，且票的权重按照这个neighbor与p的距离进行加权。假设p的neighbor中与p最近的是r，与p最远的是s，当前是x进行投票，则x的票权重是 (ps-px)/(ps-pr)。

第5种定义是Largest Target Class Component。对于之前在第一步中通过邻域定义得到的邻近关系图，将其中所有联接两个不同类别的结点的边都删除。这样，原先的邻接关系图就拆分成了多个连通分量，每个连通分量内部的都是相同类别标签的结点。假设第i个类的连通分量有C[i][1],C[i][2],…,C[i][Ki]，这些连同分量按包含的点数从多到少排序。让i作为变量，最大化C[i][1]/(C[i][1]+…+C[i][Ki])，这个值就作为这个散点图最终的类纯度。

第6种定义是Mixed Class Edge Cut。对于之前在第一步中通过邻域定义得到的邻近关系图，统计其中所有联接两个不同类别的结点的边的个数x。假设邻近关系图中有k个不同的类别，每个类别中分别有D[1],D[2],…,D[k]个结点。对于原来的邻近关系图中的所有节点删除类别标签，然后随机赋类别标签，使得最后图中仍然有k个不同类别，每个类别中分别有D[1],D[2],…,D[k]个结点。再统计其中所有联接两个不同类别的结点的边的个数x’，则x’大于等于x的概率就作为这个散点图最终的类纯度。

如果第二步使用了前4种定义，即对于单个结点的基于neighborhood的类纯度的定义，则需要第三步对类纯度求平均。求平均有两种方法，一种是对于所有点的类纯度求平均，另一种是对于某个给定的类别的所有点求平均。

图2. 视觉效果度量的计算的统一流程

将之前的3步的流程汇总，就能得到上图中的整个流程。

通过在每个步骤中选择不同的方法，以及对于含参数的方法中进行调参，最终就能得到2002种视觉效果度量的准则。

接下来作者对这些准则进行了评估。

作者首先对所有2002种方法进行了定量的评估，使用了他们先前在Data-driven Evaluation of Visual Quality Measures[1]中提出的Area Under the Receiver Operating Characteristic Curve Bootstrapped Average评估方法，给出了不同的视觉效果度量的优劣。

这个评估方法的大致思想是事先已经有了少量的由人类标注了“可分”或“不可分”的散点图。对于这些数据通过Bootstrape可以生成很多标注了“可分”或“不可分”的散点图，用于作为评判标准。假设其中一共有P个散点图标注为可分，一共有N个散点图标注为不可分。

对于所有的视觉效果度量给出的分值范围，将其线性归一化到0-100，分数越高表示可分性越好。对于一种视觉效果度量的给分，可以给定一个阈值，给分低于这个阈值时，认为那个散点图不可分，否则可分。假设对于某个给定的阈值，这种度量判断是可分的散点图中，有TP个在评判标准中也认为是可分的，有FP个在评判标准中却认为是不可分的。

现在让阈值可以变动，就能得到TP/P与FP/N形成的二维平面上的曲线，显然这条曲线一定处在[0,1]×[0,1]中。这条曲线下围的面积越大，说明使用的视觉效果度量在很多不同的阈值下都表现较好。因此就用这个面积作为对这种视觉效果度量的优劣的评分。这就是Area Under the Receiver Operating Characteristic Curve Bootstrapped Average的大致做法。

通过这种准则，发现所有2002个方法中，最好的是：在第一步使用γ-Observable Neighbor Graph，其中γ取为0.35，在第二步使用Class Proportion，记这种方法为GONG 0.35DIR CPT。这种方法用Area Under the Receiver Operating Characteristic Curve Bootstrapped Average可以得到平均0.929的评分，而此前最好的Distance Consistency measure只能得到平均0.812的评分。

然后作者对GONG 0.35DIR CPT和Distance Consistency measure进行了一个定性的case study进行比较。

作者使用了一个现实世界中的Wisconsin Cancer的数据集进行比较。这个数据集一共有30个维度，作者用他们生成了435个二维散点图。对于每一个散点图，GONG 0.35DIR CPT和Distance Consistency measure各自有一个评分，一共435对评分的分布如下图所示

图3. GONG 0.35DIR CPT和Distance Consistency measure的打分的关联

作者分析了两种情况：对于两个散点图GONG 0.35DIR CPT给分相同，而Distance Consistency measure给分不同；对于两个散点图GONG 0.35DIR CPT给分不同，而Distance Consistency measure给分相同。对于每种情况，作者都给了一个例子。

图4. GONG 0.35DIR CPT和Distance Consistency measure的打分对比，每个括号中右侧是GONG 0.35DIR CPT的打分，左侧是Distance Consistency measure的打分

在上图中(b)和(c)的GONG 0.35DIR CPT给分不同，而Distance Consistency measure给分相同。作者认为，从人的角度看，(c)比(b)更可分，因此GONG 0.35DIR CPT给分不同是有道理的，Distance Consistency measure给分相同是不合理的。而(d)和(e)的GONG 0.35DIR CPT给分相同，而Distance Consistency measure给分不同。作者认为，从人的角度看，(d)和(e)两者可分性差不多，因此GONG 0.35DIR CPT给分相同是有道理的，Distance Consistency measure给分不同是不合理的。

综上，作者提出了一套统一的计算有两类不同类别的点的散点图的视觉效果度量的流程，并尝试了在这个流程的各个步骤中使用各种不同的方法，从而组合出2002中不同的视觉效果度量准则。评估后发现其中最好的方法GONG 0.35DIR CPT显著优于此前最好的方法Distance Consistency measure，并且通过case study对这两种方法进行了比较，发现在GONG 0.35DIR CPT在被考虑的case上可能确实比Distance Consistency measure能更好地模拟人的评判标准。

[1] Sedlmair, Michael, and Michael Aupetit. “Data‐driven Evaluation of Visual Quality Measures.” Computer Graphics Forum. Vol. 34. No. 3. 2015.

[2] Aupetit, Michael, and Michael Sedlmair. “SepMe: 2002 New Visual Separation Measures.” PacificVis. 2016