python - 用于数百万对频率计数的算法和工具集

Question

更新16年5月26日：尝试了新算法。见底部。



我正在寻找有关算法和工具集的建议，以获取项目对的频率计数。对于那些熟悉它的人来说，这类似于“购物篮”问题（“啤酒和尿布”模型），除了我需要出现的每一对的频率计数。

我有大约500万条记录。每条记录是10到300个项目的列表。这些项目是1到大约250,000之间的整数。因此，例如：

1: [85708, 28302, 1045, 20395]
2: [20382, 3092, 2933, 20993, 58585, 4855, 112393, 38347, 20447, 33892]
3: [118082, 30282, 2859, 585, 1045, 20395, 2383, 85855, 182582, 223]

我想生成一个表来回答这个问题：

对于任何两个项目，它们在同一记录中出现多少次？

例如，记录1生成对：（85708、28302），（85708、1045），（85708、20395），（28302、1045），（28302、20395）和（1045、20395）。我想统计整个数据集中每个对的出现频率。 [顺序无关紧要]。

要了解它需要处理的大小：记录的平均长度为85个项目。对于该长度的记录，需要计数3655（= 86 * 85/2）对项目。对于这样的长度的500万条记录，需要计算180亿对项目。在大多数运行中，记录的中位数长度大大低于平均值（大多数记录包含<18个项目，而少数记录包含更多项目），因此，实际的对对数可能不会达到180亿，但绝对可以几十亿。

单个项的频率分布遵循幂定律，具有几个高频项和许多低频项；在最近一次比正常情况大的运行中，最终出现了大约20亿对不同的项目，其频率大于0。绝大多数潜在的配对组合都不会发生。每次运行都不同，但我估计最多会出现15％的可能的配对组合，并且在大多数情况下，会少于2％。

我有一个可以正确运行的程序，但是速度很慢。我现在想针对速度进行优化。使用Python和MySql是蛮力的：


在Python中，获取一批1,000条记录的项目。
使用python的itertools.combinations，逐条记录循环，并为每条记录生成项目的所有配对组合。
将结果存储在sql db中。我在数据库中有一个表，其中包含3个字段：item1 (int), item2 (int), frequency (int), primary key (item1, item2)。对于我们计算出的每对项组合，执行一个insert... on duplicate key update：即，如果该表中不存在该对，则插入频率为1的对。如果该对存在，则将该对的频率增加1。
对下一批1,000条记录重复循环。


处理大约花了15个小时。前一段时间写这篇文章时，时间并不重要，我只需要运行一次即可获得无需更新的静态结果。但是现在输入记录将改变，我需要进行优化，以便每天至少可以重新生成一次结果。结果必须采用可用于快​​速查找项目对频率的形式。我想像一个索引数据库表。

我从根本上更改了蛮力程序，以通过处理读写批处理的数量来提高效率。处理时间的很大一部分发生在“如果不存在则插入对，如果存在则增加对频率计数”步骤。我的小调整将处理时间缩短了约15％。

另一个调整是，因为我已经掌握了每个项目的频率，所以我可以尝试使用最可能的频繁组合（例如，顶部5,000 x 5,000）“预先种子化”数据库，然后在Python中将配对组合除根据项目编号将其分为两组：“肯定在数据库中”和“不知道它是否在数据库中”。这将为数据库节省一些时间，但以让Python需要跟踪频繁项并将其划分为代价。

因此，我可以继续做这样的调整，并在此处和那里节省更多的百分比，但是我想做的正确，现在使用一个好的算法和好的工具从头开始重新编写过程，而不是浪费时间去调整一个错误的该过程很快就被拼凑在一起以一次性使用，并且从未计划过提高效率。

它必须在用户的单个独立桌面（标准规格）上运行，没有外部存储或分布式计算。

理想情况下，我想从python运行该过程。脾气暴躁，臭皮，blas / lapack都可以。 （我在有关一个问题的每个this answer处查看了python的collections.counter，但我认为我的大小太大；请告诉我这是否错误，并且Counter可能有效）。

我的问题类似于market basket problem，它最初来自一家商店，该商店记录了顾客在一个篮子里购买的物品（并得出了著名的结论，买尿布的人很可能会买啤酒）[感谢@lzcig以链接至市场篮问题的this good description]。市场篮问题过滤器对的策略降至最频繁的对，并且不计算主存储器中不适合的任何事物。但就我而言，我需要计算出现的每一对，即使它只出现一次。因此，我需要一种算法和工具集来有效地存储和索引所有这些内容。我不想重新发明轮子，我真的很想找到一个可以有效解决此问题的解决方案。

您会推荐什么作为最佳解决方案？



更新（2016年5月26日）：
我开发了一种解决方案，可以在2小时内准确地计算出数十亿对的完整数据集。基本思路：


利用幂定律分布以及我已经计算出单个项目的频率这一事实。由前几千个项目组成的货币对占总数的很大一部分。
建立一维数组以保存最频繁对的计数。 ixj矩阵值的一半将被浪费，因为该对的顺序无关紧要[（a，b）的计数与（b，a）相同]，所以我可以通过将它们打包到单个k-中来节省空间id（将（i，j）转换为ixj矩阵上三角的k索引）。我根据单个项目的频率分布和可用内存来动态调整数组大小。我发现3,000 x 5,000（存储在1050万个ID的数组中）效果很好。
我使用本机Python数组构建了该数组。与this answer类似，我发现在执行简单的数组访问和增量计数器的情况下，本机Python比numpy占用更多的内存，但速度更快。
处理每条记录。对于每对，如果项目位于最频繁的组中，则在数组中递增其ID的计数器。如果不是，则将该对添加到低频对列表中。
当内存紧张时，请对低频对阵列进行排序，然后将其写入新文件。
在处理结束时，对（许多）排序文件进行合并heapq，以创建一个包含所有低频对的文件。仔细检查一下，获取每个唯一对的计数。最后，将高频数组转换为对数值，然后将其与低频合并。结果是具有成对频率的文件（按排序顺序）。


这在很大程度上取决于最大化系统内存。我一直在监视内存使用情况，以尝试获取尽可能多的内存。瓶颈是磁盘读/写：合并数百个大文件比我想象的要激烈得多。因此，我一直在尝试减少文件数量的设置：合并一些大型文件比合并许多较小的文件要好。

在4gb RAM上，处理最近一批的500万条记录（几十亿对）需要不到2个小时。绝对比我最初的15个小时要好，但是感觉很hacky，我敢肯定必须有更好的方法来计算配对。如果您有任何想法请告诉我。

Answer 1

您可以为每条记录打印出所有成对的不同元素，然后利用任何Unix中精心设计的sort命令将相同的对组合在一起，最后用uniq -c计算每个相同块中的行数：

perl -lne '($_) = /\[(.*)\]/ or die; @x = sort { $a <=> $b } split /, /; for ($i = 0; $i < @x - 1; ++$i) { for ($j = $i + 1; $j < @x; ++$j) { print "$x[$i] $x[$j]"; } }' | sort -g | uniq -c > outfile

对于180亿行，这将花费很长时间，但是它比重复更新B *树要快，而B *树是SQL数据库很可能在内部执行的操作。 （换句话说：如果更新B * -tree实际上比这快，那么sort的所有实现也将在内部执行此操作。）您将不得不尝试一下。

要查询此“数据库”，您可以只对outfile进行二进制搜索-无需将整个内容加载到内存中。 （您可能想先将其转换为更紧凑的二进制格式，但这实际上不是必需的-您仍然可以通过始终向前读直到每次搜索后按\n来对纯文本文件执行二进制搜索。 。一旦您要搜索的范围足够小，您可能希望将其全部读入内存，然后继续在内存中进行二进制搜索。）

如果您不关心Perl，我相信您可以使用Python或任何其他语言来编写第一部分。