# Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data
## 2 Related Work
### Notations  
Unless stated otherwise, we used the following notations in this paper. \(U=\{X_{1},\ldots,X_{n}\}\) is a set of \(n\) objects, each object is described by the same \(m\) independent attributes \(A_{1}\),..., \(A_{m}\). The value of attribute \(A_{j}\) (\(j=1,\ldots,m\)) can be taken only from domain \(D(A_{j})=\{a_{j}{}^{  
Given a set of independent variables \(V=\{A_{1},\,\ldots,\,A_{m}\}\), the entropy \(H(V)\) is:  
\[H(V)=\sum_{j}^{m}H(A_{j})=-\sum_{j}^{m}\sum_{i}^{d_{j}}p(a_{j}{}^{(i)})\log(p(a_ {j}{}^{(i)})). \tag{2}\]  
A lower \(H(V)\) indicates less uncertainty of \(V\). Given a partition \(P=\{C_{1},\,\ldots,\,C_{k}\}\), the entropy of \(V\) conditioned on \(P\), i.e., \(H(V\,|\,P)\), is considered as the 'whole entropy of the partition' [30]:  
\[ \begin{array}{ll}E(P)=H(V\,|\,P)&=-\sum\limits_{j=1}^{m}\sum\limits_{l=1}^{ k}p(C_{l})\sum\limits_{i=1}^{d_{j}}p(a_{j}{}^{(i)}\,|C_{l})\log(p(a_{j}{}^{(i)} \,|C_{l}))\\ &=-\sum\limits_{j=1}^{m}\sum\limits_{l=1}^{k}\sum\limits_{i=1}^{d_{j}}p(a_{j}{ }^{(i)},C_{l})\log(p(a_{j}{}^{(i)}\,|C_{l}))\,,\end{array}  \tag{3}\]  
where \(p(a_{i}{}^{(i)}\,|\,C_{l})\) is the conditional probability of the value \(a_{j}{}^{(i)}\), given cluster \(C_{l}\). Notice that the probability of \(C_{l}\) is \(p(C_{l})=|\,C_{l}\,|\,/\,n\). \(E(P)\) attempts to represent the total entropy of the partition, which can be construed as the degree of disorder, by summing the weighted entropy of each cluster. To minimize the function \(E(P)\) is to find a partition in which the values of attributes describing the objects in the same clusters are centralized, which indicates that the objects are more similar in each cluster. 2. The \(k\)-modes objective function (\(F\)). Similar to the \(k\)-means clustering algorithm [36], \(k\)-modes compares each object in the same cluster with the cluster center, and sums the dissimilarities [31]. Since it is improper to take the means of categorical values as the cluster center, \(k\)-modes use the modes of values of each attribute. The dissimilarity between the object and the center is defined as:  
\[d(X_{li},Z_{l})=\sum\limits_{j=1}^{m}\delta(x_{lij},z_{ij}), \tag{4}\]  
where \(X_{li}\) is the \(i\)th object in cluster \(C_{l}\), \(x_{lij}\) is the value of attribute \(A_{j}\) describing object \(X_{i}\), \(Z_{l}\) is the center of cluster \(C_{l}\), \(z_{ij}\) is the value of attribute \(A_{j}\) describing center \(Z_{For the objects in the same cluster, \(CU\) measures the possibility of these objects taking the same attribute values [32]:  
\[ \begin{array}{ll}CU(P)&=\sum\limits_{l=1}^{k}p(C_{l})\sum\limits_{j=1}^{m} \sum\limits_{i=1}^{d_{j}}\left[p\left({{a_{j}}^{(i)}\left|{{C_{l}}}\right.} \right)^{2}-p({{a_{j}}^{(i)}})^{2}\right]\\ &=\sum\limits_{l=1}^{k}p(C_{l})\sum\limits_{j=1}^{m}\sum\limits_{i=1}^{d_{j}} \left[p\left({{a_{j}}^{(i)}\left|{{C_{l}}}\right.}\right)^{2}\right]-\sum \limits_{l=1}^{k}\sum\limits_{j=1}^{m}\sum\limits_{i=1}^{d_{j}}p({{a_{j}}^{(i) }})^{2}.\end{array}  \tag{8}\]  
This process attempts to maximize both the probability that two objects in the same category have attribute values in common by \(p({{a_{j}}^{(i)}}\left|{{C_{l}}}\right. )^{2}\), and the probability that objects from different categories have different attribute values by \(-p({{a_{j}}^{(i)}})^{2}\). However, the last term \(-p({{a_{j}}^{(i)}})^{2}\) is invariable when the dataset is given. Therefore:  
\[CU(P)=\sum\limits_{l=1}^{k}p(C_{l})\sum\limits_{j=1}^{m}\sum\limits_{i=1}^{d_ {j}}\left[p\left({{a_{j}}^{(i)}\left|{{C_{l}}}\right.}\right)^{2}\right]-Constant, \tag{9}\]  
where \(C\) is a constant. This means that the \(CU\) only measures how similar the objects in the same cluster are. The authors of references [37; 38] further averaged the values of the \(CU(P)\) measure over clusters, i.e., they used \(CU(P)/k\) instead of \(CU(P)\) to compare the partitions of different size. In this paper, we refer to the modified function as \(CU_{1/k}(P)\). 4.