We present a new algorithm, ‘trimed’ for obtaining the medoid of a set, that is the element of the set which minimises the mean distance to all other elements. The algorithm is shown to have, under certain assumptions, expected run time $O(N^(3/2))$ in $R^d$ where N is the set size, making it the first sub-quadratic exact medoid algorithm for $d > 1$. Experiments show that it performs very well on spatial network data, frequently requiring two orders of magnitude fewer distance calculations than state-of-the-art approximate algorithms. As an application, we show how trimed can be used as a component in an accelerated K-medoids algorithm, and then how it can be relaxed to obtain further computational gains with only a minor loss in cluster quality.
展开▼
机译：我们提出了一种新算法“ trimed”，用于获取集合的medoid，这是集合中的元素，可最大程度地减少与所有其他元素的平均距离。在某些假设下，该算法显示出在$ R ^ d $中具有预期的运行时间$ O（N ^（3/2））$，其中N是集合大小，从而使其成为第一个用于二次二次精确精确分类的算法$ d> 1 $。实验表明，它在空间网络数据上的性能非常好，与最新的近似算法相比，距离计算通常需要少两个数量级。作为一个应用程序，我们展示了如何将修剪后的元素用作加速的K-medoids算法的组成部分，然后如何放宽修剪条件，以在群集质量仅有很小损失的情况下获得进一步的计算增益。
展开▼
