Class LOF<T>

java.lang.Object
smile.anomaly.LOF<T>
Type Parameters:
T - the data type of observations.
All Implemented Interfaces:
Serializable
public class LOF<T> extends Object implements Serializable
Local Outlier Factor (LOF). LOF is an unsupervised outlier detection algorithm based on local density estimation.

Many outlier detection algorithms compare an observation against the global data distribution or boundary. However, in datasets where clusters have varying densities, points that are normal relative to a sparse cluster might be denser than outliers near a dense cluster. LOF addresses this by comparing the local density of an observation to the local densities of its k nearest neighbors.

For each point p, the algorithm determines:

  • The k-distance, which is the distance to its k-th nearest neighbor.
  • The reachability distance from o to p: reach-dist_k(p, o) = max(k-distance(o), d(p, o)).
  • The local reachability density (lrd), defined as the inverse of the average reachability distance of p from its neighbors.
  • The LOF score, which is the average ratio of the lrds of its neighbors to that of p.

An LOF score around 1.0 indicates an inlier with local density comparable to its neighbors. A score significantly greater than 1.0 (e.g., > 1.5) signals an outlier whose local density is markedly lower than that of its neighbors.

References

  1. Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, and Jörg Sander. LOF: Identifying Density-Based Local Outliers. ACM SIGMOD, 93–104, 2000.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final record 
    LOF.Options
    Hyperparameters of LOF.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LOF(int k, KNNSearch<T,T> nns, double[] kdistance, double[] lrd, double[] scores)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    static LOF<double[]>
    fit(double[][] data)
    Fits an LOF model on numeric data using a KD-tree for spatial neighborhood search.
    static LOF<double[]>
    fit(double[][] data, int k)
    Fits an LOF model on numeric data using a KD-tree for spatial neighborhood search.
    static LOF<double[]>
    fit(double[][] data, LOF.Options options)
    Fits an LOF model on numeric data using a KD-tree for spatial neighborhood search.
    static <T> LOF<T>
    fit(T[] data, Distance<T> distance, int k)
    Fits an LOF model on arbitrary objects in a metric space.
    static <T> LOF<T>
    fit(T[] data, KNNSearch<T,T> nns, int k)
    Fits an LOF model using a provided nearest neighbor search structure.
    int
    k()
    Returns the number of nearest neighbors.
    boolean
    predict(T x, double threshold)
    Predicts whether an observation is an anomaly based on whether its LOF score exceeds the specified threshold.
    double
    score(T x)
    Returns the LOF score for an out-of-sample observation.
    double[]
    score(T[] x)
    Returns the LOF scores for an array of observations.
    double[]
    scores()
    Returns the in-sample LOF scores of the training data.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • LOF

      public LOF(int k, KNNSearch<T,T> nns, double[] kdistance, double[] lrd, double[] scores)
      Constructor.
      Parameters:
      k - the number of neighbors.
      nns - the nearest neighbor search data structure.
      kdistance - the k-distance of each training observation.
      lrd - the local reachability density of each training observation.
      scores - the LOF scores of training observations.

  • Method Details

    • k

      public int k()
      Returns the number of nearest neighbors.
      Returns:
      the number of nearest neighbors.

    • scores

      public double[] scores()
      Returns the in-sample LOF scores of the training data.
      Returns:
      the LOF scores.

    • fit

      public static LOF<double[]> fit(double[][] data)
      Fits an LOF model on numeric data using a KD-tree for spatial neighborhood search. Default k = 20.
      Parameters:
      data - the training observations.
      Returns:
      the fitted model.

    • fit

      public static LOF<double[]> fit(double[][] data, int k)
      Fits an LOF model on numeric data using a KD-tree for spatial neighborhood search.
      Parameters:
      data - the training observations.
      k - the number of nearest neighbors.
      Returns:
      the fitted model.

    • fit

      public static LOF<double[]> fit(double[][] data, LOF.Options options)
      Fits an LOF model on numeric data using a KD-tree for spatial neighborhood search.
      Parameters:
      data - the training observations.
      options - the hyperparameters.
      Returns:
      the fitted model.

    • fit

      public static <T> LOF<T> fit(T[] data, Distance<T> distance, int k)
      Fits an LOF model on arbitrary objects in a metric space.
      Type Parameters:
      T - the data type.
      Parameters:
      data - the training observations.
      distance - the distance function.
      k - the number of nearest neighbors.
      Returns:
      the fitted model.

    • fit

      public static <T> LOF<T> fit(T[] data, KNNSearch<T,T> nns, int k)
      Fits an LOF model using a provided nearest neighbor search structure.
      Type Parameters:
      T - the data type.
      Parameters:
      data - the training observations.
      nns - the nearest neighbor search structure.
      k - the number of nearest neighbors.
      Returns:
      the fitted model.

    • score

      public double score(T x)
      Returns the LOF score for an out-of-sample observation. Scores around 1.0 indicate an inlier; scores significantly greater than 1.0 indicate an anomaly.
      Parameters:
      x - the observation.
      Returns:
      the LOF score.

    • score

      public double[] score(T[] x)
      Returns the LOF scores for an array of observations.
      Parameters:
      x - the observations.
      Returns:
      the LOF scores.

    • predict

      public boolean predict(T x, double threshold)
      Predicts whether an observation is an anomaly based on whether its LOF score exceeds the specified threshold.
      Parameters:
      x - the observation.
      threshold - the LOF threshold (e.g. 1.5). An observation is flagged as an anomaly when score(x) > threshold.
      Returns:
      true if the observation is predicted to be an anomaly.