Class SOD<V extends NumberVector>

  • Type Parameters:
    V - the type of NumberVector handled by this Algorithm
    All Implemented Interfaces:
    Algorithm, OutlierAlgorithm

    @Title("SOD: Subspace outlier degree")
    @Description("Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data")
    @Reference(authors="Hans-Peter Kriegel, Peer Kr\u00f6ger, Erich Schubert, Arthur Zimek",
               title="Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data",
               booktitle="Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2009)",
               url="https://doi.org/10.1007/978-3-642-01307-2_86",
               bibkey="DBLP:conf/pakdd/KriegelKSZ09")
    public class SOD<V extends NumberVector>
    extends java.lang.Object
    implements OutlierAlgorithm
    Subspace Outlier Degree: Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data.

    Reference:

    Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek:
    Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data
    Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2009)

    Since:
    0.2
    Author:
    Arthur Zimek
    • Field Detail

      • LOG

        private static final Logging LOG
        The logger for this class.
      • knn

        private int knn
        Neighborhood size.
      • alpha

        private double alpha
        Alpha (discriminance value).
      • models

        private boolean models
        Report models.
    • Constructor Detail

      • SOD

        public SOD​(int knn,
                   double alpha,
                   Similarity<V> similarityFunction,
                   boolean models)
        Constructor with parameters.
        Parameters:
        knn - knn value
        alpha - Alpha parameter
        similarityFunction - Shared nearest neighbor similarity function
        models - Report generated models
    • 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<V> relation)
        Performs the SOD algorithm on the given database.
        Parameters:
        relation - Data relation to process
        Returns:
        Outlier result
      • getNearestNeighbors

        private DBIDs getNearestNeighbors​(Relation<V> relation,
                                          SimilarityQuery<V> simQ,
                                          DBIDRef queryObject)
        Get the k nearest neighbors in terms of the shared nearest neighbor distance.

        The query object is excluded from the knn list.

        FIXME: move this to the database layer.

        Parameters:
        relation - the database holding the objects
        simQ - similarity function
        queryObject - the query object for which the kNNs should be determined
        Returns:
        the k nearest neighbors in terms of the shared nearest neighbor distance without the query object
      • computePerDimensionVariances

        private static double[] computePerDimensionVariances​(Relation<? extends NumberVector> relation,
                                                             double[] center,
                                                             DBIDs neighborhood)
        Compute the per-dimension variances for the given neighborhood and center.
        Parameters:
        relation - Data relation
        center - Center vector
        neighborhood - Neighbors
        Returns:
        Per-dimension variances.
      • subspaceOutlierDegree

        private double subspaceOutlierDegree​(V queryObject,
                                             double[] center,
                                             long[] weightVector)
        Compute SOD score.
        Parameters:
        queryObject - Query object
        center - Center vector
        weightVector - Weight vector
        Returns:
        sod score