gov.sandia.cognition.learning.algorithm.nearest
Class KNearestNeighborKDTree<InputType extends Vectorizable,OutputType>

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.learning.function.distance.DefaultDivergenceFunctionContainer<InputType,InputType>
          extended by gov.sandia.cognition.learning.algorithm.nearest.AbstractNearestNeighbor<InputType,OutputType>
              extended by gov.sandia.cognition.learning.algorithm.nearest.AbstractKNearestNeighbor<InputType,OutputType>
                  extended by gov.sandia.cognition.learning.algorithm.nearest.KNearestNeighborKDTree<InputType,OutputType>
Type Parameters:
InputType - Type of Vectorizable data upon which we determine similarity.
OutputType - Output of the evaluator, like Matrix, Double, String
All Implemented Interfaces:
Evaluator<InputType,OutputType>, KNearestNeighbor<InputType,OutputType>, NearestNeighbor<InputType,OutputType>, DivergenceFunctionContainer<InputType,InputType>, CloneableSerializable, Serializable, Cloneable
Direct Known Subclasses:
KNearestNeighborKDTree.Learner

@PublicationReference(author="Wikipedia",
                      title="k-nearest neighbor algorithm",
                      type=WebPage,
                      year=2008,
                      url="http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm")
public class KNearestNeighborKDTree<InputType extends Vectorizable,OutputType>
extends AbstractKNearestNeighbor<InputType,OutputType>
implements Evaluator<InputType,OutputType>

A KDTree-based implementation of the k-nearest neighbor algorithm. This algorithm has a O(n log(n)) construction time and a O(log(n)) evaluate time.

Since:
3.0
Author:
Kevin R. Dixon
See Also:
KDTree, Serialized Form

Nested Class Summary
static class KNearestNeighborKDTree.Learner<InputType extends Vectorizable,OutputType>
          This is a BatchLearner interface for creating a new KNearestNeighbor from a given dataset, simply a pass-through to the constructor of KNearestNeighbor
 
Field Summary
 
Fields inherited from class gov.sandia.cognition.learning.function.distance.DefaultDivergenceFunctionContainer
divergenceFunction
 
Fields inherited from interface gov.sandia.cognition.learning.algorithm.nearest.KNearestNeighbor
DEFAULT_K
 
Constructor Summary
KNearestNeighborKDTree()
          Creates a new instance of KNearestNeighborKDTree
KNearestNeighborKDTree(int k, KDTree<InputType,OutputType,InputOutputPair<? extends InputType,OutputType>> data, Metric<? super InputType> distanceFunction, Summarizer<? super OutputType,? extends OutputType> averager)
          Creates a new instance of KNearestNeighborKDTree
 
Method Summary
 KNearestNeighborKDTree<InputType,OutputType> clone()
          This makes public the clone method on the Object class and removes the exception that it throws.
protected  Collection<OutputType> computeNeighborhood(InputType key)
          Computes the neighbors to the input key.
 KDTree<InputType,OutputType,InputOutputPair<? extends InputType,OutputType>> getData()
          Getter for data
 Metric<? super InputType> getDivergenceFunction()
          Setter for distanceFunction
 void rebalance()
          Rebalances the internal KDTree to make the search more efficient.
 void setData(KDTree<InputType,OutputType,InputOutputPair<? extends InputType,OutputType>> data)
          Setter for data
 void setDivergenceFunction(DivergenceFunction<? super InputType,? super InputType> divergenceFunction)
          Sets the divergence function used by this object.
 void setDivergenceFunction(Metric<? super InputType> divergenceFunction)
          Sets the Metric to use.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.nearest.AbstractKNearestNeighbor
evaluate, getAverager, getK, setAverager, setK
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.nearest.AbstractNearestNeighbor
add
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface gov.sandia.cognition.evaluator.Evaluator
evaluate
 
Methods inherited from interface gov.sandia.cognition.learning.algorithm.nearest.NearestNeighbor
add
 

Constructor Detail

KNearestNeighborKDTree

public KNearestNeighborKDTree()
Creates a new instance of KNearestNeighborKDTree


KNearestNeighborKDTree

public KNearestNeighborKDTree(int k,
                              KDTree<InputType,OutputType,InputOutputPair<? extends InputType,OutputType>> data,
                              Metric<? super InputType> distanceFunction,
                              Summarizer<? super OutputType,? extends OutputType> averager)
Creates a new instance of KNearestNeighborKDTree

Parameters:
k - Number of neighbors to consider, must be greater than zero
data - KDTree that holds the data to search for neighbors.
distanceFunction - Distance metric that determines how "far" two objects are apart, where lower values indicate two objects are more similar
averager - KDTree that holds the data to search for neighbors.
Method Detail

clone

public KNearestNeighborKDTree<InputType,OutputType> clone()
Description copied from class: AbstractCloneableSerializable
This makes public the clone method on the Object class and removes the exception that it throws. Its default behavior is to automatically create a clone of the exact type of object that the clone is called on and to copy all primitives but to keep all references, which means it is a shallow copy. Extensions of this class may want to override this method (but call super.clone() to implement a "smart copy". That is, to target the most common use case for creating a copy of the object. Because of the default behavior being a shallow copy, extending classes only need to handle fields that need to have a deeper copy (or those that need to be reset). Some of the methods in ObjectUtil may be helpful in implementing a custom clone method. Note: The contract of this method is that you must use super.clone() as the basis for your implementation.

Specified by:
clone in interface CloneableSerializable
Overrides:
clone in class AbstractKNearestNeighbor<InputType extends Vectorizable,OutputType>
Returns:
A clone of this object.

getDivergenceFunction

public Metric<? super InputType> getDivergenceFunction()
Setter for distanceFunction

Specified by:
getDivergenceFunction in interface NearestNeighbor<InputType extends Vectorizable,OutputType>
Specified by:
getDivergenceFunction in interface DivergenceFunctionContainer<InputType extends Vectorizable,InputType extends Vectorizable>
Overrides:
getDivergenceFunction in class DefaultDivergenceFunctionContainer<InputType extends Vectorizable,InputType extends Vectorizable>
Returns:
Distance metric that determines how "far" two objects are apart, where lower values indicate two objects are more similar.

setDivergenceFunction

public void setDivergenceFunction(DivergenceFunction<? super InputType,? super InputType> divergenceFunction)
Description copied from class: DefaultDivergenceFunctionContainer
Sets the divergence function used by this object.

Overrides:
setDivergenceFunction in class DefaultDivergenceFunctionContainer<InputType extends Vectorizable,InputType extends Vectorizable>
Parameters:
divergenceFunction - The divergence function.

setDivergenceFunction

public void setDivergenceFunction(Metric<? super InputType> divergenceFunction)
Sets the Metric to use.

Parameters:
divergenceFunction - Metric that determines closeness.

getData

public KDTree<InputType,OutputType,InputOutputPair<? extends InputType,OutputType>> getData()
Getter for data

Specified by:
getData in interface NearestNeighbor<InputType extends Vectorizable,OutputType>
Returns:
KDTree that holds the data to search for neighbors.

setData

public void setData(KDTree<InputType,OutputType,InputOutputPair<? extends InputType,OutputType>> data)
Setter for data

Parameters:
data - KDTree that holds the data to search for neighbors.

computeNeighborhood

protected Collection<OutputType> computeNeighborhood(InputType key)
Description copied from class: AbstractKNearestNeighbor
Computes the neighbors to the input key.

Specified by:
computeNeighborhood in class AbstractKNearestNeighbor<InputType extends Vectorizable,OutputType>
Parameters:
key - Input to find the nearest neighbors of.
Returns:
Collection of nearest neighbors.

rebalance

public void rebalance()
Rebalances the internal KDTree to make the search more efficient. This is an O(n log(n)) operation with n samples.