Package elki.clustering.optics

Class 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

    • Field Detail

      • LOG

        private static final Logging LOG
        The logger for this class.

      • 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

      • getInputTypeRestriction

        public TypeInformation[] getInputTypeRestriction()
        Description copied from interface: Algorithm
        Get the input type restriction used for negotiating the data query.
        Specified by:
        getInputTypeRestriction in interface Algorithm
        Returns:
        Type restriction

      • 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 result
        ixi - Parameter 1 - Xi
        minpts - 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 order
        cstart - Cluster start
        cend - Cluster end
        tmp - 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 value
        sdaset - Set of steep down areas.