Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Clustering partitions the data space into groups of points that are close together and far from other groups. K-means is the standard algorithm. Example: cluster Pokemon by Total and Speed.
Terms
Key words:
- K: the number of clusters we assume, chosen by us
- centroid: the centre of a cluster, its coordinates are the means of the points in it, e.g. (mean Total, mean Speed)
- labelling: giving each point the colour (cluster) of its nearest centroid
Algorithm
- Choose , the number of clusters (a parameter)
- Initialise: choose points from the dataset as starting centroids
- Assign: for each point, re-label it to the cluster of the nearest centroid
- Update: for each cluster, re-compute the centroid as the mean of its points
- Repeat steps 3 and 4 until the labels stop changing (convergence, the clusters are now stable)
Moving the centroids changes the partition, and the new partition moves the centroids again, which is why the loop is needed.
Limitations
Known weaknesses:
- the result depends heavily on the initial centroids, so a better initialisation strategy (e.g. k-means++, several random starts) converges faster and more reliably
- points join the "closest" centroid, which favours spherical clusters of similar size, often not true for real data
- must be chosen beforehand, see Elbow Method
- variables on very different scales should be standardised first, since distance is used
More Than Two Variables
With HP, Attack, Defense, Sp. Atk, Sp. Def and Speed, each centroid is a 6 dimensional point of means. Box plots of each variable per cluster then show what each cluster means, e.g. one cluster of high Defense Pokemon and another with high Attack and Sp. Atk. Optimality depends on whether the clusters can be interpreted.
Code
from sklearn.cluster import KMeans
X = pd.DataFrame(pkmndata[['Total', 'Speed']])
kmeans = KMeans(n_clusters=3, n_init=10)
kmeans.fit(X)
print(kmeans.cluster_centers_) # centroids
print(kmeans.inertia_) # within cluster sum of squares
labels = kmeans.predict(X)
X_labeled = X.copy()
X_labeled['Cluster'] = pd.Categorical(labels)
sb.scatterplot(x='Total', y='Speed', hue='Cluster', data=X_labeled)
sb.boxplot(x='Cluster', y='Total', data=X_labeled)