# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 3 Understanding of Internal Clustering Validation Indexes
### Analysis of Indexes \(E\) and \(F\)  
The indexes \(E\) and \(F\) use compactness measures only, and average the compactness by a weight that was linear to the cluster size \(p(C_{l})\). We can show that the values of index \(E\) and \(F\) are monotonic to the number of clusters when clustering hierarchically:  
**Theorem 1**. : _Given dataset \(U\), described by a set of independent attributes \(V=\{A_{1},\,\ldots,\,A_{m}\}\), \(P_{1}\) and \(P_{2}\) are two partitions of \(U\). If \(P_{1}=\{C_{1},\,\ldots,\,C_{k}\}\) and \(P_{2}=\{C_{1},\,\ldots,\,C_{k-1},\,C_{s1},\,\ldots,\,C_{st}\}\), where \(C_{k}=C_{s1}\cup C_{s2}\cup\ldots\cup C_{st}\), \(C_{sl}\
eq\Phi\), and \(C_{sl}\cap C_{sl^{\prime}}=\Phi\) (\(l\
eq l^{\prime}\); \(l,l^{\prime}=1,\,\ldots,\,t\)), then \(E(P_{1})\geq E(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 1.: According to Equations (2) and (3), we know that:  
\[\left\{ \begin{array}{l}E(P_{1})=-\sum\limits_{j=1}^{m}\sum\limits_{l=1}^{k-1 }p(C_{l})\sum\limits_{i=1}^{d_{j}}p(a_{i}^{(i)}\,|C_{l})\log(p(a_{j}^{(i)}\,|C_ {l}))-\sum\limits_{j=1}^{m}p(C_{k})\sum\limits_{i=1}^{d_{j}}p(a_{j}^{(i)}\,|C_ {k})\log(p(a_{j}^{(i)}\,|C_{k}))\,,\\ E(P_{2})=-\sum\limits_{j=1}^{m}\sum\limits_{l=1}^{k-1}p(C_{l})\sum\limits_{i=1 }^{d_{j}}p(a_{i}^{(i)}\,|C_{l})\log(p(a_{j}^{(i)}\,|C_{l}))-\sum\limits_{j=1}^{ m}\sum\limits_{l=1}^{t}p(C_{sl})\sum\limits_{i=1}^{d_{j}}p(a_{i}^{(i)}\,|C_{sl}) \log(p(a_{j}^{(i)}\,|C_{sl}))\,.\end{array} \right.\]  
Then:  
\[E(P_{1})-E(P_{2})=\sum\limits_{j=1}^{m}\sum\limits_{l=1}^{t}p(C_{sl})\sum \limits_{i=1}^{d_{j}}p(a_{j}^{(i)}\,|C_{sl})\log(p(a_{j}^{(i)}\,|C_{sl}))-p(C_ {k})\sum\limits_{i=1}^{d_{j}}p(a_{j}^{(i)}\,|C_{k})\log(p(a_{j}^{(i)}\,|C_{k} ))\,]. \tag{19}\]  
Therefore, the necessary and sufficient condition of \(E(P_{1})\geq E(P_{2})\) is:  
\[-\sum\limits_{j=1}^{m}p(C_{k})\sum\limits_{i=1}^{d_{j}}p(a_{j}^{(i)}\,|C_{k} )\log(p(a_{j}^{(i)}\,|C_{k}))\geq-\sum\limits_{j=1}^{m}\sum\limits_{l=1}^{t} \frac{p(C_{sl})}{p(C_{k})}\sum\limits_{i=1}^{d_{j}}p(a_{j}^{(i)}\,|C_{sl})\log (p(a_{j}^{(i)}\,|C_{sl}))\,, \tag{20}\]  
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\)), we can show that:  
\[\sum\limits_{l=1}^{t}\frac{p(C_{sl})}{p(C_{k})}=\sum\limits_{l=1}^{t}p(C_{sl} \,|C_{k})=1,\quad l=1,...,t\,\,\,. \tag{21}\]  
Meanwhile, due to [PERSON] theorem, we can establish that:  
\[ \begin{array}{lcl}\sum\limits_{l=1}^{t}\frac{p(C_{sl})}{p(C_{k})}p(a_{j}^{(i) }\,|C_{sl})&=\sum\limits_{l=1}^{t}\frac{p(C_{sl})}{p(C_{k})}\cdot\frac{p(a_{j} ^{(i)})\cdot p(C_{sl}\,|a_{j}^{(i)})}{p(C_{sl})}\\ &=\sum\limits_{l=1}^{t}\frac{1}{p(C_{k})}\cdot p(a_{j}^{(i)})\cdot p(C_{sl}\,| a_{j}^{(i)})\\ &=\frac{p(C_{k}\,|a_{j}^{(i)})}{p(C_{k})}\cdot p(a_{j}^{(i)})\\ &=p(a_{j}^{(i)}\,|C_{k}),i=1,...,d_{j},j=1,...,m\end{array}  \tag{22}\] \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multicolumn{1}{c}{CVI} & Partition 1 & Partition 2 & Partition 3 & Partition 4 & Partition 5 \\ \hline \(E(P)\)\({}^{*}\) & 2.120 & 1.016 & 0.744 & **0.396** & **0.396** \\ \(F(P)\)\({}^{*}\) & 8 & 4 & 3 & **2** & **2** \\ \(Clope1(P)\) & **2.071** & 1.750 & 1.500 & 1.343 & 1.057 \\ \(Clope2(P)\) & 0.289 & 0.396 & 0.393 & **0.402** & 0.307 \\ \(Clope3(P)\) & 0.046 & 0.094 & 0.113 & **0.125** & 0.093 \\ \(CUl_{1/k}(P)\) & 0.255 & **0.376** & 0.330 & 0.302 & 0.252 \\ \(R(P)\) & **47.353** & 29.321 & 20.652 & 14.844 & 8.019 \\ \hline \hline \end{tabular} \({}^{*}\) To optimize \(E\) and \(F\) is to minimize them, while other functions are to be maximized.  
\end{table} 
Table 3: Evaluation results of the partitions in Table 2.  
Since the attributes are independent, and we know that \(H(X)\) is a concave function, we can prove Inequality (20) to be true by [PERSON]'s inequality [51]. Also, \(H(X)\) is not linear.