在大型数据集上进行聚类

Question

我正在尝试对一个大数据集（吉字节级别）进行聚类。为了进行聚类，需要计算每个点到其他每个点的距离，因此最终会得到一个N^2大小的距离矩阵，而对于我的数据集来说，这个矩阵的大小将达到exabytes级别。在Matlab中使用pdist方法很快就会出现问题。

有没有一种方法可以先对大数据集的子集进行聚类，然后再对相似的聚类进行合并？

我不知道这是否有所帮助，但数据是固定长度的二进制字符串，因此我正在使用汉明距离（距离=字符串1 XOR 字符串2）来计算它们之间的距离。

- Marcin

---

你的位串有多长？ - denis

128位、160位、256位……它们是密码哈希。我试图将其设置得足够通用，以便可以针对不同的哈希进行操作。是否有任何长度相关的技巧？ - Marcin

我几个月前有一个类似的问题。我想知道这个解决方案是否适用于你？https://dev59.com/aFHTa4cB1Zd3GeqPUs7F - Jie

@Jie，我在我的实验中走了完全不同的方向，但我会尝试一下，谢谢你的想法。 - Marcin

并非所有聚类算法都需要计算所有n^2个距离。例如，谱聚类方法建立在相似关系的传递性质上，允许使用非常稀疏的距离/亲和力矩阵进行聚类（实际上只计算了所有n^2个距离的一小部分）。如果这种方法对您的情况也适用，我很乐意提供更多细节。 - Shai

Answer 1

从Tabei等人的单个与多个排序在所有对相似性搜索中的比较中简化了一个好方法，例如对于Hammingdist 1的一对：

• 对前32位上的所有位串进行排序
• 查看其中前32位完全相同的字符串块；这些块将相对较小
• 对于Hammingdist（左32）0 + Hammingdist（其余部分）<= 1，计算每个这些块的pdist。

这会忽略大约32/128的附近对的一小部分，它们具有Hammingdist（左32）1 + Hammingdist（其余部分）0。如果您真的想要这些，请使用“第一个32” -> “最后一个32”重复上述过程。

该方法可以扩展。 以4个32位字的Hammingdist <= 2为例；不匹配必须分裂成以下之一： 2000 0200 0020 0002 1100 1010 1001 0110 0101 0011， 因此其中2个单词必须为0，排序相同。

（顺便说一下，sketchsort-0.0.7.tar是99％src/boost/，build/，.svn/。）

- denis

---

这听起来很有潜力，我会尝试并回报的，谢谢。 - Marcin

Marcin，请告诉我。如果有赏金，我可以拼凑出一个在给定的wordnos上快速执行std::sort的C++程序，但我不知道如何将其连接到Matlab。 - denis

Answer 2

LMW-tree项目中的EM-tree和K-tree算法可以对如此大甚至更大的问题进行聚类。我们最近的结果是将7.33亿个网页聚类成60万个簇。此外，还有一种流式变体的EM-tree，其中数据集在每次迭代时从磁盘流式传输。

此外，这些算法还可以直接对位串进行聚类，其中所有簇代表和数据点都是位串，并且使用的相似度度量是汉明距离。这样可以最小化每个簇内的汉明距离。

- Chris de Vries

Answer 3

怎么先对它们进行排序呢？也许可以使用一种修改过的归并排序算法？你可以从数据集中取出适合内存容量的块，进行普通排序。

一旦你有了排序好的数据，就可以迭代地进行聚类。也许可以保持一个N-1个点的滚动质心，并与读入的第N个点进行比较。然后根据你的聚类距离阈值，将其汇入当前聚类或开始一个新的聚类。

- Ashish Uthama

---

我尝试过排序，效果很好，但它只适用于从第一位开始的模式。如果你有一个从中间某处开始且前面有随机位的模式，那么排序就没有任何帮助了。这就是为什么我更愿意按海明距离进行。我想将字符串分成4个不同的块，并对它们进行排序，但然后你就会遇到模式不完全在块边界上开始的问题，所以你无法捕获所有可能的模式。 - Marcin

问题中的那一点信息会很有帮助：）。你不能按汉明距离而不是词汇顺序对它们进行排序吗？ - Ashish Uthama

我可以这样做，但首先我必须创建一个巨大的汉明距离矩阵，而这正是我一直试图避免的。 - Marcin

基于距离任意点的二进制排序怎么样？ - Ashish Uthama