# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 3 Understanding of Internal Clustering Validation Indexes
### Analysis of Indexes \(CU_{1/k}\), Cloper, and \(R\)  
Besides the compactness measure, indexes \(CU_{1/k}\), Cloper, and \(R\) use separation measures or assumptions as well. \(CU_{1/k}(P)\) is the averaged compactness over \(k\) clusters weighted by \(p(C_{l})\), and \(CU_{1/k}(P)\) is the further averaged \(CU(P)\). The role of the multiplicand \(1/k\) is a crude overfitting control, and can be regarded as the assumed separation coefficient with respect to the number of clusters. We can show that the compactness measure in \(CU_{1/k}(P)\) also shows monotonicity in the previous scenario:  
**Theorem 3**. : _If the conditions are the same as in Theorem 1, then \(CU(P_{1})\leq CU(P_{2})\), and the equality holds if and only if \(p(V\,|\,C_{s1})=p(V\,|\,C_{s2})=\ldots=p(V\,|\,C_{st})\)._  
Proof of Theorem 3.: Similar to the proof of Theorem 1, we can show that:  
\[CU(P_{1})-CU(P_{2})=\sum_{j=1}^{m}{[p(C_{k})\sum_{i=1}^{d_{j}}{p\left({a_{j}}^ {(i)}\,|\,C_{k}\right)}^{2}}-\sum_{l=1}^{t}{p(C_{sl})\sum_{i=1}^{d_{j}}{p\left( {a_{j}}^{(i)}\,|\,C_{sl}\right)}^{2})}]. \tag{31}\]  
\(C_{k}\
eq\Phi\), so we can rewrite Equation (31) as:  
\[\frac{CU(P_{1})-CU(P_{2})}{p(C_{k})}=\sum_{j=1}^{m}{[\sum_{i=1}^{d_{j}}{p\left( {a_{j}}^{(i)}\,|\,C_{k}\right)}^{2}}-\sum_{l=1}^{t}{\frac{p(C_{sl})}{p(C_{k}) }\sum_{i=1}^{d_{j}}{p\left({a_{j}}^{(i)}\,|\,C_{sl}\right)}^{2})}]. \tag{32}\]  
Therefore, the necessary and sufficient condition of \(CU(P_{1})\leq CU(P_{2})\) is:  
\[p\left({a_{j}}^{(i)}\,|\,C_{k}\right)^{2}\leq\sum_{l=1}^{t}{\frac{p(C_{sl})}{ p(C_{k})}p\left({a_{j}}^{(i)}\,|\,C_{sl}\right)}^{2},i=1,...,d_{j},\ j=1,...,m. \tag{33}\]  
We know that \(y=x^{2}\) is a convex, and not a linear function. Therefore, Inequality (33) is true, due to [PERSON]'s inequality with Equations (21) and (22) in the proof of Theorem 1, and the equality holds if and only if \(p(V\,|\,C_{s1})=p(V\,|\,C_{s2})=\ldots=p(V\,|\,C_{st})\). \(\Box\)  
Therefore, using the category utility function to evaluate partitions of different size without the separation coefficient \(1/k\) is questionable. However, the act of multiplying the compactness with such a coefficient is based on the assumption that the separation of the partition is negatively correlated with the partition size. Such an assumption ignores the attribute value distribution between clusters, and may generate a new bias to the partitions of fewer clusters, since \(1/k\) would be dominant to the result when the change in compactness is relatively gradual. The compactness core of \(Cloper_{r}(P)\) is also monotonic. However, different to other indexes, \(Cloper_{r}(P)\) uses the quadratic weight \(p(C_{l})^{2}\) instead of \(p(C_{l})\) to average the compactness. In consequence, the partitions in which the objects are more concentrated in fewer clusters would score better with \(Cloper_{r}(P)\), which is also an assumption of separation for adjusting the evaluation results. Like the separation coefficient \(1/k\) of \(CU_{1/k}(P)\), such an assumption is irrelevant to the differences in attribute values between clusters. If we remove the assumption, i.e., we use \(p(C_{l})\) instead of \(p(C_{l})^{2}\), the averaged compactness would also be monotonic to the partition size in the previous scenario:  
**Theorem 4**.