motiwari

Definitely possible, but it would require some extensions to the algorithm. More specifically, as new datapoints enter the stream, they could be compared with the existing medoids to see if swapping them would lower the clustering loss.

This would be a nontrivial engineering effort and I likely won't be able to do it myself (I'm a PhD student about to graduate), but if you or your team is interested in adapting BanditPAM to the streaming setting, please feel free to reach out! My email's [email protected]

Where is this benchmark from? We'd be happy to run BanditPAM on these datasets and report the results

A strength if you're strictly looking to minimize squared L2 loss from each point to its closest mean -- but for a lot of other applications, it's a weakness! As the other poster mentioned, with KMedoids you can use arbitrary loss functions and cluster exotic objects (not restricted to metrics on a vector space)

You got me! As @dang mentioned, once I got feedback from him I was allowed to repost and enter the second-chance pool

(My real first post was submitted too hastily without receiving @dang's feedback)

Hey, thanks! Shout out to Daniel @ HN who gave me a lot of great feedback on how to make this post better.

One thing that's important to note is that k-medoids supports arbitrary distance metrics -- in fact, your dissimilarity measure need not even be a metric (it can be negative, asymmetric, not satisfy the triangle inequality, etc.)

An implication of this is that if you were to do some invertible data transformation and then perform clustering, that's equivalent to doing clustering with a different dissimilarity measure (without the data transformation in the first place). It should be possible to avoid doing the invertible data transformation in the first place if you're willing to engineer your dissimilarity measure.

Without more details, it's hard to say exactly what would happen to the clustering results under custom dissimilarity measures or data transformations -- but our package supports both use cases!

Interesting, thanks for the references! I'm not too familiar with this line of work; let me read up on it and get back to you

Oh cool, neat trick, thanks!

Thank you for the positive feedback! Will definitely take you up on that coffee next time I visit Ilan :)

To answer your questions:

1. When looking at k-medoids algorithms, we realized that PAM hadn't been improved since the 80s! Other, faster algorithms had been developed but sacrificed solution quality (clustering loss) for speed. Simultaneously, prior work from my coauthors had recognized that the 1-medoid problem could be solved via randomized algorithms/multi-armed bandit -- much faster but returning the same solution. Our key insight was that every stage of PAM could be recast as a multi-armed bandit problem, and that reusing information across different stages would result in further speedups.

2. Actually, the complexity guarantees/theory were pretty easy because we were able to use proof techniques that are common in the multi-armed bandit literature. The hardest part was implementing it in C++ and making it available to both Python and R via bindings. For the original paper we did everything in Python and measured sample complexity, but to make the algorithm valuable for users we had to implement it in a more performant language.

3. To be honest, this project came about from a chance meeting at a conference (ICML 2019). I was randomly introduced to Martin Zhang (ironically I met him first at the conference even though we were both at Stanford). Martin and Ilan had deep expertise in multi-armed bandits/randomized algorithms (and solved the 1-medoid problem), and I got really interested in their work when talking with them, primarily because it seemed like a straightforward win and useful for a lot of people.