On the Complexity of Encoded Nominal Data

Categorical data is a fundamental element of real-world tabular classification problems. In typical machine learning workflows, encoding strategies are used to convert categorical data into numerical representations. These encoding strategies vary in their performance, with certain strategies leading to better results in machine learning applications. This study investigates the complexity characteristics of categorically encoded datasets, specifically datasets with nominal data. The complexity characteristics include measures for determining feature importance, linearity, dimensionality and more. Twelve encoding strategies are used to encode 43 datasets, which span a range of properties and problem domains. Empirical results indicate that, in general, supervised encoders produce datasets with statistically significantly lower feature-based, dimensionality, and structural complexity values, compared to datasets encoded using other encoders. The sum and one-hot encoders are shown to produce the most linearly separable datasets. Empirical results also showed that the neighborhood, structural, and linearity complexity values of the encoded datasets correlate with classification performance. Moreover, the choice of encoder is shown to produce a statistically significant difference in the performance of untuned support vector machines and k-nearest neighbors classifiers but not in the performance of untuned random forests.