我正在尝试对大型（千兆字节）数据集进行聚类。为了进行聚类，您需要每个点到每个其他点的距离，因此您最终会得到一个 N^2 大小的距离矩阵，在我的数据集的情况下，它的数量级为艾字节。Matlab 中的 Pdist 当然会立即爆炸；）
有没有办法先对大数据的子集进行聚类，然后再对类似的聚类进行一些合并？
我不知道这是否有帮助，但数据是固定长度的二进制字符串，所以我使用汉明距离（Distance=string1 XOR string2）计算它们的距离。
问问题
2065 次
3 回答
1
来自 Tabei 等人的 nice 方法的简化版本，Single vs Multiple Sorting in All Pairs Similarity Search，比如使用 Hammingdist 1 的对：
- 对前 32 位的所有位串进行排序
- 查看前 32 位都相同的字符串块；这些块将相对较小
- pdist 这些块中的每一个用于 Hammingdist(left 32) 0 + Hammingdist(the rest) <= 1。
这错过了例如 32/128 的附近对中 Hammingdist(left 32) 1 + Hammingdist(the rest) 0 的部分。如果你真的想要这些，请用“first 32”->“last 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/ 。）
于 2011-04-08T14:32:19.037 回答
0
先把它们分类怎么样？也许类似于修改后的合并排序？您可以从适合内存以执行正常排序的数据集块开始。
一旦你有了排序的数据，就可以迭代地进行聚类。也许保持 N-1 个点的滚动质心并与正在读入的第 N 个点进行比较。然后根据您的集群距离阈值，您可以将其汇集到当前集群中或开始一个新的集群。
于 2011-03-29T17:56:21.323 回答
0
LMW-tree项目中的 EM-tree 和 K-tree 算法可以将越来越大的问题聚类。我们最近的结果是将 7.33 亿个网页聚集成 600,000 个集群。还有一个 EM 树的流式变体，其中数据集在每次迭代时从磁盘流式传输。
此外，这些算法可以直接对位串进行聚类，其中所有聚类代表和数据点都是位串，并且使用的相似性度量是汉明距离。这最小化了找到的每个集群内的汉明距离。
于 2015-05-17T05:17:22.400 回答