de.lmu.ifi.dbs.elki.algorithm.outlier.clustering

Class CBLOF<O extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,OutlierResult>

de.lmu.ifi.dbs.elki.algorithm.outlier.clustering.CBLOF<O>

Type Parameters:

O - the type of data objects handled by this algorithm

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>, OutlierAlgorithm

@Title(value="Discovering cluster-based local outliers")
 @Reference(authors="Z. He, X. Xu, S. Deng",
           title="Discovering cluster-based local outliers",
           booktitle="Pattern Recognition Letters 24(9-10)",
           url="https://doi.org/10.1016/S0167-8655(03)00003-5",
           bibkey="DBLP:journals/prl/HeXD03")
public class CBLOF<O extends NumberVector>
extends AbstractDistanceBasedAlgorithm<O,OutlierResult>
implements OutlierAlgorithm

Cluster-based local outlier factor (CBLOF).

Reference:

Z. He, X. Xu, S. Deng
Discovering cluster-based local outliers
Pattern Recognition Letters 24(9-10)

Implementation note: this algorithm is hard to implement in a generic fashion, as to support arbitrary clustering algorithms and distances, because it is not trivial to ensure both the clustering algorithm and the outlier method use compatible data types and distances.

Since:

0.7.5

Author:

Patrick Kostjens

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CBLOF.Parameterizer<O extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected double	alpha The ratio of the size that separates the large clusters from the small clusters.
protected double	beta The minimal ratio between two consecutive clusters (when ordered descending by size) at which the boundary between the large and small clusters is set.
protected ClusteringAlgorithm<Clustering<MeanModel>>	clusteringAlgorithm The clustering algorithm to use.
protected NumberVectorDistanceFunction<? super O>	distance Distance function to use.
private static Logging	LOG The logger for this class.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
CBLOF(NumberVectorDistanceFunction<? super O> distanceFunction, ClusteringAlgorithm<Clustering<MeanModel>> clusteringAlgorithm, double alpha, double beta) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	computeCBLOFs(Relation<O> relation, NumberVectorDistanceFunction<? super O> distance, WritableDoubleDataStore cblofs, DoubleMinMax cblofMinMax, java.util.List<? extends Cluster<MeanModel>> largeClusters, java.util.List<? extends Cluster<MeanModel>> smallClusters) Compute the CBLOF scores for all the data.
private double	computeLargeClusterCBLOF(O obj, NumberVectorDistanceFunction<? super O> distanceQuery, NumberVector clusterMean, Cluster<MeanModel> cluster)
private double	computeSmallClusterCBLOF(O obj, NumberVectorDistanceFunction<? super O> distance, java.util.List<NumberVector> largeClusterMeans, Cluster<MeanModel> cluster)
private int	getClusterBoundary(Relation<O> relation, java.util.List<? extends Cluster<MeanModel>> clusters) Compute the boundary index separating the large cluster from the small cluster.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
OutlierResult	run(Database database, Relation<O> relation) Runs the CBLOF algorithm on the given database.
private void	storeCBLOFScore(WritableDoubleDataStore cblofs, DoubleMinMax cblofMinMax, double cblof, DBIDIter iter)

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

run

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.outlier.OutlierAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

clusteringAlgorithm

protected ClusteringAlgorithm<Clustering<MeanModel>> clusteringAlgorithm

The clustering algorithm to use.

alpha

protected double alpha

The ratio of the size that separates the large clusters from the small clusters. The clusters are ordered descending by size and are taken until the specified ratio of the data is included. For example: a ratio of 0.9 indicates that the large clusters should cover at least 90% of the data points.

beta

protected double beta

The minimal ratio between two consecutive clusters (when ordered descending by size) at which the boundary between the large and small clusters is set. For example: a ratio of 3 means that the clusters are separated between cluster i and (i+1) (where (i+1) is the first cluster smaller than i) when cluster i is at least 3 times bigger than (i+1).

distance

protected NumberVectorDistanceFunction<? super O extends NumberVector> distance

Distance function to use.

Constructor Detail

CBLOF

public CBLOF(NumberVectorDistanceFunction<? super O> distanceFunction,
             ClusteringAlgorithm<Clustering<MeanModel>> clusteringAlgorithm,
             double alpha,
             double beta)

Constructor.

Parameters:

distanceFunction - the neighborhood distance function

clusteringAlgorithm - the clustering algorithm

alpha - the ratio of the data that should be included in the large clusters

beta - the ratio of the sizes of the clusters at the boundary between the large and the small clusters

Method Detail

run

public OutlierResult run(Database database,
                         Relation<O> relation)

Runs the CBLOF algorithm on the given database.

Parameters:

database - Database to query

relation - Data to process

Returns:

CBLOF outlier result

getClusterBoundary

private int getClusterBoundary(Relation<O> relation,
                               java.util.List<? extends Cluster<MeanModel>> clusters)

Compute the boundary index separating the large cluster from the small cluster.

Parameters:

relation - Data to process

clusters - All clusters that were found

Returns:

Index of boundary between large and small cluster.

computeCBLOFs

private void computeCBLOFs(Relation<O> relation,
                           NumberVectorDistanceFunction<? super O> distance,
                           WritableDoubleDataStore cblofs,
                           DoubleMinMax cblofMinMax,
                           java.util.List<? extends Cluster<MeanModel>> largeClusters,
                           java.util.List<? extends Cluster<MeanModel>> smallClusters)

Compute the CBLOF scores for all the data.

Parameters:

relation - Data to process

distance - The distance function

cblofs - CBLOF scores

cblofMinMax - Minimum/maximum score tracker

largeClusters - Large clusters output

smallClusters - Small clusters output

storeCBLOFScore

private void storeCBLOFScore(WritableDoubleDataStore cblofs,
                             DoubleMinMax cblofMinMax,
                             double cblof,
                             DBIDIter iter)

computeSmallClusterCBLOF

private double computeSmallClusterCBLOF(O obj,
                                        NumberVectorDistanceFunction<? super O> distance,
                                        java.util.List<NumberVector> largeClusterMeans,
                                        Cluster<MeanModel> cluster)

computeLargeClusterCBLOF

private double computeLargeClusterCBLOF(O obj,
                                        NumberVectorDistanceFunction<? super O> distanceQuery,
                                        NumberVector clusterMean,
                                        Cluster<MeanModel> cluster)

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<OutlierResult>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<OutlierResult>

Returns:

the static logger