Package smile.clustering
Class BBDTree
java.lang.Object
smile.clustering.BBDTree
Balanced BoxDecomposition Tree. BBD tree is a specialized kd tree that
vastly speeds up an iteration of kmeans. This is used internally by KMeans
and batch SOM., and will most likely not need to be used directly.
The structure works as follows:
 All data are placed into a tree where we choose child nodes by partitioning all data data along a plane parallel to the axis.
 We maintain for each node, the bounding box of all data data stored at that node.
 To do a kmeans iteration, we need to assign data to clusters and calculate the sum and the number of data assigned to each cluster. For each node in the tree, we can rule out some cluster centroids as being too far away from every single point in that bounding box. Once only one cluster is left, all data in the node can be assigned to that cluster in batch.
References
 Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. An Efficient kMeans Clustering Algorithm: Analysis and Implementation. IEEE TRANS. PAMI, 2002.
 See Also:

Constructor Summary
ConstructorDescriptionBBDTree
(double[][] data) Constructs a tree out of the given n data points living in R^d. 
Method Summary
Modifier and TypeMethodDescriptiondouble
clustering
(double[][] centroids, double[][] sum, int[] size, int[] y) Given k cluster centroids, this method assigns data to nearest centroids.

Constructor Details

BBDTree
public BBDTree(double[][] data) Constructs a tree out of the given n data points living in R^d. Parameters:
data
 the data points.


Method Details

clustering
public double clustering(double[][] centroids, double[][] sum, int[] size, int[] y) Given k cluster centroids, this method assigns data to nearest centroids. The return value is the distortion to the centroids. The parameter sums will hold the sum of data for each cluster. The parameter counts hold the number of data of each cluster. If membership is not null, it should be an array of size n that will be filled with the index of the cluster [0, k) that each data point is assigned to. Parameters:
centroids
 the current centroids of clusters.sum
 the workspace storing the sum of data in each cluster.size
 the number of samples in each cluster.y
 the class labels. Returns:
 the within cluster sum of the squared distance.
