我正在做一些测试，对大量非常大的稀疏向量进行聚类，这些向量表示各种超文本文档的词频逆文档频率。考虑到数据集的比例，你建议用什么算法来聚类这些数据？向量的维度将 > 3·10 5并且向量的数量可能在 10 9左右。我看过 dbscan 和光学算法。集群的数量是未知的。如此高维的空间索引似乎很复杂。
问问题
2800 次
5 回答
4
使用简单的 K-means 聚类，我得到的结果几乎和其他任何东西一样好，而且它肯定比大多数替代方法都要快。我也通过成对聚集获得了不错的结果，但速度要慢一些。对于 K-means，您确实必须从一些估计的集群数量开始，但您可以在进行过程中通过算法对其进行调整。如果您发现两个聚类的均值过于接近，则可以减少聚类的数量。如果您发现变异范围过大的集群，您可以尝试更多集群。我发现 sqrt(N) 是一个合理的起点——但我通常从 10^7 个文档而不是 10^9 个文档开始。对于 10^9，稍微减少它可能是有意义的。
但是，如果由我来决定，我会非常努力地考虑从使用 Landmark MDS 之类的东西降低维度开始，然后进行聚类。
于 2009-10-08T19:12:56.807 回答
2
在对数据进行聚类时，我总是会按以下顺序至少尝试这两种算法：
K-Means：尝试尽可能多地调整结果。如果您可以让 K-Means 为您工作并提供不错的结果，那么您几乎肯定不会在使用任何其他算法时做得更好。
期望最大化：K-means 算法实际上被开发为 EM 算法的廉价且良好的替代方案。EM 算法理解起来更复杂，计算成本也更高，但 EM 的结果非常好。您可以了解更多关于 EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm的信息。EM 有一个 OpenCv 实现：http: //opencv.willowgarage.com/documentation/expectation-maximization.html
如果这两个的结果都不令人满意，我会开始寻找其他地方，但直到你都尝试过。
于 2009-10-08T22:10:41.973 回答
2
我听说语义散列取得了很好的效果。然而，深度信念网很难实现。您可能想尝试最小散列（尽管这是一种概率方法）或欧几里得空间的局部敏感散列。
通常，由于维度灾难和大多数项目彼此之间具有相似距离的事实，在如此高维空间中进行聚类是困难的。如果您事先通过 SOM 或 PCA 降低维度，则 K-Means 等标准方法可能会起作用。
于 2009-10-08T19:17:17.593 回答
1
决策树因在高维空间中高效工作而广受欢迎。查看通过决策树构建进行聚类。
此外，随机森林是非常高效的学习器，如果您想使用它，可以使用OpenCV 实现。
于 2009-10-08T19:13:09.863 回答
0
K-means 或期望最大化算法计算在具有高维度的大型数据集上非常昂贵。这里的文章描述了使用树冠聚类的高效预聚类：
通常，标准 K-means 或 EM 的二次时间复杂度对于大数据而言效率不高，而且对于不断增长的数据集也具有很好的可扩展性。而不是我会找出时间复杂度为 O(n) 或 O(n*log(n)) 的算法。
此外，K-means 不保证全局收敛，而是收敛到局部最小值。EM 总是收敛到全局最小值。EM 也可以在数学上从 K-means 推导出来作为它的概率变体。
于 2020-03-11T08:50:12.180 回答