2

我有自己的基于 java 的集群实现（knn）。但是我面临可扩展性问题。我不打算使用 Mahout，因为我的要求非常简单，而且 mahout 需要大量工作。我正在寻找基于 java 的 Canopy 集群实现，我可以将其插入我的算法并进行并行处理。

基于 Mahout 的 Canopy 库与向量和索引相结合，不适用于纯字符串。如果您知道我可以使用简单库在字符串上使用树冠聚类的方式，它将解决我的问题。

我的要求是将字符串列表（比如 10K）传递给 Canopy 聚类算法，它应该返回基于 T1 和 T2 的子列表。

4

3 回答 3

2

Canopy 聚类主要用作并行化的预处理步骤。我不确定它会让你在一个节点上获得多少。我认为您不妨立即计算实际算法，或者构建一个索引，例如 M-tree。

Canopy 集群的优势在于您可以在多个节点上独立运行它，然后将它们的结果重叠。

还要检查它是否真的与您的方法兼容。我认为树冠可能需要度量属性才能正确。您的字符串距离是适当的度量（即三角不等式）吗？

于 2012-11-08T07:16:44.040 回答
1

10,000 个数据点，如果这就是您所关心的，那么标准 k-means 应该没有问题。在考虑树冠聚类（实际上是为数百万甚至数十亿的示例而设计的）之前，我会先考虑优化它。您可能错过了一些事情：

  • 预先计算每个字符串的特征向量。不要在每次要将 s_1 与 s_2 或 s_1 与集群质心进行比较时都这样做
  • 您只需将汇总统计信息保存在内存中：分配给集群的所有点的总和以及分配给集群的点数。完成迭代后，将总和除以 ns，就得到了新的质心。
  • 你的特征空间的维度是多少？请注意，您应该使用距离度量，其中两个向量都为零的维度没有影响，因此您只需要计算非零维度。将您的点存储为稀疏向量以促进这一点。

你能做一些分析并确定你的实现中的瓶颈在哪里吗？我对您关于 Mahout 无法使用纯字符串的评论感到有些困惑。

于 2012-11-08T10:01:42.213 回答
1

您应该尝试一下ELKI中的聚类算法。很抱歉如此无耻地宣传我密切相关的项目。但它是以可比方式实现的最大的聚类和异常值检测算法集合。（如果您采用某些R 包中可用的所有聚类算法，您最终可能会得到更多算法，但由于实现差异，它们不会真正具有可比性）

基准测试显示同一算法的不同实现存在巨大的速度差异。请参阅我们的基准测试网站，了解即使在诸如 k-means 之类的简单算法上，性能也会有多少变化。

我们还没有 Canopy Clustering。原因是它更像是一个预处理索引，而不是一个聚类算法。有点像 M-tree 或 DBSCAN 聚类的原始变体。然而，我们希望看到一个贡献的树冠聚类作为这样的预处理步骤。

到目前为止，ELKI 处理字符串的能力也受到了一些限制。您可以很好地加载典型的 TF-IDF 向量，我们对稀疏向量类和相似函数进行了一些优化。不过，他们还没有完全利用 k-means 的稀疏性，而且也没有球形 k-means。但是，为什么不能期望稀疏向量上的 k-means 结果非常有意义，原因有很多。它更像是一种启发式。

但是，如果您可以尝试解决您的问题并报告您的经验，那将会很有趣。与您的实施相比，性能是否具有竞争力？我们希望看到用于文本处理的贡献模块，例如进一步优化的相似性函数，或球形 k-means 变体。

更新： ELKI 现在实际上包括 CanopyClustering：CanopyPreClustering（届时将成为 0.6.0 的一部分）。但截至目前，它只是另一种聚类算法，尚未用于加速其他算法，例如 k-means。我需要检查如何最好地将它用作某种索引来加速算法。如果您设置 T1=epsilon 和 T2=0.5*T1，我可以想象它也有助于加快 DBSCAN。CanopyClustering 恕我直言的最大问题是如何选择一个好的半径。

于 2012-12-31T14:56:05.653 回答