Package elki.outlier.distance

Class KNNWeightOutlier<O>

  • Type Parameters:
    O - the type of objects handled by this algorithm
    All Implemented Interfaces:
    Algorithm, OutlierAlgorithm
    @Title("KNNWeight outlier detection")
@Description("Outlier detection based on the sum of distances of an object to its k nearest neighbors.")
@Reference(authors="F. Angiulli, C. Pizzuti",
           title="Fast Outlier Detection in High Dimensional Spaces",
           booktitle="Proc. European Conf. Principles of Knowledge Discovery and Data Mining (PKDD\'02)",
           url="https://doi.org/10.1007/3-540-45681-3_2",
           bibkey="DBLP:conf/pkdd/AngiulliP02")
@Alias("knnw")
public class KNNWeightOutlier<O>
extends java.lang.Object
implements OutlierAlgorithm
    Outlier Detection based on the accumulated distances of a point to its k nearest neighbors.

    As in the original publication (as far as we could tell from the pseudocode included), the current point is not included in the nearest neighbors (see figures in the publication). This matches the intuition common in nearest neighbor classification, where the evaluated instances are not part of the training set; but it contrasts to the pseudocode of the kNN outlier method and the database interpretation (which returns all objects stored in the database).

    Furthermore, we report the sum of the k distances (called "weight" in the original publication). Other implementations may return the average distance instead, and therefore yield different results.

    Reference:

    F. Angiulli, C. Pizzuti
    Fast Outlier Detection in High Dimensional Spaces
    Proc. European Conf. Principles of Knowledge Discovery and Data Mining (PKDD'02)

    Since:
    0.3
    Author:
    Lisa Reichert

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected Distance<? super O> distance
      Distance function used.
      protected int kplus
      Holds the number of nearest neighbors to query (plus the query point!)
      private static Logging LOG
      The logger for this class.

    • Constructor Summary

      Constructors 
      Constructor Description
      KNNWeightOutlier​(Distance<? super O> distance, int k)
      Constructor with parameters.

    • Field Detail

      • LOG

        private static final Logging LOG
        The logger for this class.

      • distance

        protected Distance<? super O> distance
        Distance function used.

      • kplus

        protected int kplus
        Holds the number of nearest neighbors to query (plus the query point!)

    • Constructor Detail

      • KNNWeightOutlier

        public KNNWeightOutlier​(Distance<? super O> distance,
                        int k)
        Constructor with parameters.
        Parameters:
        distance - Distance function
        k - k parameter (not including query point!)

    • 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<O> relation)
        Runs the algorithm in the timed evaluation part.
        Parameters:
        relation - Data relation