Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity

摘要

In many application areas, it is important to detect outliers. The traditional engineering approach to outlier detection is that we start with some "normal" values x_1.....x_n, compute the sample average E, the sample standard variation σ, and then mark a value x as an outlier if x is outside the k_0-sigma interval [E - k_0 · σ, E + k_0 · σ] (for some pre-selected parameter k_0). In real life, we often have only interval ranges [x_i, x_i,] for the normal values x_1,…,x_n. In this case, we only have intervals of possible values for the bounds E - k_0 · σ and E + k_0 · σ. We can therefore identify outliers as values that are outside all k_0 -sigma intervals. Once we identify a value as an outlier for a fixed k_0 , it is also desirable to find out to what degree this value is an outlier, i.e., what is the largest value k_0 for which this value is an outlier. In this paper, we analyze the computational complexity of these outlier detection problems, provide efficient algorithms that solve some of these problems (under reasonable conditions), and list related open problems.