I am sure that many can argue that the "optimal number of clusters" is subjective and depends on your goals from the clustering process.Silhouette analysis gives you a simple way to make your judgement. Typically you will choose the number of clusters associated with the highest silhouette value but this can be tricky because the difference in silhouette values between X and Y clusters can be very negligible. Have you tried generating silhouette plots? The silhouette plots will let you visualize the clustered data with respect to their assigned cluster proximity, on a -1 to 1 scale with the cluster numbers on the vertical axis. Ideally,  if you have 100% separable N clusters, then your plot should look like N  semi-rectangular shapes with lengths of 1 and no noise on the [-1,0] scale.Of course, this won't be the case, but you can look at the silhouette plots for different number of clusters and judge visually which plot produces the least noise on the negative scale while at the same one approaches the +1 for most clusters on the right side.

Another general rule, If you find that X and X+1 clusters are the best 2 options. then perhaps you should go with X, since the addition of 1 more cluster does not really add considerable value. But again this depends on your purpose, are you looking for very fine segregation? then go with X+1 and hope that it won't results in many  mistakes (like data assigned to cluster A when it should be in B).

Another strategy is to compute the error using cluster validity indices and generate a 2-axes plot with the error on 1 axis with the smallest cluster size (smallest number of individual grouped in a cluster)  on the 2nd axis. the x-axis is for the number of clusters. The usefulness of this plot is that you can look for a "breakeven" where you are interested in avoiding clusters of very small size.

One other thing you can try doing is to use a different method for clustering than K-modes. For instance, Fuzzy C-means, and look whether the data are clustered differently then based on your observation make a subjective judgement about the number of really distinctive clusters

.

there is not really such a thing as "the optimal number of clusters" in k-modes (as in k-means) ; your best choice (stress : YOUR best choice ...) is the result of a compromise between the simplicity of your model (few clusters but low specificity) and its descriptive performance (many clusters with large specificity)

maybe your elbow plot could perhaps be made nicer (smoother) by replicating your experiments for each number of clusters and plotting the mean

and for one experiment, you could report the result of a cross-validated estimate of the mean reconstruction error (instead of just the value of the reconstruction error)

.

Have you identified what 'optimum' means for this problem?

I have used min/max pointcount within a cluster, min/max cluster diameter, min/max point distance within any cluster, distance between cluster centroids, distance between cluster edges, cluster perimeter distance and one time clustering clusters then identifying clumps within each cluster.

I would suggest re-examining the proposed distance relationship and what it means to your data.

You can also try Calinski-Harabasz criterion which computes the ration of between-cluster variance to within-cluster variance for a given k. 

I recently encountered such a case where for every k-estimation technique I used there was no clear answer. Have you considered the case that your data might actually be quite homogeneous i.e. all observations exhibit high similarity and no specific clustering could be achieved? To check for this, you can append your data with a chunk of observations that you know is different from your current set and then try to redo the elbow plot. If you get a clear elbow point at k = 2 clusters, then that will suggest that your original observations are indeed very homogeneous.  

I am sure that many can argue that the "optimal number of clusters" is subjective and depends on your goals from the clustering process.Silhouette analysis gives you a simple way to make your judgement. Typically you will choose the number of clusters associated with the highest silhouette value but this can be tricky because the difference in silhouette values between X and Y clusters can be very negligible. Have you tried generating silhouette plots? The silhouette plots will let you visualize the clustered data with respect to their assigned cluster proximity, on a -1 to 1 scale with the cluster numbers on the vertical axis. Ideally,  if you have 100% separable N clusters, then your plot should look like N  semi-rectangular shapes with lengths of 1 and no noise on the [-1,0] scale.Of course, this won't be the case, but you can look at the silhouette plots for different number of clusters and judge visually which plot produces the least noise on the negative scale while at the same one approaches the +1 for most clusters on the right side.

Another general rule, If you find that X and X+1 clusters are the best 2 options. then perhaps you should go with X, since the addition of 1 more cluster does not really add considerable value. But again this depends on your purpose, are you looking for very fine segregation? then go with X+1 and hope that it won't results in many  mistakes (like data assigned to cluster A when it should be in B).

Another strategy is to compute the error using cluster validity indices and generate a 2-axes plot with the error on 1 axis with the smallest cluster size (smallest number of individual grouped in a cluster)  on the 2nd axis. the x-axis is for the number of clusters. The usefulness of this plot is that you can look for a "breakeven" where you are interested in avoiding clusters of very small size.

One other thing you can try doing is to use a different method for clustering than K-modes. For instance, Fuzzy C-means, and look whether the data are clustered differently then based on your observation make a subjective judgement about the number of really distinctive clusters

187

Suppose the size of your data set is N, and U(k) (average silhouette width) is ur objectif function.

Please check if the following two methods could help.

1.ITERATIVE K-means CLUSTERING (naive apploach): starting from k=1 up to k=N, search the k which maximizes U(k). However this is  constrained by the size of your data set.

2. OPTIMISATION OF U(k), SUBJECT TO CONSTRAINTS. Use  optimisation methods to get the number k which optimises U(k). For example if U(k) is differentiable, you might use some Calculus techniques.

In both cases you will need first to express the average sihouetter width as a function of the number of clusters k.

of course the optimum number of clusters is subjective 

however I suggest you to try the subtractive clustering method.

in this method a density value is calculated for each datapoint based on the similarity between datapoints. Then, you can use a subtractive formula to find cluster centers iteratively. you can check the diffrence between the density values of Nth center and (N+1)th center, and also the ratio betwen the density of Nth and first cluster centers to stop finding the centers. Then you will have N clusters and N cluster centers for the first iteration of K-means clustering algorithm

Good Luck

 There are 3 method for cluster number.  

- simple method sqrt(n/2)

- The elbowmethod is based on the observation that increasing the number of clusters

can help to reduce the sum of within-cluster variance of each cluster. This

- The “right” number of clusters in a data set can also be determined by crossvalidation, a technique often used in classification

- And you will choose your request.

And I reccommend you book "Data Mining - Concepts and Techniques (3rd Ed)",  Jiawei Han

From my perspective, the closest (objective) criteria to human (subjective) perception of clusters is Mutual Information between ensembles of clustering hypothesis. It is easy to implement and it can be applied to any kind of clustering approach, even those aimed at categorical signal.

Although the method is simple to explain, it may be a bit lengthy for a blog. Therefore, if it pleases you, a straightforward explanation with illustrations can be found in Section 'E. Cluster Analysis' of the paper my fellows and I recently published in the open journal 'Journal of Communication and Information Systems' https://jcis.sbrt.org.br/jcis/article/view/95/283 

(I also appended this message with a copy of the paper).

I hope it may help you.

https://jcis.sbrt.org.br/jcis/article/view/95/283

You can  apply automatic clustering

For defining of the optimal number of clusters Nc,opt it can used the following algorithm:

1. Determination of the maximum number of clusters Nc,max. The maximum optimal of clusters Nc,max should be set to satisfy 2

Dear Ahreum Lee, here I'm attaching the link for one of my work, a new technique for determining the number of clusters is introduced. You can refer the same for K-Modes also:

Article A Novel Color Image Segmentation Approach Based On K-Means C...

Thanks All!!

Even though I iterate k-modes to randomize the initial seed, the elbow plot seems just little bit smooth,but did not show the clarity..  

(with unknown reasons, the silhouettes width goes bigger, as the number of cluster increases. I think the sihouette width is not proper for clustering with the categorical variables)  

Based on your comments, I decided to use the different clustering method which is the Two-step cluster analysis. It suggest the proper number of clusters with AIC or BIC. and It shows better results than the K-modes.

Thanks again!

It's difficult to add something useful here with all the interesting answers I've read. However, Ahreum mentioned something very important in her question that is rarely explained for the silhouette method (a popular approach to find the "optimal" number of clusters in these analyses). She said that in her case, the average silhouette value increases with the number of clusters, so in this case this method is not very useful because then one would not cluster anything at all, but leave every point as a singleton. This normally occurs when the distances (or dissimilarities, of course) between the elements are very small, which is normally the case when a normalization has been applied to restrict the distances to a specific range, say in the range [0,1].

Let's recall that the Silhouette is computed for every element (let's say N elements), given a clustering of K clusters for those N elements. Then, for every element 'i', let

a = distance to same cluster (average of distances between i and all other members of the cluster)

b = minimum distance to other clusters (computed as an average like above)

then silhouette[i] = (b - a) / max(a, b)

and here one realizes that if the distances are very similar then a and b will be very close (and thus the maximum between them, giving a result close to 1 for that division) when every element is on its own cluster, which explains why the average over all the elements increases with the number of clusters. I mean, there is no "penalty" for the case in which a close element is on another cluster with this formula when all the elements are close enough to each other. There is a problem here with the precision of the operations that you are computing.

So I would say that in general, the silhouette method is useful when the number of elements is rather small (let's say in the hundreds) or the distances are well distributed over a range in which no precision problems with floating points can arise (for example millions of elements with distances between 0 and 1 can be a problem).

In these problematic cases I have found useful clustering methods that automatically determine the optimal number of clusters by other means. For example, an interesting approach has been developed with a method called "affinity-propagation", which is based on passing messages between data points, and whose article I am referencing here.  There is also a R package called "apcluster" which compute this clustering, for those interested (also referenced below). 

Best regards.

Article Clustering by Passing Messages Between Data Points

Article APCluster: an R package for affinity propagation clustering

You could determine the optimal number of clusters visually e.g.,

http://www.springer.com/us/book/9783658205393

because most of the common statistical methods make assumptions about the data structures.

depend on your application. k mean may unsuitable..use hierarchical clustering

Does anybody know if there is an NBclust test (30 indices) alternative for k-medoids (not k-means)?

One alternative is to use the entropy as a grouping crriterion