LocalOutlierFactor

Local outlier factor model for anomaly detection

Since R2022b

Description

Use a local outlier factor model object LocalOutlierFactor for anomaly detection.

• Outlier detection (detecting anomalies in training data) — Detect anomalies in training data by using the lof function. The lof function creates a LocalOutlierFactor object and returns anomaly indicators and scores (local outlier factor values) for the training data.

• Novelty detection (detecting anomalies in new data with uncontaminated training data) — Create a LocalOutlierFactor object by passing uncontaminated training data (data with no outliers) to lof, and detect anomalies in new data by passing the object and the new data to the object function isanomaly. The isanomaly function returns anomaly indicators and scores for the new data.

Creation

Create a LocalOutlierFactor object by using the lof function.

Properties

X — Predictors

numeric matrix | table

This property is read-only.

Predictors used to train the local outlier factor model, specified as a numeric matrix or a table. Each row of X corresponds to one observation, and each column corresponds to one variable.

BucketSize — Maximum number of data points in each leaf node

positive integer | []

This property is read-only.

Maximum number of data points in each leaf node of the Kd-tree, specified as a positive integer.

This property is valid when SearchMethod is 'kdtree'. If SearchMethod is 'exhaustive', the BucketSize value is empty ([]).

CategoricalPredictors — Categorical predictor indices

vector of positive integers | []

This property is read-only.

Categorical predictor indices, specified as a vector of positive integers. CategoricalPredictors contains index values indicating that the corresponding predictors are categorical. The index values are between 1 and p, where p is the number of predictors used to train the model. If none of the predictors are categorical, then this property is empty ([]).

ContaminationFraction — Fraction of anomalies in training data

numeric scalar in the range [0,1]

This property is read-only.

Fraction of anomalies in the training data, specified as a numeric scalar in the range [0,1].

• If the ContaminationFraction value is 0, then lof treats all training observations as normal observations, and sets the score threshold (ScoreThreshold property value) to the maximum anomaly score value of the training data.

• If the ContaminationFraction value is in the range (0,1], then lof determines the threshold value (ScoreThreshold property value) so that the function detects the specified fraction of training observations as anomalies.

Distance — Distance metric

character vector

This property is read-only.

Distance metric, specified as a character vector.

• If all the predictor variables are continuous (numeric) variables, then the Distance value can be one of these distance metrics.

  Value	Description
  'euclidean'	Euclidean distance
  "fasteuclidean"	Euclidean distance using an algorithm that usually saves time when the number of elements in a data point exceeds 10. See Algorithms. "fasteuclidean" applies only to the "exhaustive" SearchMethod.
  'mahalanobis'	Mahalanobis distance — The distance uses the covariance matrix stored in the DistanceParameter property.
  'minkowski'	Minkowski distance — The distance uses the exponent value stored in the DistanceParameter property.
  'chebychev'	Chebychev distance (maximum coordinate difference)
  'cityblock'	City block distance
  'correlation'	One minus the sample correlation between observations (treated as sequences of values)
  'cosine'	One minus the cosine of the included angle between observations (treated as vectors)
  'spearman'	One minus the sample Spearman's rank correlation between observations (treated as sequences of values)

• If all the predictor variables are categorical variables, then the Distance value can be one of these distance metrics.

  Value	Description
  'hamming'	Hamming distance, which is the percentage of coordinates that differ
  'jaccard'	One minus the Jaccard coefficient, which is the percentage of nonzero coordinates that differ

For more information on the various distance metrics, see Distance Metrics.

DistanceParameter — Distance metric parameter value

positive scalar | []

This property is read-only.

Distance metric parameter value for the Mahalanobis or Minkowski distance, specified as a positive scalar. The DistanceParameter value is empty ([]) for the other distances, indicating that the specified distance metric formula has no parameters.

• If Distance is 'mahalanobis', then DistanceParameter is the covariance matrix in the Mahalanobis distance formula. The Cov name-value argument of lof sets this property.

• If Distance is 'minkowski', then DistanceParameter is the exponent in the Minkowski distance formula. The Exponent name-value argument of lof sets this property.

IncludeTies — Tie inclusion flag

false or 0 | true or 1

This property is read-only.

Tie inclusion flag indicating whether LocalOutlierFactor includes all the neighbors whose distance values are equal to the kth smallest distance, specified as logical 0 (false) or 1 (true). If IncludeTies is true, LocalOutlierFactor includes all of these neighbors. Otherwise, LocalOutlierFactor includes exactly k neighbors.

NumNeighbors — Number of nearest neighbors

positive integer value

This property is read-only.

Number of nearest neighbors in X used to compute local outlier factor values, specified as a positive integer value.

PredictorNames — Predictor variable names

cell array of character vectors

This property is read-only.

Predictor variable names, specified as a cell array of character vectors. The order of the elements in PredictorNames corresponds to the order in which the predictor names appear in the training data.

ScoreThreshold — Threshold for anomaly score

nonnegative scalar

This property is read-only.

Threshold for the anomaly score used to identify anomalies in the training data, specified as a nonnegative scalar.

The software identifies observations with anomaly scores above the threshold as anomalies.

• The lof function determines the threshold value to detect the specified fraction (ContaminationFraction property) of training observations as anomalies.

• The isanomaly object function uses the ScoreThreshold property value as the default value of the ScoreThreshold name-value argument.

SearchMethod — Nearest neighbor search method

'kdtree' | 'exhaustive'

This property is read-only.

Nearest neighbor search method, specified as 'kdtree' or 'exhaustive'.

• 'kdtree' — This method uses a Kd-tree algorithm to find nearest neighbors. This option is valid when the distance metric (Distance) is one of the following:

  • 'euclidean' — Euclidean distance

  • 'cityblock' — City block distance

  • 'minkowski' — Minkowski distance

  • 'chebychev' — Chebychev distance

• 'exhaustive' — This method uses the exhaustive search algorithm to find nearest neighbors.

  • When you compute local outlier factor values for X using the lof function, the function finds nearest neighbors by computing the distance values from all points in X to each point in X.

  • When you compute local outlier factor values for new data Xnew using the isanomaly function, the function finds nearest neighbors by computing the distance values from all points in X to each point in Xnew.

Object Functions

isanomaly

Find anomalies in data using local outlier factor

Examples

Detect Outliers

Detect outliers (anomalies in training data) by using the lof function.

Load the sample data set NYCHousing2015.

load NYCHousing2015

The data set includes 10 variables with information on the sales of properties in New York City in 2015. Display a summary of the data set.

summary(NYCHousing2015)

NYCHousing2015: 91446x10 table

Variables:

    BOROUGH: double
    NEIGHBORHOOD: cell array of character vectors
    BUILDINGCLASSCATEGORY: cell array of character vectors
    RESIDENTIALUNITS: double
    COMMERCIALUNITS: double
    LANDSQUAREFEET: double
    GROSSSQUAREFEET: double
    YEARBUILT: double
    SALEPRICE: double
    SALEDATE: datetime

Statistics for applicable variables:

                             NumMissing          Min              Median               Max               Mean               Std      

    BOROUGH                      0                     1                  3                  5             2.8431            1.3343  
    NEIGHBORHOOD                 0                                                                                                   
    BUILDINGCLASSCATEGORY        0                                                                                                   
    RESIDENTIALUNITS             0                     0                  1               8759             2.1789           32.2738  
    COMMERCIALUNITS              0                     0                  0                612             0.2201            3.2991  
    LANDSQUAREFEET               0                     0               1700           29305534         2.8752e+03        1.0118e+05  
    GROSSSQUAREFEET              0                     0               1056            8942176         4.6598e+03        4.3098e+04  
    YEARBUILT                    0                     0               1939               2016         1.7951e+03          526.9998  
    SALEPRICE                    0                     0             333333         4.1111e+09         1.2364e+06        2.0130e+07  
    SALEDATE                     0           01-Jan-2015        09-Jul-2015        31-Dec-2015        07-Jul-2015        2470:47:17  

Remove nonnumeric variables from NYCHousing2015. The data type of the BOROUGH variable is double, but it is a categorical variable indicating the borough in which the property is located. Remove the BOROUGH variable as well.

NYCHousing2015 = NYCHousing2015(:,vartype("numeric"));
NYCHousing2015.BOROUGH = [];

Train a local outlier factor model for NYCHousing2015. Specify the fraction of anomalies in the training observations as 0.01.

[Mdl,tf,scores] = lof(NYCHousing2015,ContaminationFraction=0.01);

Mdl is a LocalOutlierFactor object. lof also returns the anomaly indicators (tf) and anomaly scores (scores) for the training data NYCHousing2015.

Plot a histogram of the score values. Create a vertical line at the score threshold corresponding to the specified fraction.

h = histogram(scores,NumBins=50);
h.Parent.YScale = 'log';
xline(Mdl.ScoreThreshold,"r-",["Threshold" Mdl.ScoreThreshold]) 

If you want to identify anomalies with a different contamination fraction (for example, 0.05), you can train a new local outlier factor model.

 [newMdl,newtf,scores] = lof(NYCHousing2015,ContaminationFraction=0.05);

Note that changing the contamination fraction changes the anomaly indicators only, and does not affect the anomaly scores. Therefore, if you do not want to compute the anomaly scores again by using lof, you can obtain a new anomaly indicator with the existing score values.

Change the fraction of anomalies in the training data to 0.05.

newContaminationFraction = 0.05;

Find a new score threshold by using the quantile function.

newScoreThreshold = quantile(scores,1-newContaminationFraction)

newScoreThreshold = 
6.7493

Obtain a new anomaly indicator.

newtf = scores > newScoreThreshold;

Detect Novelties

Create a LocalOutlierFactor object for uncontaminated training observations by using the lof function. Then detect novelties (anomalies in new data) by passing the object and the new data to the object function isanomaly.

Load the 1994 census data stored in census1994.mat. The data set consists of demographic data from the US Census Bureau to predict whether an individual makes over $50,000 per year.

load census1994

census1994 contains the training data set adultdata and the test data set adulttest. The predictor data must be either all continuous or all categorical to train a LocalOutlierFactor object. Remove nonnumeric variables from adultdata and adulttest.

adultdata = adultdata(:,vartype("numeric"));
adulttest = adulttest(:,vartype("numeric"));

Train a local outlier factor model for adultdata. Assume that adultdata does not contain outliers.

[Mdl,tf,s] = lof(adultdata);

Mdl is a LocalOutlierFactor object. lof also returns the anomaly indicators tf and anomaly scores s for the training data adultdata. If you do not specify the ContaminationFraction name-value argument as a value greater than 0, then lof treats all training observations as normal observations, meaning all the values in tf are logical 0 (false). The function sets the score threshold to the maximum score value. Display the threshold value.

Mdl.ScoreThreshold

ans = 
28.6719

Find anomalies in adulttest by using the trained local outlier factor model.

[tf_test,s_test] = isanomaly(Mdl,adulttest);

The isanomaly function returns the anomaly indicators tf_test and scores s_test for adulttest. By default, isanomaly identifies observations with scores above the threshold (Mdl.ScoreThreshold) as anomalies.

Create histograms for the anomaly scores s and s_test. Create a vertical line at the threshold of the anomaly scores.

h1 = histogram(s,NumBins=50,Normalization="probability");
hold on
h2 = histogram(s_test,h1.BinEdges,Normalization="probability");
xline(Mdl.ScoreThreshold,"r-",join(["Threshold" Mdl.ScoreThreshold]))
h1.Parent.YScale = 'log';
h2.Parent.YScale = 'log';
legend("Training Data","Test Data",Location="north")
hold off

Display the observation index of the anomalies in the test data.

find(tf_test)

ans =

  0x1 empty double column vector

The anomaly score distribution of the test data is similar to that of the training data, so isanomaly does not detect any anomalies in the test data with the default threshold value. You can specify a different threshold value by using the ScoreThreshold name-value argument. For an example, see Specify Anomaly Score Threshold.

More About

Local Outlier Factor

The local outlier factor (LOF) algorithm detects anomalies based on the relative density of an observation with respect to the surrounding neighborhood.

The algorithm finds the k-nearest neighbors of an observation and computes the local reachability densities for the observation and its neighbors. The local outlier factor is the average density ratio of the observation to its neighbor. That is, the local outlier factor of observation p is

$$LO{F}_k(p)=\frac{1}{\left|N_k(p)\right|}{\displaystyle \sum _{o\in N_k(p)}\frac{lr{d}_k(o)}{lr{d}_k(p)}},$$

where

• lrd_k(·) is the local reachability density of an observation.

• N_k(p) represents the k-nearest neighbors of observation p. You can specify the IncludeTies name-value argument as true to include all the neighbors whose distance values are equal to the kth smallest distance, or specify false to include exactly k neighbors. The default IncludeTies value of lof is false for more efficient performance. Note that the algorithm in [1] uses all the neighbors.

• |N_k(p)| is the number of observations in N_k(p).

For normal observations, the local outlier factor values are less than or close to 1, indicating that the local reachability density of an observation is higher than or similar to its neighbors. A local outlier factor value greater than 1 can indicate an anomaly. The ContaminationFraction argument of lof and the ScoreThreshold argument of isanomaly control the threshold for the local outlier factor values.

The algorithm measures the density based on the reachability distance. The reachability distance of observation p with respect to observation o is defined as

$${\tilde{d}}_k(p,o)=\max (d_k(o),d(p,o)),$$

where

• d_k(o) is the kth smallest distance among the distances from observation o to its neighbors.

• d(p,o) is the distance between observation p and observation o.

The algorithm uses the reachability distance to reduce the statistical fluctuations of d(p,o) for the observations close to observation o.

The local reachability density of observation p is the reciprocal of the average reachability distance from observation p to its neighbors.

$$lr{d}_k(p)=1/\frac{{\displaystyle \sum _{o\in N_k(p)}{\tilde{d}}_k(p,o)}}{\left|N_k(p)\right|}.$$

The density value can be infinity if the number of duplicates is greater than the number of neighbors (k). Therefore, if the training data contains duplicates, the lof and isanomaly functions use the weighted local outlier factor (WLOF) algorithm. This algorithm computes the weighted local outlier factors using the weighted local reachability density (wlrd).

$$WLO{F}_k(p)=\frac{1}{{\displaystyle \sum _{o\in N_k(p)}w(o)}}{\displaystyle \sum _{o\in N_k(p)}\frac{wlr{d}_k(o)}{wlr{d}_k(p)}},$$

where

$$wlr{d}_k(p)=1/\frac{{\displaystyle \sum _{o\in N_k(p)}w(o){\tilde{d}}_k(p,o)}}{{\displaystyle \sum _{o\in N_k(p)}w(o)}},$$

and w(o) is the number of duplicates for observation o in the training data. After computing the weight values, the algorithm treats each set of duplicates as one observation.

Distance Metrics

A distance metric is a function that defines a distance between two observations. LocalOutlierFactor supports various distance metrics for continuous variables and categorical variables.

Given an mx-by-n data matrix X, which is treated as mx (1-by-n) row vectors x₁, x₂, ..., x_mx, and an my-by-n data matrix Y, which is treated as my (1-by-n) row vectors y₁, y₂, ...,y_my, the various distances between the vector x_s and y_t are defined as follows:

• Distance metrics for continuous (numeric) variables

  • Euclidean distance

    $$d_{st}^2=(x_s-y_t)(x_s-y_t{)}^{\prime }.$$

    The Euclidean distance is a special case of the Minkowski distance, where p = 2.

    Specify Euclidean distance by setting the Distance parameter to 'euclidean'.

  • Fast Euclidean distance is the same as Euclidean distance, but uses an algorithm that usually saves time when the number of variables in an observation n exceeds 10. See Algorithms.

  • Mahalanobis distance

    $$d_{st}^2=(x_s-y_t)C^{-1}(x_s-y_t{)}^{\prime },$$

    where C is the covariance matrix.

    Specify Mahalanobis distance by setting the Distance parameter to 'mahalanobis'.

  • City block distance

    $$d_{st}={\displaystyle \sum _{j=1}^n\left|x_{sj}-y_{tj}\right|}.$$

    The city block distance is a special case of the Minkowski distance, where p = 1.

    Specify city block distance by setting the Distance parameter to 'cityblock'.

  • Minkowski distance

    $$d_{st}=\sqrt[p]{{\displaystyle \sum _{j=1}^n{\left|x_{sj}-y_{tj}\right|}^p}}.$$

    For the special case of p = 1, the Minkowski distance gives the city block distance. For the special case of p = 2, the Minkowski distance gives the Euclidean distance. For the special case of p = ∞, the Minkowski distance gives the Chebychev distance.

    Specify Minkowski distance by setting the Distance parameter to 'minkowski'.

  • Chebychev distance

    $$d_{st}={\max }_j\left\{\left|x_{sj}-y_{tj}\right|\right\}.$$

    The Chebychev distance is a special case of the Minkowski distance, where p = ∞.

    Specify Chebychev distance by setting the Distance parameter to 'chebychev'.

  • Cosine distance

    $$d_{st}=\left(1-\frac{x_s{y^{\prime }}_t}{\sqrt{\left(x_s{x^{\prime }}_s\right)\left(y_t{y^{\prime }}_t\right)}}\right).$$

    Specify cosine distance by setting the Distance parameter to 'cosine'.

  • Correlation distance

    $$d_{st}=1-\frac{\left(x_s-{\overline{x}}_s\right){\left(y_t-{\overline{y}}_t\right)}^{\prime }}{\sqrt{\left(x_s-{\overline{x}}_s\right){\left(x_s-{\overline{x}}_s\right)}^{\prime }}\sqrt{\left(y_t-{\overline{y}}_t\right){\left(y_t-{\overline{y}}_t\right)}^{\prime }}},$$

    where

    $${\overline{x}}_s=\frac{1}{n}{\displaystyle \sum _j{x}_{sj}}$$

    and

    $${\overline{y}}_t=\frac{1}{n}{\displaystyle \sum _j{y}_{tj}}.$$

    Specify correlation distance by setting the Distance parameter to 'correlation'.

  • Spearman distance is one minus the sample Spearman's rank correlation between observations (treated as sequences of values):

    $$d_{st}=1-\frac{\left(r_s-{\overline{r}}_s\right){\left(r_t-{\overline{r}}_t\right)}^{\prime }}{\sqrt{\left(r_s-{\overline{r}}_s\right){\left(r_s-{\overline{r}}_s\right)}^{\prime }}\sqrt{\left(r_t-{\overline{r}}_t\right){\left(r_t-{\overline{r}}_t\right)}^{\prime }}},$$

    where

    • r_sj is the rank of x_sj taken over x_1j, x_2j, ...x_mx,j, as computed by tiedrank.

    • r_tj is the rank of y_tj taken over y_1j, y_2j, ...y_my,j, as computed by tiedrank.

    • r_s and r_t are the coordinate-wise rank vectors of x_s and y_t, that is, r_s = (r_s1, r_s2, ... r_sn) and r_t = (r_t1, r_t2, ... r_tn).

    • $${\overline{r}}_s=\frac{1}{n}{\displaystyle \sum _j{r}_{sj}}=\frac{\left(n+1\right)}{2}$$.

    • $${\overline{r}}_t=\frac{1}{n}{\displaystyle \sum _j{r}_{tj}}=\frac{\left(n+1\right)}{2}$$.

    Specify Spearman distance by setting the Distance parameter to 'spearman'.

• Distance metrics for categorical variables

  • Hamming distance is the percentage of coordinates that differ:

    $$d_{st}=(\#(x_{sj}\ne y_{tj})/n).$$

    Specify Hamming distance by setting the Distance parameter to 'hamming'.

  • Jaccard distance is one minus the Jaccard coefficient, which is the percentage of nonzero coordinates that differ:

    $$d_{st}=\frac{\#\left[\left(x_{sj}\ne y_{tj}\right)\cap \left(\left(x_{sj}\ne 0\right)\cup \left(y_{tj}\ne 0\right)\right)\right]}{\#\left[\left(x_{sj}\ne 0\right)\cup \left(y_{tj}\ne 0\right)\right]}.$$

    Specify Jaccard distance by setting the Distance parameter to 'jaccard'.

Tips

• You can use interpretability features, such as lime, shapley, partialDependence, and plotPartialDependence, to interpret how predictors contribute to anomaly scores. Define a custom function that returns anomaly scores, and then pass the custom function to the interpretability functions. For an example, see Specify Model Using Function Handle.

References

[1] Breunig, Markus M., et al. “LOF: Identifying Density-Based Local Outliers.” Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 2000, pp. 93–104.

Version History

Introduced in R2022b

R2023b: "fasteuclidean" Distance Support

The lof function gains support for the "fasteuclidean" Distance algorithm. This algorithm usually computes distances faster than the default "euclidean" algorithm when the number of variables in a data point exceeds 10. The algorithm, described in Algorithms, uses extra memory to store an intermediate Gram matrix. Set the size of this memory allocation using the CacheSize argument.