# Why use K-medoids for sequence analysis?

In the package WeightedCluster there seems to be facilities for using K-medoids clustering (i.e. wcKMedoids()), but not the more common K-means. Some traditional recommendations of clustering specify that first one should determine the number of clusters using agglomerative clutering, e.g. Ward, and then create a final solution using K-means (Punj & Stewart, 1995).

Hence my question: why would K-medoids be more suitable than K-means for sequence analysis?

References

Punj, G., and Stewart, D. W. 1995. “Cluster Analysis in Marketing Research: Review and Suggestions for Application,” Journal of Marketing Research (20:2), pp. 134–148.

• Don't treat a marketing paper as authorative on whether to use k-means. Most likely, they simply never had heard of anything else... Jan 31, 2017 at 20:54
• Would you mind explaining what you mean by "sequence analysis"?
– whuber
Jan 31, 2017 at 21:57
• @whuber: Analyzing sequences using the TraMineR package. I guess the more appropriate question would be why data in the form of sequences might be better suited for K-medoids compared to K-means. I suspect the answer is that there is no "mean" sequence, but there is a medoid sequence. Jan 31, 2017 at 22:04

## 1 Answer

Standard K-means is intended for numeric data and is not directly applicable to other types of objects such as categorical sequences (see for example at that question.)

In sequence analysis, we generally compute pairwise dissimilarities between sequences using one of many possible different metrics (See [1] for a review.) Although we do not know what the mean of a cluster of sequences could be, we can express the distance to the (virtual) mean of the cluster in terms of pairwise distances between the cluster members (See for instance [2, page 478]). In this way, k-means should be applicable whenever we have a pairwise dissimilarity matrix. Nevertheless, for categorical sequences, pairwise-dissimilarity-based k-medoids is much easier to implement and should be much faster.

Now, regarding the choice of the number k of clusters. I don't think that determining k from the solution of a hierarchical clustering is the best way to proceed. Exploring the k-medoids solutions for a range of k values is much more efficient and it is very easily done with the wcKMedRange function of the WeightedCluster R library that returns a whole series of cluster quality measures for the requested set of values k.

[1] Studer, M., and Ritschard, G. (2016) "What Matters in Differences between Life Trajectories: A Comparative Review of Sequence Dissimilarity Measures", Journal of the Royal Statistical Society, Series A. Vol. 179(2), pp. 481-511 DOI 10.1111/rssa.12125.

[2] Studer, M., Ritschard, G., Gabadinho, A. & Müller, N.S. (2011), "Discrepancy Analysis of State Sequences", Sociological Methods and Research. Vol. 40(3), pp. 471-510. DOI 10.1177/0049124111415372