#include "kdtree.h"
#include "oldlist.h"
Go to the source code of this file.
|
CLUSTERER * | MakeClusterer (inT16 SampleSize, const PARAM_DESC ParamDesc[]) |
|
SAMPLE * | MakeSample (CLUSTERER *Clusterer, const FLOAT32 *Feature, inT32 CharID) |
|
LIST | ClusterSamples (CLUSTERER *Clusterer, CLUSTERCONFIG *Config) |
|
void | FreeClusterer (CLUSTERER *Clusterer) |
|
void | FreeProtoList (LIST *ProtoList) |
|
void | FreePrototype (void *arg) |
|
CLUSTER * | NextSample (LIST *SearchState) |
|
FLOAT32 | Mean (PROTOTYPE *Proto, uinT16 Dimension) |
|
FLOAT32 | StandardDeviation (PROTOTYPE *Proto, uinT16 Dimension) |
|
inT32 | MergeClusters (inT16 N, PARAM_DESC ParamDesc[], inT32 n1, inT32 n2, FLOAT32 m[], FLOAT32 m1[], FLOAT32 m2[]) |
|
◆ ALREADYCLUSTERED
#define ALREADYCLUSTERED 4000 |
◆ InitSampleSearch
◆ MAXBUCKETS
◆ MINBUCKETS
◆ CLUSTER
◆ SAMPLE
◆ DISTRIBUTION
Enumerator |
---|
normal | |
uniform | |
D_random | |
DISTRIBUTION_COUNT | |
Definition at line 58 of file cluster.h.
◆ PROTOSTYLE
Enumerator |
---|
spherical | |
elliptical | |
mixed | |
automatic | |
Definition at line 44 of file cluster.h.
◆ ClusterSamples()
This routine first checks to see if the samples in this clusterer have already been clustered before; if so, it does not bother to recreate the cluster tree. It simply recomputes the prototypes based on the new Config info.
If the samples have not been clustered before, the samples in the KD tree are formed into a cluster tree and then the prototypes are computed from the cluster tree.
In either case this routine returns a pointer to a list of prototypes that best represent the samples given the constraints specified in Config.
- Parameters
-
Clusterer | data struct containing samples to be clustered |
Config | parameters which control clustering process |
- Returns
- Pointer to a list of prototypes
- Note
- Exceptions: None
-
History: 5/29/89, DSJ, Created.
Definition at line 512 of file cluster.cpp.
514 if (Clusterer->
Root == NULL)
void CreateClusterTree(CLUSTERER *Clusterer)
void FreeProtoList(LIST *ProtoList)
void ComputePrototypes(CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
◆ FreeClusterer()
This routine frees all of the memory allocated to the specified data structure. It will not, however, free the memory used by the prototype list. The pointers to the clusters for each prototype in the list will be set to NULL to indicate that the cluster data structures no longer exist. Any sample lists that have been obtained via calls to GetSamples are no longer valid.
- Parameters
-
Clusterer | pointer to data structure to be freed |
- Returns
- None
- Note
- Exceptions: None
-
History: 6/6/89, DSJ, Created.
Definition at line 546 of file cluster.cpp.
547 if (Clusterer != NULL) {
549 if (Clusterer->
KDTree != NULL)
551 if (Clusterer->
Root != NULL)
BUCKETS * bucket_cache[DISTRIBUTION_COUNT][MAXBUCKETS+1 - MINBUCKETS]
void FreeCluster(CLUSTER *Cluster)
void FreeKDTree(KDTREE *Tree)
void FreeBuckets(BUCKETS *Buckets)
◆ FreeProtoList()
void FreeProtoList |
( |
LIST * |
ProtoList | ) |
|
This routine frees all of the memory allocated to the specified list of prototypes. The clusters which are pointed to by the prototypes are not freed.
- Parameters
-
ProtoList | pointer to list of prototypes to be freed |
- Returns
- None
- Note
- Exceptions: None
-
History: 6/6/89, DSJ, Created.
Definition at line 573 of file cluster.cpp.
void destroy_nodes(LIST list, void_dest destructor)
void FreePrototype(void *arg)
◆ FreePrototype()
void FreePrototype |
( |
void * |
arg | ) |
|
This routine deallocates the memory consumed by the specified prototype and modifies the corresponding cluster so that it is no longer marked as a prototype. The cluster is NOT deallocated by this routine.
- Parameters
-
arg | prototype data structure to be deallocated |
- Returns
- None
- Note
- Exceptions: None
-
History: 5/30/89, DSJ, Created.
Definition at line 587 of file cluster.cpp.
591 if (Prototype->
Cluster != NULL)
596 free (Prototype->
Mean);
◆ MakeClusterer()
This routine creates a new clusterer data structure, initializes it, and returns a pointer to it.
- Parameters
-
SampleSize | number of dimensions in feature space |
ParamDesc | description of each dimension |
- Returns
- pointer to the new clusterer data structure
- Note
- Exceptions: None
-
History: 5/29/89, DSJ, Created.
Definition at line 399 of file cluster.cpp.
410 Clusterer->
Root = NULL;
416 for (i = 0; i < SampleSize; i++) {
424 (ParamDesc[i].
Max + ParamDesc[i].
Min) / 2;
BUCKETS * bucket_cache[DISTRIBUTION_COUNT][MAXBUCKETS+1 - MINBUCKETS]
KDTREE * MakeKDTree(inT16 KeySize, const PARAM_DESC KeyDesc[])
◆ MakeSample()
This routine creates a new sample data structure to hold the specified feature. This sample is added to the clusterer data structure (so that it knows which samples are to be clustered later), and a pointer to the sample is returned to the caller.
- Parameters
-
Clusterer | clusterer data structure to add sample to |
Feature | feature to be added to clusterer |
CharID | unique ident. of char that sample came from |
- Returns
- Pointer to the new sample data structure
- Note
- Exceptions: ALREADYCLUSTERED MakeSample can't be called after ClusterSamples has been called
-
History: 5/29/89, DSJ, Created.
Definition at line 455 of file cluster.cpp.
461 if (Clusterer->
Root != NULL)
463 "Can't add samples after they have been clustered");
473 Sample->
Right = NULL;
477 Sample->
Mean[i] = Feature[i];
482 if (CharID >= Clusterer->
NumChar)
483 Clusterer->
NumChar = CharID + 1;
void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data)
void DoError(int Error, const char *Message)
◆ Mean()
This routine returns the mean of the specified prototype in the indicated dimension.
- Parameters
-
Proto | prototype to return mean of |
Dimension | dimension whose mean is to be returned |
- Returns
- Mean of Prototype in Dimension
- Note
- Exceptions: none
-
History: 7/6/89, DSJ, Created.
Definition at line 644 of file cluster.cpp.
645 return (Proto->
Mean[Dimension]);
◆ MergeClusters()
This routine merges two clusters into one larger cluster. To do this it computes the number of samples in the new cluster and the mean of the new cluster. The ParamDesc information is used to ensure that circular dimensions are handled correctly.
- Parameters
-
N | # of dimensions (size of arrays) |
ParamDesc | array of dimension descriptions |
n1,n2 | number of samples in each old cluster |
m | array to hold mean of new cluster |
m1,m2 | arrays containing means of old clusters |
- Returns
- The number of samples in the new cluster.
- Note
- Exceptions: None
-
History: 5/31/89, DSJ, Created.
Definition at line 880 of file cluster.cpp.
889 for (i = N; i > 0; i--, ParamDesc++, m++, m1++, m2++) {
890 if (ParamDesc->Circular) {
894 if ((*m2 - *m1) > ParamDesc->HalfRange) {
895 *m = (n1 * *m1 + n2 * (*m2 - ParamDesc->Range)) / n;
896 if (*m < ParamDesc->Min)
897 *m += ParamDesc->Range;
899 else if ((*m1 - *m2) > ParamDesc->HalfRange) {
900 *m = (n1 * (*m1 - ParamDesc->Range) + n2 * *m2) / n;
901 if (*m < ParamDesc->Min)
902 *m += ParamDesc->Range;
905 *m = (n1 * *m1 + n2 * *m2) / n;
908 *m = (n1 * *m1 + n2 * *m2) / n;
◆ NextSample()
This routine is used to find all of the samples which belong to a cluster. It starts by removing the top cluster on the cluster list (SearchState). If this cluster is a leaf it is returned. Otherwise, the right subcluster is pushed on the list and we continue the search in the left subcluster. This continues until a leaf is found. If all samples have been found, NULL is returned. InitSampleSearch() must be called before NextSample() to initialize the search.
- Parameters
-
SearchState | ptr to list containing clusters to be searched |
- Returns
- Pointer to the next leaf cluster (sample) or NULL.
- Note
- Exceptions: None
-
History: 6/16/89, DSJ, Created.
Definition at line 620 of file cluster.cpp.
626 *SearchState =
pop (*SearchState);
628 if (Cluster->
Left == NULL)
630 *SearchState =
push (*SearchState, Cluster->
Right);
631 Cluster = Cluster->
Left;
LIST push(LIST list, void *element)
◆ StandardDeviation()
This routine returns the standard deviation of the prototype in the indicated dimension.
- Parameters
-
Proto | prototype to return standard deviation of |
Dimension | dimension whose stddev is to be returned |
- Returns
- Standard deviation of Prototype in Dimension
- Note
- Exceptions: none
-
History: 7/6/89, DSJ, Created.
Definition at line 657 of file cluster.cpp.
658 switch (Proto->
Style) {
665 switch (Proto->
Distrib[Dimension]) {