public class KDTree extends NearestNeighbourSearch implements TechnicalInformationHandler
@article{Friedman1977, author = {Jerome H. Friedman and Jon Luis Bentley and Raphael Ari Finkel}, journal = {ACM Transactions on Mathematics Software}, month = {September}, number = {3}, pages = {209-226}, title = {An Algorithm for Finding Best Matches in Logarithmic Expected Time}, volume = {3}, year = {1977} } @techreport{Moore1991, author = {Andrew Moore}, booktitle = {University of Cambridge Computer Laboratory Technical Report No. 209}, howpublished = {Extract from PhD Thesis}, title = {A tutorial on kd-trees}, year = {1991}, HTTP = {Available from http://www.autonlab.org/autonweb/14665.html} }Valid options are:
-S <classname and options> Node splitting method to use. (default: weka.core.neighboursearch.kdtrees.SlidingMidPointOfWidestSide)
-W <value> Set minimal width of a box (default: 1.0E-2).
-L Maximal number of instances in a leaf (default: 40).
-N Normalizing will be done (Select dimension for split, with normalising to universe).
Modifier and Type | Field and Description |
---|---|
static int |
MAX
The index of MAX value in attributes' range array.
|
static int |
MIN
The index of MIN value in attributes' range array.
|
static int |
WIDTH
The index of WIDTH (MAX-MIN) value in attributes' range array.
|
Constructor and Description |
---|
KDTree()
Creates a new instance of KDTree.
|
KDTree(Instances insts)
Creates a new instance of KDTree.
|
Modifier and Type | Method and Description |
---|---|
void |
addInstanceInfo(Instance instance)
Adds one instance to KDTree loosly.
|
void |
assignSubToCenters(KDTreeNode node,
Instances centers,
int[] centList,
int[] assignments)
Assigns instances of this node to center.
|
void |
centerInstances(Instances centers,
int[] assignments,
double pc)
Assigns instances to centers using KDTree.
|
java.util.Enumeration<java.lang.String> |
enumerateMeasures()
Returns an enumeration of the additional measure names.
|
DistanceFunction |
getDistanceFunction()
returns the distance function currently in use.
|
double[] |
getDistances()
Returns the distances to the kNearest or 1 nearest neighbour currently
found with either the kNearestNeighbours or the nearestNeighbour method.
|
int |
getMaxInstInLeaf()
Get the maximum number of instances in a leaf.
|
double |
getMeasure(java.lang.String additionalMeasureName)
Returns the value of the named measure.
|
double |
getMinBoxRelWidth()
Gets the minimum relative box width.
|
KDTreeNodeSplitter |
getNodeSplitter()
Returns the splitting method currently in use to split the nodes of the
KDTree.
|
boolean |
getNormalizeNodeWidth()
Gets the normalize flag.
|
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 the k nearest neighbours of the supplied instance.
|
java.util.Enumeration<Option> |
listOptions()
Returns an enumeration describing the available options.
|
java.lang.String |
maxInstInLeafTipText()
Tip text for this property.
|
double |
measureMaxDepth()
Returns the depth of the tree.
|
double |
measureNumLeaves()
Returns the number of leaves.
|
double |
measureTreeSize()
Returns the size of the tree.
|
java.lang.String |
minBoxRelWidthTipText()
Tip text for this property.
|
Instance |
nearestNeighbour(Instance target)
Returns the nearest neighbour of the supplied target
instance.
|
java.lang.String |
nodeSplitterTipText()
Returns the tip text for this property.
|
java.lang.String |
normalizeNodeWidthTipText()
Tip text for this property.
|
void |
setDistanceFunction(DistanceFunction df)
sets the distance function to use for nearest neighbour search.
|
void |
setInstances(Instances instances)
Builds the KDTree on the given set of instances.
|
void |
setMaxInstInLeaf(int i)
Sets the maximum number of instances in a leaf.
|
void |
setMeasurePerformance(boolean measurePerformance)
Sets whether to calculate the performance statistics or not.
|
void |
setMinBoxRelWidth(double i)
Sets the minimum relative box width.
|
void |
setNodeSplitter(KDTreeNodeSplitter splitter)
Sets the splitting method to use to split the nodes of the KDTree.
|
void |
setNormalizeNodeWidth(boolean n)
Sets the flag for normalizing the widths of a KDTree Node by the width of
the dimension in the universe.
|
void |
setOptions(java.lang.String[] options)
Parses a given list of options.
|
void |
update(Instance instance)
Adds one instance to the KDTree.
|
combSort11, distanceFunctionTipText, getInstances, getMeasurePerformance, getPerformanceStats, measurePerformanceTipText, quickSort
public static final int MIN
public static final int MAX
public static final int WIDTH
public KDTree()
public KDTree(Instances insts)
insts
- The instances/points on which the BallTree
should be built on.public TechnicalInformation getTechnicalInformation()
getTechnicalInformation
in interface TechnicalInformationHandler
public Instances kNearestNeighbours(Instance target, int k) throws java.lang.Exception
kNearestNeighbours
in class NearestNeighbourSearch
target
- The instance to find the nearest neighbours for.k
- The number of neighbours to find.java.lang.Exception
- if the nearest neighbour could not be found.public Instance nearestNeighbour(Instance target) throws java.lang.Exception
nearestNeighbour
in class NearestNeighbourSearch
target
- The instance to find the nearest neighbour for.java.lang.Exception
- if the neighbours could not be found.public double[] getDistances() throws java.lang.Exception
getDistances
in class NearestNeighbourSearch
java.lang.Exception
- if called before calling kNearestNeighbours or
nearestNeighbours.public void setInstances(Instances instances) throws java.lang.Exception
setInstances
in class NearestNeighbourSearch
instances
- The insts on which the KDTree is to be
built.java.lang.Exception
- If some error occurs while
building the KDTreepublic void update(Instance instance) throws java.lang.Exception
update
in class NearestNeighbourSearch
instance
- the instance to be added. Usually the newly added instance in the
training set.java.lang.Exception
- If the instance cannot be added.public void addInstanceInfo(Instance instance)
addInstanceInfo
in class NearestNeighbourSearch
instance
- the new instance. Usually this is the test instance
supplied to update the range of attributes in the distance function.public double measureTreeSize()
public double measureNumLeaves()
public double measureMaxDepth()
public java.util.Enumeration<java.lang.String> 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 value.java.lang.IllegalArgumentException
- If the named measure
is not supported.public void setMeasurePerformance(boolean measurePerformance)
setMeasurePerformance
in class NearestNeighbourSearch
measurePerformance
- Should be true if performance
statistics are to be measured.public void centerInstances(Instances centers, int[] assignments, double pc) throws java.lang.Exception
centers
- the current centersassignments
- the centerindex for each instancepc
- the threshold value for pruning.java.lang.Exception
- If there is some problem
assigning instances to centers.public void assignSubToCenters(KDTreeNode node, Instances centers, int[] centList, int[] assignments) throws java.lang.Exception
node
- The KDTreeNode whose instances are to be assigned.centers
- all the input centerscentList
- the list of centers to work withassignments
- index list of last assignmentsjava.lang.Exception
- If there is error assigning the instances.public java.lang.String minBoxRelWidthTipText()
public void setMinBoxRelWidth(double i)
i
- the minimum relative box widthpublic double getMinBoxRelWidth()
public java.lang.String maxInstInLeafTipText()
public void setMaxInstInLeaf(int i)
i
- the maximum number of instances in a leafpublic int getMaxInstInLeaf()
public java.lang.String normalizeNodeWidthTipText()
public void setNormalizeNodeWidth(boolean n)
n
- true to use normalizing.public boolean getNormalizeNodeWidth()
public DistanceFunction getDistanceFunction()
getDistanceFunction
in class NearestNeighbourSearch
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 nodeSplitterTipText()
public KDTreeNodeSplitter getNodeSplitter()
public void setNodeSplitter(KDTreeNodeSplitter splitter)
splitter
- The KDTreeNodeSplitter to use.public java.lang.String globalInfo()
globalInfo
in class NearestNeighbourSearch
public java.util.Enumeration<Option> listOptions()
listOptions
in interface OptionHandler
listOptions
in class NearestNeighbourSearch
public void setOptions(java.lang.String[] options) throws java.lang.Exception
-S <classname and options> Node splitting method to use. (default: weka.core.neighboursearch.kdtrees.SlidingMidPointOfWidestSide)
-W <value> Set minimal width of a box (default: 1.0E-2).
-L Maximal number of instances in a leaf (default: 40).
-N Normalizing will be done (Select dimension for split, with normalising to universe).
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 java.lang.String getRevision()
getRevision
in interface RevisionHandler