# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 4 Internal Clustering Validation Index: CUBAGE
### Cibage Index
When the number was pre-known, the partitions chosen by \(E\) were identical to those chosen by \(\mathit{CUBAGE}\) on the datasets Voting, Breast, and Mushroom (datasets with two classes), which agreed with Equation (47); \(\mathit{CUBAGE}\) performed better than \(E\) on other datasets when \(k\) is fixed as well, which indicates that the separation measure \(AGE\) not only contributes to the performance of evaluating partitions of different sizes, it also has a positive impact when evaluating the partitions of the same size. For comparison, \(R\) was outperformed by its equivalent compactness measure \(F\) when \(k\) was fixed, and the separation coefficient of \(CU_{1/k}\) had no impact on the performance, since \(1/k\) is a constant under such circumstances. As a result, \(\mathit{CUBAGE}\) performed better than other internal CVIs in general in the conducted experiments. Figure 7: The number of incidences of increased, equivalent, and decreased performances in both NMI and ARI when the number of clusters changes from pre-known to unknown in the \(k\)-modes clustering. ## 6 Conclusions and Future Work

This paper studies internal clustering validation measures for categorical data. We analyzed the compactness and separation measures or assumptions of five well-known internal CVIs, and proposed a new index--_CUBAGE_. Analysis results showed that the indexes without separation measures based on the attribute distribution do not necessarily ignore the impact of separation, since some indexes (i.e., \(CUI_{1/k}\) and \(Clope_{r}\)) adjusted the evaluation results by the separation assumptions with respect to the partition size or the object distribution, although the assumptions may be crude and not universally suitable. The compactness cores of the indexes are all monotonic with respect to the number of clusters in the hierarchical clustering, which makes them biased toward partitions with more clusters. The separation measures or assumptions corrected such biases by their preferences for the concentrated partitions. Therefore, the coordination of separation and compactness affects the evaluation considerably. For instance, as discussed, the role of parameter \(r\) is to adjust the importance of the compactness and the separation of the index \(Clope_{r}\), which influenced the effectiveness. The proposed internal CVI--_CUBAGE_--is based on a new separation measure that uses the averaged information gain of isolating each cluster to measure the overall separation of the partition. Theoretical analysis showed that this separation measure scores the minimum possible value when the objects are least separated. Meanwhile, _CUBAGE_ uses the reciprocal entropy of the dataset conditioned on the partition--which is also the reciprocal of index \(E\)--to measure the whole compactness. As the product of the separation and compactness measures, _CUBAGE_ showed better performance in the experiments than other indexes, which indicates that the separation and the compactness measures are accurate, and that they coordinate well on most datasets. In the future, we will investigate the internal CVIs in an extended range to provide systematic studies on the relation of within-cluster compactness and intracluster-separation. Secondly, the performance on evaluating the partitions of different characteristic patterns can be studied. Additionally, we will analyze the possibility of using _CUBAGE_ as the objective function in the clustering process from the aspects, such as convergence speed. The following are available online at [[http://www.mdpi.com/1999-4893/11/11/177/s1](http://www.mdpi.com/1999-4893/11/11/177/s1)]([http://www.mdpi.com/1999-4893/11/11/177/s1](http://www.mdpi.com/1999-4893/11/11/177/s1)). [PERSON] and [PERSON] conceived and designed the research, [PERSON] performed the experiments, [PERSON] and [PERSON] wrote and edited the paper. This research was funded by the National Natural Science Foundation of China (No. 71272161). The authors declare no conflict of interest. ## References

* (1) [PERSON]; [PERSON].