All Packages  Class Hierarchy  This Package  Previous  Next  Index  WEKA's home

Class weka.core.KDTree 

java.lang.Object
    |
    +----weka.core.KDTree
public class KDTree
extends java.lang.Object
implements OptionHandler, java.io.Serializable
This is a KD-Tree structure that stores instances using a divide and conquer method. The connection to dataset is only a reference. For the tree structure the indexes are stored in a dynamic array Building the tree: If a node has (option -L) instances no further splitting is done. Also if the split would leave one side empty, the branch is not split any further even if the instances in the resulting node are more than instances. -P
Pruning flag.

-W
minimal width of a box -L
maximal instance number in a leaf -D Distance function to be used (default = Euclidean distance) -N
Set Normalization. Used when building the tree and selecting the widest dimension, each dimension is 'normalized' to the universe range. -U
Set debuglevel.

Version:
$Revision: 1.4 $
Author:
Gabi Schmidberger (gabi@cs.waikato.ac.nz)
Author:
Malcolm Ware (mfw4@cs.waikato.ac.nz)

Variable Index

o R_MAX
 
o R_MIN
Index in ranges for LOW and HIGH and WIDTH
o R_WIDTH
 

Constructor Index

o KDTree()
Default Constructor
o KDTree(KDTree)
Constructor, copies all options from an existing KDTree.

Method Index

o addLooslyInstance(Instance)
Adds one instance to KDTree loosly.
o buildKDTree(Instances)
Builds the KDTree.
o buildKDTree(Instances, double[][])
Builds the KDTree.
o centerInstances(Instances, int[], double)
Assigns instances to centers using KDTree.
o deleteInstance(Instance)
Deletes one instance in the KDTree.
o deleteInstance(int)
Deletes one instance in the KDTree.
o findKNearestNeighbour(Instance, int, int[], double[])
Find k nearest neighbours to target.
o getDebugLevel()
Gets the debug level.
o getDistanceFunction()
Gets the distance function.
o getInstances()
Gets instances used in the tree.
o getInstList()
Gets instance list used in the tree.
o getMaxInstInLeaf()
Get the maximum number of instances in a leaf.
o getMinBoxRelWidth()
Gets the minimum relative box width.
o getNormalize()
Gets the normalize flag.
o getOptions()
Gets the current settings of KDtree.
o getPrune()
Gets the pruning flag.
o isValid()
Returns true if valid flag is true.
o listOptions()
Returns an enumeration describing the available options.
o main(String[])
Main method for testing this class
o numInstances()
Gets number of instances in KDTree.
o setDebugLevel(int)
Sets the debug level.
o setDistanceFunction(DistanceFunction)
Sets the distance function.
o setMaxInstInLeaf(int)
Sets the maximum number of instances in a leaf.
o setMinBoxRelWidth(double)
Sets the minimum relative box width.
o setNormalize(boolean)
Sets the flag for normalizing the widths of a KDTree Node by the width of the dimension in the universe.
o setOptions(String[])
Parses a given list of options.
o setPrune(boolean)
Sets the flag for pruning of the blacklisting algorithm.
o setValid(boolean)
Sets KDTree to be valid for dataset in m_Instances.
o toString()
toString
o updateKDTree(Instance)
Adds one instance to the KDTree.

Field Detail

o R_MIN
public static int R_MIN
          Index in ranges for LOW and HIGH and WIDTH
o R_MAX
public static int R_MAX
o R_WIDTH
public static int R_WIDTH

Constructor Detail

o KDTree
public KDTree()
          Default Constructor
o KDTree
public KDTree(KDTree tree)
          Constructor, copies all options from an existing KDTree.
Parameters:
tree - the KDTree to copy from

Method Detail

o addLooslyInstance
public void addLooslyInstance(Instance instance)
          Adds one instance to KDTree loosly. It only changes the ranges. The ranges are important for the distance function.
Parameters:
instance - the new instance
o buildKDTree
public void buildKDTree(Instances instances) throws java.lang.Exception
          Builds the KDTree.
Parameters:
instances - instances to build the tree of
o buildKDTree
public void buildKDTree(Instances instances,
                        double ranges[][]) throws java.lang.Exception
          Builds the KDTree. It is adviseable to run the replace missing attributes filter on the passed instances first.
Parameters:
instances - instances to build the tree of
o updateKDTree
public void updateKDTree(Instance instance) throws java.lang.Exception
          Adds one instance to the KDTree.
Parameters:
instance - the instance to be added
o deleteInstance
public void deleteInstance(Instance instance) throws java.lang.Exception
          Deletes one instance in the KDTree.
Parameters:
instance - the instance to be deleted
o deleteInstance
public boolean deleteInstance(int index) throws java.lang.Exception
          Deletes one instance in the KDTree.
Parameters:
index - the index of the instance to be deleted
Returns:
true if instance was deleted
o toString
public java.lang.String toString()
          toString
Returns:
string representing the tree
Overrides:
toString in class java.lang.Object
o centerInstances
public void centerInstances(Instances centers,
                            int assignments[],
                            double pc) throws java.lang.Exception
          Assigns instances to centers using KDTree.
Parameters:
centers - the current centers
assignments - the centerindex for each instance
pc - the threshold value for pruning.
p - True if pruning should be used.
o findKNearestNeighbour
public int findKNearestNeighbour(Instance target,
                                 int kNN,
                                 int nearestList[],
                                 double distanceList[]) throws java.lang.Exception
          Find k nearest neighbours to target. This is the main method.
Parameters:
target - the instance to find nearest neighbour for
maxDist - the distance to the nearest neighbor so far
nearest - the index of the nearest neighbor (second return value)
o setValid
public void setValid(boolean valid)
          Sets KDTree to be valid for dataset in m_Instances.
Parameters:
flag - if KDtree is valid
o isValid
public boolean isValid()
          Returns true if valid flag is true.
Returns:
flag if KDtree is valid
o numInstances
public int numInstances()
          Gets number of instances in KDTree.
Returns:
number of instances
o getInstances
public Instances getInstances()
          Gets instances used in the tree.
Returns:
model information
o getInstList
public DynamicArrayOfPosInt getInstList()
          Gets instance list used in the tree.
Returns:
instance list
o setDistanceFunction
public void setDistanceFunction(DistanceFunction distanceF)
          Sets the distance function.
Parameters:
distanceF - the distance function with all options set
o getDistanceFunction
public DistanceFunction getDistanceFunction()
          Gets the distance function.
Returns:
the distance function
o setMinBoxRelWidth
public void setMinBoxRelWidth(double i) throws java.lang.Exception
          Sets the minimum relative box width.
Parameters:
i - the minimum relative box width
o getMinBoxRelWidth
public double getMinBoxRelWidth()
          Gets the minimum relative box width.
Returns:
the minimum relative box width
o setMaxInstInLeaf
public void setMaxInstInLeaf(int i) throws java.lang.Exception
          Sets the maximum number of instances in a leaf.
Parameters:
i - the maximum number of instances in a leaf
o getMaxInstInLeaf
public int getMaxInstInLeaf()
          Get the maximum number of instances in a leaf.
Returns:
the maximum number of instances in a leaf
o setPrune
public void setPrune(boolean p)
          Sets the flag for pruning of the blacklisting algorithm.
Parameters:
p - true to use pruning.
o getPrune
public boolean getPrune()
          Gets the pruning flag.
Returns:
True if pruning
o setNormalize
public void setNormalize(boolean n)
          Sets the flag for normalizing the widths of a KDTree Node by the width of the dimension in the universe.
Parameters:
n - true to use normalizing.
o getNormalize
public boolean getNormalize()
          Gets the normalize flag.
Returns:
True if normalizing
o setDebugLevel
public void setDebugLevel(int d)
          Sets the debug level. debug level = 0, means no output
Parameters:
d - debuglevel
o getDebugLevel
public int getDebugLevel()
          Gets the debug level.
Returns:
debug level
o listOptions
public java.util.Enumeration listOptions()
          Returns an enumeration describing the available options.
Returns:
an enumeration of all the available options.
o setOptions
public void setOptions(java.lang.String options[]) throws java.lang.Exception
          Parses a given list of options.
Parameters:
options - the list of options as an array of strings
Throws:
java.lang.Exception - if an option is not supported
o getOptions
public java.lang.String[] getOptions()
          Gets the current settings of KDtree.
Returns:
an array of strings suitable for passing to setOptions
o main
public static void main(java.lang.String args[])
          Main method for testing this class
All Packages  Class Hierarchy  This Package  Previous  Next  Index  WEKA's home