在大型数据集上进行聚类

Question

我正在尝试聚集一个大的(Gigabyte)数据集.为了进行聚类,您需要每个点到每个其他点的距离,因此最终得到一个N ^ 2大小的距离矩阵,在我的数据集中,它将是exabytes的数量级.Matlab中的Pdist当然会立即爆炸;)

有没有办法首先对大数据的子集进行聚类,然后可能会对类似的聚类进行一些合并？

我不知道这是否有帮助,但数据是固定长度的二进制字符串,所以我使用汉明距离计算它们的距离(Distance = string1 XOR string2).

Answer 1

先对它们进行排序怎么样？也许类似于修改后的合并排序？您可以从适合内存的数据集块开始执行正常排序。

一旦获得排序后的数据，就可以迭代地进行聚类。也许保留 N-1 个点的滚动质心，并与读入的第 N 个点进行比较。然后，根据您的簇距离阈值，您可以将其合并到当前簇中或启动一个新簇。