从拓扑数据分析到压缩感知——复杂数据处理新贵

导语

科学数据集将变得更加动态而复杂，未来的数据处理，亟待发明能与微积分相提并论的革命式数学新技术，而几何学或许可以为此提供思路。

编译：集智俱乐部翻译组

来源：quantamagazine

原题：The mathematical shape of things to come

复杂“大数据”难题

圣塔菲研究所应用数学和复杂系统研究员 Simon DeDeo 遇到了一个问题。

他在合作研究一个新项目，分析来自伦敦老贝利档案馆的300 年来英格兰和威尔士的中央刑事法院记录的数据。当然，简单常见的 Excel 格式中有清晰的数据，包括每个案例的起诉，判决和判刑等变量。但其中还包括完整的庭审记录，不到 200,000 次审判记录了总计约为 1000 万字的数据。

“你到底该如何分析这些数据？”

DeDeo 想知道这个问题答案。数据集的大小并没那么可怕; 根据大数据标准，数据集的大小非常容易处理。问题在于他们缺乏结构，并且非常的复杂。

这种“大数据”看起来不像这位前物理学家在以前在职业生涯中遇到的传统数据集，传统的研究规范要求提出一个假设，并确定需要测量什么，然后构建一个装置，来进行精确的测量。

“在物理学中，通常只会有一种类型的数据，并且你对整个系统的了解非常全面。”DeDeo 说道。“现在我们从生物系统和人类社会系统中收集了多种形态的新数据，甚至在我们提出假设之前，就已经收集了数据。”

纷杂且令人惊讶的高维度数据，等待着被人查询。但是当科学规范从一开始就被颠覆，谁又知道该提出什么样的问题呢？

DeDeo 不是唯一被这些挑战所困扰的研究员。无论是处理病历、基因组测序、大脑中的神经网络、天体物理学、历史档案还是社交网络，在每个学科中，数据集都变得越来越大、越来越复杂。

© wired

Alessandro Vespignani 是东北大学的物理学家，他专门利用社交网络的力量来模拟疾病爆发、股票市场行为、集体社会动态和选举结果，他已经从 Twitter 等社交网络收集了 TB 级的数据，几乎所有这些数据都是非结构化的原始数据。“我们没有控制实验条件，所以我们不知道我们会得到什么样的数据。”

今天的大数据充满杂音，缺乏结构，并且动态多变。这些数据可能已经损坏，或者不完整。

尝试解决

俄克拉荷马州立大学数学家 Jesse Johnson 说:“我们认为数据是由向量组成的——数字和维度构成的序列。”但来自 Twitter 或 Facebook 的数据，或者伦敦老贝利档案馆的庭审记录，看起来都不像向量，这意味着研究人员需要新的数学工具，以便于从数据集中收集有用的信息。

Johnson 说：“要么你需要更复杂的方法将它转化为向量，要么你需要提出一种更通行的方法来分析它们。”

Vespignani 使用各种数学工具和技术来理解他的数据，包括文本识别。为了给任何他想尝试的系统建模，他都需要在数以百万计的推文中查找相关的词汇。

DeDeo 在伦敦老贝利档案馆项目中使用了类似的方法。他的解决方案是通过使用关键字和同义词将10万个单词分成1000个类别，以此来缩减他初始的数据集。现在，你已经把这个试验变成了一个1000维空间中的一个点，告诉你这个试验是关于友谊、信任还是服装，”他这样解释道。

新思路

像 DeDeo 和 Vespignani 这样的科学家很好地利用了这种零敲碎打的方法( picemeal approach )去分析大数据，但是耶鲁大学数学家 Ronald Coifman 说，真正需要的是大数据领域中牛顿式的革命，他认为这与17世纪发明的微积分不相上下。

仅仅收集和存储大数据是不够的; 必须要有明智的设计，这需要有全局的框架。

“我们已经掌握了所有的拼图碎片——现在我们要如何组装它们才能看到大图景（全局）？”他说，“你能在一个微小的局部尺度上得到一个非常简单的模型，但“微积分式”的发明可以让你用很多简单的模型并将它们整合到一个大图景中。”

© wired

同样，Coifman 认为现代数学——特别是几何学——可以帮助识别潜在的大数据的全局结构。例如，数据集可以按地理或气候来组织，这样，每一个数据集都会产生一幅形状非常不同的地图。

节点与连边

七桥问题：位于波罗的海的普鲁士城市 Königsberg（现在的 Kalingrad）由 Pregel 河划分为四个不同的地理区域，七个桥梁连接这些区域。18世纪，数学家莱昂哈德·欧拉对那个时代的一个流行难题感到困惑——

有没有可能走过 Königsberg 的所有桥梁，每座桥只穿过一次，最终还能回到起点？

七桥问题 | sohu

为了解决这个问题，欧拉将问题简化为节点和边，四片区域是四个节点，桥梁用节点间的连边表示。他发现为了穿过所有的桥梁，每一个区域都需要连接偶数个桥梁，因为在 Königsberg 不是这样的情形，所以这样的旅程是不可能的。

谜底后文揭晓

欧拉从这个谜题中发现的最重要的洞见就是，桥梁的位置和解决方法无关；重要的问题是桥梁的数量以及它们的连接方式。数学家们意识到，这是现代拓扑学的萌芽。

（TDA）

拓扑数据分析原理

斯坦福大学的数学家 Gunnar Carlsson 以欧拉的做法为参照，将庞大而复杂的大数据集表示为节点和边的网络，仅基于数据点的相似性创建了直观的数据图示；这使用距离作为输入，输出为拓扑形状或网络。

斯坦福大学的数学家Gunnar Carlsson，通过拓扑数据分析，找寻复杂且非结构的数据中的结构。

题目：

Extracting insights from the shape of complex data using topology

地址：

https://www.nature.com/articles/srep01236.ris

数据点越相似，它们在结果图示上就越接近；他们越不同，他们在图示上的距离就越远。

这是拓扑数据分析( TDA )的本质。

TDA 是机器学习的产物，而机器学习则是大数据分析中使用的一套标准工具。机器学习中的许多方法在处理矩阵数据（如 Excel 表格）时最有效，但是如果你的数据集不适合这个框架，怎么办？

Carlsson 说:“拓扑数据分析是一种从非结构化数据中获取结构化数据的方法，这样机器学习算法可以更直接地对其进行操作。”

拓扑方法很像在墙上投射三维物体的二维投影。—— Gunnar Carlsson

就像欧拉桥一样，这一切都与连边有关。

社交网络描绘了人与人之间的关系，一个集群的名字(节点)和联系(边)说明了我们是如何联系在一起的。将会有与家庭、大学同学、职场等相关的集群。

Carlsson 认为这种方法也可以扩展到其他种类的数据集，例如基因组序列。“人们可以将序列排列在一起，并计算出它们不同之处的数量，”他这样解释，“这个数字可以衡量它们的相似度，你可以将其编码为距离函数。”

这个想法就是将高维度的大型原始数据，压缩成低维度的数据，同时又不会牺牲相关的拓扑结构。

七桥问题解决思路：欧拉将其简化为“一笔画”问题 | cnblogs

在理想情况下，这将揭示数据的基本结构。理论上球体存在于每一个空间，但是我们只能够理解三维空间中的球体，然而，有了“数学眼镜”，人们可以通过它收集关于这些高维形状的信息。

Carlsson说：“一个形状有无数个点，这些点之间有的距离有无穷多个，但是如果我们愿意做出一些牺牲，我们可以用一个六边形来表示一个圆，这仍然是一个可以被识别的圆。”

TDA的应用

Ayasdi公司

这正是 Carlsson  的创业公司 Ayasdi 能提供的技术的基础，就像地铁线路图一样，公司能把高维的数据压缩至更小的片段表示出来。这样的地图可能无法准确地表示城市的每个细枝末节的特征，但是它能突出主要区域，以及这些区域的连接方式。

https://www.ayasdi.com/

使用这个软件，得到的图示并不仅仅是一个炫目的数据可视化图片，它还能够让用户就像使用 Photoshop 或 Illustrator 一样直接与数据集交互。

“这意味着我们不会完全忠实于原始数据，但是如果低维度的数据中存在拓扑特征，这表明原始数据也有类似特征。”Carlsson 说。

如果你的高维数据集有155个变量，应如何在所有的变量中着手查找它？

Carlsson 把这项任务比喻成摸黑在车库里找锤子。

如果你唯一的工具是手电筒，你所能做的事情就是一次照亮车库的一小部分地方，你最终可能会找到锤子，但是你很可能会对这样的低效的方法失去耐心。

而打开一盏能照亮整个车库的大灯，会提高你的效率，能给你提供一个全局视角，你不仅会发现锤子，还会意识到旁边放着一盒钉子，而之前你并没有意识到你需要这些钉子。

 Ayasdi 的技术类似于照亮整个车库。

处理基因组数据集

作为验证，Carlsson 和斯坦福以及普林斯顿高级研究所的合作者将这种方法应用于十多年前荷兰乳腺癌患者基因组研究中的一个更古老的数据集。

最初，它是标准的 Excel 表格形式，有 1500 列和 272 行对应着受试者提供的基因组样本。一旦这被转换成网络，产生的“图示”呈现出Y形，颜色编码指示出哪些受试者存活（蓝色）而哪些受试者死亡（红色）。那些预后糟糕的患者聚集在Y的左分支，右分支仅由 8%-9% 存活者够成。

一旦能够确定该群体，遗传学家就可以更仔细地分析这些基因，以确定最有可能是哪些基因影响了他们的生存。

该方法足够灵活，可以应用于不同的系统。

分析球员潜力

Ayasdi 的实习生中有一位是休斯顿本地人，也是休斯顿火箭队的球迷。他创建了一个包含 2010 年所有 NBA 球员的数据集，并将他们的联盟平均数分为七个统计类别：得分，篮板，助攻，抢断，盖帽，失误和个人犯规，精细化到每一分钟，以确保上场时间不是一个影响因素。

如果事实证明，你所有的数据中掩藏着一头球形的牛，那么 TDA 将是一个不错的选择，如果它不存在，你又能做什么？——Benjamin Recht

他最初在标准的 Excel 表格中呈现这些数据，球员表示为 400 行，每行数据点有 7 列，但是 Ayasdi 软件检测到球员潜在的统计模式，与他们的比赛风格相关联，并创建了这些连接的图示。

根据图示，除了篮球的五个主要位置（控球后卫、投篮后卫、大前锋、小前锋和中锋）以外，还有13个“隐藏”位置。被他称之为“油漆捍卫者（paint protectors）”的球员在篮板和拦网方面表现出色，但是他们犯规更多。“摘分油漆捍卫者(Scoring paint protectors)”与之近似，犯规更少，积分更多。这项工作在 MIT 的体育分析会议上获得了最佳体育发展奖，部分原因归功于它能够识别有潜力而被低估的运动员。

TDA的局限

拓扑方法很像在墙上投射三维物体的二维投影：这能够使得我们用投影降维的方法可视化大规模的高维数据。但是，就像皮影戏所制造出来的影子，我们能够看到并不真实存在的模式影像，而这是一个缺点。

加州大学伯克利分校的计算机科学家 Benjamin Recht 说:“有一个带有恶趣味的数学笑话——拓扑学家无法分辨他们的屁股和咖啡杯之间的区别，因为两者在拓扑上是等价的。”他表示目前并不清楚 TDA 何时管用，何时不管用。

这项技术依赖于一个假设：高维数据集有一个内在固有的低维结构，并且有可能通过数学发现这种结构。

Recht 认为，一些数据集本身具有很高的维度，但不能通过拓扑分析来降维。“如果事实证明，你所有的数据中掩藏着一头球形的牛一样的具体结构，那么 TDA 将是一个不错的选择，如果它不存在，你又能做什么？如果数据集被污损，不完整，拓扑方法将产生有类似错误的结果。”

奥卡姆积木

2004年2月，斯坦福大学的数学家 Emmanuel Candes 和他当时的博士后 Justin Romberg 在他的电脑上处理着一幅严重受损的图像，这类图像通常被计算机科学家用来测试成像算法。

他们试图找到一种改进模糊图像的方法，例如当没有足够的时间完成 MRIs 扫描时，产生的模糊的图像。凭借直觉，Candes 实现了一种处理模糊图像的算法，希望图像能稍微变得清晰一点。

从左至右图像恢复 | cvchina

然而，一幅完美的图像呈现在他电脑屏幕上。Candes 将这个不太可能的结果比喻为只给出了十位银行账户的头三位数字，而要准确的猜出剩余的七位。但这并不是侥幸，他将同样的技术应用于其它的不完整图像，生成了怎样的结果。

一个被称为稀疏性（sparsity）的概念是这项技术成功的关键，这个概念通常用于表示图像的复杂性或不够复杂。这是奥卡姆剃刀的数学版本：虽然图像模糊，不明确的图像可能有数百万种可能的重建方式，但最简单（最稀疏）的原图可能是最合适的。

从这个意外的发现，诞生了压缩感知。

压缩感知：

为数据划分优先级

考虑一下在线视频流的情况。视频中的原始数据非常巨大——3200万像素每秒——所以数码相机、数码摄像机使用压缩算法存储图像。人们为了执行压缩程序，必须收集所有的数据，并存储这些数据。

利用压缩感知，就可以丢弃那些不太重要的数据，人们可以先知道，哪些数据是重要的，而不是先收集存储他们。Recht 说，这允许你更快地获取医学图像，制造更好的雷达系统，甚至用单像素相机拍照。

筛查感染者

“如果我对人群进行罕见疾病筛查，我是否需要做和人口数量一样多的血液样本检测？”Candes 说。“答案是否定的。我可以用更少的测试来做到这一点。我采集的信号很少，因为只有少数人会被检测为阳性。“

假设32个人中有一名感染者，测试样本中包含了32份血液样本，如果检测为阴性，就没有感染者，如果检测是阳性，如何确定谁是感染者呢？

根据 Candes 的说法，可以取一半（16）的样本，并重新进行检测，如果是阳性，则该感染者属于该组，如果是阴性感染，感染者位于另外的一组，并且可以再次进行二分法，直到找到感染者。“总体检测”法将在 5 次检测中给出答案，相比于，对 32 个人逐一进行检测，这就是压缩感知的本质。

使用压缩感知算法，只要存在稀疏性和分组(或“ 总体检测”)的关键元素，就有可能对具有一百万个像素的图像中的十万个像素进行采样，并且仍然能够以完整的分辨率重建图像。当遇到一个大数据集，并且其中的很大一部分数据丢失不完整时，这就是一个有用的方法。

对于医疗数据，传感器可能无法准确记录数据，或者医院的工作人员可能太忙而来不及将数据传输到计算机，也许他们采集了不正确的信息。

对于面部识别，压缩感知可以用于处理识别系统中的遮挡问题，例如眼睛是识别脸部的关键因素，而戴墨镜就会遮挡眼睛。

扩展应用：

解决评级缺失问题

严格来说，这种方法甚至可以应用于非压缩感知的问题，如 Netflix 大奖。

Netflix 设立了一项百万美元的大奖，奖励那些能够改进家庭电影推荐系统Cinematch的过滤算法的人。一个由统计学家、机器学习专家和计算机工程师组成的国际团队在2009年获得了大奖，但是学术界也能普遍从中受益，因为他们获得了由 Netflix 提供的高质量的巨大数据集。Recht 就是其中一位改进该算法的人。他的工作证实了能够将压缩感知算法应用于填补数据集中的评级缺失问题。

Cinematch 的运作依赖于客户反馈，鼓励用户对他们观看的电影进行评级，并且基于这些评级，推荐系统能够给定用户对类似电影的喜爱程度。

Netflix 提供的数据集非常巨大，但是并不完整，总体而言，用户只对近 18,000 部电影中的 200 部进行评级。考虑到 Netflix 的普及范围之广，推荐系统的一点点改进，也能够极大地提高公司利润。

Recht 发现，只要客户看了足够多的电影，他就可以准确预测客户会感兴趣购买哪些电影。25 至 100 部电影就足够完善数据矩阵。

压缩感知原理图示 | CSDN

Candes 说:“我们在数学上已经表明，在某些条件下，通过易于处理的计算技术，你可以非常准确地做到这一点。”从这一原理中得到的经验现在回馈给了研究界，解决了量子物理、X-射线晶体学和计算机视觉以及其他应用领域的问题。

未来趋势：

整合工具，构建模型

未来，天文学家使用红外天文望远镜时可能只需要记录 20% 的像素，在以往，他们需要获得同样的高分辨率图像，而现在压缩感知可以填补这些空白。

Recht 和 Candes 可能会采用像压缩感知这样的方法，而 Carlsson 和 Coifman 则更倾向于使用拓扑方法，但从根本上说，这两种方法能互为补充而非彼此竞争。

同时还有一些其他的有前景的数学工具正在开发之中，为了更好的处理这个数据庞杂而复杂的新世界。Vespignani 使用了一切可利用的工具，从网络分析（创建人、对象、文档之间的关系网络，以此揭示潜藏在数据中的结构）到机器学习以及经过考验的老式统计方法。

© Behance

Coifman 声称需要一个和微积分同等重要的基础理论，使得研究者能够更好的成为“大数据监管人”。同样的，各种正在开发的工具技术需要整合到一个更广泛的理论模型中。

Vespignani 坚定的认为：“到头来，数据科学不仅仅是方法论的加和。当你融合了一些东西的时候，你能做出一个崭新的、伟大的、不一样的东西。”

翻译：Leo

审校：高飞

编辑：王怡蔺

原文：

https://www.quantamagazine.org/the-mathematical-shape-of-big-science-data-20131004

推荐阅读

推荐课程

课程地址：

https://campus.swarma.org/gpac=10406

---

集智俱乐部QQ群｜292641157

商务合作及投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！