# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 4 Internal Clustering Validation Index: CUBAGE
### Cibage Index  
Our internal clustering validation index, \(CUBAGE\), uses \(AGE(P)\) as the inter-cluster separation measure, and uses the reciprocal of the conditional entropy, \(E(P)^{-1}\), as the intra-cluster compactness:  
\[CUBAGE(P)=Sep(P)*Com(P)=AGE(P)\cdot E(P)^{-1}. \tag{46}\]  
This index takes a form of the product of the separation and the compactness. A higher value of \(CUBAGE(P)\) indicates a better clustering result. As shown in Table 4, neither \(AGE(P)\) nor \(CUBAGE(P)\) showed monotonicity with respect to the partition size. Figure 2: This figure illustrates how the information gain of separating each clusters \(GE_{l}\) are calculated and averaged to represent the whole separation of the partition. In the figure, \(H_{U}\) is the entropy of unpartitioned dataset \(U\) (\(n\) objects), \(H_{l}\) is the entropy of cluster \(l\) (\(n_{l}\) objects), and \(H_{rest}\) is the entropy of the rest of the objects. Additionally, when the size of the partition is no greater than 2, we can establish the following by Equations (44) and (46):  
\[CUBAGE(P)=\frac{\frac{1}{k}\sum{[H(V)-E(P)]}}{E(P)}=\frac{H(V)-E(P)}{E(P)}=\frac{ H(V)}{E(P)}-1,\quad k\leq 2. \tag{47}\]  
Equation (47) is actually the information gain ratio of the partition. This means that for a given dataset, maximizing \(CUBAGE(P)\) is equivalent to minimizing \(E(P)\) when the number of clusters is no greater than 2, since the term \(H(V)\) is a constant to the dataset. Given a partition \(P\), the value of \(CUBAGE(P)\) can be calculated, as shown in Figure 3. Algorithms 1 and 2 are the pseudocode of \(CUBAGE\). ```
Input: dataset with \(n\) objects: \(U=(X_{i})\); label of a partition with \(k\) clusters; Output:\(CUBAGE\) value of the partition;  Called Function: entropy calculation function: Entropy(objects); Begin:
1. Calculate the entropy of the whole dataset, save as \(HU\): \(HU\) = Entropy(\(U\));
2. For each cluster \(C_{l}\):
3. Calculate the entropy of objects in \(C_{l}\), save in vector \(H\):\(H\)(\(l\)) = Entropy(\(C_{l}\));
4. Calculate the entropy of objects in \(U-C_{l}\), save in vector \(HC\):\(HC\)(\(l\)) = Entropy(\(U-C_{l}\));
5. End for;
6. Generate weight vector: \(W=1/n\):\(\{\,\mid\,C_{1}\,\mid\,C_{2}\,\mid\,\ldots,\,\mid\,C_{l}\,\mid\,\}\);
7. Calculate the dot product \(E=W\):\(H_{i}\);
8. Calculate \(AGE=HU-1/k\):\(\{\,\mid\,E+(1-W)\cdot HC\}\); Return:
9. \(CUBAGE\) = AGE/E;
```  
**Algorithm 1** Clustering Utility based on Entropy (\(CUBAGE\))  
The time complexity of \(CUBAGE(P)\) is \(O(kmn)\), where \(k\) is the number of clusters, \(m\) is the number of attributes, and \(n\) is the total number of objects. Note that there is no extra time cost for computing the compactness \(E^{-1}(P)\), since the weighted entropy of each cluster is already calculated during computing the separation \(AGE(P)\). The time cost could be lower if the data is sparse. Furthermore, one can easily apply parallel or distributed computing to \(CUBAGE(P)\) by the objects or the attributes to reduce the computing time. Therefore, such time complexity makes \(CUBAGE(P)\) scalable to large datasets. ``` Input: a set of \(x\) objects; Output: Entropy of objects in a single set; Begin:
1. For each attribute \(A_{j}\):
2. Calculate the entropy of the attribute by Equation (1), save in vector \(HA\);
3. End for; Return:
4. Entropy = sum(\(HA\)); \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**CVI** & **Partition 1** & **Partition 2** & **Partition 3** & **Partition 4** & **Partition 5** \\ \hline \(AGE\) & 1.032 & 1.191 & 0.912 & 0.769 & 0.601 \\ \(CUBAGE\) & 0.487 & 1.172 & 1.226 & **1.941** & 1.518 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The \(AGE\) (averaged information gain of isolating each cluster) and \(CUBAGE\) (clustering utility based on \(AGE\)) outcomes of the partitions in Table 2.

## 5 Experiments and Discussion

In this section, we present the results of the comparative experiments to evaluate the effectiveness of _CUBAGE_, along with the five internal CVIs mentioned above.