JuliaStats/Clustering.jl — pull request #22 by cyocum (2014-05-25 17:34:33+00:00)
Title: New Implementation of k-medoids

This implementation is based on the algorithm given in the paper "A simple and fast algorithm for K-medoids clustering" by Hae-Sang Park, Chi-Hyuck Jun (http://dx.doi.org/10.1016/j.eswa.2008.01.039). This version scales better and is faster than the original (PAM) for large datasets.

In our tests, this algorithm took ~0.25 seconds to cluster on a 500 object dataset vs. ~1.80 seconds for the original. With a 10,000 object dataset, it was ~1.2 seconds vs. ~66 seconds for the original version.

Additionally, the original implementation was an intersection of three subtly different version of the PAM algorithm and it suffered from a bug which occasionally produced empty clusters.