制作距离矩阵或重复计算距离
To make a distance matrix or to repeatedly calculate distance
我正在 K-medoids algorithm 实施。它是一种聚类算法，其步骤之一包括找到聚类中最具代表性的点。
所以，事情是这样的
- 我有一定数量的集群
- 每个簇包含一定数量的点
- 我需要在每个聚类中找到错误最少的点，如果它被选为聚类代表
- 需要计算集群中每个点到所有其他点的距离
- 这个距离计算可以像欧几里德那样简单，也可以像两个信号之间的 DTW（动态时间扭曲）一样复杂
有两种方法，一种是计算距离矩阵，保存数据集中所有点之间的值，另一种是在聚类时计算距离，结果会重复计算一些点之间的距离。
一方面，要构建距离矩阵，您必须计算整个数据集中所有点之间的距离，并且永远不会使用某些计算值。
另一方面，如果你不建立距离矩阵，你会在一定的迭代次数中重复一些计算。
哪种方法更好？
我也在考虑实现MapReduce，所以也欢迎从这个角度提出意见。
谢谢
第三种方法可以是两者的结合，并且懒惰地评估距离矩阵。使用默认值（不切实际的值，如负值）初始化矩阵，当您需要计算两点之间的距离时，如果值已经存在于矩阵中 - 只需从中取出即可。
否则，计算它并存储在矩阵中。
这种方法以计算为代价（并且在进行尽可能少的配对计算方面是最佳的），用于代码中的更多分支和更多指令。但是，由于分支预测器，我认为这种开销不会那么显着。
我预计当计算量相对较大时它会有更好的性能。
它的另一个优化可能是当已经计算的数量超过某个阈值时，动态切换为普通矩阵实现（并计算矩阵的剩余部分）。这可以在 OOP 语言中很好地实现，方法是在满足特定阈值时切换接口的实现。
实际上哪个更好的实现将在很大程度上取决于距离函数的成本，以及您正在聚类的数据，因为有些数据集需要比其他数据集更频繁地计算相同的点。
我建议做一个基准测试，然后使用 statistical tools 来评估哪种方法实际上更好。
我正在 K-medoids algorithm 实施。它是一种聚类算法，其步骤之一包括找到聚类中最具代表性的点。
所以，事情是这样的
- 我有一定数量的集群
- 每个簇包含一定数量的点
- 我需要在每个聚类中找到错误最少的点，如果它被选为聚类代表
- 需要计算集群中每个点到所有其他点的距离
- 这个距离计算可以像欧几里德那样简单，也可以像两个信号之间的 DTW（动态时间扭曲）一样复杂
有两种方法，一种是计算距离矩阵，保存数据集中所有点之间的值，另一种是在聚类时计算距离，结果会重复计算一些点之间的距离。
一方面，要构建距离矩阵，您必须计算整个数据集中所有点之间的距离，并且永远不会使用某些计算值。
另一方面，如果你不建立距离矩阵，你会在一定的迭代次数中重复一些计算。
哪种方法更好？
我也在考虑实现MapReduce，所以也欢迎从这个角度提出意见。
谢谢
第三种方法可以是两者的结合，并且懒惰地评估距离矩阵。使用默认值（不切实际的值，如负值）初始化矩阵，当您需要计算两点之间的距离时，如果值已经存在于矩阵中 - 只需从中取出即可。 否则，计算它并存储在矩阵中。
这种方法以计算为代价（并且在进行尽可能少的配对计算方面是最佳的），用于代码中的更多分支和更多指令。但是，由于分支预测器，我认为这种开销不会那么显着。
我预计当计算量相对较大时它会有更好的性能。
它的另一个优化可能是当已经计算的数量超过某个阈值时，动态切换为普通矩阵实现（并计算矩阵的剩余部分）。这可以在 OOP 语言中很好地实现，方法是在满足特定阈值时切换接口的实现。
实际上哪个更好的实现将在很大程度上取决于距离函数的成本，以及您正在聚类的数据，因为有些数据集需要比其他数据集更频繁地计算相同的点。
我建议做一个基准测试，然后使用 statistical tools 来评估哪种方法实际上更好。