1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#ifndef KM_H
#define KM_H
#include <stddef.h> // size_t
// forward typedef for callbacks
typedef struct km_rand_src_t_ km_rand_src_t;
// random number source callbacks
typedef struct {
_Bool (*fill)(km_rand_src_t * const, const size_t, float * const);
void (*fini)(km_rand_src_t * const);
} km_rand_src_cbs_t;
// random number source
struct km_rand_src_t_ {
const km_rand_src_cbs_t *cbs;
void *data;
};
// fill buffer with N random floats
_Bool km_rand_src_fill(km_rand_src_t * const, const size_t, float * const);
// finalize random source
void km_rand_src_fini(km_rand_src_t * const);
// init system random source (uses system rand())
void km_rand_src_system_init(km_rand_src_t *);
// shape of data set
typedef struct {
size_t num_floats,
num_ints;
} km_shape_t;
// data set
typedef struct {
float *floats;
int *ints;
km_shape_t shape;
size_t num_rows,
capacity;
} km_set_t;
// init data set with shape and initial size
_Bool km_set_init(km_set_t * const, const km_shape_t *, const size_t);
// finalize data set
void km_set_fini(km_set_t * const);
// append rows to data set, growing set if necessary
_Bool km_set_push_rows(km_set_t *, const size_t, const float *, const int *);
// get row from data set
float *km_set_get_row(const km_set_t *, const size_t);
// init a cluster set of size N from a data set by picking random
// cluster centers
_Bool km_clusters_rand_init(
km_set_t *,
const size_t,
const size_t,
km_rand_src_t *
);
typedef struct {
void (*on_step)(const km_set_t *, void *);
void (*on_means)(const km_set_t *, const float *, const size_t, void *);
} km_clusters_solve_cbs_t;
// use k-means to iteratively update the cluster centroids until there
// are no more changes to the centroids
_Bool
km_clusters_solve(
km_set_t * const,
const km_set_t * const,
const km_clusters_solve_cbs_t * const,
void * const
);
typedef struct {
const km_set_t * const cluster_set;
const size_t num_clusters;
const float mean_distance;
const size_t num_empty_clusters;
} km_search_row_t;
typedef void (*km_search_row_cb_t)(
const km_search_row_t * const,
void *
);
// repeatedly test different cluster sizes and report results
_Bool
km_search(
const km_set_t * const set,
const size_t max_clusters,
const size_t num_tests,
const km_search_row_cb_t on_row,
void *cb_data
);
#endif /* KM_H */
|
