machine-learning - ELKI 可以处理多大的数据集？

Question

我有 100,000 个点要使用 ELKI 中的 OPTICS 算法进行聚类。对于这个点集，我有一个大约 50 亿个条目的上三角距离矩阵。在 ELKI 想要的矩阵格式中，大约需要 100GB 的内存。我想知道 ELKI 是否处理这种数据负载？任何人都可以确认您以前是否做过这项工作？

Answer 1

我经常使用 100k 点的 ELKI，最高可达 1000 万。

但是，为了更快，您应该使用索引。

出于显而易见的原因，任何基于密集矩阵的方法最多只能扩展O(n^2)，并且需要O(n^2)内存。这就是为什么我不能用 R 或 Weka 或 scipy 处理这些数据集的原因。他们通常首先尝试计算全距离矩阵，要么中途失败，要么中途内存不足，要么因分配大小为负而失败（Weka，当您的数据集溢出 2^31 个正整数时，即大约 46k对象）。

在具有浮点精度的二进制格式中，ELKI 矩阵格式应该围绕100000*999999/2*4 + 4字节，可能会添加另外 4 个字节用于大小信息。这是20 GB。如果使用“好用”的ascii格式，那确实会更多。但是，如果您使用 gzip 压缩，它可能最终大小相同。让 gzip 将此类数据压缩到原始大小的 10-20% 是很常见的。根据我的经验，gzip 压缩的 ascii 可以像二进制编码的 doubles 一样小。二进制格式的主要好处是它实际上将驻留在磁盘上，并且内存缓存将由您的操作系统处理。

无论哪种方式，我建议首先不要计算距离矩阵。

因为如果你决定从 10 万增加到 100 万，原始矩阵将增长到 2 TB，而当你达到 1000 万时，原始矩阵将增长到 200 TB。如果你想要双精度，那就加倍。

如果您使用距离矩阵，您的方法最多只能是O(n^2)，因此无法缩放。首先避免计算所有成对距离是一个重要的速度因素。

我对一切都使用索引。对于 kNN 或半径绑定方法（对于 OPTICS，使用 epsion 参数使索引有效！选择低 epsilon！）如果您将重复需要它们，您可以预先计算这些查询一次。

在我经常使用的具有 75k 个实例和 27 个维度的数据集上，存储预先计算的 101 个最近邻 + 关系的文件，具有双精度，为 81 MB（注意：这可以看作是一个稀疏相似度矩阵）。通过使用索引来预计算这个缓存，计算只需几分钟；然后我可以在 108 毫秒内在这个 75k 数据集上运行大多数基于 kNN 的算法，例如 LOF（加载 kNN 缓存 +262 毫秒 + 解析原始输入数据 2364 毫秒，总运行时间为 3 秒；主要是解析双精度值）。