# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 4 Internal Clustering Validation Index: CUBAGE
### Cibage Index
From the generated partitions with the number of clusters ranging from 2-10, we selected one 'optimal' partition by each internal CVI, then compared the external CVI values (NMI and ARI, respectively) of the selected partitions. 2. The \(k\)-modes clustering is a partitioning approach that is similar to the more famous \(k\)-means clustering. It starts with \(k\) randomly-generated cluster centers (seeds), and each object is assigned to the most appropriate cluster if the dissimilarity of their union is the lowest. In the next iteration, the centers of the clusters are updated by the attribute modes, and the objects are reassigned in the previous manner. The iteration ends if the value of the objective function \(F\) stabilizes. The clustering results are inconsistent over different seeds, even if the number of clusters \(k\) is fixed. To test the performances when the number of clusters is unknown, we used the internal CVIs to search for the optimal partition from all the partitions produced by \(k\)-modes with \(k\) ranging from 2-10 (each value of \(k\) is conducted 100 times, therefore 900 candidate partitions generated). We further repeated the process 100 times and compared the average external CVI values (ARI and NMI, respectively) of the partitions selected by each internal CVI. Additionally, we tested the internal CVIs with \(k\) set to the pre-defined number of clusters to examine the performance when the number of clusters is determined. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Dataset** & **Objects** & **Attributes** & **Classes** & **Object Distribution** \\ \hline Voting & 435 & 16 & 2 & 168, 267 \\ Breast Cancer Wisconsin (Original) & 683 & 9 & 2 & 444, 239 \\ Mushroom & 5644 & 22 & 2 & 2156, 3488 \\ Soybean (Small) & 47 & 35 & 4 & 10, 10, 10, 17 \\ Car Evaluation & 1728 & 6 & 4 & 1210, 384, 69, 65 \\ Heart Disease (Cleveland) & 297 & 13 & 5 & 54, 35, 35, 13, 160 \\ Dermatology & 358 & 34 & 6 & 111, 60, 71, 48, 48, 20 \\ Zoo & 101 & 16 & 7 & 41, 20, 5, 13, 4, 8, 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Datasets from UCI. Figure 4: Procedures of the hierarchical and \(k\)-modes clustering validation experiments. Figure 5: Determining the external index value of the partition selected by an internal index, where \(IV\) and \(EV\) are the values of the internal and the external index, respectively. ### Results of the Hierarchical Clustering Validation Evaluation

The NMI and ARI scores of the partitions chosen by each internal CVI in the hierarchical clustering are shown in Tables 6 and 7; the bracketed figures are the performance ranks over indexes. In general, the indexes \(CUBAGE\) and \(CU_{1/k}\) performed the best when evaluating the layers of the hierarchical clustering. The results of indexes \(-F\) and \(-E\) were worse than other indexes in both NMI and ARI. Figure 6 illustrates the changing of validation scores over the layers of the hierarchy; as we can see, the indexes \(CUBAGE\) and \(CU_{1/k}\) matched the benchmark evaluation criteria the best. Figure 6: _Cont._Figure 6: The validation scores of each layer of the hierarchy on different datasets. On axis OX are the layers, i.e., partitions of different size; on axis OY are the values of the validation (quality) of each partition measured by different CVIs. Note that the values of \(\mathit{Clope}_{r}(P)\) with the parameter \(r=1\)–\(3\) have been normalized for convenience of comparison. ### Results of the k-Modes Clustering Validation Evaluation

The NMI and ARI scores of the partitions chosen by each internal CVI in the \(k\)-modes clustering are shown in Tables 8-11. When \(k\) was not determined (Tables 8 and 9), _CUBAGE_ outperformed the other indexes on most of the datasets, and _CUI\({}_{1/k}\)_ came second. When \(k\) was determined (Tables 10 and 11), _CUBAGE_ still outperformed others, and indexes \(-E\) and \(-F\) advanced in performance.