我想使用ELKI中的OPTICS算法对10万个点进行聚类。我有一个包含大约50亿个条目的上三角距离矩阵。对于ELKI需要的矩阵格式，内存占用将达到约100GB。我想知道ELKI是否能处理这种数据量？有谁能确认之前是否成功处理过这种情况？
回答：
我经常使用ELKI处理10万到1000万个点的数据集。
然而，为了提高速度，你应该使用索引。
显然，任何基于密集矩阵的方法，最好的情况下也会达到O(n^2)的复杂度，并且需要O(n^2)的内存。这就是为什么我无法用R、Weka或scipy处理这些数据集的原因。它们通常会先尝试计算完整的距离矩阵，然后要么在计算过程中失败，要么在计算过程中耗尽内存，要么因为负的分配大小而失败（当你的数据集超过2^31个正整数，即大约46000个对象时，Weka会这样）。
在二进制格式下，使用浮点精度，ELKI的矩阵格式应该大约是100000*99999/2*4 + 4字节，可能还需要再加上4字节用于大小信息。这就是20 GB。如果你使用“易于使用”的ascii格式，确实会更大。但如果你使用gzip压缩，最终大小可能会大致相同。通常gzip可以将此类数据压缩到原始大小的10-20%。根据我的经验，gzip压缩的ascii格式可以和二进制编码的双精度数一样小。二进制格式的主要好处是它实际上会存储在磁盘上，内存缓存将由你的操作系统处理。
无论如何，我建议从一开始就不计算距离矩阵。
因为如果你决定从10万增加到100万，原始矩阵将增长到2 TB，当你增加到1000万时，它将达到200 TB。如果你想要双精度，再翻倍。
如果你使用距离矩阵，你的方法将至少是O(n^2)的复杂度，因此无法扩展。避免从一开始就计算所有成对距离是一个重要的速度因素。
我对所有事情都使用索引。对于kNN或半径限定方法（对于OPTICS，使用epsilon参数使索引有效！选择一个低的epsilon！），如果你需要反复使用这些查询，你可以预先计算这些查询。
在一个我经常使用的数据集上，有75000个实例和27个维度，存储预计算的101个最近邻居+平局的文件，使用双精度，是81 MB（注意：这可以看作是一个稀疏的相似性矩阵）。通过使用索引来预计算这个缓存，只需几分钟就能计算出来；然后我可以在75000个数据集上运行大多数基于kNN的算法，例如在108毫秒内运行LOF（加载kNN缓存需要262毫秒+解析原始输入数据2364毫秒，总运行时间为3秒；主要由解析双精度值所主导）。
