EDMD: An Entropy based Dissimilarity measure to cluster Mixed-categorical Data

The effectiveness of clustering techniques is significantly influenced by proximity measures irrespective of type of data and categorical data is no exception. Most of the existing proximity measures for categorical data assume that all attributes contribute equally to the distance measurement which is not true. Usually, frequency or probability-based approaches are better equipped in principle to counter this issue by appropriately weighting the attributes based on the intra-attribute statistical information. However, owing to the qualitative nature of categorical features, the intra-attribute disorder is not captured effectively by the popularly used continuum form of entropy known as Shannon or information entropy. If the categorical data contains ordinal features, then the problem multiplies because the existing measures treat all attributes as nominal. To address these issues, we propose a new Entropy-based Dissimilarity measure for Mixed categorical Data (EDMD) composed of both nominal and ordinal attributes. EDMD treats both nominal and ordinal attributes separately to capture the intrinsic information from the values of two different attribute types. We apply Boltzmann's definition of entropy, which is based on the principle of counting microstates, to exploit the intra-attribute statistical information of nominal attributes while preserving the order relationships among ordinal values in distance formulation. Additionally, the statistical significance of different attributes of the data towards dissimilarity computation is taken care of through attribute weighting. The proposed measure is free from any user-defined or domain-specific parameters and there is no prior assumption about the distribution of the data sets. Experimental results demonstrate the efficacy of EDMD in terms of cluster quality, accuracy, cluster discrimination ability, and execution time to handle mixed categorical data sets of different characteristics.