Package elki.clustering.optics
Class OPTICSXi
- java.lang.Object
-
- elki.clustering.optics.OPTICSXi
-
- All Implemented Interfaces:
Algorithm
,ClusteringAlgorithm<Clustering<OPTICSModel>>
@Title("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") @Priority(200) public class OPTICSXi extends java.lang.Object implements ClusteringAlgorithm<Clustering<OPTICSModel>>
Extract clusters from OPTICS plots using the original ξ (Xi) extraction, which defines steep areas if the reachability drops below 1-ξ, respectively increases to 1+ξ, of the current value, then constructs valleys that begin with a steep down, and end with a matching steep up area.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 Description private static class
OPTICSXi.ClusterHierarchyBuilder
Class to build the hierarchical clustering result structure.static class
OPTICSXi.Par
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 xi-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 areasstatic class
OPTICSXi.SteepUpArea
Data structure to represent a steep-down-area for the xi method.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field 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
-
Constructor Summary
Constructors Constructor Description OPTICSXi(OPTICSTypeAlgorithm optics, double xi)
Constructor.OPTICSXi(OPTICSTypeAlgorithm optics, double xi, boolean nocorrect, boolean keepsteep)
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Clustering<OPTICSModel>
autorun(Database database)
Try to auto-run the algorithm on a database by calling a method calledrun
, with an optionalDatabase
first, and with data relations as specified byAlgorithm.getInputTypeRestriction()
.private Clustering<OPTICSModel>
extractClusters(ClusterOrder clusterOrderResult, double ixi, int minpts)
Extract clusters from a cluster order result.TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.private static int
predecessorFilter(ClusterOrder clusterOrderResult, int cstart, int cend, DBIDArrayIter tmp)
Filtering step to remove bad tailing points from the clusters.Clustering<OPTICSModel>
run(ClusterOrder clusterOrder)
Process the cluster order of an OPTICS clustering.private static void
updateFilterSDASet(double mib, java.util.List<OPTICSXi.SteepDownArea> sdaset, double ixi)
Update the mib values of SteepDownAreas, and remove obsolete areas.
-
-
-
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 usexi
- Xi valuenocorrect
- Disable the predecessor correctionkeepsteep
- Keep the steep areas for visualization
-
OPTICSXi
public OPTICSXi(OPTICSTypeAlgorithm optics, double xi)
Constructor.- Parameters:
optics
- OPTICS algorithm to usexi
- Xi value
-
-
Method Detail
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Returns:
- Type restriction
-
autorun
public Clustering<OPTICSModel> autorun(Database database)
Description copied from interface:Algorithm
Try to auto-run the algorithm on a database by calling a method calledrun
, with an optionalDatabase
first, and with data relations as specified byAlgorithm.getInputTypeRestriction()
.- Specified by:
autorun
in interfaceAlgorithm
- Specified by:
autorun
in interfaceClusteringAlgorithm<Clustering<OPTICSModel>>
- Parameters:
database
- the database to run the algorithm on- Returns:
- the Result computed by this algorithm
-
run
public Clustering<OPTICSModel> run(ClusterOrder clusterOrder)
Process the cluster order of an OPTICS clustering.- Parameters:
clusterOrder
- cluster order result- Returns:
- Clustering
-
extractClusters
private Clustering<OPTICSModel> extractClusters(ClusterOrder clusterOrderResult, double ixi, int minpts)
Extract clusters from a cluster order result.- Parameters:
clusterOrderResult
- cluster order resultixi
- Parameter 1 - Ximinpts
- Parameter minPts
-
predecessorFilter
private static int predecessorFilter(ClusterOrder clusterOrderResult, int cstart, int cend, DBIDArrayIter tmp)
Filtering step to remove bad tailing points from the clusters.Erich Schubert, Michael Gertz
Improving the Cluster Structure Extracted from OPTICS Plots
Proc. Lernen, Wissen, Daten, Analysen (LWDA 2018)- Parameters:
clusterOrderResult
- Cluster ordercstart
- Cluster startcend
- Cluster endtmp
- Cluster order iterator- Returns:
- New end position
-
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 valuesdaset
- Set of steep down areas.
-
-