数据摘要的常见方法
共 7145字，需浏览 15分钟
·
2022-01-04 09:58
在许多计算设置中，相同信息的超载是一个需要关注的问题。例如，跟踪其网络应用以识别整个网络的健康状况以及现场异常或行为变化。然而，事件发生的规模是巨大的，每个网络元素每小时可能会发生数以万计的网络事件。虽然技术上允许监控事件的规模和粒度在某个数量级内的增加，但是，处理器、内存和磁盘理解这些事件的能力几乎没有增加。即使规模很小，信息量也可能过大，无法方便地放在存储中。
为了应对这一挑战，流数据处理模型变得越来越流行。其目的不再是捕获、存储和索引每一事件，而是快速处理每一个观察结果，以便创建当前状态的摘要。处理完成后，事件被删除，不再可访问。这样的处理意味着另一种权衡: 对世界的描述是近似的而不是精确的，而且需要回答的问题性质必须事先决定，因此有些问题是无法解决的。然而，用适度的资源以极快的速度处理大量数据的能力，可以突破数据量的限制。因此，流处理技术已经在许多领域得到应用，从电信扩展到搜索引擎、社交网络、金融以及时间序列分析领域（例如IoT领域）。数据摘要的方法是更具成本效益，涉及到算法技巧、系统知识和数学洞察力的混合。
具体的方法可能有哪些呢？
抽样
当面对大量需要处理的相同信息时，可能有一种强烈的诱惑，就是完全忽略它。一个稍微有点原则的方法就是忽略大部分，也就是从整个数据集中选取少量的样本，在这个子集上执行计算，然后尝试外推到整个数据集。为了给出一个好的估计，抽样必须是随机的。
抽样方式有很多种，最基本的方式是均匀随机抽样。对于大量的数据记录，随机选择少量记录作为样本。然后根据样本回答各种问题， 例如，估计什么比例的客户在一个特定的城市或购买了一个特定的产品。
那么，样本应该有多大才能提供好的结论呢？根据标准的统计结果，对于像客户记录中的抽样问题，s 大小的样本的标准误差与1/s 成正比。粗略地说，这意味着在从样本中估计一个比例时，误差应该看起来像 ± 1/s。因此，观察一个1000个用户投票的一个意见调查，其误差大约为3% ，即真实的答案在样本结果的3% 之内，增加样本数量会使错误以一种可以预测的方式减少，如果将调查的误差降低到0.3% 需要联系100,000个用户。
其次，如何抽取样本？简单地获取第一个 s 记录并不能保证是随机的，所以需要确保每个记录都有同样的机会被包含在样本中。这可以通过使用标准的随机数生成器来选择要包含在样本中的记录。一个常见的技巧是给每个记录附加一个随机数，然后根据这个随机标记对数据进行排序，并按照排序顺序获取第一个 s 记录。只要对整个数据集进行排序不会花费太多的成本，这种方法就可以很好地工作。
最后，当增加新数据时，如何维护样本呢？一个简单的方法是，对于 p 的某个选择值，以概率 p 来挑选每条记录。当一个新的记录出现时，在0和1之间随机选择一个分数，如果它小于 p，将记录放入样本中。这种方法的问题在于，我们事先并不知道 p 应该是什么。在以前的分析中，需要一个固定的样本大小 s，并且使用固定的抽样率 p。这意味着最初的元素太少，而随着记录的增加又会使元素太多。这个问题就像是一个算法难题，事实上这是多年来技术面试中常见的问题。一个解决方案是随着新记录的到来，递增地调整 p。维护抽样的一种简单而优雅的方法是采用随机标记的思想。向每个记录附加一个随机标记，并将样本定义为具有最小标记值的 s 记录。当新记录到达时，标记值决定是否将新记录添加到样本中，并删除旧记录以保持样本大小固定在 s。
抽样方法是如此普遍，应用的示例很多，一个简单的例子是在数据库系统中，为了进行查询规划，通常需要保存一个大型关系的样本。在决定如何执行查询时，评估不同的策略可以估计每个步骤中可能发生的数据缩减量。另一个例子来自数据集成和链接领域，其中的一个子问题是测试来自不同表的两列是否可以与同一组实体相关。全面比较各个列可能会耗费时间，特别是在希望测试所有列对的兼容性时，比较小的样本通常足以确定列是否有任何机会与相同的实体相关。
抽样方法如此简单而通用，那为什么还需要其他方法来总结数据呢？事实证明，抽样并不能适用于某些问题。任何需要详细了解数据中各个记录的问题都不能通过抽样方法来解决。这样的问题最终需要记录所有的信息，并且可以通过高度紧凑的编码来解决。一个更复杂的例子是当问题涉及到确定数量基数的时候，在具有许多不同值的数据集中，某种类型的不同值有多少？例如，在一个特定的客户数据集中有多少个不同的姓氏？使用一个样本基并不能揭示这个信息。最后，一些样本可以估计的数量，但是对于这些数量，还有更好的摘要方法。
对于诸如估计一个特定属性(如居住城市)的频率问题，可以建立一个 s 大小的样本集，保证的误差是1/s。这是相当强大的采样保证，只有提高了我们投入更多的空间，草图。本文后面描述的 Count-Min 示意图具有此属性。其中一个限制是，必须在设置草图之前指定感兴趣的属性，而示例允许您评估查询中所采样项目的任何记录属性。假设在100万个记录中的1000个样本中，只有900个姓氏出现在抽样的名字中。关于这些名字在其他数据集中的流行程度，您能得出什么结论？完整数据集中的几乎所有其他名称也都是唯一的。或者，示例中的每个唯一名称在剩余的数据中重复出现数十次或数百次。由于样本信息的存在，这两种情况无法区分，导致了这两种统计方法的巨大置信区间。跟踪有关基数的信息，并省略重复的信息，可以通过诸如 HyperLogLog 之类的技术进行处理，稍后将进行处理。
布隆过滤器
布隆过滤器是一种紧凑的数据结构，可以作为一组数据项的摘要。任何计算机科学的数据结构类型都有“字典”，例如数组、链表、哈希表和许多平衡树及其变体。这些结构的共同特点是，都可以回答某个项目是否存储在结构中。布隆过滤器也可以回答这样的成员资格问题，而且空间利用率更高。
为了理解这个过滤器，考虑一个简单成员问题的精确解是有帮助的。假设希望跟踪一百万个可能记录中的哪一个，并且每个记录都被贴上了 ID 标签，然后可以保持一个一百万位的数组，初始化的0。每次看到记录 i 时，只需将数组中的第 i 位设置为1。对记录j 的查找查询相应地非常简单，只需查看位 j 是1还是0。该结构非常紧凑，如果将位数据放到内存中，125KB 就足够了。
然而，真正的数据很少有这么好的结构。一般来说，可能有一个更大的输入集，例如客户的名称，其中可能的名称字符串数量是巨大的。不过，可以通过借用不同的字典结构来调整位数组的方法。假设位数组是一个哈希表，将使用哈希函数 h 将输入空间映射到表的索引范围。也就是说，给定输入 i，现在将关键字 i 设置为1。当然，我们会注意哈希冲突。这里显然有一个权衡，最初，添加额外的哈希函数可以减少出现假阳性的机会，然而，随着越来越多的哈希函数被添加，位数组中的1个值越来越多，因此更有可能发生冲突。这种权衡可以通过数学方法进行分析，通过假设哈希函数看起来完全是随机的 ，并通过查看不在集合中任意元素存在的几率来进行工作。
如果在一个大小为 m 的布隆过滤器中存储了 n 个不同的项，并且使用了 k 哈希函数，那么一个成员资格查询得到一个假阳性结果的机会大约是 exp (k ln (1 exp (kn/m)))。一些简单的分析表明，通过选择 k = (m/n) ln 2，这个比率可以最小化，即过滤器中大约一半位为1，一半位为0的情况相对应。
为了实现这一点，过滤器中的位数应该是存储在其中的记录数的几倍。一个常见的设置是 m = 10n 和 k = 7，这意味着假阳性率低于1% 。请注意，这里没有魔法可以压缩超出信息理论限制的数据，在这些参数下，布隆过滤器每个条目使用约10位，并且必须使用与存储的不同条目数量成比例的空间。当表示整数值时，这是一个适度的节省，但是当存储项具有大的描述符(比如 url 等任意字符串)时，这是一个相当大的好处。因为，将这些数据存储在传统的结构中，比如哈希表或平衡搜索树，每个项目将消耗数十或数百个字节。
当一个假阳性的结果不是在计算中引入一个错误，而只是一些额外的工作，并且不对系统的整体性能产生不利影响时，布隆过滤器是最有吸引力的。一个很好的例子来自于浏览网页的场景，如果用户试图访问一个已知的恶意站点时，Web 浏览器通常会警告用户。简单对比“恶意”URL 数据库检查 URL 就可以做到这一点，但是需要数据库足够大，把完整的数据库作为浏览器的一部分是很难操作的，尤其是在移动设备上。相反，数据库的布隆过滤器编码可以包含在浏览器中，每个访问过的 URL 都可以根据它进行检查。糟糕的结果只是浏览器可能认为一个无辜网站在黑名单上，为了处理这个问题，浏览器可以联系数据库并检查列表中是否有完整的 URL，以远程数据库查找为代价来消除误报。布隆过滤器为大多数 URL 提供所有信息，并且对一小部分url产生轻微的延迟。这比在浏览器中保存数据库副本的解决方案和对每个 URL 进行远程查找都要好的多，像 Chrome 和 Firefox 这样的浏览器就采用了这个概念。
布隆过滤器是在1970年作为一种紧凑存储字典的方式引入的，当时的内存很珍贵。随着计算机内存的增长，似乎不再需要它了。然而，随着网络的迅速发展，已经出现了许多布隆过滤器的应用，许多大型分布式数据库(Google 的 Bigtable、 Apache 的 Cassandra 和 HBase)都使用布隆过滤器作为分布式数据块的索引。它们使用过滤器来跟踪数据库的哪些行或列存储在磁盘上，从而避免对不存在的属性进行磁盘访问。
Count-min
也许规范的数据汇总问题是最不重要的，一个简单的计数器就足够了，每观察一次就增加一次。计数器必须有足够的位深度，以应付所观察到的事件的大小。当存在不同类型的数据项时，如果希望计算每个类型的数量时，自然的方法是为每个项分配一个计数器。然而，当项目类型的数量增长巨大时，会遇到困难，为每个项目类型分配一个计数器可能不实用，当计数器的数量超过内存的容量时，递增相关计数器的时间成本可能会变得过高。例如，社交网络可能希望跟踪一条记录在外部网站显示的频率，有如果数十亿个网页，每个网页原则上都可以链接到一个或多个记录，因此为每个网页分配计数器是不可行的，也是不必要的。寻找一种更紧凑的方式来对项目计数进行编码是很自然的事情，尽管可能会失去一些精确度。
Count-Min 也是一种数据结构，允许进行这种权衡，它在一个小数组中对大量的记录类型进行编码。保证大的计数将被相当准确地保存，而小的计数可能会有误差。Count-Min 由一组计数器和一组哈希函数组成，这些函数将数据项映射到数组中。乍一看，很像布隆过滤器，但在细节方面存在着显著的差异。确切地说，数组被视为一个行序列，每个项目由第一个哈希函数映射到第一行，由第二个哈希函数映射到第二行，以此类推，并递增映射到的计数器。注意，这与 布隆过滤器不同，后者允许哈希函数映射到重叠的范围。
对于给定的一个数据项，Count-min允许对其计数进行估计: 检查第一行中由第一个哈希函数映射项的计数器，以及第二行中由第二个哈希函数映射项的计数器，依此类推。每一行都有一个计数器，该计数器已按该项的每次出现次数递增。但是，由于预期会发生冲突，计数器还可能因映射到同一位置的其他项。给定包含所需计数器和噪声的计数器集合，将这些计数器中的最小值作为估计值。
Count-min也实现了输入数据的紧凑表示，并在精确度上进行了权衡。如果使用布隆过滤器，答案是二进制的，所以有可能出现假阳性; 使用 Count-Min ，答案是频率，所以有可能出现一个被夸大的灭国。Count-Min 最适合处理轻微的频率膨胀，不适用于可能使用 布隆过滤器的情况，如果一个数据项是否存在非常重要，那么 Count-Min 引入的不确定性将掩盖这种精确程度。但是，count-min 非常适合跟踪哪些数据项超过了给定的流行度阈值。Count-Min 具有更大的压缩性，它的大小可以被认为与输入大小无关，而只取决于所期望的精度保证。
自问世以来，Count-Min 已在跟踪频率统计数据的系统中有了广泛的应用，例如不同群体的内容流行程度、不同用户群体中在线视频的流行程度，以及通信网络中的流行节点。网络流量的摘要分布可以检测到热点，为网络规划的决策提供了信息，也可以用来检测何时发生了流行趋势的变化，作为简单的异常检测。
HyperLogLog
如何跟踪在大量的可能性中有多少不同的项目呢?例如，Web 网站可能希望跟踪有多少不同的人接触到了特定的广告。在这种情况下，不希望对同一个用户浏览进行多次计数。当记录项数量不太大时，保持一个列表或二进制数组是一个自然的解决方案。当可能的项目数量变得非常大时，这些方法所需的空间与所跟踪的项目数量成正比。能指望做得更好吗？
HyperLogLog 承诺了更强大的功能，成本只需依赖于计算量的对数。当然，也有一些缩放常数，这意味着所需的空间并不像表示的那么小，但最终的结果往往只需要几K字节的空间，就可以高精度地估计数量。HyperLogLog的本质是使用应用于数据项标识符的哈希函数来确定如何更新计数器，以便对重复项进行相同的处理。对每个数据项 i 应用一个散列函数 g，g 以2j 的概率将数据项映射到 j ，例如，在均匀的二进制展开式中取前导零位的数目。然后可以保留一组位标识，指示到目前为止已经得到的那些j 值。这里只需要一个对数位数，因为只需要这么多不同的 j 值。HyperLogLog方法只保留应用哈希函数时看到的最大 j 值，从而进一步减少了位数。这可能与基数相关，为了减少这种变化，使用第二个哈希函数将项分成组，因此同一项总是放在同一组中，并保留关于每个组中最大哈希的信息。每个组都会产生估计值，这些估计值都被组合起来以获得总基数的估计值。方法是计算估计值的平均值，使用调和平均值来减少这种影响。算法的分析具有一定的技术性，但该算法已被广泛采用并在实践中应用，例如Redis。
HyperLogLog 的一个典型示例就是跟踪在线广告的收视率。在许多网站和不同的广告中，每天可能发生数以万亿计的观看事件。广告商感兴趣的是有多少不同的人接触过这些内容。收集和传输这些数据并不是不可行的，只是相当笨拙，特别是如果希望执行更高级的查询(例如，计算有多少独立访问者同时看到两个特定的广告)。HyperLogLog使得这种查询可以直接得到答案，而不是通过搜索整个数据。近似差异计数在 web 系统中也被广泛使用，例如，谷歌的广告系统提供了不同的计数，作为日志数据分析的原语。
小结
在处理大型高维数值数据时，通常寻求在保持数据逼真度的同时降低维数。假设数据处理和建模的艰苦工作已经完成，数据可以被建模为一个巨大的矩阵，其中每一行是一个样本点，每一列编码为数据的一个属性。一种常用的技术是应用 PCA从数据中提取少量的“方向”，沿着每个方向的每一行数据会产生不同的数据表示形式，这些表示形式可以捕获数据集的大部分变化。其局限性是需要找到协方差矩阵的特征向量，这对于大型矩阵来说就变得不可持续。与其寻找“最佳”方向，不如使用(数量稍大的)随机向量。数据矩阵的每一行的随机投影可以看作是数据摘要的一个例子。更直接的是，Count-Min 可以被看作是各种类型的随机投影，这是加速高维机器学习方法的基础，例如哈希核函数方法。
数据摘要的一个目标是允许任意复杂的大量数据上快速得到近似结果。一些核心的数学运算可以通过数据摘要的思路来解决，例如随机数值线性代数。一个简单的例子是矩阵乘法矩阵: 给定两个大矩阵 A 和 B，找到它们的乘积 AB。一种数据摘要方法是为A 的每一行和 B 的每一列建立一个降维的数据摘要，提供一个估计。在这个领域中已解决的问题包括了回归。这输入是一个高维数据集，建模为矩阵 A 和列向量 b， A的每一行都是一个数据点，b 的相应条目是与该行关联的值, 目标是找到最小二乘法的回归系数 x。这个问题的精确解是可能的，但是时间上的开销与行的数量有关，而在矩阵 A上应用数据摘要可以解决低维空间的问题。
对于图，有一些技术可以概括每个节点的邻接信息，从而可以提取连通性和生成树信息。对于几何数据来说，解决聚类等问题的输入可以捕获大量的总体结构信息，通过将聚类合并在一起，也可以保留整体点密度分布的良好特征。
一般地，简单的方法可以提供准确的答案，但需要保留完整的信息。而在许多情况下，近似方法可以更快，更节省空间。布隆过滤器有时被认为是“大数据分析”必须掌握的核心技术之一，通常，基于快速数据摘要的技术可以提供不同的折衷。
【关联阅读】