chinavis2018参会总结1：信息论在可视化中的应用

今年7月25日，中国可视化与可视分析大会chinavis 2018在上海举行（大会网址http://www.chinavis.org/2018/challenge.html）。暌违两年之久，我也专程前往。可能因为是在上海的缘故吧，这几日天气相当湿热，同时会议费也为历届最高。虽然如此，依然挡不住我等与会者的热情。3天的会议内容，包括特邀报告、前导课程、博士生论坛、专题、特别Panel、产学研高峰论坛及企业展览报告、360杯数据可视分析挑战赛，以及包括VIS分享之夜、可视化与可视分析专委会会议、游船晚宴在内的其他议程。会议内容如此之丰富，无法尽述，故而本人只以个人研究兴趣——“网络安全可视化”为中心，记录一些相关内容。

首先想记录的内容是7月25日下午在华东师范大学计算机学院内举办的前导课程，《Information Theory for Visualization》(信息论在可视化中的应用)。演讲者为沈汉威教授，他本人是台湾人，现就职于美国俄亥俄州大学，承接过很多NASA项目，主要研究方向是面向流体力学的科学可视化。他还有民乐方面的个人爱好，对音乐可视化很有兴趣。此次前来，除了办讲座，也有招收博士生的目的。毕竟美国那边的科研主力，还是打拼H1B的各路博士生。以下文字是我课上的拍照记录，再加上我大量的内容补充。希望各位读者看后能对信息论的应用场景有更丰富的联想。如有不对的地方欢迎大家批评指正。

信息论对我等而言并非生疏的概念。因为计算机科学与应用数学本来就是一堆孪生兄弟，都源自二战期间弹道计算和密码分析学研究。应用数学中包括三个重要理论：信息论、密码学和计算数论。信息论是关于信息的理论，而信息的传播又离不开加密，加密的主要方法目前又是通过数论、质数这方面的知识来实现。这些应用数学理论直接构成了现代计算机技术的基础，在数据可视化、数据分析领域有着重要的作用。

问题的提出：大数据可视化中常见的问题

数据精简和筛选

哪里是显著区域？应该使用什么样的分辨率呈现数据？如何找到数据最精髓的代表者?

特征提取和追踪

如何选择最好的算法参数(如流线起始点，等值面等)？

数据可视化时能揭示多少有用的信息？

可视化映射和图像分析

这是一个好的观察点吗？这是一个好的转换方法吗？衡量指标是什么？

众所周知，数据可视化的一般过程如下：

数据-->filtering(过滤或者精简)-->feature extraction(特征提取) -->visual mapping(视觉映射)-->rendering(渲染)

以上每一步处理，都会丢失一些数据。如何确定哪些数据可以丢，哪些不能丢？为了必须要有一个量化标准。

常规统计分析方法

在数据分析过程中，分析人员往往会根据数据集的特点，计算其范围分布、向量分布、特征分布等的概率密度模型，以此作为数据集最精髓的代表。计算概率密度模型有参数估计和非参数估计两大类方法。参数估计就是假定样本集符合某一概率分布，然后根据样本集拟合该分布中的参数，得到一个解析解。典型例子有似然估计、高斯分布、混合高斯等等，这些内容在大学概率论里都讲过。非参数估计则是不预先设定概率分布模型，只利用数据本身来对概率密度做拟合，得到一个近似解。典型例子有直方图，核密度估计等。

概率密度模型给出了数据分布规律，方便人们进行估值和预测，不过并没有指明“哪些数据可以丢，哪些不能丢”。显然我们希望丢掉的数据是那些重复的、意义不大的数据，而信息论给出了一个判断标准。

信息熵的概念

信息论将信息传递作为一种统计现象来考虑。信息论的核心，是信息量和信息熵（Entropy）两个概念：

设一个离散型随机变量X可以有n种取值{X1, X2, X3, ... , Xn}，每种取值的概率是{p1, p2, p3, ..., pn}。p(Xi)=pi。那么每种取值Xi发生时所产生的“信息量”被定义为：

H(Xi) = − 

而随机变量X的“信息熵”记为：

公式一多大家不容易理解。那么举个例子：在新闻X中，狗咬人发生的可能性是0.9（记为事件X1），人咬狗的可能性是0.1（记为事件X2）。那么新闻内容是X1的信息量是多少？是X2的信息量是多少？计算如下：

H(X1)=-  ≈0.152（比特）

H(X2)=-  ≈3.32（比特）

通过计算得出的结果，显然是人咬狗事件X2包含的信息量更大。也就是说，极少见的事件所带来的信息量多，这也符合我们日常生活经验。如果用统计学的术语来描述，就是出现概率小的事件信息量多。因此，事件出现得概率越小，信息量愈大。即信息量的多少是与事件发生频繁（即概率大小）成反比。信息量的概念虽然简单，不过这样我们就有了一个衡量信息价值高低的标准。

对于新闻X，它的“信息熵”为：

H(X) = -0.9*  - 0.1*  = 0.468 (比特)

信息熵的计算结果，其实就是新闻X包含信息量的数学期望。“信息熵”反映了信息本身是否难以预测。如果新闻X随机性很大，比如狗咬人和人咬狗事件发生的概率相同都是0.5，则信息熵就达到最大值1。反之，如果新闻X的随机性很小，比如狗咬人的概率是趋近100%，而人咬狗的概率趋紧0%，那么新闻X的信息熵就会无限趋近0。也可以说，信息熵越大，则每个其中事件的发生概率就越接近，越难以预测哪个事件会发生。

以上讨论的都是单一随机变量的情况。如果有两个随机变量X和Y，则还有交叉熵H(X,Y)，条件熵（也被用作计算两个变量分布之间的距离）H(X|Y)，共有信息量（即信息重叠）I(X,Y)，他们的计算公式如上图所示。它们之间的关系则可以用下图表示：

 

总而言之，。关键就在于信息重叠的部分I(X,Y)的大小。

如果X和Y是独立随机变量，那么显然I(X,Y) =0，H(X,Y)=H(X)+ H(Y)。

信息熵的应用

显然，数据集也是一种信息。只要能被计算概率密度模型，就可以使用信息论方法进行处理。因而信息论可以广泛应用于数据处理过程中，包括解决“哪些数据可以丢，哪些不能丢”的评价标准问题。下面是一些应用举例。

应用案例1：最优投影视图的选取标准

如何给定一个评价标准，确定哪个可视化图形效果最好？

对于3D模型，根据摄像机的位置不同，看到的图片结果也不同。比如一颗牙齿，根据视角不同，投影出来的2D图像也各有不同，例如上面这四个照片。那么其中哪个牙齿照片算是最优的2D视图呢？有什么可以量化的客观评价标准吗？

一个有效评价标准是计算每一个2D视图的信息熵。我们根据3D图形中每一个体素投影到2D空间上时所贡献的信息量，来计算每个2D视图的信息熵。所谓体素（voxel），三维空间中的最小立体单位，类似二维空间中的最小单位像素pixel。经此计算后，如果一个2D视图的信息熵高，那么就意味着各个体素出现的概率接近，也就是说这个2D视图能反映更多的体素。可以说这是一个较容易计算并且有一定参考价值的最优视图评选标准了。

具体的计算过程如以上两张图所示：首先计算每个体素Vi的贡献率Pi。Pi的值基于能见度V和权重W来计算。这样我们就可以根据Pi计算出每个体素Vi的信息量，最后再计算整个2D视图的平均信息熵。

可以想见，用这种方式计算出来的最优2D视图，应该是每个体素都有相同贡献率的视角，在这种情况下信息熵最大。

应用案例2：图像压缩

对大图的压缩，通常是将其分割成很多小图（chunks），每个小图依据不同的压缩率进行压缩，效果比以同种压缩率进行压缩要好。问题是，我们应以何种标准，确定哪个小图压缩率高，哪个小图压缩率低？

如同上一个问题，图像中主要负责贡献视觉效果的元素，被称为数据块（data block）。显然，有更多数据块起作用的小图，压缩率应降低，这样有助于保持数据精度。如何衡量小图中有多少数据块起作用呢？我们的依据就是小图在特定的细节等级（Level of Detail, LOD）下的信息熵。

具体而言，计算过程如上面两张图所示：首先计算每个数据块的贡献率Pi，Pi的值基于图像渲染时数据单元的贡献Ci（基于数据单元的颜色、投影面积、浓度、可见度）和形变程度Di（基于数据单元在当前和原始分辨率下的差异）来计算。根据Pi，就可以计算每个数据块的信息量，进而计算每个小图信息熵。

应用3，向量场的绘制

向量场的概率密度分布，可以通过polar histogram（径向直方图）来表示，进而可以计算向量场的熵。不过径向直方图对于人们理解向量场不够直观，更直观的方式是绘制流线图。在绘制流线时，我们需要先放置一些种子点，作为绘制流线的基础。问题是，种子点应该放多少？放到哪里比较好？

首先关于种子点放多少的问题，可以通过条件熵来决定。设原始向量场的熵为H(X). 流线图中的熵为H(Y)。那么它的条件熵H(X|Y)的值就是指，在原始向量场X中存在而在流线图Y中不存在的信息量。显然，我们希望H(X|Y)越小越好，这样流线图才更加接近真实情况。有了这个标准，我们就可以通过反复迭代的方法，不断计算H(X|Y)，以求得种子点放置数量的最佳水平。

种子点的位置，可以通过计算局部熵得到。具体的说，就是计算每个预设点位临近区域的熵，然后做比较。熵越大，说明该点位具有更多信息量，种子点放在这里，其代表意义比其他位置要大。

应用4：多元数据分析

分析高维数据集的一般方法是：固定某个数据维度X，然后观察其他维度（Y，Z ...）数值的变化，从而一步一步探索数据维度之间的关系。问题的关键在于，选择分析路径X的标准是什么？尤其是在缺乏先验知识的情况下。

信息论给出了一个通用的评判标准。比方说有两个数据维度X和Y，我们可以计算X和Y的共有信息量（即信息重叠）I(X,Y)。I(X,Y)的值越高说明X和Y关系越紧密，反之关系越淡薄。再通过条件熵H(X|Y)和H(Y |X)的比较，我们可以知道哪个数据维度具有更多的独立信息量。我们可以选择条件熵更高的数据维度作为分析路径。

回顾一下交叉熵、条件熵、共有信息量的计算公式。

在实际应用中，数据集往往会有数十个数据维度。那么怎么进行挑选呢？可以构造分层聚类树，把大量数据维度最终分为2组，选择信息熵最大的那一组。

然后再分析组内数据维度。可以先计算本组内数据维度的交叉熵，然后去掉一个数据维度，再计算一下交叉熵。如果交叉熵降低的多，说明去掉的数据维度具有更多的独立信息，这个数据维度更重要，可用作分析路径。

当一个数据维度值确定时，如何简单地预测另一个数据维度的值？我们可以固定其中一个数据维度的值，看另一个数据维度的变化范围，计算条件熵。

总结

信息论可以用来分析那些可以计算概率密度模型的数据。具体的说：