半年没写博客。这次分享一下我的两份数据可视化的作品。
  强烈建议点击看原图,比缩略图好看多了。

一、好友关系图


  这个图是看了一篇报道(Facebook实习生画出全球好友关系可视化地图,下文称“原图”)之后抓取了国内一家社交网络的数据照着做的。
  其实原理非常简单,搜集了足够多的好友关系,及用户所在的城市,在这两个城市之间连上一条边。如果两个城市之间的好友越多,线也就越亮。和原作一样,最后会根据城市之间的距离衰减,距离近的城市,线条会亮一些。
  原图在我看来非常 cool,居然直接通过好友关系描绘出了海岸线,而我的这个图里无奈只能自己描上了国境线。可视化确实是数据分析的良师益友啊,在这个图里,也可以看到一些有趣的东西。比如线条最密集的长三角、珠三角;无数城市与帝都紧密联系;还有西部城市低调地和东部城市保持了千丝万缕的联系。
  为了方便查看,我把一些重要城市的地名也标上了,可以对照着挖掘一下。

二、北京吃货地图


  绝对不是打广告,但是看着这个图基本上就可以指导你,馋了可以去哪逛逛。
  数据来自大众点评的点评数据。每一份点评在店铺的位置做一次记录,然后使用 红-橙-黄-绿-蓝 的渐变色,根据每个地方点评的数据量,染上相应的颜色。最后叠加上地图,就成了。
  吃货们的集体智慧是不会错的,看图中西单、王府井、中关村、南锣鼓巷、后海、簋街、五道口、国贸,都一片红啊。
  还有另一个版本,直接计算方圆500米里的点评数,画出来就成这样。变得很Q了……

  这两幅图都是C#编程+PS画出来的,如果有人知道简单好用的可视化工具,恳请推荐一下。

  这是一个月前的比赛了。一直 YY 着能拿到奖金,直到膝盖中了一箭:事情发生在比赛的最后一天,神一般的提交都诞生于那天,直接破灭了我保住第五的希望。最后一晚上的苦逼挣扎由于编码速度太慢,也没完成理想中质的飞跃。总而言之就是好久不编程,高估了自己的实力,最后花了不少时间没刷到奖。

  简单介绍一下比赛的题目。这次马拉松是一个压缩问题。有一个 pH 测试仪的阵列,摆成 X*Y (其实就是 900*900)的方阵。仪器运行 L(L在60左右)个时间单位,每个时刻记录一下 pH 值。也就是说,一次实验一共记录了 X*Y*L 个实验数据。现在的任务是,压缩这些值,压缩率越高越好。比较有意思的是,比赛允许有损压缩,但是复原以后的值和原值的差、以及差的平方和都有误差限制。

我的方法

  观察数据发现,pH 测试仪里面每个测试点得到的测试结果,在总体上是连续的,不会有太大的变化。于是对于每个测试点的 L 个测试结果,可以采样若干点,并用插值算法对完成复原。
  于是就形成了这样的算法框架:

原始序列: d[0] ... d[L-1]
抽样其中的某些点:d[x_0], d[x_1] ... d[x_n]
用不精确的方式存储:d[x_1]-d[x_0], d[x_2]-d[x_1] ... d[x_n]-d[x_{n-1}], 以及d[x0]。 (x_0 = 0, x_n = L-1)
最后插值产生没存储的点

  由于存储的那些数据是使用 Huffman 编码的,重复的数字越多,压缩率就越高。在比赛中,我使用的“不精确的方式存储”是使用 val/t*t 代替 val。其中 t 是参数,一般在 8 到 20 之间。使用这种方式可以将相邻的 t 个数计入一个数,使用 Huffman 编码时压缩率会有显著地提高。
  这里同时要解决两个参数的优化,抽样的点集(对于每个位置的 pH 仪器使用相同的抽样点)、t。抽样点集可以使用 DP 算法求的在有 n 个抽样点时,最佳的抽样位置在哪(见参考文献,基本类似他的思路。实际上比均匀采点好不了多少,但还是用了)。确定了抽样点之后,穷举 t,找到符合精度要求的压缩率最高的 t。
  经过这两步计算,就可以得到一大堆 <n, t> 对的集合,有着不同的误差和压缩率。从中选取出最佳的搭配即可。最后使用的 n 一般在 10 到 20 之间。

  在实践中,直接对整个数据集进行优化,复杂度较高,不能在 10 秒内完成计算。我先从 X*Y 个仪器中抽样出 1000 个样例仪器,只对这 1000*L 个数据进行压缩,求得参考的 <n, t> 对集合,并选择若干个最优的跑一遍完整的数据,选择在实际数据集上符合误差要求且压缩率最优的。

  只有这些优化还不足以让我刚刚没奖,还有两个重要优化可以提升较多。
  1. 使用多棵 Huffman 树代替一棵树。观察数据可以发现,在各时刻,不同位置的 pH 仪器获得的结果是有一个总体趋势的,可能总体上涨,或者总体下跌。这样的话,在不同的时间用不同的 Huffman 树存储,由于数据的分布更集中了,压缩率会有提升。
  2. 对于某些特殊位置的 pH 仪,使用一套特别的压缩方式。在开放的数据集中,有些数据有一些 pH 仪测试出来的结果不符合主流分布。它们的记录结果随机震荡,非常不适合插值。如图 1 中第二行第五列的黑色区域。由于这部分区域非常难插值,选用较少的抽样点(n)会造成很大的误差(即便这只是 5% 的仪器造成的误差)。这个优化就是,对于这些特殊的位置,采用大量抽样点(甚至不抽样)的方式存储,当然 t 可以选取的比较大;同时对于大部分数据,仍然采用之前描述的方法存储。

  最后就是一大堆常数优化了,模运算打表之类。

  自认为这套框架已经走到基本极限了,从最后的结果来看也是。排在前面的人都有独到之处。

zaq1xsw2tktk 的方法

  赛后,我向 zaq1xsw2tktk 大神请教了他的方法。和我前面描述的方法基本类似,zaq1xsw2tktk 大神也是采样加上 val/t*t 的方式取近似值。不同的是,他在采样时,采样点非常的多,每隔一个位置就设一个采样点。由于采样点非常密集,求差时 0 会非常多。如果误差还没有超过阈值,则会修改某些值,使得连续的 0 变得更多。
  对于生成的差值序列,zaq1xsw2tktk 大神并没有直接使用 Huffman 编码压缩,而是先作了一步预处理。对于连续的 0,只存储 0 的个数。下面是一个 zaq1xsw2tktk 大神提供的例子:

0,0,0,0,0,10,10,0,0,0,0,-10
编成两个序列(5,0,4),(10,10,-10)
5个0 , 一个10 ,0个0,一个10, 4个0,一个-10

  预处理之后,再使用 Huffman 编码压缩,会有巨大的提升。

delicato 的方法

  delicato 在这场比赛中是毫无悬念地夺冠了,比赛排行榜的前面大概是这个样子的:

名次 成绩 handel
1 4143 delicato
2 2649 zaq1xsw2tktk
3 2490 Psyho
4 2479 Celebrandil
5 2204 davies
6 2156 venco
7 2089 licstar

  冠军的方法究竟是什么呢?其实我挣扎了这么久,早应该想到……裸的 SVD。不用多解释了,SVD 就是干这个的。(细节上 delicato 也对震荡激烈的特殊位置的 pH 值做了单独处理。)

总结

  对我来说,处理这种问题很重要的一步就是“看”数据,包括一行行地看,分析其中的关联等等。
  这次我用了两种比较简单的方法可视化数据,第一个图描述了 0 时刻各位置的测试值大小,颜色越亮表示值越大。里面的每个小图表示一个待压缩的文件。
  每张第二个图是相邻两个时刻各位置的变化情况,图片里的每个小图依次描述了某个文件不同时刻的变化情况。绿色表示值变小了,红色表示值变大了。如果仔细观察,会发现里面有比较明显的区域化现象,前面几个小图中能看出一些有规律的方块。另一个规律是变化总是从右下往左上推进的。这两点在比赛中并没有用到,或许能有好的方法可以用上各种数据特征,达到更优的结果。
  最后又回到老问题,遇事总是先 YY,吃了一次又一次的亏。什么时候才会先去找已有工作呢……

图1

图2

辛卯年乙未月己巳日,大局已定。仿三国演义,记下赛事五回。

第一回 山中有寨柠檬香,邪道异术出山狂
第二回 绝世秘籍未相传,独门小式败探花
第三回 光阴有痕巧破译,大象无形气莫测
第四回 山穷水尽疑无路,九易参数又一村
第五回 强强联合遇强敌,人品爆发显王道

继续阅读

  科研间隙,突然想验证一下@郑渊洁提出的公蓝北京、风蓝北京。遂从twitter上抓取美帝使馆数据,并做了一些简单的统计分析。
  统计数据为从去年11月21日至今的共100多天的空气质量数据与风力数据。先上图。


  在PM2.5随时间变化情况图中,我将数据分为工作日和非工作日统计(考虑节假日调休)。很明显,天亮期间休息天的空气质量要明显好于工作日的,从侧面体现了“公蓝北京”。在这样的统计规律下,把户外锻炼的时间安排到周末也是非常合适的~另外有个值得注意的,晚间的空气比白天明显要差,网上能找到很多介绍,如大气对流、植物的净化作用等等。不管怎样,在数据面前,早起锻炼和晚上睡觉前跑个步,都是不合理的。

继续阅读

  晒代码发布前,我们构想了 N 种吸引人来发代码的策略。后讨论认定,如果网站发布初期就有大量的代码作为基础,之后则更有可能吸引人来晒代码。就像某百科和某社区问答建站初期那样。

  本着这个目标,我试着用最简单粗暴的方法,尽可能多地从网上抽取出 ACM 代码。由于很多 ACMer 都会在网上开博客,博客里又很可能会写解题报告,有些解题报告会附上珍贵的 AC 代码。如果能把这里的 AC 代码都抽取出来,效果肯定会很理想。

  下面就简单介绍一下整个代码抽取过程。

系统框架

系统框架

继续阅读