Package smile.clustering
Class BBDTree
- java.lang.Object
-
- smile.clustering.BBDTree
-
public class BBDTree extends java.lang.Object
Balanced Box-Decomposition Tree. BBD tree is a specialized k-d tree that vastly speeds up an iteration of k-means. 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 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 k-means 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 k-Means Clustering Algorithm: Analysis and Implementation. IEEE TRANS. PAMI, 2002.
- Author:
- Haifeng Li
- See Also:
KMeans
,smile.vq.SOM
-
-
Constructor Summary
Constructors Constructor Description BBDTree(double[][] data)
Constructs a tree out of the given n data data living in R^d.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
clustering(double[][] centroids, double[][] sums, int[] counts, int[] membership)
Given k cluster centroids, this method assigns data to nearest centroids.
-
-
-
Method Detail
-
clustering
public double clustering(double[][] centroids, double[][] sums, int[] counts, int[] membership)
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.
-
-