# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 4 Internal Clustering Validation Index: CUBAGE
### Cibage Index
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline
**Dataset** & _CUBAGE_ & \(-F\) & \(-E\) & _CUU\({}_{\text{LR}}\)_ & _Clope\({}_{\text{1}}\)_ & _Clope\({}_{\text{2}}\)_ & _Clope\({}_{\text{3}}\)_ & \(R\) \\ \hline Voting & (1) 0.53 & (8) 0.174 & (7) 0.191 & (1) 0.53 & (3) 0.503 & (3) 0.503 & (3) 0.503 & (3) 0.503 & (6) 0.428 \\ Breast & (1) 0.787 & (6) 0.217 & (7) 0.195 & (1) 0.787 & (8) \(-\)0.001 & (4) 0.551 & (5) 0.337 & (3) 0.639 \\ Mushroom & (1) 0.489 & (7) 0.187 & (6) 0.228 & (3) 0.319 & (8) 0.155 & (2) 0.447 & (5) 0.268 & (4) 0.309 \\ Soybean & (1) 0.654 & (4) 0.442 & (3) 0.461 & (1) 0.654 & (8) 0.26 & (6) 0.297 & (6) 0.297 & (6) 0.352 \\ Car & (2) 0.023 & (4) 0.017 & (3) 0.021 & (1) 0.025 & (6) \(-\)0.001 & (6) \(-\)0.001 & (6) \(-\)0.001 & (5) 0.014 \\ Heart & (2) 0.199 & (4) 0.092 & (5) 0.079 & (3) 0.19 & (6) 0.065 & (8) 0.055 & (7) 0.065 & (1) 0.263 \\ Dermatology & (1) 0.552 & (3) 0.493 & (4) 0.487 & (1) 0.552 & (7) 0.136 & (6) 0.159 & (5) 0.21 & (8) 0.119 \\ Zoo & (1) 0.817 & (3) 0.573 & (4) 0.544 & (5) 0.448 & (7) 0.342 & (8) 0.341 & (2) 0.769 & (6) 0.411 \\
**Average ARI \({}^{*}\)** & 0.506 & 0.274 & 0.276 & 0.438 & 0.183 & 0.294 & 0.306 & 0.317 \\
**Average Rank \({}^{*}\)** & 1.25 & 4.875 & 4.875 & 2 & 6.625 & 5.375 & 4.875 & 4.75 \\ \hline \hline \end{tabular} \({}^{*}\) Averaged over datasets (average values of each column).

\end{table} 
Table 9: Average ARI values of the chosen _k_-modes partitions over 100 runs (_k_ ranging from 2–10). Indexes \(F\) and \(R\) had lower sensitivities to the value distribution, since they only consider the most and/or the least common values in the cluster. The performances of these CVIs were below average in the experiments. The performance drop of \(F\) appeared when the number of clusters was unknown, similar to index \(E\). As the compactness measure of \(F\) and \(R\) are equivalent, by comparing the trends in the hierarchical clustering experiments (Figure 6), we can observe that the compactness measure of \(R\) had little effect on the partition evaluation, and the role of the separation was dominant. Index \(CU_{1/k}\) uses \(1/k\) as the separation coefficient without respect to the value distribution between clusters. In the \(k\)-modes clustering experiments, the performance of \(CU_{1/k}\) dropped on most of the occasions when the number of clusters changed from known to unknown, as shown in Figure 7. This indicates that the separation assumption is not universally suitable, although it corrected the monotonicity of the compactness core. The performance of the index \(\mathit{Clope}_{r}\) is highly dependent on the parameter \(r\). As we discussed, the effect of compactness drops as \(r\) decreases. In the hierarchical clustering experiments, the value of \(\mathit{Clope}_{1}(P)\) monotonically decreased as the number of clusters increased under the effect of the separation measure. For the same reason, in the k-modes clustering, \(\mathit{Clope}_{1}(P)\) was outperformed by \(\mathit{Clope}_{2}(P)\) and \(\mathit{Clope}_{3}(P)\). However, \(\mathit{Clope}_{2}(P)\) and \(\mathit{Clope}_{3}(P)\) outperformed each other on different datasets, which indicates that setting \(r\) appropriately to compromise the compactness and the separation is difficult. Additionally, the performance drop of \(\mathit{Clope}_{r}\), when the number of clusters changed from known to unknown, as shown in Figure 7, indicates that the separation assumption of index \(\mathit{Clope}_{r}\) is not suitable for most datasets as well. Such a performance drop happened least with our internal CVI--_CIBAGE_. The separation measure \(AGE\) showed advantageous applicability to the datasets and clustering methods, and coordinated well with the compactness measure \(E^{-1}\). When the number of clusters was unknown, \(\mathit{CUBAGE}\) had improved performance compared to index \(E\) for introducing inter-cluster information.