Outlier Detection for Categorical Data

Abstract

Outlier detection or anomaly detection is a very important process to detect instances with unexpected behavior that occurs in a given system. From many years, outlier detection has gained a significant consideration due to its applications in various areas such as credit cards fraud in banking sector, illegal access in networking field, data analysis in medical field, weather prediction etc. Till now, many techniques have been developed to detect outliers. However, most existing techniques focus on numerical data and they can not be applied directly for categorical data because of the difficulty of defining a meaningful similarity measure for categorical data. Also, high dimensional categorical data impose significant challenges due to their unique data discreteness. To handle this type of data we can use entropy related measures. The concept of entropy is developed over the probabilistic explanation of data distribution which quantifies the variation or diversity of a discrete variable. For outlier detection, we applied a simple and effective ranking based algorithm based on entropy and mutual information, and we also analyzed corresponding time complexity of the algorithm. Experimental results on car evaluation data set and two other data sets demonstrate the effectiveness and efficiency of our algorithm.