前两周在北大上
可视化的暑期班，有幸和五湖四海的朋友们一起聆听Kwan-Liu Ma、Han-Wei Shen、Alex Pang、Michelle Zhou、Hua-min Qu、Jean-Daniel Fekete、Jian Huang、田捷等老师的教诲，这些老师、研究人员在各自的领域内都非常优秀，部分还是界内大牛，更可敬的是他们都对学生很有感情、很有耐心——标准的德艺双馨。
整个暑期班的学习中，课程包含流体可视化、张量可视化、医学影像、信息可视化、时变可视化、智能可视化、并行可视化等很多方面，其中我最感兴趣的是：Jean-Daniel的
Visualizing Social Networks using Hybrid Matrix/Node-Link Representations，因为和我之前的工作颇有渊源。
Jean-Daniel在做social network的时候，用到了类似相关矩阵可视化的东西，就是将两两之间的关系数字化，得到一个相似度矩阵，然后可视化这个矩阵。social network的传统做法是画个网络图，用节点和连线来表示，但这样很容易使整个图变得乱七八糟，什么也看不清。可视化相似度矩阵的方法则不存在这个问题，当然也会带来新的麻烦。
对于相似度矩阵的可视化，主要存在两个问题：
1. 如何用颜色、图形、线条表示这个矩阵，；
2. 如何对矩阵对应的变量进行重排序，使得相似的变量聚在一起，不相似的分开，这样我们可以通过可视化的图形直观地发掘变量之间内在的关系。
其中，第一点已经很成熟了，就是用方块、圆，再辅之以渐变色等，corrplot包的初期也就是做这些工作；而第二点，即如何重现排序变量，这会涉及到统计、数学知识，也是本问题的精髓之所在。之前，我仅知道用PCA、聚类等方法重排变量，也在corrplot包中实现了。而现在，我发现重排变量是个不小的问题，因为它本身非常重要，而PCA、聚类方法有时在效果或者速度上并不占优势，这就需要我们探索其他方法。Jean-Daniel在课堂上介绍了两个， Robinsonian和TSP。Robinsonian是个很数学的东西，我暂时还没有翻看论文，但是TSP（Travelling salesman problem）大家都再熟悉不过了，把这个东西灵活地用在变量排序中，的确是别出心裁，匪夷所思！！相似度、相关系数等本身都是距离，而TSP问题恰恰求最短路的。
TSP是个NP问题，但很幸运的是，我们目前已经有很多算法可以快速得到不错的解，R中有相关的包（TSP），包含了常见算法并提供了concorde软件（解TSP问题的优秀开源软件）的接口。这样一来，写个用TSP排列变量函数就方便很多了。
当然，除了TSP问题的求解难度问题之外，它在变量排序中还存在一个问题，就是TSP问题求出的最短路是个环线，所以在重排序的变量中，第一个和最后一个可能很相似，但在图中，它们一个最上、一个最下，离得最远。这个问题可以这么解决：
1.
不在一张图上吊死。用至少两张图，第二张图的变量顺序是第一个图的水平移动，比如第一个图中（A, B, C, D, E)，而第二个图则是（D, E, A, B, C），这样第二个图中E和A就在一起了。当然，我们也可以通过观察图形，得到一个最容易接受的排序。这虽然是个解决方法，但是人总是贪婪而又懒惰的，一张图能看清楚的，绝不会看两张图，因此还需要探索一张图的方法。
2.
不在一个算法上吊死。既然TSP可以，那么图论中经典的Dijkstra 、Floyd算法也很可能适用，虽然这两个算法不是穷尽各个节点的，而是求各个节点之间的最小路程。
比如，我们可以通过这两个算法辅助TSP算法确定起点和终点：我们可以求出网络中任意两点间的距离，然后找出最大距离所对应的两个节点。然后，将距离矩阵中这两个节点所对应的距离修改为0，这样得到的结果中这两个节点肯定挨在一起，这相当于将TSP环路算法转换为非环路算法。然后，将这两个节点分别设置为头尾，就可以得到一个粗糙的结果了。我在R中试了试，基于经典的mtcars数据，将得到的图展示出来：
从上图可以看到，两种排序方法还是比较相似的，并且效果都不错。
这样确定起点终点的好处是，起点和终点对应线路是所有两两路程中最长的，这样再用非环线的TSP算法就不容易使排序失去意义。当然，这种方法还是很粗糙，比如计算量过大。实际中，我们可以通过别的方法更快地确定起始点和终点。
3. 不在一种介质上吊死。常见的纸、屏幕是平面的，如果我们有圆柱形式的立体介质，那么TSP得到的变量重排序就很有舞台了。将图绘制在圆柱上，首尾相接，看的时候转动圆柱即可。这个方法听起来的确有些扯，但是我觉得这种介质的出现不是没有可能（实际上，一些路边的广告就是这样的），当然这种方法的局限性也很大。
等手头的杂事忙完的话，corrplot包也会逐步更新，添加一些变量排序的新方法。可视化不是简单的画图，背后的算法、模型非常重要。
注：
1. 已经有很多文献讨论了矩阵的重排序，不过我都没看，先自己折腾一番。
2. 本文之前写得不太明了，因此重新修改了，2009-08-27，19:16。
