Mar*_*rko 12 algorithm hadoop mapreduce
我正在研究K-medoids算法的实现.它是一种聚类算法,其中一个步骤包括在群集中查找最具代表性的点.
所以,这就是事情
有两种方法,一种是计算距离矩阵,它将在数据集中的所有点之间保存值,另一种是计算聚类期间的距离,这将导致重复计算某些点之间的距离.
一方面,要构建距离矩阵,您必须计算整个数据集中所有点之间的距离,并且永远不会使用某些计算值.
另一方面,如果不构建距离矩阵,则将在特定次数的迭代中重复某些计算.
哪种方法更好？
我也正在考虑MapReduce的实现,所以也欢迎来自这个角度的意见.
谢谢
第三种方法可以是两者的组合，并且延迟评估距离矩阵。使用默认值（不切实际的值，如负值）初始化一个矩阵，当您需要计算两点之间的距离时，如果这些值已经存在于矩阵中 - 只需从中取出它即可。否则，计算它并将其存储在矩阵中。
这种方法通过计算（并且在执行尽可能少的对计算时是最佳的）来换取代码中的更多分支和更多指令。然而，由于分支预测器的存在，我认为这种开销不会那么严重。
我预计当计算量相对较大时它会有更好的性能。
它的另一个优化可能是当已计算的数量超过某个阈值时动态切换为普通矩阵实现（并计算矩阵的剩余部分）。在 OOP 语言中，通过在满足某个阈值时切换接口的实现，可以很好地实现这一点。
实际上哪个更好的实现将在很大程度上依赖于距离函数的成本以及您正在聚类的数据，因为有些数据需要比其他数据集更频繁地计算相同的点。
我建议做一个基准测试，并使用统计工具来评估哪种方法实际上更好。
| 归档时间： |
|
| 查看次数： |
902 次 |
| 最近记录： |