/****************************************************************************** **	Filename:	cluster.c **	Purpose:	Routines for clustering points in N-D space **	Author:		Dan Johnson **	History:	5/29/89, DSJ, Created. ** **	(c) Copyright Hewlett-Packard Company, 1988. ** Licensed under the Apache License, Version 2.0 (the "License"); ** you may not use this file except in compliance with the License. ** You may obtain a copy of the License at ** http://www.apache.org/licenses/LICENSE-2.0 ** Unless required by applicable law or agreed to in writing, software ** distributed under the License is distributed on an "AS IS" BASIS, ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. ** See the License for the specific language governing permissions and ** limitations under the License. ******************************************************************************/#include "oldheap.h"#include "const.h"#include "cluster.h"#include "emalloc.h"#include "danerror.h"#include "freelist.h"#include <math.h>#define HOTELLING 1  // If true use Hotelling's test to decide where to split.#define FTABLE_X 10  // Size of FTable.#define FTABLE_Y 100  // Size of FTable.// Table of values approximating the cumulative F-distribution for a confidence of 1%.double FTable[FTABLE_Y][FTABLE_X] = { {4052.19, 4999.52, 5403.34, 5624.62, 5763.65, 5858.97, 5928.33, 5981.10, 6022.50, 6055.85,},  {98.502,  99.000,  99.166,  99.249,  99.300,  99.333,  99.356,  99.374,  99.388,  99.399,},  {34.116,  30.816,  29.457,  28.710,  28.237,  27.911,  27.672,  27.489,  27.345,  27.229,},  {21.198,  18.000,  16.694,  15.977,  15.522,  15.207,  14.976,  14.799,  14.659,  14.546,},  {16.258,  13.274,  12.060,  11.392,  10.967,  10.672,  10.456,  10.289,  10.158,  10.051,},  {13.745,  10.925,   9.780,   9.148,   8.746,   8.466,   8.260,   8.102,   7.976,   7.874,},  {12.246,   9.547,   8.451,   7.847,   7.460,   7.191,   6.993,   6.840,   6.719,   6.620,},  {11.259,   8.649,   7.591,   7.006,   6.632,   6.371,   6.178,   6.029,   5.911,   5.814,},  {10.561,   8.022,   6.992,   6.422,   6.057,   5.802,   5.613,   5.467,   5.351,   5.257,},  {10.044,   7.559,   6.552,   5.994,   5.636,   5.386,   5.200,   5.057,   4.942,   4.849,},  { 9.646,   7.206,   6.217,   5.668,   5.316,   5.069,   4.886,   4.744,   4.632,   4.539,},  { 9.330,   6.927,   5.953,   5.412,   5.064,   4.821,   4.640,   4.499,   4.388,   4.296,},  { 9.074,   6.701,   5.739,   5.205,   4.862,   4.620,   4.441,   4.302,   4.191,   4.100,},  { 8.862,   6.515,   5.564,   5.035,   4.695,   4.456,   4.278,   4.140,   4.030,   3.939,},  { 8.683,   6.359,   5.417,   4.893,   4.556,   4.318,   4.142,   4.004,   3.895,   3.805,},  { 8.531,   6.226,   5.292,   4.773,   4.437,   4.202,   4.026,   3.890,   3.780,   3.691,},  { 8.400,   6.112,   5.185,   4.669,   4.336,   4.102,   3.927,   3.791,   3.682,   3.593,},  { 8.285,   6.013,   5.092,   4.579,   4.248,   4.015,   3.841,   3.705,   3.597,   3.508,},  { 8.185,   5.926,   5.010,   4.500,   4.171,   3.939,   3.765,   3.631,   3.523,   3.434,},  { 8.096,   5.849,   4.938,   4.431,   4.103,   3.871,   3.699,   3.564,   3.457,   3.368,},  { 8.017,   5.780,   4.874,   4.369,   4.042,   3.812,   3.640,   3.506,   3.398,   3.310,},  { 7.945,   5.719,   4.817,   4.313,   3.988,   3.758,   3.587,   3.453,   3.346,   3.258,},  { 7.881,   5.664,   4.765,   4.264,   3.939,   3.710,   3.539,   3.406,   3.299,   3.211,},  { 7.823,   5.614,   4.718,   4.218,   3.895,   3.667,   3.496,   3.363,   3.256,   3.168,},  { 7.770,   5.568,   4.675,   4.177,   3.855,   3.627,   3.457,   3.324,   3.217,   3.129,},  { 7.721,   5.526,   4.637,   4.140,   3.818,   3.591,   3.421,   3.288,   3.182,   3.094,},  { 7.677,   5.488,   4.601,   4.106,   3.785,   3.558,   3.388,   3.256,   3.149,   3.062,},  { 7.636,   5.453,   4.568,   4.074,   3.754,   3.528,   3.358,   3.226,   3.120,   3.032,},  { 7.598,   5.420,   4.538,   4.045,   3.725,   3.499,   3.330,   3.198,   3.092,   3.005,},  { 7.562,   5.390,   4.510,   4.018,   3.699,   3.473,   3.305,   3.173,   3.067,   2.979,},  { 7.530,   5.362,   4.484,   3.993,   3.675,   3.449,   3.281,   3.149,   3.043,   2.955,},  { 7.499,   5.336,   4.459,   3.969,   3.652,   3.427,   3.258,   3.127,   3.021,   2.934,},  { 7.471,   5.312,   4.437,   3.948,   3.630,   3.406,   3.238,   3.106,   3.000,   2.913,},  { 7.444,   5.289,   4.416,   3.927,   3.611,   3.386,   3.218,   3.087,   2.981,   2.894,},  { 7.419,   5.268,   4.396,   3.908,   3.592,   3.368,   3.200,   3.069,   2.963,   2.876,},  { 7.396,   5.248,   4.377,   3.890,   3.574,   3.351,   3.183,   3.052,   2.946,   2.859,},  { 7.373,   5.229,   4.360,   3.873,   3.558,   3.334,   3.167,   3.036,   2.930,   2.843,},  { 7.353,   5.211,   4.343,   3.858,   3.542,   3.319,   3.152,   3.021,   2.915,   2.828,},  { 7.333,   5.194,   4.327,   3.843,   3.528,   3.305,   3.137,   3.006,   2.901,   2.814,},  { 7.314,   5.179,   4.313,   3.828,   3.514,   3.291,   3.124,   2.993,   2.888,   2.801,},  { 7.296,   5.163,   4.299,   3.815,   3.501,   3.278,   3.111,   2.980,   2.875,   2.788,},  { 7.280,   5.149,   4.285,   3.802,   3.488,   3.266,   3.099,   2.968,   2.863,   2.776,},  { 7.264,   5.136,   4.273,   3.790,   3.476,   3.254,   3.087,   2.957,   2.851,   2.764,},  { 7.248,   5.123,   4.261,   3.778,   3.465,   3.243,   3.076,   2.946,   2.840,   2.754,},  { 7.234,   5.110,   4.249,   3.767,   3.454,   3.232,   3.066,   2.935,   2.830,   2.743,},  { 7.220,   5.099,   4.238,   3.757,   3.444,   3.222,   3.056,   2.925,   2.820,   2.733,},  { 7.207,   5.087,   4.228,   3.747,   3.434,   3.213,   3.046,   2.916,   2.811,   2.724,},  { 7.194,   5.077,   4.218,   3.737,   3.425,   3.204,   3.037,   2.907,   2.802,   2.715,},  { 7.182,   5.066,   4.208,   3.728,   3.416,   3.195,   3.028,   2.898,   2.793,   2.706,},  { 7.171,   5.057,   4.199,   3.720,   3.408,   3.186,   3.020,   2.890,   2.785,   2.698,},  { 7.159,   5.047,   4.191,   3.711,   3.400,   3.178,   3.012,   2.882,   2.777,   2.690,},  { 7.149,   5.038,   4.182,   3.703,   3.392,   3.171,   3.005,   2.874,   2.769,   2.683,},  { 7.139,   5.030,   4.174,   3.695,   3.384,   3.163,   2.997,   2.867,   2.762,   2.675,},  { 7.129,   5.021,   4.167,   3.688,   3.377,   3.156,   2.990,   2.860,   2.755,   2.668,},  { 7.119,   5.013,   4.159,   3.681,   3.370,   3.149,   2.983,   2.853,   2.748,   2.662,},  { 7.110,   5.006,   4.152,   3.674,   3.363,   3.143,   2.977,   2.847,   2.742,   2.655,},  { 7.102,   4.998,   4.145,   3.667,   3.357,   3.136,   2.971,   2.841,   2.736,   2.649,},  { 7.093,   4.991,   4.138,   3.661,   3.351,   3.130,   2.965,   2.835,   2.730,   2.643,},  { 7.085,   4.984,   4.132,   3.655,   3.345,   3.124,   2.959,   2.829,   2.724,   2.637,},  { 7.077,   4.977,   4.126,   3.649,   3.339,   3.119,   2.953,   2.823,   2.718,   2.632,},  { 7.070,   4.971,   4.120,   3.643,   3.333,   3.113,   2.948,   2.818,   2.713,   2.626,},  { 7.062,   4.965,   4.114,   3.638,   3.328,   3.108,   2.942,   2.813,   2.708,   2.621,},  { 7.055,   4.959,   4.109,   3.632,   3.323,   3.103,   2.937,   2.808,   2.703,   2.616,},  { 7.048,   4.953,   4.103,   3.627,   3.318,   3.098,   2.932,   2.803,   2.698,   2.611,},  { 7.042,   4.947,   4.098,   3.622,   3.313,   3.093,   2.928,   2.798,   2.693,   2.607,},  { 7.035,   4.942,   4.093,   3.618,   3.308,   3.088,   2.923,   2.793,   2.689,   2.602,},  { 7.029,   4.937,   4.088,   3.613,   3.304,   3.084,   2.919,   2.789,   2.684,   2.598,},  { 7.023,   4.932,   4.083,   3.608,   3.299,   3.080,   2.914,   2.785,   2.680,   2.593,},  { 7.017,   4.927,   4.079,   3.604,   3.295,   3.075,   2.910,   2.781,   2.676,   2.589,},  { 7.011,   4.922,   4.074,   3.600,   3.291,   3.071,   2.906,   2.777,   2.672,   2.585,},  { 7.006,   4.917,   4.070,   3.596,   3.287,   3.067,   2.902,   2.773,   2.668,   2.581,},  { 7.001,   4.913,   4.066,   3.591,   3.283,   3.063,   2.898,   2.769,   2.664,   2.578,},  { 6.995,   4.908,   4.062,   3.588,   3.279,   3.060,   2.895,   2.765,   2.660,   2.574,},  { 6.990,   4.904,   4.058,   3.584,   3.275,   3.056,   2.891,   2.762,   2.657,   2.570,},  { 6.985,   4.900,   4.054,   3.580,   3.272,   3.052,   2.887,   2.758,   2.653,   2.567,},  { 6.981,   4.896,   4.050,   3.577,   3.268,   3.049,   2.884,   2.755,   2.650,   2.563,},  { 6.976,   4.892,   4.047,   3.573,   3.265,   3.046,   2.881,   2.751,   2.647,   2.560,},  { 6.971,   4.888,   4.043,   3.570,   3.261,   3.042,   2.877,   2.748,   2.644,   2.557,},  { 6.967,   4.884,   4.040,   3.566,   3.258,   3.039,   2.874,   2.745,   2.640,   2.554,},  { 6.963,   4.881,   4.036,   3.563,   3.255,   3.036,   2.871,   2.742,   2.637,   2.551,},  { 6.958,   4.877,   4.033,   3.560,   3.252,   3.033,   2.868,   2.739,   2.634,   2.548,},  { 6.954,   4.874,   4.030,   3.557,   3.249,   3.030,   2.865,   2.736,   2.632,   2.545,},  { 6.950,   4.870,   4.027,   3.554,   3.246,   3.027,   2.863,   2.733,   2.629,   2.542,},  { 6.947,   4.867,   4.024,   3.551,   3.243,   3.025,   2.860,   2.731,   2.626,   2.539,},  { 6.943,   4.864,   4.021,   3.548,   3.240,   3.022,   2.857,   2.728,   2.623,   2.537,},  { 6.939,   4.861,   4.018,   3.545,   3.238,   3.019,   2.854,   2.725,   2.621,   2.534,},  { 6.935,   4.858,   4.015,   3.543,   3.235,   3.017,   2.852,   2.723,   2.618,   2.532,},  { 6.932,   4.855,   4.012,   3.540,   3.233,   3.014,   2.849,   2.720,   2.616,   2.529,},  { 6.928,   4.852,   4.010,   3.538,   3.230,   3.012,   2.847,   2.718,   2.613,   2.527,},  { 6.925,   4.849,   4.007,   3.535,   3.228,   3.009,   2.845,   2.715,   2.611,   2.524,},  { 6.922,   4.846,   4.004,   3.533,   3.225,   3.007,   2.842,   2.713,   2.609,   2.522,},  { 6.919,   4.844,   4.002,   3.530,   3.223,   3.004,   2.840,   2.711,   2.606,   2.520,},  { 6.915,   4.841,   3.999,   3.528,   3.221,   3.002,   2.838,   2.709,   2.604,   2.518,},  { 6.912,   4.838,   3.997,   3.525,   3.218,   3.000,   2.835,   2.706,   2.602,   2.515,},  { 6.909,   4.836,   3.995,   3.523,   3.216,   2.998,   2.833,   2.704,   2.600,   2.513,},  { 6.906,   4.833,   3.992,   3.521,   3.214,   2.996,   2.831,   2.702,   2.598,   2.511,},  { 6.904,   4.831,   3.990,   3.519,   3.212,   2.994,   2.829,   2.700,   2.596,   2.509,},  { 6.901,   4.829,   3.988,   3.517,   3.210,   2.992,   2.827,   2.698,   2.594,   2.507,},  { 6.898,   4.826,   3.986,   3.515,   3.208,   2.990,   2.825,   2.696,   2.592,   2.505,},  { 6.895,   4.824,   3.984,   3.513,   3.206,   2.988,   2.823,   2.694,   2.590,   2.503}};/* define the variance which will be used as a minimum variance for any  dimension of any feature. Since most features are calculated from numbers  with a precision no better than 1 in 128, the variance should never be  less than the square of this number for parameters whose range is 1. */#define MINVARIANCE     0.0001/* define the absolute minimum number of samples which must be present in  order to accurately test hypotheses about underlying probability  distributions.  Define separately the minimum samples that are needed  before a statistical analysis is attempted; this number should be  equal to MINSAMPLES but can be set to a lower number for early testing  when very few samples are available. */#define MINBUCKETS      5#define MINSAMPLESPERBUCKET 5#define MINSAMPLES    (MINBUCKETS * MINSAMPLESPERBUCKET)#define MINSAMPLESNEEDED  1/* define the size of the table which maps normalized samples to  histogram buckets.  Also define the number of standard deviations  in a normal distribution which are considered to be significant.  The mapping table will be defined in such a way that it covers  the specified number of standard deviations on either side of  the mean.  BUCKETTABLESIZE should always be even. */#define BUCKETTABLESIZE   1024#define NORMALEXTENT    3.0typedef struct{  CLUSTER *Cluster;  CLUSTER *Neighbor;}TEMPCLUSTER;typedef struct{  FLOAT32 AvgVariance;  FLOAT32 *CoVariance;  FLOAT32 *Min;                  // largest negative distance from the mean  FLOAT32 *Max;                  // largest positive distance from the mean}STATISTICS;typedef struct{  DISTRIBUTION Distribution;     // distribution being tested for  UINT32 SampleCount;            // # of samples in histogram  FLOAT64 Confidence;            // confidence level of test  FLOAT64 ChiSquared;            // test threshold  UINT16 NumberOfBuckets;        // number of cells in histogram  UINT16 Bucket[BUCKETTABLESIZE];// mapping to histogram buckets  UINT32 *Count;                 // frequency of occurence histogram  FLOAT32 *ExpectedCount;        // expected histogram}BUCKETS;typedef struct{  UINT16 DegreesOfFreedom;  FLOAT64 Alpha;  FLOAT64 ChiSquared;}CHISTRUCT;typedef FLOAT64 (*DENSITYFUNC) (INT32);typedef FLOAT64 (*SOLVEFUNC) (CHISTRUCT *, double);#define Odd(N) ((N)%2)#define Mirror(N,R) ((R) - (N) - 1)#define Abs(N) ( ( (N) < 0 ) ? ( -(N) ) : (N) )//--------------Global Data Definitions and Declarations----------------------/* the following variables are declared as global so that routines whichare called from the kd-tree walker can get to them. */static HEAP *Heap;static TEMPCLUSTER *TempCluster;static KDTREE *Tree;static INT32 CurrentTemp;/* the following variables describe a discrete normal distribution  which is used by NormalDensity() and NormalBucket().  The  constant NORMALEXTENT determines how many standard  deviations of the distribution are mapped onto the fixed  discrete range of x.  x=0 is mapped to -NORMALEXTENT standard  deviations and x=BUCKETTABLESIZE is mapped to  +NORMALEXTENT standard deviations. */#define SqrtOf2Pi     2.506628275static FLOAT64 NormalStdDev = BUCKETTABLESIZE / (2.0 * NORMALEXTENT);static FLOAT64 NormalVariance =(BUCKETTABLESIZE * BUCKETTABLESIZE) / (4.0 * NORMALEXTENT * NORMALEXTENT);static FLOAT64 NormalMagnitude =(2.0 * NORMALEXTENT) / (SqrtOf2Pi * BUCKETTABLESIZE);static FLOAT64 NormalMean = BUCKETTABLESIZE / 2;// keep a list of histogram buckets to minimize recomputing themstatic LIST OldBuckets[] = { NIL, NIL, NIL };/* define lookup tables used to compute the number of histogram buckets  that should be used for a given number of samples. */#define LOOKUPTABLESIZE   8#define MAXBUCKETS      39#define MAXDEGREESOFFREEDOM MAXBUCKETSstatic UINT32 CountTable[LOOKUPTABLESIZE] = {  MINSAMPLES, 200, 400, 600, 800, 1000, 1500, 2000};static UINT16 BucketsTable[LOOKUPTABLESIZE] = {  MINBUCKETS, 16, 20, 24, 27, 30, 35, MAXBUCKETS};/*-------------------------------------------------------------------------          Private Function Prototypes--------------------------------------------------------------------------*/void CreateClusterTree(CLUSTERER *Clusterer);void MakePotentialClusters(CLUSTER *Cluster, VISIT Order, INT32 Level);CLUSTER *FindNearestNeighbor(KDTREE *Tree,                             CLUSTER *Cluster,                             FLOAT32 *Distance);CLUSTER *MakeNewCluster(CLUSTERER *Clusterer, TEMPCLUSTER *TempCluster);INT32 MergeClusters (INT16 N,register PARAM_DESC ParamDesc[],register INT32 n1,register INT32 n2,register FLOAT32 m[],register FLOAT32 m1[], register FLOAT32 m2[]);void ComputePrototypes(CLUSTERER *Clusterer, CLUSTERCONFIG *Config);PROTOTYPE *MakePrototype(CLUSTERER *Clusterer,                         CLUSTERCONFIG *Config,                         CLUSTER *Cluster);PROTOTYPE *MakeDegenerateProto(UINT16 N,                               CLUSTER *Cluster,                               STATISTICS *Statistics,                               PROTOSTYLE Style,                               INT32 MinSamples);PROTOTYPE *TestEllipticalProto(CLUSTERER *Clusterer,                               CLUSTER *Cluster,                               STATISTICS *Statistics);PROTOTYPE *MakeSphericalProto(CLUSTERER *Clusterer,                              CLUSTER *Cluster,                              STATISTICS *Statistics,                              BUCKETS *Buckets);PROTOTYPE *MakeEllipticalProto(CLUSTERER *Clusterer,                               CLUSTER *Cluster,                               STATISTICS *Statistics,                               BUCKETS *Buckets);PROTOTYPE *MakeMixedProto(CLUSTERER *Clusterer,                          CLUSTER *Cluster,                          STATISTICS *Statistics,                          BUCKETS *NormalBuckets,                          FLOAT64 Confidence);void MakeDimRandom(UINT16 i, PROTOTYPE *Proto, PARAM_DESC *ParamDesc);void MakeDimUniform(UINT16 i, PROTOTYPE *Proto, STATISTICS *Statistics);STATISTICS *ComputeStatistics (INT16 N,PARAM_DESC ParamDesc[], CLUSTER * Cluster);