Recognize outliers in a set as data collected Suppose I am aggregating data at multiple granularities, where each key is associated with the number of counts collected during the time interval.
EX:
1 minute {
x:2,
y:5,
z:3,
a:312
}
This is a small example, the real set will have anywhere from 1000-6000 unique keys associated with the number of hits collected in a time interval.
Is there a method that will immediately allow me to recognize that a member(s) of the set is an outlier? If not, what are some efficient algorithms to recognize outliers for data of this sort?
 A: Your data comes from an unknown distribution $f:\mathbb{Z}_+^d \rightarrow \mathbb{R}$ where d>1000. If you cannot assume anything about this distribution then there is no way to detect outliers.
One weak and relatively standard assumption you can make is that the distribution has bounded finite differences. i.e. if $|\bf x_1 - \bf x_2|$ is small then $|f({\bf x_1}) - f({\bf x_2})|$ must be small.
In that case, it is possible in principle to use nonparametric density estimation such as Kernel Density Estimation to estimate the density at each new data point (given all the previously recorded points) and give an outlier alert if this density lies below a threshold. This approach is easy to implement and needs only a reasonable choice of distance metric, kernel function and kernel width. The width can be estimated via cross-validation and the choice of kernel usually does not matter too much.
For a much simpler procedure, you can just compute the distance to the nearest sample. If this distance is large then you have an outlier.
However, given that the dimension is high, you probably won't get good results using both of these methods due to the curse of dimensionality - accurate nonparametric density estimation requires a number of samples exponential in the dimension.
I can think of several solutions to this problem:


*

*Use nonparametric density estimation on each key separately. Create an outlier alert if one of the keys is an outlier.

*Use nonparametric density estimation on each key separately. Estimate the density using the product of marginal densities and alert if this result is low. (i.e. take the product of estimated densities for all keys)

*Apply a dimension reduction algorithm such as PCA to go down to 2-3 dimensions and use nonparametric density estimation in that space. 

