Class VarianceOfVolume<O extends SpatialComparable>

  • Type Parameters:
    O - the type of data objects handled by this algorithm
    All Implemented Interfaces:
    Algorithm, OutlierAlgorithm

    @Reference(authors="T. Hu, S. Y. Sung",
               title="Detecting pattern-based outliers",
               booktitle="Pattern Recognition Letters 24(16)",
    public class VarianceOfVolume<O extends SpatialComparable>
    extends java.lang.Object
    implements OutlierAlgorithm
    Variance of Volume for outlier detection.

    The volume is estimated by the distance to the k-nearest neighbor, then the variance of volume is computed.

    Unfortunately, this approach needs an enormous numerical precision, and may not work for high-dimensional, non-normalized data. We therefore divide each volume by the average across the data set. This means values are even less comparable across data sets, but this avoids some of the numerical problems of this method.


    T. Hu, S. Y. Sung
    Detecting pattern-based outliers
    Pattern Recognition Letters 24(16)

    Erich Schubert
    • Field Detail

      • LOG

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

        protected int kplus
        The number of neighbors to query (plus the query point!)
    • Constructor Detail

      • VarianceOfVolume

        public VarianceOfVolume​(int k,
                                Distance<? super O> distance)
        k - number of neighbors to use for comparison
        distance - the neighborhood distance function
    • 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
        Type restriction
      • run

        public OutlierResult run​(Relation<O> relation)
        Runs the VOV algorithm on the given database.
        relation - Data to process
        VOV outlier result
      • computeVolumes

        private void computeVolumes​(KNNSearcher<DBIDRef> knnq,
                                    int dim,
                                    DBIDs ids,
                                    WritableDoubleDataStore vols)
        Compute volumes
        knnq - KNN query
        dim - Data dimensionality
        ids - IDs to process
        vols - Volume storage