A simultaneous two-level clustering algorithm for automatic model selection

One of the most crucial questions in many real-world cluster applications is determining a suitable number of clusters, also known as the model selection problem. Determining the optimum number of clusters is an ill posed problem for which there is no simple way of knowing that number without a priori knowledge. In this paper we propose a new two-level clustering algorithm based on self organizing map, called S2L-SOM, which allows an automatic determination of the number of clusters during learning. Estimating true numbers of clusters is related to the cluster stability which involved the validity of clusters generated by the learning algorithm. To measure this stability we use the sub-sampling method. The great advantage of our proposed algorithm, compared to the common partitional clustering methods, is that it is not restricted to convex clusters but can recognize arbitrarily shaped clusters. The validity of this algorithm is superior to standard two-level clustering methods such as SOM+k-means and SOM+Hierarchical agglomerative clustering. This is demonstrated on a set of critical clustering problems.