Project-Algorithms/cluster.cpp at master · Hepic/Project-Algorithms · GitHub

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
#include <iostream>
#include <cstdlib>
#include "cluster.h"
#include "curve.h"
#include "distances.h"
#include "help_functions.h"
#include "binary_mean_tree.h"
#include "initialization.h"
#include "assignment.h"
#include "update.h"

void clustering(const vector<HashTable> &hashtables, double delta, vector<double> &silhouette_cluster, vector<const Curve*> &centroids, vector<vector<int> > &clusters, const char *metric) {
    bool check;
    double value, prev_value = -1;

    if (method_init == 1) {
        k_means_pp(centroids, input_curves.size(), metric);
    } else if (method_init == 2) {
        k_random_selection(centroids, input_curves.size());
    }

    do {
        if (method_assign == 1) {
            value = loyd_assignment(centroids, clusters, metric);
        } else if (method_assign == 2) {
            value = range_search(hashtables, centroids, clusters, delta, metric);
        }

        if (method_update == 1) {
            check = mean_frechet_update(centroids, clusters);
        } else if (method_update == 2) {
            check = PAM_update(centroids, value, clusters, metric);
        }

        if (prev_value != -1 && prev_value <= value) {
            break;
        }

        prev_value = value;

    } while(check);

    silhouette(centroids, clusters, silhouette_cluster, metric);
}

void silhouette(const vector<const Curve*> &centroids, vector<vector<int> > &clusters, vector<double> &silhouette_cluster, const char *metric) {
    vector<double> close_dist((int)input_curves.size(), -1), close_dist_sec((int)input_curves.size(), -1);

    for (int i = 0; i < (int)input_curves.size(); ++i) {
        for (int j = 0; j < (int)centroids.size(); ++j) {
            double dist = compute_distance(input_curves[i], *centroids[j], metric);

            if (close_dist[i] == -1 || dist < close_dist[i]) {
                close_dist_sec[i] = close_dist[i];
                close_dist[i] = dist;
            } else if (close_dist_sec[i] == -1 || close_dist_sec[i] < dist) {
                close_dist_sec[i] = dist;
            }
        }
    }

    for (int i = 0; i < num_of_clusters; ++i) {
        double diss_a = 0, diss_b = 0, res = 0;

        for (int j = 0; j < (int)clusters[i].size(); ++j) {
            diss_a += close_dist[clusters[i][j]];
            diss_b += close_dist_sec[clusters[i][j]];

            double s_elem = (diss_b - diss_a) / max(diss_a, diss_b);
            res += s_elem;
        }

        res = (double)(res / (int)clusters[i].size());
        silhouette_cluster[i] = res;
    }
}