ELKI能处理多大的数据集？

Question

我有10万个点，我想用ELKI中的光学算法进行聚类。对于这个点集，我有一个约50亿项的上三角距离矩阵。在ELKI想要的格式中，它将占用大约100 In的内存。我想知道ELKI是否处理这种数据负载？有人能确认你以前做过这种工作吗？

Answer 1

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

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

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

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

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

因为如果你决定从10万增加到100万，原始基体就会增长到2TB，当你达到1000万的时候，它将是200 TB。如果你想要双倍精度，那就加倍。

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

我对一切都使用索引。对于kNN或半径界限方法(对于光学，使用感测参数使索引有效！选择低感应器！)如果要重复使用这些查询，则可以预计算这些查询一次。

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