binaries/src/clustalo/src/kmpp/KmTree.h

   1 // BEWARE: BETA VERSION\r
   2 // --------------------\r
   3 //\r
   4 // A k-d tree that vastly speeds up an iteration of k-means (in any number of dimensions). The main\r
   5 // idea for this data structure is from Kanungo/Mount. This is used internally by Kmeans.cpp, and\r
   6 // will most likely not need to be used directly.\r
   7 //\r
   8 // The stucture works as follows:\r
   9 //   - All data points are placed into a tree where we choose child nodes by partitioning all data\r
  10 //     points along a plane parallel to the axis.\r
  11 //   - We maintain for each node, the bounding box of all data points stored at that node.\r
  12 //   - To do a k-means iteration, we need to assign points to clusters and calculate the sum and\r
  13 //     the number of points assigned to each cluster. For each node in the tree, we can rule out\r
  14 //     some cluster centers as being too far away from every single point in that bounding box.\r
  15 //     Once only one cluster is left, all points in the node can be assigned to that cluster in\r
  16 //     batch.\r
  17 //\r
  18 // Author: David Arthur (darthur@gmail.com), 2009\r
  19 \r
  20 #ifndef KM_TREE_H__\r
  21 #define KM_TREE_H__\r
  22 \r
  23 // Includes\r
  24 #include "KmUtils.h"\r
  25 \r
  26 // KmTree class definition\r
  27 class KmTree {\r
  28  public:\r
  29   // Constructs a tree out of the given n data points living in R^d.\r
  30   KmTree(int n, int d, Scalar *points);\r
  31   ~KmTree();\r
  32 \r
  33   // Given k cluster centers, this runs a full k-means iterations, choosing the next set of\r
  34   // centers and returning the cost function for this set of centers. If assignment is not null,\r
  35   // it should be an array of size n that will be filled with the index of the cluster (0 - k-1)\r
  36   // that each data point is assigned to. The new center values will overwrite the old ones.\r
  37   Scalar DoKMeansStep(int k, Scalar *centers, int *assignment) const;\r
  38 \r
  39   // Choose k initial centers for k-means using the kmeans++ seeding procedure. The resulting\r
  40   // centers are returned via the centers variable, which should be pre-allocated to size k*d.\r
  41   // The cost of the initial clustering is returned.\r
  42   Scalar SeedKMeansPlusPlus(int k, Scalar *centers) const;\r
  43 \r
  44  private:\r
  45   struct Node {\r
  46     int num_points;                 // Number of points stored in this node\r
  47     int first_point_index;          // The smallest point index stored in this node\r
  48     Scalar *median, *radius;        // Bounding box center and half side-lengths\r
  49     Scalar *sum;                    // Sum of the points stored in this node\r
  50     Scalar opt_cost;                // Min cost for putting all points in this node in 1 cluster\r
  51     Node *lower_node, *upper_node;  // Child nodes\r
  52     mutable int kmpp_cluster_index; // The cluster these points are assigned to or -1 if variable\r
  53   };\r
  54 \r
  55   // Helper functions for constructor\r
  56   Node *BuildNodes(Scalar *points, int first_index, int last_index, char **next_node_data);\r
  57   Scalar GetNodeCost(const Node *node, Scalar *center) const;\r
  58 \r
  59   // Helper functions for DoKMeans step\r
  60   Scalar DoKMeansStepAtNode(const Node *node, int k, int *candidates, Scalar *centers,\r
  61                             Scalar *sums, int *counts, int *assignment) const;\r
  62   bool ShouldBePruned(Scalar *box_median, Scalar *box_radius, Scalar *centers, int best_index,\r
  63                       int test_index) const;\r
  64 \r
  65   // Helper functions for SeedKMeansPlusPlus\r
  66   void SeedKmppSetClusterIndex(const Node *node, int index) const;\r
  67   Scalar SeedKmppUpdateAssignment(const Node *node, int new_cluster, Scalar *centers,\r
  68                                   Scalar *dist_sq) const;\r
  69 \r
  70   int n_, d_;\r
  71   Scalar *points_;\r
  72   Node *top_node_;\r
  73   char *node_data_;\r
  74   int *point_indices_;\r
  75 };\r
  76 \r
  77 #endif\r