Detect Outlier (LOF)


Synopsis

Identifies outliers in the given ExampleSet based on local outlier factors.


Description

This operator performs a LOF outlier search. LOF outliers or outliers with a local outlier factor per object are density based outliers according to Breuning, Kriegel, et al.

The approach to find those outliers is based on measuring the density of objects and its relation to each other (referred to as local reachability density). Based on the average ratio of the local reachability density of an object and its k-nearest neighbours (e.g. the objects in its k-distance neighbourhood), a local outlier factor (LOF) is computed. The approach takes a parameter MinPts (actually specifying the "k") and it uses the maximum LOFs for objects in a MinPts range (lower bound and upper bound to MinPts).

Currently, the operator supports cosine, sine or squared distances in addition to the usual euclidian distance which can be specified by the corresponding parameter. In the first step, the objects are grouped into containers. For each object, using a radius screening of all other objects, all the available distances between that object and another object (or group of objects) on the (same) radius given by the distance are associated with a container. That container than has the distance information as well as the list of objects within that distance (usually only a few) and the information, how many objects are in the container.

In the second step, three things are done: (1) The containers for each object are counted in acending order according to the cardinality of the object list within the container (= that distance) to find the k-distances for each object and the objects in that k-distance (all objects in all the subsequent containers with a smaller distance). (2) Using this information, the local reachability densities are computed by using the maximum of the actual distance and the k-distance for each object pair (object and objects in k-distance) and averaging it by the cardinality of the k-neighbourhood and than taking the reciprocal value. (3) The LOF is computed for each MinPts value in the range (actually for all up to upper bound) by averaging the ratio between the MinPts-local reachability-density of all objects in the k-neighbourhood and the object itself. The maximum LOF in the MinPts range is passed as final LOF to each object.

Afterwards LOFs are added as values for a special real-valued outlier attribute in the example set which the operator will return.


Input


Output


Parameters


ExampleProcess