论文笔记-TagPies: Comparative Visualization of Textual Data

Jänicke S, Blumenstein J, Rücker M, et al. TagPies: Comparative Visualization of Textual Data[C]//VISIGRAPP (3: IVAPP). 2018: 40-51.

TagPie 是一种标签云布局，它以饼图的方式排列属于多个数据类别的标签。出于古典语言学研究的动机，TagPies 旨在支持古典术语的比较分析。在这种情况下，数据类别表示不同搜索关键字的共现词，因此使用 TagPies 可以比较使用这些关键字的上下文。

Introduction

传统上，人文学者阅读纸质文献是为了产生和验证一些研究问题的假设。如今学者们可以访问包含大量文本的大型数字图书馆，通过查询数字图书馆来接收包含特定关键字的文本段落的能力可以加快假设的生成。但是通常情况下，大量的结果很难处理，因为文本段落需要逐个检查。

TagPie 能够呈现每个搜索关键词及其共现词，每个搜索关键词及其共现词作为一个数据类别，TagPie 能够呈现标签与各个数据类别的相关性和这些标签之间的关联关系，也能够分析标签出现的上下文或语境。

需求分析：

1. 支持单个关键词的上下文分析，和多个关键词上下文的比较。
2. 传达标签与它共现关键词的相关性，以及它与所有关键词的相关性。
3. 反映不同数据类别标签的比例。

TagPies Layout

首先介绍一些概念定义：

$T^1,…,T^n$ 是 n 个待搜索的关键词，使用这些关键词进行搜索、处理后得到 n 个数据分类（搜索结果） $d^1,…,d^n$，每个数据类别对应一个关键词的搜索结果，数据类别 $d^i$ 表示关键词 $T^i$ 的共现词。

对于每一个数据类别 $d^i$，都需要放置搜索关键词 $T^i$ 和 $T^i$ 的共现词的位置。$T^i$ 的共现词表示为：

$$t^i_1,...,t^i_{|d^i|} (d^i=\{t^i_k|1 \le k \le |d{^i}|\})$$

$F(T^i)$ 表示标签 $T^i$ 的共现词的数量，$F(t^i_k)$ 表示标签 $t^i_k$ 与标签 $T^i$ 共现的次数，标签 $t{^i_k}$ 与数据类别 $i$ 的相关性大小定义为：

$$R(t^i_k) = \frac {F(t^i_k)} {F(T^i)}$$

所有标签可以分为两类：共享标签和唯一标签。共享标签是在多个数据类别中都存在的标签，它在 TagPie 中有多个实例，也就是可以重复出现。某个共享标签 $t^i_s$ 的所有实例被定义为：

$$I(t^i_s) = \{t^i_s\} \cup \{t^j_s|1 \le j \le n, i \neq j, t^i_s=t^j_s\}$$

$|I(t^i_s)|$ 表示实例的数量。

唯一标签在 TagPie 中只出现一次，因此对于数据类别 $i$ 中的唯一标签 $t^i_u$， $I(t^i_u) = {t^i_u}$ 并且 $|I(t^i_u)| = 1$。

Layout Algorithm

布局的基本思想：将共享标签放在布局中心，将唯一标签放在布局外部区域。

首先，根据数据类别的相似性将所有数据类别进行排序。数据类别 $d^i$ 和 $d^j$ 的相似性 $s(d^i, d^j)$ 被定义为：

$$s(d^i, d^j) = \frac {|d^i \cap d^j|} {|d^i \cup d^j|}$$

然后采用如下排序方法：将最相似的两个数据类别放入一个双端队列中，然后迭代地确定与队列中的队头元素或队尾元素相似性最高的数据类别，插入队头或队尾。

标签字体大小由标签频率映射，为所有的标签添加边界框，估计在空间中放置每个数据类别的所有标签所需的空间大小。根据各数据类别的比例，确定了每个数据类别在圆中对应扇区所占的角度，数据类别 $d^1,…,d^n$ 对应的角度分别为 $\phi^1,…,\phi^n$，如图 Figure 1 所示。

主标签位置放置
主标签（搜索关键词） $T^1,…,T^n$ 的位置，放置在圆内每个扇区的中心位置。首先，需要估算出圆的半径 $r$，可以计算一个没有包含标签扇区的 Wordle 词云，将该词云的半径作为 TagPie 的期望半径 $r$，然后将每个数据类别 $d^i$ 的主标签 $T^i$ 放在 TagPie 对应扇区的中心 $p(T^i) = (x^i, y^i)$，如 Figure 1 所示，由 $s$ 位置开始顺时针旋转，$p(T^i)$ 的坐标定义为：

$$x^i = \gamma \cdot r \cdot cos(\pi + \sum_{k=0}^{i-1}\phi^k + \frac{\phi^i}{2})$$ $$y^i = \gamma \cdot r \cdot sin(\pi + \sum_{k=0}^{i-1}\phi^k + \frac{\phi^i}{2})$$

设置 $\gamma=0.5$，将主标签放置在扇区的中心。当几个小扇区相邻时，相应的主标签可能会被遮挡。为了避免这些遮挡,在这种情况下可以减少或增加 $\gamma$。

标签排序
排序方法的思想是将与所有数据类别高度相关的标签（共享标签）放在 TagPie 的中心，将只与某一类别相关的标签（唯一标签）放置在TagPie 扇区的外部区域。要获得这种排序，需要先获得一个按如下排序规则的标签列表，对于标签列表 ${…,X,Y,…}$ 中任意两个相邻的标签 $X$ 和 $Y$，需要满足以下条件之一：

C1: $|I(X)| > |I(Y)|$，表示共享标记移到列表开头，唯一标记移到列表末尾，标签实例数大的排在前面；

C2：$|I(X)| = |I(Y)|$, and $U(X) < U(Y)$

$$U(X) = \frac{max(R(X_1))}{max(R(X_2))}, (X_1 \in I(X), X_2 \in I(X), X_2 \neq X_1).$$

$U(X)$ 表示标签 $X$ 的唯一性，由所有数据类别中标签 $X$ 出现频率最高的两个总数的商定义。标签 $X$ 与某一数据类别的相关性远比其它数据类别大，得到的 $U(X)$ 就越大。条件 C2 表示标签实例数量相同时，唯一性大标签的排在列表后面；

C3：$|I(X)| = |I(Y)|$, $U(X) = U(Y)$ and $ F(X) \ge F(Y)$，表示标签实例数量和唯一性相同时，出现次数更少的标签排在列表后面。

最后一步是根据 TagPie 中数据类别的比例对标记进行轻微的重新排序。由于标签数量较小的数据类别中唯一标签的出现次数通常低于标签数量较大的数据类别，因此根据上述条件进行排序后，将标签数量较小的数据类别中的唯一标签移到标签列表的后面。

在完成最后的标签排序之后，迭代地沿着阿基米德螺旋线定位标签位置，螺旋线是从标签云中心开始。如果螺旋线上确定的位置位于分配给相应数据类别的扇区中，并且标签没有遮挡其它标签，则放置标签；否则，标签被放置在离中心较远的后续螺旋线上。

Design

1. 不对标签进行旋转，以提高可读性。
2. 给不同类别的标签分配不同的颜色。为了区别共享标签和唯一标签，给共享标签分配黑色，给唯一标签分配与数据类别相同的颜色。
3. 给不同类别的标签添加不同的背景色，需要计算出背景形状的边界，步骤如下：根据所有标签边界框中心点的位置，计算 Delaunay triangulation(德劳内三角剖分)。(1) 三角形三个点对应的标签属于同一类别时不需要计算背景形状的边界，因为它们在相同的扇区内。(2) 当三角形有两个点对应的标签属于同一数据类别时，在标签边界框之间插入一条线段，见 Figure(a)。 (3) Delaunay triangulation 的最外沿，将所有标签边界框外边的顶点连接起来，见 Figure 2(b)。(3) 三角形的三个点对应的标签都属于不同的数据类别时，生成三条线段，每条线段都起源于三角形质心，见 Figure 2(c)。(4) 最后，用 Bezier Spline（贝兹曲线）绘制数据类别的边界。

可视化结果