8

我一直在尝试聚集一些更大的数据集。由 50000 个维度为 7 的测量向量组成。我正在尝试生成大约 30 到 300 个集群以进行进一步处理。

我一直在尝试以下集群实现，但没有成功：

  • Pycluster.kcluster（在我的数据集上只给出 1-2 个非空集群）
  • scipy.cluster.hierarchy.fclusterdata（运行时间过长）
  • scipy.cluster.vq.kmeans（内存不足）
  • sklearn.cluster.hierarchical.Ward（运行时间过长）

还有其他我可能会错过的实现吗？

4

5 回答 5

11

50000 个实例和 7 个维度并不是很大，也不应该扼杀一个实现。

虽然它没有 python 绑定，但试试ELKI 。他们在主页上使用的基准集是 8 个维度的 110250 个实例，他们显然在 60 秒内运行 k-means，在 350 秒内运行更高级的 OPTICS。

避免层次聚类。它实际上只适用于小型数据集。它通常在矩阵运算上实现的方式是O(n^3)，这对于大型数据集来说确实很糟糕。所以我对这两个超时并不感到惊讶。

使用索引支持实现的 DBSCAN 和 OPTICS 是O(n log n). 当天真地实施时，它们在O(n^2). K-means 确实很快，但结果往往不尽如人意（因为它总是在中间分裂）。它应该运行在O(n * k * iter)通常不会在太多迭代中收敛的地方 ( iter<<100)。但它只适用于欧几里得距离，并且不适用于某些数据（高维、离散、二进制、不同大小的集群......）

于 2012-06-19T06:06:18.593 回答
6

由于您已经在尝试 scikit-learn:应该比多核机器上的并行拟合sklearn.cluster.KMeans更好并且支持并行拟合。更好，但不会为您随机重启。WardMiniBatchKMeans

>>> from sklearn.cluster import MiniBatchKMeans
>>> X = np.random.randn(50000, 7)
>>> %timeit MiniBatchKMeans(30).fit(X)
1 loops, best of 3: 114 ms per loop
于 2012-06-19T08:42:14.590 回答
3

我的包装牛奶很容易解决这个问题：

import milk
import numpy as np
data = np.random.rand(50000,7)
%timeit milk.kmeans(data, 300)
1 loops, best of 3: 14.3 s per loop

我想知道你是否打算写 500,000 个数据点，因为 50,000 个点并没有那么多。如果是这样，牛奶需要更长的时间（约 700 秒），但仍然可以很好地处理它，因为它不会分配除您的数据和质心之外的任何内存。

于 2012-09-21T16:50:05.853 回答
0

OpenCV 有一个 k-means 实现，Kmeans2

预期运行时间约为O(n**4)- 对于数量级的近似值，请查看聚类 1000 个点需要多长时间，然后将其乘以 700 万（50**4 向上舍入）。

于 2012-06-19T02:16:25.120 回答
0

对于实际大规模情况的真正答案是使用诸如 FAISS 之类的东西，它是 Facebook Research 的库，用于高效的相似性搜索和密集向量的聚类。

见 https://github.com/facebookresearch/faiss/wiki/Faiss-building-blocks:-clustering,-PCA,-quantization

于 2021-07-13T23:10:20.677 回答