de.lmu.ifi.dbs.elki.distance.distancefunction

Class MinKDistance<O,D extends Distance<D>>

java.lang.Object

de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractDatabaseDistanceFunction<O,D>

de.lmu.ifi.dbs.elki.distance.distancefunction.MinKDistance<O,D>

Type Parameters:

O - Database object type

D - Distance type

All Implemented Interfaces:

DistanceFunction<O,D>, InspectionUtilFrequentlyScanned, Parameterizable

public class MinKDistance<O,D extends Distance<D>>
extends AbstractDatabaseDistanceFunction<O,D>

A distance that is at least the distance to the kth nearest neighbor. This is essentially the "reachability distance" of LOF, but with arguments reversed! Reachability of B from A, i.e.

   reachability-distance(A,B) = max( k-distance(A), distance(A,B) )
 

Where k-distance(A) is the distance to the k nearest neighbor of A, and distance is the actual distance of A and B. This distance is NOT symmetric. You need to pay attention to the order of arguments!

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	MinKDistance.Instance<T extends O> Instance for an actual database.
static class	MinKDistance.Parameterizer<O,D extends Distance<D>> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static OptionID	DISTANCE_FUNCTION_ID OptionID for the base distance used to compute reachability
private int	k The value of k
static OptionID	K_ID OptionID for the "k" parameter.
static OptionID	KNNQUERY_ID OptionID for the KNN query class to use (preprocessor, approximation, ...)
(package private) static boolean	objectIsInKNN Include object itself in kNN neighborhood.
protected DistanceFunction<? super O,D>	parentDistance The distance function to determine the exact distance.

Constructor Summary

Constructors

Constructor and Description
MinKDistance(DistanceFunction<? super O,D> parentDistance, int k) Full constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected D	computeReachdist(List<DistanceResultPair<D>> neighborhood, D truedist) Actually compute the distance, whichever way we obtained the neighborhood above.
boolean	equals(Object obj)
D	getDistanceFactory() Method to get the distance functions factory.
TypeInformation	getInputTypeRestriction() Get the input data type of the function.
<T extends O> DistanceQuery<T,D>	instantiate(Relation<T> relation) Instantiate with a database to get the actual distance query.
boolean	isMetric() Is this distance function metric (in particular, does it satisfy the triangle equation?)
boolean	isSymmetric() Is this function symmetric?

Methods inherited from class java.lang.Object

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

Field Detail

DISTANCE_FUNCTION_ID

public static final OptionID DISTANCE_FUNCTION_ID

OptionID for the base distance used to compute reachability

KNNQUERY_ID

public static final OptionID KNNQUERY_ID

OptionID for the KNN query class to use (preprocessor, approximation, ...)

K_ID

public static final OptionID K_ID

OptionID for the "k" parameter.

parentDistance

protected DistanceFunction<? super O,D extends Distance<D>> parentDistance

The distance function to determine the exact distance.

k

private int k

The value of k

objectIsInKNN

static boolean objectIsInKNN

Include object itself in kNN neighborhood. In the official LOF publication, the point itself is not considered to be part of its k nearest neighbors.

Constructor Detail

MinKDistance

public MinKDistance(DistanceFunction<? super O,D> parentDistance,
            int k)

Full constructor. See MinKDistance.Parameterizer for factory.

Parameters:

parentDistance - distance function to use

k - K parameter

Method Detail

instantiate

public <T extends O> DistanceQuery<T,D> instantiate(Relation<T> relation)

Description copied from interface: DistanceFunction

Instantiate with a database to get the actual distance query.

Parameters:

relation - The representation to use

Returns:

Actual distance query.

computeReachdist

protected D computeReachdist(List<DistanceResultPair<D>> neighborhood,
                 D truedist)

Actually compute the distance, whichever way we obtained the neighborhood above.

Parameters:

neighborhood - Neighborhood

truedist - True distance

Returns:

Reachability distance

isMetric

public boolean isMetric()

Description copied from interface: DistanceFunction

Is this distance function metric (in particular, does it satisfy the triangle equation?)

Specified by:

isMetric in interface DistanceFunction<O,D extends Distance<D>>

Overrides:

isMetric in class AbstractDatabaseDistanceFunction<O,D extends Distance<D>>

Returns:

true when metric.

isSymmetric

public boolean isSymmetric()

Description copied from interface: DistanceFunction

Is this function symmetric?

Specified by:

isSymmetric in interface DistanceFunction<O,D extends Distance<D>>

Overrides:

isSymmetric in class AbstractDatabaseDistanceFunction<O,D extends Distance<D>>

Returns:

true when symmetric

getDistanceFactory

public D getDistanceFactory()

Description copied from interface: DistanceFunction

Method to get the distance functions factory.

Specified by:

getDistanceFactory in interface DistanceFunction<O,D extends Distance<D>>

Specified by:

getDistanceFactory in class AbstractDatabaseDistanceFunction<O,D extends Distance<D>>

Returns:

Factory for distance objects

getInputTypeRestriction

public TypeInformation getInputTypeRestriction()

Description copied from interface: DistanceFunction

Get the input data type of the function.

Returns:

Type restriction

equals

public boolean equals(Object obj)

Overrides:

equals in class Object