## 1 Introduction
### Similarity Measurement for Categorical Attributes  
For categorical attributes, each pair of values chosen from the value domain are considered to have the same distance as they do not have a natural ordering. By contrast, each pair of values of a numerical attribute has a numerical distance. Due to this different characteristic, it is not appropriate to use the Euclidian distance to evaluate categorical attributes-clustering similarity. Hereby, we adopt the frequency that the value \(x_{i,r}^{c}\) appears in the cluster \(C_{j}\) for the categorical attribute \(A_{r}^{c}\), where \(A_{r}^{c}\) (\(r=1,2,\ldots,d_{c}\)) represents the \(r\)th categorical attribute. **Definition 1**. : _The similarity between a categorical attribute value \(x_{i,r}^{c}\) and cluster \(C_{j}\), where \(i\in\{1,2,\ldots,m\}\), \(r\in\{1,2,\ldots,d_{c}\}\), \(j\in\{1,2,\ldots,k\}\), is defined as_  
\[s_{c}(x_{i,r}^{c},C_{j})=\frac{\sigma_{A_{i}^{c}=x_{i,r}^{c}}(C_{j})}{\sigma_{ A_{i}^{c}\
eq NULL}(C_{j})} \tag{3}\]  
where \(\sigma_{A_{i}^{c}=x_{i,r}^{c}}(C_{j})\) represents the number of objects in cluster \(C_{j}\), whose value for the categorical attribute \(A_{r}^{c}\) is equal to \(x_{i,r}^{c}\), \(NULL\) means empty, and \(\sigma_{A_{i}\
eq NULL}(C_{j})\) represents the number of objects in cluster \(C_{j}\), whose value for the categorical attribute \(A_{r}^{c}\) is not empty. From Definition 1, we can find the following properties:  
1. \(0\leq s_{c}(x_{i,r}^{c},C_{j})\leq 1\);
2. \(s_{c}(x_{i,r}^{c},C_{j})=0\) only if none of the attribute \(A_{r}^{c}\)'s values of the objects belonging to cluster \(C_{j}\) are equal to \(x_{i,r}^{c}\);
3. \(s_{c}(x_{i,r}^{c},C_{j})=1\) only if all of the Non NULL attribute \(A_{r}^{c}\)'s values of the objects belonging to cluster \(C_{j}\) are equal to \(x_{i,r}^{c}\). Optimizing attribute weights can improve the clustering performance. In information theory, the inhomogeneity degree of the dataset with respect to an attribute can be used to measure the significance of this attribute. In addition, according to Measure III proposed in [21], the higher the information content of an attribute, the higher the inhomogeneity degree of this attribute. **Definition 2**. : _Since the value domain of each attribute is definite, values of each attribute can be regarded as discrete and independent. The significance of an arbitrary categorical attribute \(A\) in dataset \(X\) can be quantified by the following entropy metric:_  
\[H(A)=-\sum_{g=1}^{h}p(a_{g})logp(a_{g}) \tag{4}\]  
where \(A\) has a value domain, denoted as \(dom(A)\), which consists of all the possible values that attributes \(A\) can choose, and \(dom(A)\) can be represented with \(dom(A)=\{a_{1},a_{2},\ldots,a_{h}\}\), \(h\) is the total number of values in \(dom(A)\). \(p(a_{g})=\frac{\sigma_{A=a_{g}}(X)}{\sigma_{A\
eq NULL}(X)}\), where \(a_{g}\) is a value of attribute \(A\), \(a_{g}\in dom(A)\), \(g=1,2,\ldots,h\). Therefore, \(p(a_{g})\) is the probability density function of \(a_{g}\) in dataset \(X\) for attribute \(A\). According to Equation (4), an attribute with more varying values has higher significance. However, in practice, an attribute with too many different values may have little clustering contribution, such as the instance ID number, which is unique for each instance; however, this information is useless for clustering analysis [12]. Thus, Equation (4) can be modified with Equation (5),  
\[H(A_{r}^{c})=-\frac{1}{h}\sum_{g=1}^{h}p(a_{g})logp(a_{g}) \tag{5}\]Then, the weight of each attribute based on information entropy is defined as in Equation (6),  
\[w^{c}_{r}=\frac{H(A^{c}_{r})}{\sum_{r=1}^{d_{c}}H(A^{c}_{r})+\sum_{r=1}^{d_{u}}H(A ^{u}_{r})},r=1,2,\ldots,d_{c} \tag{6}\]  
where \(\sum_{r=1}^{d_{u}}H(A^{u}_{r})\) denotes the sum of modified information entropy of all the numeric attributes, which will be described in detail in the next section. Therefore, the metric function of similarity between object \(x^{c}_{i}\) and cluster \(C_{j}\) on categorical attributes is modified as Equation (7).