kohonen_som_topology.c File Reference

Kohonen self organizing map (topological map) More...

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

Include dependency graph for kohonen_som_topology.c:

Data Structures
struct	kohonen_array_3d
	to store info regarding 3D arrays More...

Macros
#define	_USE_MATH_DEFINES
	required for MS Visual C
#define	max(a, b)   (((a) > (b)) ? (a) : (b))
	shorthand for maximum value
#define	min(a, b)   (((a) < (b)) ? (a) : (b))
	shorthand for minimum value

Functions
double *	kohonen_data_3d (const struct kohonen_array_3d *arr, int x, int y, int z)
	Function that returns the pointer to (x, y, z) ^th location in the linear 3D array given by:
double	_random (double a, double b)
	Helper function to generate a random number in a given interval.
int	save_2d_data (const char *fname, double **X, int num_points, int num_features)
	Save a given n-dimensional data martix to file.
int	save_u_matrix (const char *fname, struct kohonen_array_3d *W)
	Create the distance matrix or U-matrix from the trained weights and save to disk.
void	get_min_2d (double **X, int N, double *val, int *x_idx, int *y_idx)
	Get minimum value and index of the value in a matrix.
double	kohonen_update_weights (const double *X, struct kohonen_array_3d *W, double **D, int num_out, int num_features, double alpha, int R)
	Update weights of the SOM using Kohonen algorithm.
void	kohonen_som (double **X, struct kohonen_array_3d *W, int num_samples, int num_features, int num_out, double alpha_min)
	Apply incremental algorithm with updating neighborhood and learning rates on all samples in the given datset.
void	test_2d_classes (double *const *data, int N)
	Creates a random set of points distributed in four clusters in 3D space with centroids at the points.
void	test1 ()
	Test that creates a random set of points distributed in four clusters in 2D space and trains an SOM that finds the topological pattern.
void	test_3d_classes1 (double *const *data, int N)
	Creates a random set of points distributed in four clusters in 3D space with centroids at the points.
void	test2 ()
	Test that creates a random set of points distributed in 4 clusters in 3D space and trains an SOM that finds the topological pattern.
void	test_3d_classes2 (double *const *data, int N)
	Creates a random set of points distributed in four clusters in 3D space with centroids at the points.
void	test3 ()
	Test that creates a random set of points distributed in eight clusters in 3D space and trains an SOM that finds the topological pattern.
double	get_clock_diff (clock_t start_t, clock_t end_t)
	Convert clock cycle difference to time in seconds.
int	main (int argc, char **argv)
	Main function.

Detailed Description

Kohonen self organizing map (topological map)

This example implements a powerful unsupervised learning algorithm called as a self organizing map. The algorithm creates a connected network of weights that closely follows the given data points. This thus creates a topological map of the given data i.e., it maintains the relationship between various data points in a much higher dimensional space by creating an equivalent in a 2-dimensional space.

Author

Krishna Vedala

Warning

MSVC 2019 compiler generates code that does not execute as expected. However, MinGW, Clang for GCC and Clang for MSVC compilers on windows perform as expected. Any insights and suggestions should be directed to the author.

See also

kohonen_som_trace.c

Function Documentation

get_clock_diff()

double get_clock_diff	(	clock_t	start_t,
		clock_t	end_t
	)

Convert clock cycle difference to time in seconds.

Parameters

[in]	start_t	start clock
[in]	end_t	end clock

Returns

time difference in seconds

{
    return (double)(end_t - start_t) / (double)CLOCKS_PER_SEC;
}

main()

int main	(	int	argc,
		char **	argv
	)

Main function.

{
#ifdef _OPENMP
    printf("Using OpenMP based parallelization\n");
#else
    printf("NOT using OpenMP based parallelization\n");
#endif
    clock_t start_clk, end_clk;
 
    start_clk = clock();
    test1();
    end_clk = clock();
    printf("Test 1 completed in %.4g sec\n",
           get_clock_diff(start_clk, end_clk));
 
    start_clk = clock();
    test2();
    end_clk = clock();
    printf("Test 2 completed in %.4g sec\n",
           get_clock_diff(start_clk, end_clk));
 
    start_clk = clock();
    test3();
    end_clk = clock();
    printf("Test 3 completed in %.4g sec\n",
           get_clock_diff(start_clk, end_clk));
 
    printf("(Note: Calculated times include: writing files to disk.)\n\n");
    return 0;
}

Here is the call graph for this function:

test1()

void test1

(

)

Test that creates a random set of points distributed in four clusters in 2D space and trains an SOM that finds the topological pattern.

The following CSV files are created to validate the execution:

• test1.csv: random test samples points with a circular pattern
• w11.csv: initial random U-matrix
• w12.csv: trained SOM U-matrix

{
    int j, N = 300;
    int features = 2;
    int num_out = 30;  // image size - N x N
 
    // 2D space, hence size = number of rows * 2
    double **X = (double **)malloc(N * sizeof(double *));
 
    // cluster nodex in 'x' * cluster nodes in 'y' * 2
    struct kohonen_array_3d W;
    W.dim1 = num_out;
    W.dim2 = num_out;
    W.dim3 = features;
    W.data = (double *)malloc(num_out * num_out * features *
                              sizeof(double));  // assign rows
 
    for (int i = 0; i < max(num_out, N); i++)  // loop till max(N, num_out)
    {
        if (i < N)  // only add new arrays if i < N
            X[i] = (double *)malloc(features * sizeof(double));
        if (i < num_out)  // only add new arrays if i < num_out
        {
            for (int k = 0; k < num_out; k++)
            {
#ifdef _OPENMP
#pragma omp for
#endif
                // preallocate with random initial weights
                for (j = 0; j < features; j++)
                {
                    double *w = kohonen_data_3d(&W, i, k, j);
                    w[0] = _random(-5, 5);
                }
            }
        }
    }
 
    test_2d_classes(X, N);  // create test data around circumference of a circle
    save_2d_data("test1.csv", X, N, features);  // save test data points
    save_u_matrix("w11.csv", &W);               // save initial random weights
    kohonen_som(X, &W, N, features, num_out, 1e-4);  // train the SOM
    save_u_matrix("w12.csv", &W);  // save the resultant weights
 
    for (int i = 0; i < N; i++) free(X[i]);
    free(X);
    free(W.data);
}

Here is the call graph for this function:

test2()

void test2

(

)

Test that creates a random set of points distributed in 4 clusters in 3D space and trains an SOM that finds the topological pattern.

The following CSV files are created to validate the execution:

• test2.csv: random test samples points
• w21.csv: initial random U-matrix
• w22.csv: trained SOM U-matrix

{
    int j, N = 500;
    int features = 3;
    int num_out = 30;  // image size - N x N
 
    // 3D space, hence size = number of rows * 3
    double **X = (double **)malloc(N * sizeof(double *));
 
    // cluster nodex in 'x' * cluster nodes in 'y' * 2
    struct kohonen_array_3d W;
    W.dim1 = num_out;
    W.dim2 = num_out;
    W.dim3 = features;
    W.data = (double *)malloc(num_out * num_out * features *
                              sizeof(double));  // assign rows
 
    for (int i = 0; i < max(num_out, N); i++)  // loop till max(N, num_out)
    {
        if (i < N)  // only add new arrays if i < N
            X[i] = (double *)malloc(features * sizeof(double));
        if (i < num_out)  // only add new arrays if i < num_out
        {
            for (int k = 0; k < num_out; k++)
            {
#ifdef _OPENMP
#pragma omp for
#endif
                for (j = 0; j < features; j++)
                {  // preallocate with random initial weights
                    double *w = kohonen_data_3d(&W, i, k, j);
                    w[0] = _random(-5, 5);
                }
            }
        }
    }
 
    test_3d_classes1(X, N);                     // create test data
    save_2d_data("test2.csv", X, N, features);  // save test data points
    save_u_matrix("w21.csv", &W);               // save initial random weights
    kohonen_som(X, &W, N, features, num_out, 1e-4);  // train the SOM
    save_u_matrix("w22.csv", &W);  // save the resultant weights
 
    for (int i = 0; i < N; i++) free(X[i]);
    free(X);
    free(W.data);
}

Here is the call graph for this function:

test3()

void test3

(

)

Test that creates a random set of points distributed in eight clusters in 3D space and trains an SOM that finds the topological pattern.

The following CSV files are created to validate the execution:

• test3.csv: random test samples points
• w31.csv: initial random U-matrix
• w32.csv: trained SOM U-matrix

{
    int j, N = 500;
    int features = 3;
    int num_out = 30;
    double **X = (double **)malloc(N * sizeof(double *));
 
    // cluster nodex in 'x' * cluster nodes in 'y' * 2
    struct kohonen_array_3d W;
    W.dim1 = num_out;
    W.dim2 = num_out;
    W.dim3 = features;
    W.data = (double *)malloc(num_out * num_out * features *
                              sizeof(double));  // assign rows
 
    for (int i = 0; i < max(num_out, N); i++)  // loop till max(N, num_out)
    {
        if (i < N)  // only add new arrays if i < N
            X[i] = (double *)malloc(features * sizeof(double));
        if (i < num_out)  // only add new arrays if i < num_out
        {
            for (int k = 0; k < num_out; k++)
            {
#ifdef _OPENMP
#pragma omp for
#endif
                // preallocate with random initial weights
                for (j = 0; j < features; j++)
                {
                    double *w = kohonen_data_3d(&W, i, k, j);
                    w[0] = _random(-5, 5);
                }
            }
        }
    }
 
    test_3d_classes2(X, N);  // create test data around the lamniscate
    save_2d_data("test3.csv", X, N, features);  // save test data points
    save_u_matrix("w31.csv", &W);               // save initial random weights
    kohonen_som(X, &W, N, features, num_out, 0.01);  // train the SOM
    save_u_matrix("w32.csv", &W);  // save the resultant weights
 
    for (int i = 0; i < N; i++) free(X[i]);
    free(X);
    free(W.data);
}

Here is the call graph for this function:

test_2d_classes()

void test_2d_classes	(	double *const *	data,
		int	N
	)

Creates a random set of points distributed in four clusters in 3D space with centroids at the points.

• \((0,5, 0.5, 0.5)\)
• \((0,5,-0.5, -0.5)\)
• \((-0,5, 0.5, 0.5)\)
• \((-0,5,-0.5, -0.5)\)

Parameters

[out]	data	matrix to store data in
[in]	N	number of points required

{
    const double R = 0.3;  // radius of cluster
    int i;
    const int num_classes = 4;
    const double centres[][2] = {
        // centres of each class cluster
        {.5, .5},   // centre of class 1
        {.5, -.5},  // centre of class 2
        {-.5, .5},  // centre of class 3
        {-.5, -.5}  // centre of class 4
    };
 
#ifdef _OPENMP
#pragma omp for
#endif
    for (i = 0; i < N; i++)
    {
        int class =
            rand() % num_classes;  // select a random class for the point
 
        // create random coordinates (x,y,z) around the centre of the class
        data[i][0] = _random(centres[class][0] - R, centres[class][0] + R);
        data[i][1] = _random(centres[class][1] - R, centres[class][1] + R);
 
        /* The follosing can also be used
        for (int j = 0; j < 2; j++)
            data[i][j] = _random(centres[class][j] - R, centres[class][j] + R);
        */
    }
}

Here is the call graph for this function:

test_3d_classes1()

void test_3d_classes1	(	double *const *	data,
		int	N
	)

Creates a random set of points distributed in four clusters in 3D space with centroids at the points.

• \((0,5, 0.5, 0.5)\)
• \((0,5,-0.5, -0.5)\)
• \((-0,5, 0.5, 0.5)\)
• \((-0,5,-0.5, -0.5)\)

Parameters

[out]	data	matrix to store data in
[in]	N	number of points required

{
    const double R = 0.2;  // radius of cluster
    int i;
    const int num_classes = 4;
    const double centres[][3] = {
        // centres of each class cluster
        {.5, .5, .5},    // centre of class 1
        {.5, -.5, -.5},  // centre of class 2
        {-.5, .5, .5},   // centre of class 3
        {-.5, -.5 - .5}  // centre of class 4
    };
 
#ifdef _OPENMP
#pragma omp for
#endif
    for (i = 0; i < N; i++)
    {
        int class =
            rand() % num_classes;  // select a random class for the point
 
        // create random coordinates (x,y,z) around the centre of the class
        data[i][0] = _random(centres[class][0] - R, centres[class][0] + R);
        data[i][1] = _random(centres[class][1] - R, centres[class][1] + R);
        data[i][2] = _random(centres[class][2] - R, centres[class][2] + R);
 
        /* The follosing can also be used
        for (int j = 0; j < 3; j++)
            data[i][j] = _random(centres[class][j] - R, centres[class][j] + R);
        */
    }
}

Here is the call graph for this function:

test_3d_classes2()

void test_3d_classes2	(	double *const *	data,
		int	N
	)

Creates a random set of points distributed in four clusters in 3D space with centroids at the points.

• \((0,5, 0.5, 0.5)\)
• \((0,5,-0.5, -0.5)\)
• \((-0,5, 0.5, 0.5)\)
• \((-0,5,-0.5, -0.5)\)

Parameters

[out]	data	matrix to store data in
[in]	N	number of points required

{
    const double R = 0.2;  // radius of cluster
    int i;
    const int num_classes = 8;
    const double centres[][3] = {
        // centres of each class cluster
        {.5, .5, .5},    // centre of class 1
        {.5, .5, -.5},   // centre of class 2
        {.5, -.5, .5},   // centre of class 3
        {.5, -.5, -.5},  // centre of class 4
        {-.5, .5, .5},   // centre of class 5
        {-.5, .5, -.5},  // centre of class 6
        {-.5, -.5, .5},  // centre of class 7
        {-.5, -.5, -.5}  // centre of class 8
    };
 
#ifdef _OPENMP
#pragma omp for
#endif
    for (i = 0; i < N; i++)
    {
        int class =
            rand() % num_classes;  // select a random class for the point
 
        // create random coordinates (x,y,z) around the centre of the class
        data[i][0] = _random(centres[class][0] - R, centres[class][0] + R);
        data[i][1] = _random(centres[class][1] - R, centres[class][1] + R);
        data[i][2] = _random(centres[class][2] - R, centres[class][2] + R);
 
        /* The follosing can also be used
        for (int j = 0; j < 3; j++)
            data[i][j] = _random(centres[class][j] - R, centres[class][j] + R);
        */
    }
}

Here is the call graph for this function: