algorithm - 制作距离矩阵或重复计算距离

Question

我正在研究 K-medoids algorithm执行。它是一种聚类算法，其步骤之一包括找到聚类中最具代表性的点。

原来是这样

• 我有一定数量的集群
• 每个簇包含一定数量的点
• 我需要在每个聚类中找到错误最少的点，如果它被选为聚类代表的话
• 需要计算集群中每个点到所有其他点的距离
• 这种距离计算可以像欧几里得那样简单，也可以像两个信号之间的 DTW(动态时间扭曲)一样复杂

有两种方法，一种是计算距离矩阵，将保存数据集中所有点之间的值，另一种是在聚类时计算距离，结果会重复计算某些点之间的距离。

一方面，要构建距离矩阵，您必须计算整个数据集中所有点之间的距离，并且永远不会使用某些计算值。

另一方面，如果你不建立距离矩阵，你会在一定的迭代次数中重复一些计算。

哪种方法更好？

我也在考虑 MapReduce 的实现，所以也欢迎从这个角度提出意见。

谢谢

Answer 1

第三种方法可以是两者的结合，并且懒惰地评估距离矩阵。使用默认值(不切实际的值，如负值)初始化矩阵，当您需要计算两点之间的距离时，如果值已经存在于矩阵中 - 只需从中取出即可。否则，对其进行计算并将其存储在矩阵中。

这种方法以计算(并且在执行尽可能少的对计算数量方面是最佳的)换取代码中的更多分支和更多指令。但是，由于分支预测器，我认为这种开销不会那么显着。
我预计当计算量相对较大时，它会有更好的性能。

它的另一个优化可能是当已经计算的数量超过某个阈值时，动态切换到普通矩阵实现(并计算矩阵的剩余部分)。这可以在 OOP 语言中很好地实现，方法是在满足特定阈值时切换接口(interface)的实现。

实际上哪个更好的实现将在很大程度上依赖于距离函数的成本，以及您正在聚类的数据，因为有些数据集需要比其他数据集更频繁地计算相同的点。
我建议做一个基准测试，并使用statistical tools评估哪种方法实际上更好。