人人“机不离手”的这个时代，你能想象下一旦没了WiFi世界会怎样吗？WiFi使用越来越普遍，基于WiFi使用相关的数据研究也多了起来。
来自美国麻省理工学院（MIT）的大一学生Moin Nadeem和他的3位同学，就获得了MIT校园内的357万条手机WiFi“连接请求”数据，并在此基础上展开了一个敏感的“试验”：如何追踪乃至预测大学生们的出行轨迹~
▍开启一个关于WiFi连接的数据研究
在大一的春季学期，我有幸选了“嵌入式系统互联”这门课（MIT的课程代码是6.S08），主要学习密码学、算法设计等电气工程与计算机科学方面的基础理论。
这是一门十分耗时且非常有挑战性的一门课，但也是我参加的课程中为数不多的颇有收获的课。在课上，我很高兴结识了非常有才华的一些同学（他们是Avery Lamp、Daniel Gonzalez和Ethan Weber）。
在准备期末论文时，我们小组的几个人都非常希望能做一些比较新奇的课题。
有天我们一起出去买冰淇淋，Avery提议做一个能够监控WiFi“连接请求”（probe requests）的设备，就像很多大商场做的那样。
在做了充分准备后，我们说服了导师同意这个课题。
这项研究是我大一生涯最激动人心的亮点之一，在追寻这个项目中学到了很多东西，从时间序列数据聚类到在校园里部署追踪“连接请求”数据的设备。在我们团队的这次神奇经历中，我得到的太多太多。
▍WiFi的“连接请求”指的是什么
在大部分人眼中，手机是作为接收器存在的，用来连接WiFi网络等等，只有在联网后，这部手机的诸多功能才能得到发挥。
当需要连接公共网络时，手机会向外发出一些特有的信息，这就是“连接请求”。
手机在发出“连接请求”时，会发送一些诸如MAC地址（就好比是采集指纹）、RSSI信号（提示信号的强度）、你之前连接过的无线网络的SSID（WiFi名称）列表等。
因为每部手机都会发出一个自己的MAC地址（当然这得排除掉有些匿名访问的情况），所以我们可以利用这些数据来追踪学生们在校园里的行走轨迹。
▍怎样收集“连接请求”数据
为了这个课题，我们打算用到在这学期中接触的一些器材：一台Teensy单片机、一个ESP8266芯片以及一个GPS模块（集成了RF射频芯片、基带芯片和核心CPU，并加上相关外围电路而组成的一个集成电路）。
不过，鉴于ESP8266芯片耗电很少（120毫安），我们也不需要搞那么强大的CPU，最终我们还是放弃了Teensy单片机。
接着，我们转而使用Arduino（一款便捷灵活、方便上手的开源电子原型平台，包含硬件和软件）。
尽管我们不得不去重新学习特殊的编程方法，但机器为我们提供了非常友好的操作方法，固件也内置了丰富的AT指令。
（图片说明：芯片组装以及发送“连接请求”的页面）
在接下来的一些天，我们开始用这台设备对校园里的“连接请求”进行了一些初步的测试，结果还算令人满意。
▍编写一个验证程序
现在我们已经知道了怎样收集这些“连接请求”数据，为了收集到全部这些数据，接下来我们小组又花了一些天，编写了基础的系统架构。
我负责开发了一个基于“Flask MySQL”的后台，从而可以控制整个设备的运行；Avery负责开发一个iOS应用，让我们更轻松地部署设备；Daniel给我们的项目设计了一个漂亮的前端网页；Ethan则负责创建数据分析平台，让收集到的相对抽象的数据更加直观易懂。
（图片说明：管理页面的截图）
在硬件方面，Daniel和Ethan在原型板上焊接了ESP8266芯片和电池。我们使用的电池是班上同学提供给我们的二手电池（型号是PowerBoost1000C)，这种电池非常轻便，这就让我们即便在非常狭窄的地方也不会因为电池体积过大而影响数据收集。
（图片说明：完成设备的焊接，并将它们固定在了小盒子里）
在这期间，我很高兴我们的团队相处地非常融洽，一起开玩笑，一起学习，一起工作，在这样的氛围下就算工作到凌晨4点也不会感到累。
▍设备部署
Ethan写得一手漂亮的代码，从而让我们的设备能够自动连接上离设备最近的不安全的WiFi热点；Avery则写了一个App来更新“目标的位置 目标最后一次活动的位置”（每个位置其实都基于MAC地址来获得）。
（关于设备在校园里的部署，看了这个视频你就懂了~）
设备部署起来很容易，你需要确保设备之间的网络是能够ping通的。一番操作下来，让人越发觉得这过程其实还挺有趣并富有创意的。
▍数据采集
在项目部署实施一周后，我们大约收集了350万个“连接请求”。
我需要声明的是，这些数据都经过了匿名化处理，另外这些数据的精确度还不足以让我们通过MAC地址来追踪个人的准确位置，这样也减少了我们的指导老师对隐私问题的担忧。
有了数据后，我们开始用Ethan提供的数据分析平台来分析校园内不同地点采集到的数据，结果惊讶地发现每个地点的网络使用都存在着周期性变化。
（图片说明：Lobby10、Lobby26-100、Stata、Lobby7四个地点的网络流量使用图）
分析结果能够很明显地反映出我们校园里的一些网络使用规律：
每天下午5点左右，校园的主要场所（Lobby10，26-100）的网络流量达到了峰值，而校园角落的一些建筑物（比如有一个咖啡馆的Stata），网络的使用峰值出现在了中午。
毫无疑问，因为有了我们的设备的部署和采集，数据开始变得很有趣。
而当我们发现这些规律之后，就不再只满足于这些现成的结论，我们希望能通过这些数据发现一些更有趣的东西。比如：
通过在MIT的不同地点的设备部署和数据采集，我们得到了什么结论？
如果用基于WiFi连接的数据来给我们的校园画一个“网络图”，会是怎样的？
校园里哪一条路走的人最多？
更有趣的一点是，我们是不是可以通过一个人之前走过的轨迹来预测他下一步要去哪？
▍数据集分析
MAC地址实际上提供了6个字节的信息，这个信息量其实已经够大了，我们可以利用这些信息来了解那些步行经过我们周围的人，比如，我们可以发现在MIT校园里面，哪些电子设备最流行。
但这样做其实也有难度，因为NSA(美国国家安全局）最近就曾使用这种技术来追踪个人，为了保护用户的隐私，很多设备制造厂商开始试图让设备匿名发送“连接请求”。
其结果就是，我们无法精确知道所有的设备的分布情况，不过我们可以大致调查出，匿名设备所在的更大一点的范围。
很讽刺的是，很多匿名发送“连接请求”的设备，实际上恰恰暴露了他们想干什么——在那些匿名的设备上，MAC地址中的“Locally addressed”（第二低的有效位）一般是被设定为1。
因此，我们简单地使用SQL数据库的查询功能，就发现了在我们附近大概有25%的设备使用了匿名的MAC地址（我们总共收集到了357万48条“连接请求”数据，其中匿名的数据有89万1131条。）
通过MAC地址前三个字节的信息，我们可以看出电子设备使用排名的前8位中，前两个都是匿名的：
Locally addressed “02:18:6a”, 162,589 occurrences
Locally addressed “ da:a1:19”, 145,707 occurrences
74:da:ea from Texas Instruments, 116,133 occurrences
68:c4:4d from Motorola Mobility, 66,829 occurrences
fc:f1:36 from Samsung, 66,573 occurrences
64:bc:0c from LG, 63,200 occurrences
ac:37:43 from HTC, 60,420 occurrences
ac:bc:32 from Apple, 55,643 occurrences
有趣的是，我们发现，其实苹果手机就是被使用最多的匿名设备。
尽管是匿名的，我们还是从中找到了“漏洞”：因为这些苹果手机每隔一段时间，就会发送一次详细的地址。
对于像我们这种几乎每一秒都在追踪“连接请求”信息发送的人来说，能接收到这样详细的地址，不得不承认，这对于设备的使用者而言并不是好事。
我们对身边使用iPhone的朋友进行了测试，发现我们竟然可以非常精准地知道他们的位置和行走路径。
▍数据集的“缺陷”
在将学生们行走的轨迹可视化为网络图之后，我们发现可以通过计算前一个节点到另一个节点的概率来预测下一步他们要去哪，这好像与马尔可夫链有点像。
马尔可夫链（Markov Chain）是指数学中具有马尔可夫性质的离散事件随机过程。在这个过程中，在给定当前知识或信息的情况下，过去发生的事情，对于预测未来是无关的。
（图片说明：行人的移动轨迹网络图，图中黑线的箭头代表移动的方向。）
（图片说明：采集到MAC地址的状况，为了保护隐私，我们进行了打码处理。）
但是，如果真要去作预测的话又会出现另一个问题：
我们的数据集没有办法自动辨别节点和时间戳（timestamps），我们一开始收集到的数据不能看出一次行走什么时间开始、何时结束。
我们必须手动去检查这些数据，这样做之后可以清楚地看到，当一些人开始行走的同时，另一些人却停下了脚步，时间分布上是非常分散的。
这些都可以从前面的图表中看出。
比如，这个人显然没有从State走到Whitaker，因为这些数据根本不在同一天。然而，我们的数据库却看不出这一点，因此，后续对这些数据的使用如果不加检查，就会产生有缺陷的结果。
不过当我们把这些数据按照时间序列来重新排列，这就有点意思了。
我们可以设想，如果有办法将这些时间戳作聚类，我们是不是能够识别一个学生的各种“行走”姿势呢？
▍给数据集加上时间戳
为了更好地去了解如何来给数据做聚类，我需要更好地了解时间戳。我开始将时间戳绘制到柱状图上，以更好地了解数据的分布。
令人高兴的是，这个简单的步骤帮了我一个大忙：事实证明，各种设备发出“连接请求”的频率，大致上按照离ESP8266芯片的距离远近呈现出高斯分布（Gaussian distribution）。
于是，我开始使用高斯混合模型（Gaussian Micture Model），更简单来说，我们可以基于这样一个分布的事实得出结论：各种时间戳都遵循着这样的分布规律。
（图片说明：举例来说，图中的绿线显示，这个模型有十个优化过的数据聚类。）
接下来的问题是高斯混合模型需要被告知要使用多少个数据集，它不会自动识别。这是一个非常难的问题，特别是考虑到每个人的行走情况是非常易变的。
令人高兴的是，我能够利用贝叶斯信息准则（Bayes Information Criterion），对复杂性进行定量评分。
贝叶斯信息准则在一开始运行地相当顺利，但在分析那些行走次数非常多的人时，却出了问题。
为此，我将其与“剪影评分”（Silhouette Scoring）进行了比较，该评分通过将内部数据集的距离与距离最近的数据集的距离来进行对比，从而得出分值。
令人惊讶的是，这提供了一种更合理的时间序列数据聚类的方法，避免了贝叶斯信息准则遇到的许多陷阱。
我扩大了我在DigitalOean主机（一家成立于2012年的总部设置在纽约的云主机商家）上的虚拟服务器的容量，让它运行了一些天。
我甚至还开发了一个快速的Facebook机器人，一旦数据处理完成，就自动来通知我。有了这个工具，我可以暂时脱身，继续去解决如何的问题。
（图片说明：“剪影评分”的相关结果）
▍预测大家下一步要去哪
现在我们已将大量的“连接请求”数据分解成了一次次单独的“行走”，我们可以进一步发展马尔科夫链，这允许我们基于前一个事件的状态预测下一个状态。
我使用一个叫Markovvify的Python库生成了一个马尔可夫模型，并且加入了我们在上一步中获得的数据，从而大大缩短了开发时间。
（图片说明：经过马尔科夫链分析后，数据已经归类成一次次行走，上面是某个人在校园里的活动轨迹。）
到这里，我已经获得了上面生成的马尔可夫链样本；并且可以发现，上图的数据实际上代表了一个学生离开讲座（26-100是一个演讲厅），并去了他的宿舍！
一台电脑能够采集到这些数据，并且将其识别为一次“行走”的过程。
这真的很让人兴奋。
有一些地点反复出现，这是因为每个位置都被记录下来。并且，如果某个地点比其他地点出现地更多，这意味着这个人在那里度过了更多的时间。
尽管这项研究还挺初级的，但却让我们感到兴奋。
如果我们利用这项技术创造更智慧的城市，城市是不是就能没有拥堵，出行的平均时间也能减少呢？这项研究带来的数据科学方面的可能性是无止境的，我会带着极大的热忱继续去追寻。
注：本文编译自freecodecamp.org网站文章：《How we tracked and analyzed over 200,000 people’s footsteps at MIT》，作者Moin Nadeem。
作者 | Moin Nadeem
编译 | 肖鉴容 胡世龙
▍数据侠门派
本文数据侠Moin Nadeem、Avery Lamp、Daniel Gonzalez和Ethan Weber，四人均为麻省理工学院本科生。
