Class HiCS

  • All Implemented Interfaces:
    Algorithm, OutlierAlgorithm

    @Title("HiCS: High Contrast Subspaces for Density-Based Outlier Ranking")
    @Description("Algorithm to compute High Contrast Subspaces in a database as a pre-processing step for for density-based outlier ranking methods.")
    @Reference(authors="F. Keller, E. M\u00fcller, K. B\u00f6hm",
               title="HiCS: High Contrast Subspaces for Density-Based Outlier Ranking",
               booktitle="Proc. IEEE 28th Int. Conf. on Data Engineering (ICDE 2012)",
               url="https://doi.org/10.1109/ICDE.2012.88",
               bibkey="DBLP:conf/icde/KellerMB12")
    public class HiCS
    extends java.lang.Object
    implements OutlierAlgorithm
    Algorithm to compute High Contrast Subspaces for Density-Based Outlier Ranking.

    Reference:

    F. Keller, E. Müller, K. Böhm
    HiCS: High Contrast Subspaces for Density-Based Outlier Ranking
    Proc. IEEE 28th Int. Conf. on Data Engineering (ICDE 2012)

    Since:
    0.5.0
    Author:
    Jan Brusis, Erich Schubert
    • Field Detail

      • LOG

        private static final Logging LOG
        The Logger for this class.
      • MAX_RETRIES

        private static final int MAX_RETRIES
        Maximum number of retries.
        See Also:
        Constant Field Values
      • m

        private int m
        Monte-Carlo iterations.
      • alpha

        private double alpha
        Alpha threshold.
      • outlierAlgorithm

        private OutlierAlgorithm outlierAlgorithm
        Outlier detection algorithm.
      • cutoff

        private int cutoff
        Candidates limit.
    • Constructor Detail

      • HiCS

        public HiCS​(int m,
                    double alpha,
                    OutlierAlgorithm outlierAlgorithm,
                    GoodnessOfFitTest statTest,
                    int cutoff,
                    RandomFactory rnd)
        Constructor.
        Parameters:
        m - value of m
        alpha - value of alpha
        outlierAlgorithm - Inner outlier detection algorithm
        statTest - Test to use
        cutoff - Candidate limit
        rnd - Random generator
    • 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 OutlierResult run​(Relation<? extends NumberVector> relation)
        Perform HiCS on a given database.
        Parameters:
        relation - the database
        Returns:
        The aggregated resulting scores that were assigned by the given outlier detection algorithm
      • buildOneDimIndexes

        private java.util.ArrayList<ArrayDBIDs> buildOneDimIndexes​(Relation<? extends NumberVector> relation)
        Calculates "index structures" for every attribute, i.e. sorts a ModifiableArray of every DBID in the database for every dimension and stores them in a list
        Parameters:
        relation - Relation to index
        Returns:
        List of sorted objects
      • calculateSubspaces

        private java.util.Set<HiCS.HiCSSubspace> calculateSubspaces​(Relation<? extends NumberVector> relation,
                                                                    java.util.ArrayList<ArrayDBIDs> subspaceIndex,
                                                                    java.util.Random random)
        Identifies high contrast subspaces in a given full-dimensional database.
        Parameters:
        relation - the relation the HiCS should be evaluated for
        subspaceIndex - Subspace indexes
        Returns:
        a set of high contrast subspaces
      • calculateContrast

        private void calculateContrast​(Relation<? extends NumberVector> relation,
                                       HiCS.HiCSSubspace subspace,
                                       java.util.ArrayList<ArrayDBIDs> subspaceIndex,
                                       java.util.Random random)
        Calculates the actual contrast of a given subspace.
        Parameters:
        relation - Relation to process
        subspace - Subspace
        subspaceIndex - Subspace indexes