TLDR
本文包含我对论文"SineStream: Improving the Readability of Streamgraphs by Minimizing Sine Illusion Effects"（SineStream：通过最小化正弦错觉效应提高流图可读性）的笔记。我将讨论问题陈述、评估标准、作者的方法以及案例研究。
下载 PDF
.
流图（Stream graph），有时写作 streamgraph，是围绕"中心轴"的堆叠图，形成流动的有机形状。流图展示了主题是如何演变的。
问题陈述：
给定一个时间序列 f 1 , f 2 , . . . f n {f_1,f_2,...f_n} f 1 , f 2 , ... f n g 0 g_0 g 0 f i f_i f i
g i = g 0 + ∑ j = 1 i f j g_i=g_0+\sum_{j=1}^if_j g i = g 0 + j = 1 ∑ i f j 关于如何计算 g 0 g_0 g 0
简单模型：g 0 ≡ 0 g_0\ \equiv\ 0 g 0 ≡ 0
围绕 x 轴对称：g 0 = − 1 2 ∑ i = 1 n f i g_0\ =\ -\frac{1}{2}\sum_{i=1}^nf_i g 0 = − 2 1 ∑ i = 1 n f i
备注：
f i = f i ( t 0 ) , f i ( t 1 ) , . . . f i ( t n ) f_i\ =\ {f_i(t_0),f_i(t_1),...f_i(t_n)} f i = f i ( t 0 ) , f i ( t 1 ) , ... f i ( t n ) ，因此 g i = g i ( t 0 ) , g i ( t 1 ) , . . . g i ( t n ) g_i\ =\ {g_i(t_0),g_i(t_1),...g_i(t_n)} g i = g i ( t 0 ) , g i ( t 1 ) , ... g i ( t n )
如何计算基准线
参考文献：Stacked Graphs - Geometry and Aesthetic, L. Byron, M. Wattenberg
简单模型：g 0 ≡ 0 g_0\ \equiv\ 0 g 0 ≡ 0
解决方案 1：最小化轮廓（与对称模型相同）f ( g 0 ) = g 0 2 + g n 2 = g 0 2 + ( g 0 + ∑ i = 1 n f i ) f(g_0)\ =\ g_0^2 + g_n^2\ =\ g_0^2+(g_0+\sum_{i=1}^nf_i) f ( g 0 ) = g 0 2 + g n 2 = g 0 2 + ( g 0 + ∑ i = 1 n f i )
d f d g 0 = 0 ⟹ g 0 = − 1 2 ∑ i = 1 n f i \frac{df}{dg_0} = 0\ \Longrightarrow\ g_0=-\frac{1}{2}\sum_{i=1}^nf_i d g 0 df = 0 ⟹ g 0 = − 2 1 ∑ i = 1 n f i
解决方案 2：最小化 g i g_i g i f ( g 0 ) = ∑ i = 0 n g i 2 f(g_0)=\sum_{i=0}^ng_i^2 f ( g 0 ) = ∑ i = 0 n g i 2
d f d g 0 = 0 ⟹ g 0 = − 1 n + 1 ∑ i = 1 n ( n − i + 1 ) f i \frac{df}{dg_0} = 0\ \Longrightarrow\ g_0=-\frac{1}{n+1}\sum_{i=1}^n(n-i+1)f_i d g 0 df = 0 ⟹ g 0 = − n + 1 1 ∑ i = 1 n ( n − i + 1 ) f i
正弦错觉效应
(a) 沿着正弦曲线绘制了一条均匀厚度的线。我们的感知导致我们使用正交距离而不是垂直距离来确定其厚度。(b) 流图中带有虚线边框的绿色层看起来具有恒定的厚度。然而，在其垂直厚度中出现了一个峰值 (c) 。
方法：
由于流图的几何形状由其基准线（最底部的曲线）和层的排序控制。对于基准线计算 ，通过引入高斯权重来惩罚具有大厚度变化的层，从而改进之前的方法。对于层排序 ，提出了三个设计要求，并通过层次聚类算法实现。
基准线计算
评估标准
Wiggle 度量
Byron 和 Wattenberg：
W i g g l e = ∑ i = 1 n ( 1 2 ( g i ′ + g i − 1 ′ ) ) 2 ∗ w i Wiggle=\sum_{i=1}^n(\frac{1}{2}(g_i'+g_{i-1}'))^2*w_i Wi gg l e = i = 1 ∑ n ( 2 1 ( g i ′ + g i − 1 ′ ) ) 2 ∗ w i
Bartolomeo 和 Hu：
W i g g l e n 1 = ∑ i = 1 n ∣ g i ′ ∣ + ∣ g i − 1 ′ ∣ 2 ∗ w i Wiggle_{n1}=\sum_{i=1}^n\frac{|g_i'|+|g_{i-1}'|}{2}*w_i Wi gg l e n 1 = i = 1 ∑ n 2 ∣ g i ′ ∣ + ∣ g i − 1 ′ ∣ ∗ w i
然而，尽管它被广泛使用，但使用 wiggle 度量来优化流图布局主要基于经验观察，缺乏明确的感知基础。这就是为什么作者想在这一点上引入正弦错觉的原因。
I l l u s t i o n = W i g g l e = ∑ i = 1 n ( 1 2 ( g i ′ + g i − 1 ′ ) ) 2 ∗ w i = ∑ i = 1 n ( g 0 ′ + 1 2 f i ′ + ∑ j = 1 i − 1 f j ′ ) 2 ∗ w i Illustion = Wiggle = \sum_{i=1}^n(\frac{1}{2}(g_i'+g_{i-1}'))^2*w_i = \sum_{i=1}^n(g_0'+\frac{1}{2}f_i'+\sum_{j=1}^{i-1}f_j')^2*w_i I ll u s t i o n = Wi gg l e = i = 1 ∑ n ( 2 1 ( g i ′ + g i − 1 ′ ) ) 2 ∗ w i = i = 1 ∑ n ( g 0 ′ + 2 1 f i ′ + j = 1 ∑ i − 1 f j ′ ) 2 ∗ w i 作者的方法
g 0 ′ = − 1 ∑ i = 1 n W i ∑ i = 0 n 1 2 ( ∑ j = 1 i f j ′ + ∑ j = 1 i − 1 f j ′ ) w i = − ∑ i = 1 n w i ( f 1 ′ + ∑ j = 1 i − 1 ( f j ′ + f j + 1 ′ ) ) 2 ∑ i = 1 n w i g_0' = -\frac{1}{\sum_{i=1}^nW_i}\sum_{i=0}^n\frac{1}{2}(\sum_{j=1}^if_j'+\sum_{j=1}^{i-1}f_j')w_i = -\frac{\sum_{i=1}^nw_i(f_1'+\sum_{j=1}^{i-1}(f_j'+f_{j+1}'))}{2\sum_{i=1}^nw_i} g 0 ′ = − ∑ i = 1 n W i 1 i = 0 ∑ n 2 1 ( j = 1 ∑ i f j ′ + j = 1 ∑ i − 1 f j ′ ) w i = − 2 ∑ i = 1 n w i ∑ i = 1 n w i ( f 1 ′ + ∑ j = 1 i − 1 ( f j ′ + f j + 1 ′ )) 作者修改了原始权重 w i = f i，采用高斯权重来减少当层厚度发生较大变化时该层的影响：
w i = e x p ( − f i ′ 2 2 c 2 ) ∗ f i w_i=exp(-\frac{f_i'^2}{2c^2})*f_i w i = e x p ( − 2 c 2 f i ′2 ) ∗ f i 其中 c 可以是 ∣ f 1 ′ ∣ , ∣ f 2 ′ ∣ , . . . , ∣ f n ′ ∣ |f_1'|,|f_2'|,...,|f_n'| ∣ f 1 ′ ∣ , ∣ f 2 ′ ∣ , ... , ∣ f n ′ ∣
层排序算法
传统计算
作者的方法
作者定义了补偿度 c o m p ( i , j ) comp(i,j) co m p ( i , j ) f i , f j f_i,f_j f i , f j
c o m p ( i , j ) = 1 L ∑ t = 0 T ∣ f i ′ ( t ) + f j ′ ( t ) ∣ ∣ f i ′ ( t ) ∣ + ∣ f j ′ ( t ) ∣ comp(i,j) = \frac{1}{L}\sum_{t=0}^T\frac{|f_i'(t)+f_j'(t)|}{|f_i'(t)|+|f_j'(t)|} co m p ( i , j ) = L 1 t = 0 ∑ T ∣ f i ′ ( t ) ∣ + ∣ f j ′ ( t ) ∣ ∣ f i ′ ( t ) + f j ′ ( t ) ∣ 其中 L 表示组合层的长度。作者定义当 ∣ f i ′ ( t ) ∣ + ∣ f j ′ ( t ) ∣ = 0 |f_i'(t)|+|f_j'(t)| = 0 ∣ f i ′ ( t ) ∣ + ∣ f j ′ ( t ) ∣ = 0 ∣ f i ′ ( t ) + f j ′ ( t ) ∣ ∣ f i ′ ( t ) ∣ + ∣ f j ′ ( t ) ∣ = 0 \frac{|f_i'(t)+f_j'(t)|}{|f_i'(t)|+|f_j'(t)|} = 0 ∣ f i ′ ( t ) ∣ + ∣ f j ′ ( t ) ∣ ∣ f i ′ ( t ) + f j ′ ( t ) ∣ = 0
作者引入了厚度权重来描述我们对相对较薄层补偿的偏好：
w t h ( i , j ) = m a x { f i ( t ) + f j ( t ) : t ∈ [ 1 , m ] } w_{th}(i,j) = max\{f_i(t)+f_j(t):t\in[1,m]\} w t h ( i , j ) = ma x { f i ( t ) + f j ( t ) : t ∈ [ 1 , m ]} 其中 f i ( t ) f_i(t) f i ( t ) f i f_i f i t t t m m m
作者使用长度权重来描述我们对相对较长层补偿的偏好：
w l e n ( i , j ) = m a x ( m L i , m L j ) w_{len}(i,j)=max(\frac{m}{L_i},\frac{m}{L_j}) w l e n ( i , j ) = ma x ( L i m , L j m ) 其中 L i L_i L i f i f_i f i
d i s t ( i , j ) = c o m p ( i , j ) ∗ w l e n ( i , j ) ∗ w t h ( i , j ) dist(i,j)=comp(i,j)*w_{len}(i,j)*w_{th}(i,j) d i s t ( i , j ) = co m p ( i , j ) ∗ w l e n ( i , j ) ∗ w t h ( i , j ) d i s t ( i , j ) dist(i, j) d i s t ( i , j ) f i f_i f i f j f_j f j
在每个时间步骤（蓝色圆圈中的编号），具有最短距离的两层 f i f_i f i f j f_j f j f k = f i + f j f_k={f_i+f_j} f k = f i + f j f k f_k f k
为了保证最小化正弦错觉的排序，作者通过最小化相邻层之间的距离总和来创建最终顺序：
a r g m i n ∑ i = 1 n − 1 d i s t ( i , i + 1 ) arg\ min\sum_{i=1}^{n-1}dist(i,i+1) a r g min i = 1 ∑ n − 1 d i s t ( i , i + 1 ) 其中第 i i i i + 1 i+1 i + 1
