在损坏的数据中找到模式

数据分析通常是将数据拟合到某种数学模型的问题。这方面最熟悉的例子可能是线性回归，它找到一条接近数据点分布的直线。但将数据拟合到概率分布上，比如我们熟悉的钟形曲线，也同样常见。

然而，如果一个数据集只有几个损坏的条目——比如说，不可思议的测量——标准的数据拟合技术就会失效。这个问题在高维数据或具有许多变量的数据中变得更加严重，这些数据在数字时代无处不在。自20世纪60年代初以来，人们就知道有一些算法可以从高维数据中清除腐败，但在过去50年里提出的算法中，没有一个在变量数超过12时是实用的。

这种情况即将改变。本月早些时候，在IEEE计算机科学基础研讨会上，来自麻省理工学院计算机科学与人工智能实验室、南加州大学和加州大学圣地亚哥分校的一组研究人员提出了一套新的算法，可以有效地将概率分布拟合到高维数据中。

值得注意的是，在同一次会议上，来自佐治亚理工学院的研究人员提出了一个非常相似的算法。

关于“稳健统计”或可以容忍损坏数据的统计方法的开创性工作是由统计学家完成的，但这两篇新论文都来自计算机科学家小组。这可能反映了该领域的注意力转向了模型拟合技术的计算效率。

麻省理工学院罗克韦尔国际职业发展数学助理教授、麻省理工学院-南加州大学-加州大学圣地亚哥分校项目的负责人之一安库尔·莫伊特拉说:“从理论计算机科学的有利位置来看，一个问题有效解决是多么罕见。”“如果你以一些假设的事情开始——‘天哪，我希望我能做到这一点。如果我可以，它将是健壮的-你将会有一个糟糕的时间，因为它将是低效的。你应该从你知道你可以有效地做的事情开始，然后弄清楚如何将它们组合在一起以获得健壮性。”

抵制腐败

Moitra解释说，要理解稳健统计背后的原理，可以考虑正态分布——钟形曲线，或者用数学术语来说，一维高斯分布。一维高斯分布完全由两个参数描述:数据的平均值和方差，方差是衡量数据在平均值附近扩散的速度的指标。

如果一个数据集中的数据——比如给定人群中的人的身高——可以用高斯分布很好地描述，那么平均值就是算术平均值。但是，假设你有一个数据集，包含100位女性的身高测量数据，虽然她们中的大多数人都集中在64英寸左右——有些高一点，有些低一点——但出于某种原因，其中一个是1000英寸。用算术平均数来计算，女性的平均身高是6英尺4英寸，而不是5英尺4英寸。

避免这种无意义结果的一种方法是估计平均值，不是通过取数据的数值平均值，而是通过找到它的中位数。这包括按顺序列出所有100个测量值，从最小到最高，然后取第50或51个。因此，使用中位数来估计平均值的算法比使用平均值的算法更健壮，这意味着它对损坏的数据的响应更弱。然而，中位数只是平均值的近似值，随着变量的增加，近似值的准确性会迅速下降。大数据分析可能需要检查数千甚至数百万个变量;在这种情况下，用中位数接近平均值往往会产生不可用的结果。

识别异常值

从高维数据集中清除损坏数据的一种方法是获取数据图的2-D横截面，并查看它们是否看起来像高斯分布。如果他们没有，你可能已经找到了一组虚假的数据点，比如那个80英尺高的女人，可以简单地切除。

问题是，在所有采用这种方法的已知算法中，发现损坏数据所需的横截面数量是维数的指数函数。相比之下，Moitra和他的合著者——都是麻省理工学院电气工程和计算机科学研究生的gautam Kamath和Jerry Li;南加州大学的Ilias Diakonikolas和Alistair Stewart;和uscd的丹尼尔·凯恩(Daniel Kane)发现了一种算法，其运行时间随着数据维度的数量以更合理的速度增加(或者，用计算机科学术语来说是多项式)。

他们的算法依赖于两个洞见。第一个问题是在测量数据集与具有大致相同形状的分布范围的距离时使用什么度量。这使他们能够判断何时已经筛选出足够多的损坏数据来进行良好的匹配。

另一个问题是如何确定数据的区域，从哪个区域开始进行横断面。为此，研究人员依赖于一种被称为分布峰度的东西，它测量了其尾部的大小，或数据集中远远低于平均值的速度。同样，有多种方法可以从数据样本中推断峰度，选择正确的方法是算法效率的核心。

研究人员的方法适用于高斯分布，高斯分布的某些组合，另一种常见的分布称为积分布，以及积分布的某些组合。尽管他们相信他们的方法可以扩展到其他类型的分布，但在正在进行的工作中，他们的主要关注点是将他们的技术应用到现实世界的数据中。

麻省理工学院

www.mit.edu

-由克里斯·瓦夫拉编辑，制作编辑，控制工程， CFE传媒，cvavra@cfemedia.com．查看更多控制工程大数据和资产管理故事．

您是否具有本内容中提到的主题的经验和专业知识?你应该考虑为我们的CFE媒体编辑团队做出贡献，并获得你和你的公司应得的认可。点击在这里开始这个过程。