Novel Initial Seed Selection Methodology for Partitional Clustering Algorithms

Abstract

The underlying open issues in the partitional clustering algorithms such as K means newlineand K modes algorithms are as follows - random initial seed point selection, identifying the number of clusters, clustering tendency, handling empty clusters, identifying outliers and so on. Many authors have proposed different techniques to identify initial seed points which may involve setting of values for parameters, randomisation etc. This may not generate clustering solution having the minimal number of misclassifications. Thus, a clustering solution having high intra-cluster similarity and very low inter-cluster similarity cannot be assured. Also the same clustering solution which satisfies the above condition cannot be generated every time the clustering algorithm is executed. Therefore, it is important to identify the initial seed points which are representative points of the clusters of the final clustering solution. This ensures the final clustering solution to have high intra-cluster similarity and low inter-cluster similarity. Since the initial seed points are identified the final clustering solution can be regenerated everytime the clustering algorithm is executed. We have, hence, put forth a novel and simple methodology to overcome the problem of initial seed point selection which has a major impact on the final clustering solution. Our methodology ensures that the clustering solution is a repeatable one with minimal number of misclassifications compared to the existing newlineclustering techniques or generates the same clustering solution as that of the existing algorithms. This is not possible using K means clustering algorithm as the initial seeds are selected randomly during the clustering process. In K means clustering algorithm one needs to make all possible enumerations to find the clustering solution having minimal number of misclassifications. The proposed methodology overcomes this problem by selecting the seed points which are well separated from each other such that they fall into different clusters of the fina