  We present a novel notion of outlier, called the Concentration Free Outlier
Factor, or CFOF. As a main contribution, we formalize the notion of
concentration of outlier scores and theoretically prove that CFOF does not
concentrate in the Euclidean space for any arbitrary large dimensionality. To
the best of our knowledge, there are no other proposals of data analysis
measures related to the Euclidean distance for which it has been provided
theoretical evidence that they are immune to the concentration effect. We
determine the closed form of the distribution of CFOF scores in arbitrarily
large dimensionalities and show that the CFOF score of a point depends on its
squared norm standard score and on the kurtosis of the data distribution, thus
providing a clear and statistically founded characterization of this notion.
Moreover, we leverage this closed form to provide evidence that the definition
does not suffer of the hubness problem affecting other measures. We prove that
the number of CFOF outliers coming from each cluster is proportional to cluster
size and kurtosis, a property that we call semi-locality. We determine that
semi-locality characterizes existing reverse nearest neighbor-based outlier
definitions, thus clarifying the exact nature of their observed local behavior.
We also formally prove that classical distance-based and density-based outliers
concentrate both for bounded and unbounded sample sizes and for fixed and
variable values of the neighborhood parameter. We introduce the fast-CFOF
algorithm for detecting outliers in large high-dimensional dataset. The
algorithm has linear cost, supports multi-resolution analysis, and is
embarrassingly parallel. Experiments highlight that the technique is able to
efficiently process huge datasets and to deal even with large values of the
neighborhood parameter, to avoid concentration, and to obtain excellent
accuracy.
