Suppose I am aggregating data at multiple granularities, where each key is associated with the number of counts collected during the time interval.


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?

  • 1
    $\begingroup$ Can you give more details about the null hypothesis? i.e. What do you know about the "typical" distribution of counts? $\endgroup$ May 6, 2014 at 0:51
  • $\begingroup$ This is somewhat tricky, as I am unable to assume anything about the data, or how the counts are aggregated - For instance, the aggregation function could be a function of time elapsed in the interval. I am attempting to create a tool to handle data aggregation for realtime streams, and provide various interfaces into the data - In this case, reporting a set free of outliers, or reporting a maximum which is not an outlier, within a reasonable time frame, as this is meant for realtime visualization. $\endgroup$
    – Algonomaly
    May 6, 2014 at 1:03
  • $\begingroup$ For others that may encounter a problem such as this... Have a look at:tulips.tsukuba.ac.jp/dspace/bitstream/2241/106312/1/… $\endgroup$
    – Algonomaly
    May 6, 2014 at 1:28
  • $\begingroup$ If you have no assumptions, what could constitute an outlier? $\endgroup$
    – Glen_b
    May 6, 2014 at 2:27
  • $\begingroup$ Glen_b: it's obvious: observations that don't follow the pattern of the bulk of the data! @Jordan Dillon Chapian: so this is 4-variate data, right? $\endgroup$
    – user603
    May 6, 2014 at 8:10

1 Answer 1


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.