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.
|
Enumeration |
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(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.
|
String[] |
getOptions()
Gets the current settings of KDtree.
|
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.
|
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.
|
Enumeration |
listOptions()
Returns an enumeration describing the available options.
|
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.
|
String |
minBoxRelWidthTipText()
Tip text for this property.
|
Instance |
nearestNeighbour(Instance target)
Returns the nearest neighbour of the supplied target
instance.
|
String |
nodeSplitterTipText()
Returns the tip text for this property.
|
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(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 Exception
kNearestNeighbours
in class NearestNeighbourSearch
target
- The instance to find the nearest neighbours for.k
- The number of neighbours to find.Exception
- if the nearest neighbour could not be found.public Instance nearestNeighbour(Instance target) throws Exception
nearestNeighbour
in class NearestNeighbourSearch
target
- The instance to find the nearest neighbour for.Exception
- if the neighbours could not be found.public double[] getDistances() throws Exception
getDistances
in class NearestNeighbourSearch
Exception
- if called before calling kNearestNeighbours or
nearestNeighbours.public void setInstances(Instances instances) throws Exception
setInstances
in class NearestNeighbourSearch
instances
- The insts on which the KDTree is to be
built.Exception
- If some error occurs while
building the KDTreepublic void update(Instance instance) throws Exception
update
in class NearestNeighbourSearch
instance
- the instance to be added. Usually the newly added instance in the
training set.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 Enumeration enumerateMeasures()
enumerateMeasures
in interface AdditionalMeasureProducer
enumerateMeasures
in class NearestNeighbourSearch
public double getMeasure(String additionalMeasureName)
getMeasure
in interface AdditionalMeasureProducer
getMeasure
in class NearestNeighbourSearch
additionalMeasureName
- the name of
the measure to query for its value.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 Exception
centers
- the current centersassignments
- the centerindex for each instancepc
- the threshold value for pruning.Exception
- If there is some problem
assigning instances to centers.public void assignSubToCenters(KDTreeNode node, Instances centers, int[] centList, int[] assignments) throws 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 assignmentsException
- If there is error assigning the instances.public String minBoxRelWidthTipText()
public void setMinBoxRelWidth(double i)
i
- the minimum relative box widthpublic double getMinBoxRelWidth()
public String maxInstInLeafTipText()
public void setMaxInstInLeaf(int i)
i
- the maximum number of instances in a leafpublic int getMaxInstInLeaf()
public 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 Exception
setDistanceFunction
in class NearestNeighbourSearch
df
- the distance function to useException
- if not EuclideanDistancepublic String nodeSplitterTipText()
public KDTreeNodeSplitter getNodeSplitter()
public void setNodeSplitter(KDTreeNodeSplitter splitter)
splitter
- The KDTreeNodeSplitter to use.public String globalInfo()
globalInfo
in class NearestNeighbourSearch
public Enumeration listOptions()
listOptions
in interface OptionHandler
listOptions
in class NearestNeighbourSearch
public void setOptions(String[] options) throws 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 stringsException
- if an option is not supportedpublic String[] getOptions()
getOptions
in interface OptionHandler
getOptions
in class NearestNeighbourSearch
public String getRevision()
getRevision
in interface RevisionHandler
Copyright © 2019 University of Waikato, Hamilton, NZ. All rights reserved.