How to evaluate the K-Modes Clusters?
The are some techniques to choose the number of clusters K.

The most common ones are The Elbow Method and The Silhouette Method.

Elbow Method

In this method, you calculate a score function with different values for K. You can use the Hamming distance like you proposed, or other scores, like dispersion.

Then, you plot them and where the function creates "an elbow" you choose the value for K.



Silhouette Method

This method measure the distance from points in one cluster to the other clusters. Then visually you have silhouette plots that let you choose K.

Observe:

K=2, silhouette of similar heights but with different sizes. So, potential candidate.


K=3, silhouettes of different heights. So, bad candidate.


K=4, silhouette of similar heights and sizes. Best candidate.