Paolo Giordani • Maria Brigida Ferraro • Francesca Martella
1 Introduction to Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Part II Standard Clustering
2 Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Distance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Agglomerative Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . 14
2.4 Divisive Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 agnes and hclust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.1 Case Study with Quantitative Data . . . . . . . . . . . . . . . . 18
2.5.2 Case Studies with Mixed Data . . . . . . . . . . . . . . . . . . . 33
2.5.3 One Further Case Study . . . . . . . . . . . . . . . . . . . . . . . . 44
2.6 Functions for Divisive Clustering . . . . . . . . . . . . . . . . . . . . . . . 65
2.6.1 diana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6.2 mona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3 Non-Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2 k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.3 k-Medoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.4 kmeans. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.4.1 Alternative Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.5 pam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.5.1 Plotting Cluster Solutions . . . . . . . . . . . . . . . . . . . . . . . 100
3.5.2 clara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.5.3 Alternative Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.6 Divisive k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4 Big Data and Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.1 Standard Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Part III Fuzzy Clustering
5 Fuzzy Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2 Fuzzy k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.1 Cluster Validity Indices . . . . . . . . . . . . . . . . . . . . . . . . 128
5.2.2 FKM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.2.3 cmeans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.2.4 fcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.2.5 fuzzy.CM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.3 Gustafson-Kessel Extensions of Fuzzy k-Means . . . . . . . . . . . . . 143
5.3.1 FKM.gk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.3.2 FKM.gkb and fuzzy.GK . . . . . . . . . . . . . . . . . . . . . . 152
5.4 Entropic Fuzzy k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
5.4.1 FKM.ent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.5 Fuzzy k-Means with Polynomial Fuzzifier . . . . . . . . . . . . . . . . . 158
5.5.1 FKM.pf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.6 Fuzzy k-Medoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.6.1 FKM.med . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.7 Fuzzy Clustering for Relational Data . . . . . . . . . . . . . . . . . . . . . 173
5.7.1 fanny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.7.2 NEFRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.8 Fuzzy k-Means with Noise Cluster . . . . . . . . . . . . . . . . . . . . . . 189
5.8.1 FKM.noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.9 Possibilistic k-Means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5.9.1 pcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.10 Hybrid (Fuzzy/Possibilistic) Clustering Methods . . . . . . . . . . . . . 198
5.10.1 fpcm, mfpcm and pfcm . . . . . . . . . . . . . . . . . . . . . . . 201
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208