Initialization of K-modes clustering using outlier detection techniques

• We considered the initialization of K-modes clustering from the view of outlier detection.
• We proposed an initialization algorithm for K-modes clustering via the distance-based outlier detection technique.
• We presented a partition entropy-based outlier detection technique, and designed an initialization algorithm via it.
• We proposed a new distance metric – weighted matching distance metric.
• The effectiveness of our initialization algorithms was shown on several UCI data sets.

The K-modes clustering has received much attention, since it works well for categorical data sets. However, the performance of K-modes clustering is especially sensitive to the selection of initial cluster centers. Therefore, choosing the proper initial cluster centers is a key step for K-modes clustering. In this paper, we consider the initialization of K-modes clustering from the view of outlier detection. We present two different initialization algorithms for K-modes clustering, where the first is based on the traditional distance-based outlier detection technique, and the second is based on the partition entropy-based outlier detection technique. By using the above two outlier detection techniques to calculate the degree of outlierness of each object, our algorithms can guarantee that the chosen initial cluster centers are not outliers. Moreover, during the process of initialization, we adopt a new distance metric — weighted matching distance metric, to calculate the distance between two objects described by categorical attributes. Experimental results on several UCI data sets demonstrate the effectiveness of our initialization algorithms for K-modes clustering.