-
Notifications
You must be signed in to change notification settings - Fork 0
/
cluster_validity.py
275 lines (184 loc) · 358 KB
/
cluster_validity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
# -*- coding: utf-8 -*-
"""Cluster Validity
Automatically generated by Colab.
Original file is located at
https://colab.research.google.com/drive/1P8PQNrrQQ5mdfETJEzAkFurO8AboRfL5
# Cluster Validity Using Multiple Validty Indices
Clustering is used to group similar objects together and seperate them from dissimilar objects. While there are several different clustering methods, most do not provide the optimal number of clusters. This parameter is usually user defined, which can be tricky to determine as too little clusters can cause oversimplify the data and too many can cause overfitting. Cluster validity indices (CVIs) are used to help address this problem and validate the quality of clustering alogrithms and to determine the optimal number of clusters. CVIs use the within-group scatter abd between-group scatter ti determine the quality of the clustering solution [1]. There are many different CVIs that all have their own advantages and weaknesses. In this study, 3 different CVIs will be applied to 2 datasets and the results will be compared with analysis previously done with Fuzzy C-means (FCM) and visual cluster assesement tendency (VAT) and improved VAT (iVAT) on the same datasets.
## Methods
There are many different cluster validity indices (CVIs). In this study, the Calinski-Harabasz (CH), the Davies-Bouldin (DB), the Silhouette coefficent index (SIL), and the Chou-Su-Lai (CS) indices will be used. The CH index is a classic and effective ratio-type index [1]. The cohesion is computed using the sum of the distances of the clusters to their respective centroids [1]. The separation is calculated by the sum of the distances from the centroids to the global prototype [1]. Cohesion for the DB is calculated using the mean distance of objects to their centroids and separation is the measurement between centroids [1]. The SIL calculates cohesion by taking the sum of the distances between all points in a cluster [1]. The sepration for this index is calculated using the nearest neighbor distance between points in different clusters [1]. The CS is also a ratio-type index.The CS measures cohesion using the cluster diameters and the separation is calculated using the nearest neighbor distance between prototypes [1]. This index is good for handling clusters with different densities and sizes [2]. A basic flow chart of the clustering process with validation using indices is shown below. The equations for the different indices are also shown below. In this study, the three indices described will be used to validate the clustering results for 2 datasets used in previous clustering studies.
### Importing Dataset
"""
#Upload first dataset
import matplotlib.pyplot as plt
import numpy as np
#Upload PGM
Image =plt.imread('/4cov.PGM')
print(Image.shape)
plt.imshow(Image);
#convert PGM to Numpy Array
from numpy import asarray
np_array= np.array(Image)
print(np_array.shape)
print(np_array)
"""### Calculate CH index for 4cov.PGM"""
#Calculate CH Index
from sklearn import cluster
from sklearn.cluster import KMeans
from sklearn import metrics
from sklearn.metrics import pairwise_distances
#Run K-means with 5 Clusters
kmeans= KMeans(n_clusters=5, random_state=1).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.calinski_harabasz_score(np_array, labels))
#Run K-means with 3 Clusters
kmeans= KMeans(n_clusters=3, random_state=0).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.calinski_harabasz_score(np_array, labels))
#Run K-means with 2 Cluster
kmeans= KMeans(n_clusters=2, random_state=0).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.calinski_harabasz_score(np_array, labels))
"""### Calculating Davies- Bouldin index for 4cov.PGM
"""
#Calculate CH Index
from sklearn import cluster
from sklearn.cluster import KMeans
from sklearn import metrics
from sklearn.metrics import pairwise_distances
#Run K-means with 5 Clusters
kmeans= KMeans(n_clusters=5).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.davies_bouldin_score(np_array, labels))
#Run K-means with 3 Clusters
kmeans= KMeans(n_clusters=3).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.davies_bouldin_score(np_array, labels))
#Run K-means with 2 Clusters
kmeans= KMeans(n_clusters=2).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.davies_bouldin_score(np_array, labels))
"""### Calculating Silhouette Index for 4cov.PGM"""
from sklearn.metrics import silhouette_score
#Run K-means with 5 Clusters
kmeans= KMeans(n_clusters=5).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.silhouette_score(np_array, labels))
#Run K-means with 3 Clusters
kmeans= KMeans(n_clusters=3).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.silhouette_score(np_array, labels))
#Run K-means with 2 Clusters
kmeans= KMeans(n_clusters=2).fit(np_array)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.silhouette_score(np_array, labels))
"""### Importing 2nd Dataset"""
#import 2nd dataset
import matplotlib.pyplot as plt
import numpy as np
#Upload PGM
Image =plt.imread('/Five_Clust.PGM')
print(Image.shape)
plt.imshow(Image);
#convert PGM to Numpy Array
from numpy import asarray
np_array_2 = np.array(Image)
print(np_array_2.shape)
print(np_array_2)
"""### CH index calculations for Five_Clust.PGM"""
#Calculate CH Index
from sklearn import cluster
from sklearn.cluster import KMeans
from sklearn import metrics
from sklearn.metrics import pairwise_distances
#Run K-means with 5 Clusters
kmeans= KMeans(n_clusters=5, random_state=0).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.calinski_harabasz_score(np_array_2, labels))
#Run K-means with 3 Clusters
kmeans= KMeans(n_clusters=3, random_state=0).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.calinski_harabasz_score(np_array_2, labels))
#Run K-means with 2 Clusters
kmeans= KMeans(n_clusters=2, random_state=0).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.calinski_harabasz_score(np_array_2, labels))
"""### Calculating DB Index for Five_Clust.PGM
"""
#Run K-means with 5 Clusters
kmeans= KMeans(n_clusters=5).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.davies_bouldin_score(np_array_2, labels))
#Run K-means with 3 Clusters
kmeans= KMeans(n_clusters=3).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.davies_bouldin_score(np_array_2, labels))
#Run K-means with 2 Clusters
kmeans= KMeans(n_clusters=2).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.davies_bouldin_score(np_array_2, labels))
"""### Calculating Silhouette Index for Five_Clust.PGM
"""
from sklearn.metrics import silhouette_score
#Run K-means with 5 Clusters
kmeans= KMeans(n_clusters=5).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.silhouette_score(np_array_2, labels))
#Run K-means with 3 Clusters
kmeans= KMeans(n_clusters=3).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.silhouette_score(np_array_2, labels))
#Run K-means with 2 Clusters
kmeans= KMeans(n_clusters=2).fit(np_array_2)
#Store Cluster Labels
labels=kmeans.labels_
#Print CH Score
print(metrics.silhouette_score(np_array_2, labels))
"""## Results
For the 4cov.PGM dataset, the CH scores were as follows: for 5 clusters 7.909, 3 clusters 16.698, and 2 clusters 20.97. The DB index scores were 3.485, 3.93, and 2.935 for 5,3, and 2 clusters respectively. The silhouette index scores were 0.244, 0.256, and 0.257 for 5, 3, and 2 clusters respectively.
The five_clust.PGM dataset had CH scores for 3.348, 5.953, and 8.583 for 5, 3, and 2 clusters respectively. The DB scores were 2.605, 3.858, and 4.605 for 5, 3, and 2 clusters respectively. The silhouette index scores were 0.119, 0.070, and 0.174 for 5, 3, and 2 clusters respectively. Results for the previous studies using VAT, iVAT and FCM showed 1 cluster to be the ideal number for both datasets.
## Discussion and Conclusions
The CH scores for the first dataset indicate that 2 clusters is the optimal amount since it has a higher score than the other cluster numbers. A higher score indicates that the clusters are dense and well seperated. Although, all CH scores were relatively low and below 25. The DB scores for different cluster numbers were all within 1 of each other, which indicates that all DB scores may be poor. Still, 2 clusters had the lowest score of the 3 different cluster numbers, indicating that 2 clusters are better seperated and more compact than the other options. All of the silhouette scores were fairly similar for the first dataset, within 0.02 of one another. Unfortunately, that means this measure does not really give any insight into which number of clusters is optimal. The VAT and iVAT clustering done previously suggested that 1 cluster was the ideal number of clusters for this dataset. The FCM clustering also had similar results. A cluster value of 1 is not really a cluster, so based on the results from this cluster validity analysis 2 clusters appears to be the ideal number.
The CH scores for the second dataset also indicated that 2 clusters was the optimal number since it had the highest score of the cluster numbers. The DB scores for the second dataset showed that 5 clusters had the lowest score, thus indicating that 5 clusters is the optimal number of clusters. 2 clusters had the highest DB score, which contradictes with previous findings from the FCM and VAT and iVAT results which indicated that 1 cluster was the ideal number. The silhouette score for 5, 3, and 2 clusters are all below 0.2, indicating that none of these cluster values are the optimal number. A SIL score closer to 1 would indicate a better match. Based on the results from this analysis, 2 clusters seems to be the better match. Previous analysis done using VAT and iVAT suggested only 1 cluster present in the data. FCM clustering had similar results to VAT and iVAT. Based on the scores from this analysis, 2 clusters seems to be ideall. However, a reasonable amount of error should be accounted for.
The VAT and iVAT analysis done on both datasets previously had white lines present throughout the mapping, suggesting there may have been an issue with this analysis. The FCM plots only showed 1 large dot for all cluster number variations. Given this, I beleive there is an issue in the code. Since the conversion of the PGM to a numpy array has been consistent throughout the different analyses, this leads me to believe this is where the issue may be. Additionally, the CS index was not used in this analysis due to finding insufficent research on the topic and the paper from the authors of this method was not open source. The SIL method was implemented in its place.
In conclusion, the results from this valadation analysis suggest that 2 clusters is the ideal number for both datasets. A deeper dive into previous analyses is needed to conclusively say this is the ideal number as all previous analyses on these datasets have raised questions and potential issues with the data conversion.
## References
[1] José-García, A., & Gómez-Flores, W. (2021). A survey of cluster validity indices for automatic data clustering using differential evolution. Proceedings of the Genetic and Evolutionary Computation Conference. https://doi.org/10.1145/3449639.3459341
[2] Wiroonsri, N. (2024). Clustering performance analysis using a new correlation-based cluster validity index. Pattern Recognition, 145, 109910. https://doi.org/10.1016/j.patcog.2023.109910
"""