A Sub-Quadratic Exact Medoid Algorithm
| Type of publication: | Idiap-RR |
| Citation: | Newling_Idiap-RR-19-2017 |
| Number: | Idiap-RR-19-2017 |
| Year: | 2017 |
| Month: | 7 |
| Institution: | Idiap |
| Abstract: | 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 weak assumptions, complexity 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 distances than state-of-the-art approximate algorithms. We show how trimed can be used as a component in an accelerated K-medoids algorithm, and how it can be relaxed to obtain further computational gains with an only minor loss in quality. |
| Keywords: | clustering, exact, k-medoids, medoid, scalable, sub-quadratic |
| Projects |
Idiap |
| Authors | |
| Added by: | [ADM] |
| Total mark: | 0 |
|
Attachments
|
|
|
|
|
Notes
|
|
|
|
|
