在Spark中使用Silhouette Clustering

Question

我想在Spark中使用KMeans群集时使用轮廓来确定k的最佳值.有没有最佳方式并行化这个？即使其可扩展

Answer 1

不，根据定义，轮廓不可缩放。

它使用成对距离，这总是需要 O(n^2) 时间来计算。

您将需要使用不同的东西。在大数据上使用Silhouette是荒谬的，计算评估度量比运行实际的k-means聚类算法花费的时间要长得多。

或者重新考虑你在做什么。例如，使用轮廓是否有意义。您还可以决定在单个节点上运行比 Spark 更快的东西，在那里计算轮廓，并通过k简单地并行化，而没有分布式计算的所有开销。Spark 可能会战胜 MapReduce-Mahout，但它会输给一个好的非分布式实现。

Answer 2

是的,有方法可以使剪影度量标准可扩展.没有它像我在这里描述的那样没有发表.它并不复杂,所以你也可以理解它,也许可以写出来.请让我知道,所以如果你先写它,我可以使用它.

看起来我们都需要写一个高性能的剪影得分手.输入任何群集列向量,使该记分器功能可以与每个群集实现一起使用.如果可能,请使用mapreduce以获得简单的分布式版本以及共享内存.看起来很可能.第4页显示了数学: http ://cran.us.r-project.org/web/packages/clValid/vignettes/clValid.pdf LSH可以帮助算法,因为它避免了主导数学的精确距离计算.一个好的LSH实现将是必不可少的,但我还没有找到.Sklearn的LSHForest是正确的想法,但实施得不够好.简化的轮廓或近似也很有趣.LSH包含将导致近似结果.使用LSH功能仅查找最近的点和质心,这避免了所有对计算.本文的第28页有几个很好的建议:https://arxiv.org/pdf/1605.01802.pdf 似乎说:使用简化的轮廓而不是简单的轮廓,如下所示:从点到点的距离改变计算距离指向群集质心.它是集群内所有点对和最近邻居集群的减少,即O(n ^ 2),直到线性长度O(N)计算.这是我的理解和翻译:

Start with:
File of cluster tuples: (clusterID, cluster centroid point) 
File of example point tuples: (example point, clusterID). Notice the clusterID is the clusterID column vector described above.
Processing:
For each cluster tuple, run a map(): hashmap[clusterID] = cluster centroid point
For each example point tuple, run:
map(): (dist = distance between point and its cluster centroid point, example point (copy), clusterID(copy))
map(): find closest cluster centroid point to the example point
map(): emit SSI = (distance - minClusterDistance)/minClusterDistance
reduce(): By clusterID emit (clusterID, cluster’s sum of SSI / #points)

我可能最终成为实施者.很疯狂没有人写过这样的快速之前.人们已经按照我的期望做到了这一点,但是他们为了竞争目的而保留自己(公司利润,Kaggle排名等).

以上格式为代码但不是代码.它是英文大纲或伪代码.stackoverflow强迫我将此部分格式化为接受它的代码.