# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 3 Understanding of Internal Clustering Validation Indexes
### Analysis of Indexes \(E\) and \(F\)
Due to [PERSON]'s inequality, the equality holds if and only if \(p(a_{j}{}^{(i)}\mid C_{s1})=p(a_{j}{}^{(i)}\mid C_{s2})=\ldots=p(a_{j}{}^{(i)} \mid C_{st})\) (\(j=1,\ldots,m\); \(i=1,\ldots,d_{j}\)), which is \(p(V\mid C_{s1})=p(V\mid C_{s2})=\ldots=p(V\mid C_{st})\). \(\square\)  
Theorem 2: _If the conditions are the same as in Theorem 1, then \(F(P_{1})\geq F(P_{2})\), and the equality holds if and only if \(z_{lj}=z_{2j}=\ldots=z_{lj}\) (\(j=1,\ldots,m\)), where \(z_{lj}\) is the mode of the values of attribute \(A_{j}\) in cluster \(C_{sl}\) (\(l=1,\ldots,t\))._  
Proof of Theorem 2: Similar to the proof of Theorem 1, we can show that:  
\[F(P_{1})-F(P_{2})=d_{cluster}(C_{k})-\sum_{l=1}^{t}d_{cluster}(C_{sl})=\sum_{j =1}^{m}\sum_{i=1}^{|C_{k}|}\delta(x_{kij},z_{kj})-\sum_{l=1}^{t}\sum_{j=1}^{m }\sum_{i=1}^{|C_{sl}|}\delta(x_{lij},z_{lj}). \tag{23}\]  
Since \(C_{s1}\cup C_{s2}\cup\ldots\cup C_{st}=C_{k}\), \(C_{sl}\
eq\Phi\), and \(C_{sl}\cap C_{sl^{\prime}}=\Phi\) (\(l\
eq l^{\prime}\); \(l,l^{\prime}=1,\ldots,t\)), to any attribute \(A_{j}\), the occurrence of value \(a_{j}{}^{(i)}\) in cluster \(C_{k}\) is equal to the sum of the occurrence of the same value in cluster \(C_{s1}\) to \(C_{st}\):  
\[Occ(a_{j}{}^{(i)},C_{k})=\sum_{l=1}^{t}Occ(a_{j}{}^{(i)},C_{sl}),\ \ \ j=1,\ldots,m,\ \ \ \ i=1,...,d_{j}. \tag{24}\]  
Meanwhile, we can rewrite the dissimilarity of any cluster \(C_{q}\) of dataset \(U\) as:  
\[d_{cluster}(C_{q})=\sum_{j}^{m}\left[\left|C_{q}\right|-Occ(z_{qj},C_{q}) \right]. \tag{25}\]  
Applying Equation (25) to Equation (23) yields:  
\[F(P_{1})-F(P_{2})=\sum_{j}^{m}\left[\left|C_{k}\right|-Occ(z_{kj},C_{k}) \right]-\sum_{l=1}^{t}\sum_{j}^{m}\left[\left|C_{sl}\right|-Occ(z_{lj},C_{sl })\right]. \tag{26}\]  
By the definition of mode, we know that:  
\[Occ(z_{lj},C_{sl})\geq Occ(z_{kj},C_{sl}),\ j=1,\ldots,m,\ l=1,...,t. \tag{27}\]  
Then:  
\[\sum_{l=1}^{t}\sum_{j}^{m}\left[\left|C_{sl}\right|-Occ(z_{lj},C_{sl})\right] \leq\sum_{l=1}^{t}\sum_{j}^{m}\left[\left|C_{sl}\right|-Occ(z_{kj},C_{sl}) \right]. \tag{28}\]  
Therefore:  
\[F(P_{1})-F(P_{2})\geq\sum_{j}^{m}\left[\left|C_{k}\right|-Occ(z_{kj},C_{k}) \right]-\sum_{l=1}^{t}\sum_{j}^{m}\left[\left|C_{sl}\right|-Occ(z_{kj},C_{sl })\right]. \tag{29}\]  
By Equation (24), we can show that the right-hand part of Inequality (29) equals 0. Therefore, \(F(P_{1})\geq F(P_{2})\), and the equality holds if and only if:  
\[Occ(z_{lj},C_{sl})=Occ(z_{kj},C_{sl}),\ j=1,\ldots,m,\ l=1,...,t. \tag{30}\]  
\(\square\)  
Theorems 1 and 2 show that one cannot determine whether any clusters in the partition should be merged by \(E\) or \(F\), since the evaluation results always suggest to divide. Even if the attribute distribution in the candidate clusters are equivalent (in which case they are generally regarded as the most similar clusters), the scores of whether to merge them would be in a tie. This most affects the hierarchical clustering, in which objects are clustered in either agglomerative or divisive manners, and the suggested layer of hierarchy by these CVIs would always be the layer with the most clusters, unless the layer with the second-most clusters has the same evaluation score. We should point out that, in some researches, the separation coefficient \(1/k\) of index \(CU_{1/k}\) (which will be discussed shortly) was multiplied to the function \(E(P)\) directly, which would aggravate the monotonicity, since \(1/k\) is also a monotonically decreasing function with respect to the partition size. Therefore, we will not discuss such a method in this paper.