# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
###### Abstract  
Clustering is one of the main tasks of machine learning. Internal clustering validation indexes (CVIs) are used to measure the quality of several clustered partitions to determine the local optimal clustering results in an unsupervised manner, and can act as the objective function of clustering algorithms. In this paper, we first studied several well-known internal CVIs for categorical data clustering, and proved the ineffectiveness of evaluating the partitions of different numbers of clusters without any inter-cluster separation measures or assumptions; the accurateness of separation, along with its coordination with the intra-cluster compactness measures, can notably affect performance. Then, aiming to enhance the internal clustering validation measurement, we proposed a new internal CVI--clustering utility based on the averaged information gain of isolating each cluster (_CUBAGE_)--which measures both the compactness and the separation of the partition. The experimental results supported our findings with regard to the existing internal CVIs, and showed that the proposed _CUBAGE_ outperforms other internal CVIs with or without a pre-known number of clusters. machine learning; clustering; internal clustering validation index; categorical data +
Footnote †: journal:  
0000-0001-4111-1107-0000-0000-0000-0000-0000-0000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-000000  
On the other hand, Internal CVIs require no such prior knowledge, and have extensive practical applications in information retrieval, text and image analysis, biological engineering, and other domains of data mining [9; 10; 11; 12; 13; 14; 15; 16]. The quality of clustering results is usually inspected internally from two aspects--the intra-cluster compactness, and the inter-cluster separation (also known as isolation) [17; 18; 19; 20; 21; 22; 23]. The compactness reflects the degree of similarity of the objects in the same cluster, while the separation reflects how the objects in one cluster are dissimilar to others. Meanwhile, the internal CVIs for numerical data, such as the Dunn index [24], the \(I\) index [25], the Silhouette index [26], and the Calinski-Harabasz index [27], use intuitive geometric information to evaluate the partitions, which makes them unsuitable for categorical data clustering. Considering the increasing amount of categorical data in practical applications and the challenging issues that have not been adequately addressed in the literature, further research on internal CVIs for categorical data is in need [9; 14; 15; 28; 29]. Therefore, in this paper, we limit our scope to provide insight and enhancement of the internal CVIs for categorical data:  
1. Do internal CVIs for categorical data show monotonicity with respect to the number of clusters? One should avoid the monotonicity in validation measurement to prevent the bias towards partitions with more clusters, which would leave the performance of the evaluation to the boundary of the number of clusters in the candidate partitions. 2. Do internal CVIs for categorical data which use no separation measures really ignore the separation? A partition of good compactness is not necessarily a good partition, since the objects in one cluster may be similar to the objects in other clusters as well. Some internal CVIs for categorical data use no separation measures based on the attribute distribution between clusters, and have been proven to be effective when the number of clusters is constant in reference [9]. Figure 1: Clustering procedure consists of four steps with a feedback pathway. However, if the impact of separation on the clustering validation is ignored, the compactness measure alone may not be effective in evaluating partitions of different sizes due to the first issue. 3. What can we offer to enhance performance? After research on the above issues, we wish to offer an alternative internal CVI that has improved performance on categorical data clustering validation measurement.