chapter  4
K-Medoids and Other Criteria for Crisp Clustering
ByDouglas Steinley
Pages 12

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 K -Medoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.2.2.1 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.2.2 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2.3 Choosing the Number of Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2.4 Advantages of K -Medoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.3 Example and Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Example: Classifying Animals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.2 Software Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.4 Other Crisp Clustering Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.4.1 K -Midranges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4.2 K -Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.5 Conclusion and Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

This chapter addresses crisp clustering techniques other than K -means, which was covered in the previous chapter. Primarily, focus is given to the K -medoids (e.g., p-median) approach to assigning observations to clusters. In addition to K -medoids clustering, a brief discussion of K -midranges and K -modes clustering is provided.