public class CoverTree extends NearestNeighbourSearch implements TechnicalInformationHandler
@inproceedings{Beygelzimer2006, address = {New York, NY, USA}, author = {Alina Beygelzimer and Sham Kakade and John Langford}, booktitle = {ICML'06: Proceedings of the 23rd international conference on Machine learning}, pages = {97-104}, publisher = {ACM Press}, title = {Cover trees for nearest neighbor}, year = {2006}, location = {Pittsburgh, Pennsylvania}, HTTP = {http://hunch.net/\~jl/projects/cover_tree/cover_tree.html} }Valid options are:
-B <value> Set base of the expansion constant (default = 1.3).
Modifier and Type | Class and Description |
---|---|
class |
CoverTree.CoverTreeNode
class representing a node of the cover tree.
|
Constructor and Description |
---|
CoverTree()
default constructor.
|
Modifier and Type | Method and Description |
---|---|
void |
addInstanceInfo(Instance ins)
Adds the given instance info.
|
java.lang.String |
baseTipText()
Returns the tip text for this property.
|
java.util.Enumeration |
enumerateMeasures()
Returns an enumeration of the additional measure names.
|
double |
getBase()
Returns the base in use for expansion constant.
|
double[] |
getDistances()
Returns the distances of the (k)-NN(s) found earlier
by kNearestNeighbours()/nearestNeighbour().
|
double |
getMeasure(java.lang.String additionalMeasureName)
Returns the value of the named measure.
|
java.lang.String[] |
getOptions()
Gets the current settings of KDtree.
|
java.lang.String |
getRevision()
Returns the revision string.
|
TechnicalInformation |
getTechnicalInformation()
Returns an instance of a TechnicalInformation object, containing detailed
information about the technical background of this class, e.g., paper
reference or book this class is based on.
|
java.lang.String |
globalInfo()
Returns a string describing this nearest neighbour search algorithm.
|
Instances |
kNearestNeighbours(Instance target,
int k)
Returns k-NNs of a given target instance, from among the previously
supplied training instances (supplied through setInstances method)
P.S.: May return more than k-NNs if more one instances have
the same distance to the target as the kth NN.
|
java.util.Enumeration |
listOptions()
Returns an enumeration describing the available options.
|
static void |
main(java.lang.String[] args)
Method for testing the class from command line.
|
double |
measureMaxDepth()
Returns the depth of the tree.
|
double |
measureNumLeaves()
Returns the number of leaves.
|
double |
measureTreeSize()
Returns the size of the tree.
|
Instance |
nearestNeighbour(Instance target)
Returns the NN instance of a given target instance, from among
the previously supplied training instances.
|
void |
setBase(double b)
Sets the base to use for expansion constant.
|
void |
setDistanceFunction(DistanceFunction df)
Sets the distance function to use for nearest neighbour search.
|
void |
setInstances(Instances instances)
Builds the Cover Tree on the given set of instances.
|
void |
setOptions(java.lang.String[] options)
Parses a given list of options.
|
void |
update(Instance ins)
Adds an instance to the cover tree.
|
combSort11, distanceFunctionTipText, getDistanceFunction, getInstances, getMeasurePerformance, getPerformanceStats, measurePerformanceTipText, quickSort, setMeasurePerformance
public java.lang.String globalInfo()
globalInfo
in class NearestNeighbourSearch
public TechnicalInformation getTechnicalInformation()
getTechnicalInformation
in interface TechnicalInformationHandler
public java.util.Enumeration listOptions()
listOptions
in interface OptionHandler
listOptions
in class NearestNeighbourSearch
public void setOptions(java.lang.String[] options) throws java.lang.Exception
-B <value> Set base of the expansion constant (default = 1.3).
setOptions
in interface OptionHandler
setOptions
in class NearestNeighbourSearch
options
- the list of options as an array of stringsjava.lang.Exception
- if an option is not supportedpublic java.lang.String[] getOptions()
getOptions
in interface OptionHandler
getOptions
in class NearestNeighbourSearch
public Instances kNearestNeighbours(Instance target, int k) throws java.lang.Exception
kNearestNeighbours
in class NearestNeighbourSearch
target
- The instance for which k-NNs are required.k
- The number of k-NNs to find.java.lang.Exception
- If there is some problem find the k-NNs.public Instance nearestNeighbour(Instance target) throws java.lang.Exception
nearestNeighbour
in class NearestNeighbourSearch
target
- The instance for which NN is required.java.lang.Exception
- If there is some problem finding the nearest
neighbour.public double[] getDistances() throws java.lang.Exception
getDistances
in class NearestNeighbourSearch
java.lang.Exception
- If the tree hasn't been built (by calling
setInstances()), or none of kNearestNeighbours() or
nearestNeighbour() has been called before.public void setInstances(Instances instances) throws java.lang.Exception
setInstances
in class NearestNeighbourSearch
instances
- The insts on which the Cover Tree is to be
built.java.lang.Exception
- If some error occurs while
building the Cover Treepublic void update(Instance ins) throws java.lang.Exception
update
in class NearestNeighbourSearch
ins
- The instance to add.java.lang.Exception
- Alway throws this, as current
implementation doesn't allow addition of instances
after building.public void addInstanceInfo(Instance ins)
addInstanceInfo
in class NearestNeighbourSearch
ins
- The instance to add the information of. Usually this is
the test instance supplied to update the range of
attributes in the distance function.public void setDistanceFunction(DistanceFunction df) throws java.lang.Exception
setDistanceFunction
in class NearestNeighbourSearch
df
- the distance function to usejava.lang.Exception
- if not EuclideanDistancepublic java.lang.String baseTipText()
public double getBase()
public void setBase(double b)
b
- the new base;public double measureTreeSize()
public double measureNumLeaves()
public double measureMaxDepth()
public java.util.Enumeration enumerateMeasures()
enumerateMeasures
in interface AdditionalMeasureProducer
enumerateMeasures
in class NearestNeighbourSearch
public double getMeasure(java.lang.String additionalMeasureName)
getMeasure
in interface AdditionalMeasureProducer
getMeasure
in class NearestNeighbourSearch
additionalMeasureName
- the name of the measure to query for
its valuejava.lang.IllegalArgumentException
- if the named measure is not supportedpublic java.lang.String getRevision()
getRevision
in interface RevisionHandler
public static void main(java.lang.String[] args)
args
- The supplied command line arguments.