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

Class OPTICSXi

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<Clustering<OPTICSModel>>

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.OPTICSXi

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<OPTICSModel>>

@Title(value="OPTICS Xi Cluster Extraction")
 @Reference(authors="Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, J\u00f6rg Sander",title="OPTICS: Ordering Points to Identify the Clustering Structure",booktitle="Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD \'99)",url="https://doi.org/10.1145/304181.304187",bibkey="DBLP:conf/sigmod/AnkerstBKS99") @Reference(authors="Erich Schubert, Michael Gertz",title="Improving the Cluster Structure Extracted from OPTICS Plots",booktitle="Proc. Lernen, Wissen, Daten, Analysen (LWDA 2018)",url="http://ceur-ws.org/Vol-2191/paper37.pdf",bibkey="DBLP:conf/lwa/SchubertG18")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.clustering.OPTICSXi")
 @Priority(value=200)
public class OPTICSXi
extends AbstractAlgorithm<Clustering<OPTICSModel>>
implements ClusteringAlgorithm<Clustering<OPTICSModel>>

Extract clusters from OPTICS Plots using the original Xi extraction.

Note: this implementation includes an additional filter step that prunes elements from a steep up area that don't have the predecessor in the cluster. This removes a popular type of artifacts.

Reference:

Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander
OPTICS: Ordering Points to Identify the Clustering Structure
Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD '99)

Filtering technique:

Erich Schubert, Michael Gertz
Improving the Cluster Structure Extracted from OPTICS Plots
Proc. Lernen, Wissen, Daten, Analysen (LWDA 2018)

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	OPTICSXi.Parameterizer Parameterization class.
static class	OPTICSXi.SteepArea Data structure to represent a steep-down-area for the xi method.
static class	OPTICSXi.SteepAreaResult Result containing the chi-steep areas.
static class	OPTICSXi.SteepDownArea Data structure to represent a steep-down-area for the xi method.
private static class	OPTICSXi.SteepScanPosition Position when scanning for steep areas
static class	OPTICSXi.SteepUpArea Data structure to represent a steep-down-area for the xi method.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) boolean	keepsteep Keep the steep areas, for visualization.
private static Logging	LOG The logger for this class.
(package private) boolean	nocorrect Disable the predecessor correction.
(package private) OPTICSTypeAlgorithm	optics The actual algorithm we use.
(package private) double	xi Xi parameter

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

ALGORITHM_ID

Constructor Summary

Constructors

Constructor and Description
OPTICSXi(OPTICSTypeAlgorithm optics, double xi) Constructor.
OPTICSXi(OPTICSTypeAlgorithm optics, double xi, boolean nocorrect, boolean keepsteep) Constructor.

Method Summary

Modifier and Type	Method and Description
private Clustering<OPTICSModel>	extractClusters(ClusterOrder clusterOrderResult, Relation<?> relation, double ixi, int minpts) Extract clusters from a cluster order result.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
Clustering<OPTICSModel>	run(Database database, Relation<?> relation)
private static void	updateFilterSDASet(double mib, java.util.List<OPTICSXi.SteepDownArea> sdaset, double ixi) Update the mib values of SteepDownAreas, and remove obsolete areas.

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.clustering.ClusteringAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

optics

OPTICSTypeAlgorithm optics

The actual algorithm we use.

xi

double xi

Xi parameter

nocorrect

boolean nocorrect

Disable the predecessor correction.

keepsteep

boolean keepsteep

Keep the steep areas, for visualization.

Constructor Detail

OPTICSXi

public OPTICSXi(OPTICSTypeAlgorithm optics,
                double xi,
                boolean nocorrect,
                boolean keepsteep)

Constructor.

Parameters:

optics - OPTICS algorithm to use

xi - Xi value

nocorrect - Disable the predecessor correction

keepsteep - Keep the steep areas for visualization

OPTICSXi

public OPTICSXi(OPTICSTypeAlgorithm optics,
                double xi)

Constructor.

Parameters:

optics - OPTICS algorithm to use

xi - Xi value

Method Detail

run

public Clustering<OPTICSModel> run(Database database,
                                   Relation<?> relation)

extractClusters

private Clustering<OPTICSModel> extractClusters(ClusterOrder clusterOrderResult,
                                                Relation<?> relation,
                                                double ixi,
                                                int minpts)

Extract clusters from a cluster order result.

Parameters:

clusterOrderResult - cluster order result

relation - Relation

ixi - Parameter 1 - Xi

minpts - Parameter minPts

updateFilterSDASet

private static void updateFilterSDASet(double mib,
                                       java.util.List<OPTICSXi.SteepDownArea> sdaset,
                                       double ixi)

Update the mib values of SteepDownAreas, and remove obsolete areas.

Parameters:

mib - Maximum in-between value

sdaset - Set of steep down areas.

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<Clustering<OPTICSModel>>

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<Clustering<OPTICSModel>>

Returns:

the static logger