Is K-Medoids really better at dealing with outliers than K-Means? (with example showing the contrary)

K-Medoids and K-Means are two popular methods of partitional clustering. The consensus is that K-Medoids is better at clustering data when there are outliers (source). This is because it chooses data points as cluster centers (and uses Manhattan distance), whereas K-Means chooses any center that minimizes the sum of squares, so it is more influenced by outliers.

This makes sense, however when I use these methods to do a simple test on made up data, it does not suggest that using Medoids is better at dealing with outliers, in fact it is sometimes worse. My question is: Where in the following test have I gone wrong? Perhaps I have some fundamental misunderstanding about these methods.

Demonstration:

First, some made up data (named 'comp') which makes 3 obvious clusters

x <- c(2, 3, 2.4, 1.9, 1.6, 2.3, 1.8, 5, 6, 5, 5.8, 6.1, 5.5, 7.2, 7.5, 8, 7.2, 7.8, 7.3, 6.4)
y <- c(3, 2, 3.1, 2.6, 2.7, 2.9, 2.5, 7, 7, 6.5, 6.4, 6.9, 6.5, 7.5, 7.25, 7, 7.8, 7.5, 8.1, 7)

data.frame(x,y) -> comp

library(ggplot2)
ggplot(comp, aes(x, y)) + geom_point(alpha=.5, size=3, pch = 16) It is clustered with the package 'vegclust', which can do both K-Means and K-Medoids.

library(vegclust)
k <- vegclust(x=comp, mobileCenters=3, method="KM", nstart=100, iter.max=1000) #K-Means
k <- vegclust(x=comp, mobileCenters=3, method="KMdd", nstart=100, iter.max=1000) #K-Medoids

When making a scatterplot, both K-Means and K-Medoids pick up the 3 obvious clusters.

color <- k$memb[,1]+k$memb[,2]*2+k\$memb[,3]*3 # Making the different clusters have different colors

# K-Means scatterplot
ggplot(comp, aes(x, y)) + geom_point(alpha=.5, color=color, pch = 16, size=3)

# K-Medoids scatterplot
ggplot(comp, aes(x, y)) + geom_point(alpha=.5, color=color, size=3, pch = 16) Now an outlier is added:

comp[21,1] <- 3
comp[21,2] <- 7.5

This outlier shifts the center of the blue cluster to the left of the graph.

As a result, when using K-Medoids on the new data, the right-most point of the blue cluster is broken off and joins the red cluster. K-Medoids finds the correct clusters 0% of the time. Interestingly, K-means actually generates better (more intuitive) clusters with the new data about 25% of the time depending on the random initial cluster centers (you may have to run several times to get the correct clustering). As you can see from this example, K-Means was actually better at handling outliers than K-Medoids (same data, same package etc.). While K-Means wasn't always correct, K-Medoids was never correct. If a researcher studied this data and ran both K-Means and K-Medoids several times, then chose the best result from each, K-Means would have been better at dealing with the outlier.

Can someone explain these results? Have I done something wrong in my test or misunderstood how these methods work?

• This is a really interesting question, and I appreciate the amount of work you've put into studying it. I know it's been 3 years since you posted this, but have you found a suitable answer? If not, I'd like to open a bounty on this problem with my own reputation. – user3002473 Nov 22 '18 at 20:10
{"ft_lang_label":"__label__en","ft_lang_prob":0.8649668,"math_prob":0.91375357,"size":2791,"snap":"2019-43-2019-47","text_gpt3_token_len":871,"char_repetition_ratio":0.12845354,"word_repetition_ratio":0.01594533,"special_character_ratio":0.3009674,"punctuation_ratio":0.20658682,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9925904,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,1,null,1,null,1,null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-21T05:22:20Z\",\"WARC-Record-ID\":\"<urn:uuid:b810d5c7-14e3-4c31-bbe6-ec0e8f85df1d>\",\"Content-Length\":\"135195\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0254cfdd-a435-4023-a2c2-d5a126559068>\",\"WARC-Concurrent-To\":\"<urn:uuid:50b8e0df-9705-48da-b367-9c82c6eb8263>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://stats.stackexchange.com/questions/183220/is-k-medoids-really-better-at-dealing-with-outliers-than-k-means-with-example\",\"WARC-Payload-Digest\":\"sha1:YAXFFKXKSHGJQRSWSLQR3PXEFUJG5KPJ\",\"WARC-Block-Digest\":\"sha1:NFGIBTQLACYOWWVQHDNQ2BFX5KXVAPXU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987756350.80_warc_CC-MAIN-20191021043233-20191021070733-00499.warc.gz\"}"}