# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 4 Internal Clustering Validation Index: CUBAGE
### Cibage Index
We used \(-F(P)\) and \(-E(P)\) instead of \(F(P)\) and \(E(P)\) to unify the objectives, and maximized each function to search for the local optimal partition. ### Experimental Methods

We tested the CVIs on eight datasets from the UCI (University of California, Irvine) Machine Learning Repository ([[http://archive.ics.uci.edu/mL/index.php](http://archive.ics.uci.edu/mL/index.php)]([http://archive.ics.uci.edu/mL/index.php](http://archive.ics.uci.edu/mL/index.php))), as shown in Table 5; records with missing values are removed. To compare the quality of the partitions chosen by the internal CVIs, we used two external CVIs as the benchmark evaluation criteria, respectively:

1. The adjusted Rand index (ARI)--the corrected-for-chance version of the Rand index--is based on the numbers of objects in common (or not) between the pre-defined classes and the produced clusters [6]. Given two partitions \(P\) = {\(C_{1}\),..., \(C_{k}\)} and \(P^{\prime}\) = {\(C^{{}^{\prime}}_{1}\),..., \(C^{{}^{\prime}}_{k^{\prime}}\)} ARI is defined as: \[\text{ARI}=\frac{\sum_{ij}\left( \begin{array}{c}n_{ij}\\ 2\end{array} \right)-\left[\sum_{i}\left( \begin{array}{c}b_{i}\\ 2\end{array} \right)\sum_{j}\left( \begin{array}{c}d_{j}\\ 2\end{array} \right)\right]/\left( \begin{array}{c}n\\ 2\end{array} \right)}{\frac{1}{2}\left[\sum_{i}\left( \begin{array}{c}b_{i} \\ 2\end{array} \right)+\sum_{j}\left( \begin{array}{c}d_{j}\\ 2\end{array} \right)\right]-\left[\sum_{i}\left( \begin{array}{c}b_{i}\\ 2\end{array} \right)\sum_{j}\left( \begin{array}{c}d_{j}\\ 2\end{array} \right)\right]/\left( \begin{array}{c}n\\ 2\end{array} \right)},\] (48) where \(n_{ij}\) is the number of common objects in \(C_{i}\) and \(C^{{}^{\prime}}_{j}\), \(n_{ij}=1\)\(C_{i}\cap C^{{}^{\prime}}_{j}\), \(b_{i}=\sum\limits_{j}n_{ij}\), \(d_{j}=\sum\limits_{i}n_{ij}\). In a specific dataset, a partition that is more similar to the pre-defined classes would score higher values in ARI. Note that ARI may take negative values. Figure 3: Flowchart of _CUBAGE_. 2. The normalized mutual information (NMI) calculates the mutual information of two partitions, and normalizes it with the sum of their entropy [16]: \[\text{NMI}=\frac{2\sum_{i=1}^{k}\sum_{j=1}^{k^{\prime}}\frac{n_{ij}}{n}\log\frac{ n_{ij}n}{b_{i}d_{j}}}{-\sum_{i=1}^{k}\frac{b_{i}}{n}\log\frac{b_{j}}{n}-\sum_{j=1 }^{k^{\prime}}\frac{d_{j}}{n}\log\frac{d_{j}}{n}}\.\] (49)

In a specific dataset, a higher value of NMI indicates that the partition is more proximal to the pre-defined classes. For example, in one measurement of several partitions, partitions \(P_{1}\) and \(P_{2}\) scores best in internal CVIs \(IV_{1}\) and \(IV_{2}\), respectively. \(EV\) is an external CVI, if \(EV(P_{1})>EV(P_{2})\), we can establish that partition \(P_{1}\) is more proximal to the pre-defined classes than partition \(P_{2}\) in the opinion of \(EV\). Therefore, \(IV_{1}\) performs better than \(IV_{2}\) in this example. We first compare the NMI values of the partitions selected by each internal CVIs to find out which internal CVI can select the better partition, i.e., performs better in the opinion of NMI. Then we use ARI to evaluate the internal CVIs in the same manner. On each dataset, we used the classical agglomerative hierarchical clustering and the \(k\)-modes clustering to produce the partitions, and both clustering methods applied the same cluster dissimilarity that was defined in \(F\). The experimental procedures are shown in Figures 4 and 5. 1. The agglomerative hierarchical clustering is a 'bottom-up' approach; each object is treated as an individual cluster in the beginning. When moving up the hierarchy, pairs of clusters are merged progressively if the dissimilarity of their union is lower than the other pairs in the same layer, until all objects are merged into one cluster eventually. The layers in the hierarchy are different partitions of the dataset.