Class IntrinsicNearestNeighborAffinityMatrixBuilder<O>

  • Type Parameters:
    O - Object type
    All Implemented Interfaces:

    @Title("Intrinsic t-Stochastic Neighbor Embedding")
    @Reference(authors="Erich Schubert, Michael Gertz",
               title="Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection: A Remedy Against the Curse of Dimensionality?",
               booktitle="Proc. Int. Conf. Similarity Search and Applications, SISAP 2017",
    public class IntrinsicNearestNeighborAffinityMatrixBuilder<O>
    extends NearestNeighborAffinityMatrixBuilder<O>
    Build sparse affinity matrix using the nearest neighbors only, adjusting for intrinsic dimensionality. On data sets with high intrinsic dimensionality, this can give better results.

    Furthermore, this approach uses a different rule to combine affinities: rather than taking the arithmetic average of \(p_{ij}\) and \(p_{ji}\), we use \(\sqrt{p_{ij} \cdot p_{ji}}\), which prevents outliers from attaching closely to nearby clusters.


    Erich Schubert, Michael Gertz
    Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection: A Remedy Against the Curse of Dimensionality?
    Proc. Int. Conf. Similarity Search and Applications, SISAP 2017

    Erich Schubert
    • Constructor Detail

      • IntrinsicNearestNeighborAffinityMatrixBuilder

        public IntrinsicNearestNeighborAffinityMatrixBuilder​(Distance<? super O> distance,
                                                             double perplexity,
                                                             DistanceBasedIntrinsicDimensionalityEstimator estimator)
        distance - Distance function
        perplexity - Perplexity
        estimator - Estimator of intrinsic dimensionality
    • Method Detail

      • computePij

        protected void computePij​(DBIDRange ids,
                                  KNNSearcher<DBIDRef> knnq,
                                  boolean square,
                                  int numberOfNeighbours,
                                  double[][] pij,
                                  int[][] indices,
                                  double initialScale)
        Compute the sparse pij using the nearest neighbors only.
        computePij in class NearestNeighborAffinityMatrixBuilder<O>
        ids - ID range
        knnq - kNN query
        square - Use squared distances
        numberOfNeighbours - Number of neighbors to get
        pij - Output of distances
        indices - Output of indexes
        initialScale - Initial scaling factor
      • convertNeighbors

        protected void convertNeighbors​(DBIDRange ids,
                                        DBIDRef ix,
                                        boolean square,
                                        KNNList neighbours,
                                        DoubleArray dist,
                                        IntegerArray ind,
                                        Mean m)
        Load a neighbor query result into a double and and integer array, also removing the query point. This is necessary, because we have to modify the distances. TODO: sort by index, not distance
        ids - Indexes
        ix - Current Object
        square - Use squared distances
        neighbours - Neighbor list
        dist - Output distance array
        ind - Output index array
        m - Mean id, for statistics.