Neighbors (Nearest, Farthest, Range, k, Classification)

Nearest neighbor search is a very fundamental algorithm in statistics and machine learning. The goal is to find each a given or query point’s nearest neighbor from a reference dataset. The distance between points is often defined in terms of the Euclidean distance. In general any similarity can be used, but only if the similarity satisfies the triangular inequality or if it is a bregman divergence. We have fast algorithms for computing all nearest/farthest/range/k neighbors with metrics and bregman divergences and use them for classification.

In short:

• For dense continuous data use euclidean metric.
• For normalized histograms (probabilities) use KL divergence (You typically use it in documents after doing Non-Negative Matrix Factorization or LSA)
• For sparse data points that are normalized to be probilites (nonegative and sum up to one) use the hellinger metric. The most typical example is netflix or bag of words representation of documents.

Related articles:

• Nearest Neighbor
  • Computational Complexity
  • 1305 Implementation
  • K-Nearest Neighbor Classifier
  • Other Extensions of Nearest Neighbor Implemented in 1305
• NEW !!! Nearest Neighbors with Bregman Divergences
  • Planned Extensions of Nearest Neighbor Implemented in 1305

Downloading

You can download it from here

Usage examples

NOTE: From 0.4.4 release the driver for nearest neighbor allkn will become deprecated
      Instead you can use
        mnneighbors   : for nearest neighbors based on a metric
        mfneighbors   : for further neighbors based on a metric
        mnnclassifier : for nearest neighbor classification based on metric neighbors
        bnneighbors   : for nearest neighbors based on a bregman divergence
        bnnclassifier : for nearest neighbor classification based on bregman divergence

• Running all sorts of neighbors, command line arguments
• A Simple Example
• Kd-tree versus Ball-tree
• Sparse dataset
• Bichromatic Neighbors
• Furthest neighbors
• Range neighbors
• Dual tree, single tree algorithm
• Bregman divergence neighbors
• Nearest neighbor with the Hellinger metric

Suggestions and bug reports

We would like to know your opinion about our product. Please send us bug reports and suggestions at support@analytics1305.com

If you didn't find an answer to your question, check the forum http://www.analytics1305.com/forum