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 |
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 |
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 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 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