Context

This project is the final project for the course entitled "Big Data" during my last semester.

Description and goals

The goal of this project was to manipulate a large volume of data and understand the k-means algorithm*.

[*] k-means is an unsupervised clustering algorithm that groups data points in an n-dimensional space into k clusters (or groups), minimizing the distance between clusters. Each point is assigned to the cluster whose center is closest to it.

The project involved two choices:

1. Implementing the k-means algorithm from scratch
2. Using a k-means library and visualizing data and clusters.

My partner and I decided to implement both options, each of us taking care of one. I was therefore responsible for implementing the k-means algorithm from scratch.

Tech Stack

• Python Additional librairies:
  • numpy
  • matplotlib
  • sklearn

Concepts used and developped

• Big Data
• k-means
• Clustering
• PCA

Implementation

Cluster generation

The Clusters class is created to store data with dimensions between 1 and 4 (for simplicity). Subclasses inheriting from this class are responsible for data generation:

• DataClusters: imports external data (e.g., from a file)
• RandomClusters: generates n-dimensional data points according to algorithms from the sklearn and numpy libraries

The basic algorithm

The JAMeans class (named after the initials of our duo and playing on the sound of "K" in French) takes the data and the desired number of clusters and executes the iterations of the classic algorithm, calculating the centers and distances.

Improvement 1: k-means++

K-Means++ is an improvement on the basic algorithm, calculating the cluster centers at the first iteration instead of assigning them randomly.

An improvement in speed is clearly visible.

Improvement 2: Mini-batch k-means

Another way to improve the algorithm is to divide the data into batches and run the slightly modified algorithm on these small batches, thereby improving performance.

Tests

First, tests are performed on the randomly generated clusters. Next, data from the MNIST dataset (a dataset containing images of handwritten digits) is also used. Since these points contained more dimensions, they were reduced using the PCA algorithm (an algorithm for reducing the dimensions of data without losing much of its meaning).

Each execution of the algorithm is logged (in a .log file) with the option of plotting the steps.

Results

The results are presented in the report stored in the same directory as the code.

How to run

The main.py file contains the script used to demonstrate the report.

With the different classes, more testing options are possible. It's up to you! Clone the repository and have fun!

Code

The code is available on this GitLab repository.