Author: Michele Salvatori
Realizzazione di un servizio distribuito che implementa l'algoritmo di clusterizzazione Kmeans utilizzando il paradigma di computazione MapReduce. L'algoritmo è stato implementato utilizzando una delle euristiche più note e più semplici, quella di Lloyd, che trova in modo iterativo il centroide di ciascun cluster in cui è partizionato l'insieme di punti e quindi riassegna i punti ai cluster in base al centroide più vicino. In questa repository è inoltre possibile consultare:
- Report in formato
.pdf
: report.pdf - Analisi delle performance: exectime.xls
Il deployment del servizio è stato effettuato utilizzando i servizi web Amazon Web Services (AWS). In particolare è stata utilizzata un'istanza del servizio EC2 sulla quale viene eseguito un cluster di Docker Container composto da
Per riprodurre tale scenario è sufficiente:
- Creare un'istanza EC2
- [optional] Assegnargli un IP Statico creatndo un ElasticIP offerto sempre dal servizio EC2
- Clonare in una macchina locale questa repository
- Eseguire lo script Ansible che procederà ad installare le componenti Docker e Docker Compose sull'istanza virtuale e ad eseguire l'upload delle librerie che implementano il servizio KMeans.
cd aws
ansible-playbook -i host.ini deploy-kmeans.yaml
# Per eseguire solamente l'upload del progetto, e saltare l'installazione Docker, utilizzare il tag "upload"
ansible-playbook -i host.ini deploy-kmeans.yaml --tags "upload"
# Per eseguire l'aggiornamento dei dataset utilizzare il tag "dataset"
ansible-playbook -i host.ini deploy-kmeans.yaml --tags "dataset"
Terminato il deployment bisognerà istanziare il cluster di Docker Container all'interno dell'istanza EC2:
ssh -i ${aws_private_key.pem} ec2-user@$EC2_IP
cd /home/ec2-user/KMeans-MR
docker-compose up --scale mapper=$MAPPER_NUM --scale reducer=$REDUCER_NUM
Il deployment potrà essere eseguito su macchina locale semplicemente attraverso il file
docker-compose.yml
e sostuitendo l'indirizzo IP dell'istanza EC2 con l'indirizzolocalhost
dove sarà richiesto.
All'utente viene offerta la possibilità di configurare alcuni parametri dell'algoritmo, tra cui:
- Indirizzo 'host' del Master
- Porte utilizzate dal Master e il Worker per la comunicazione
- Soglia di convergenza dell'algoritmo
- Possibilità di abilitare o meno l'ottimizzazione offerta dalla fase Combiner
Tali parametri sono configurabili all'interno del file config.yml
:
# Server configurations
server:
host: "3.229.222.181"
master_port: 9001
worker_port: 9999
dataset_dir: "/go/src/kmeans-MR/datasets/"
# Algorithm parameters
parameters:
test_file_name: "results.csv"
conv_thresh: 0.002
combiner: true
L'utente potrà generare i propri dataset utilizzando lo script Python dataset_generator.py
in cui dovrà specificare il numero di punti che comporranno il dataset e il numero di cluster che essi formeranno.
python3 dataset_generato.py -h
Usage: dataset_gerator.py [-h] dim N K std
d-Dimensional Dataset Generator formed by K cluster.
positional arguments:
dim Number of features
N Number of instances
K Number of clusters
std Standard deviation of the clusters
options:
-h, --help show this help message and exit
Al termine della generazione del dataset, all'utente verrà mostrata una visualizzazione del dataset stesso attraverso uno scatter-plot.
Dopo aver avviato correttamente l'intera architettura sull'istanza EC2, l'utente potrà accedere al servizio attraverso l'apposito client specificando il path del dataset da clusterizzare e il numero
cd $this_repository
./clientKMeans datasets/dataset_3d_3cluster_5000000samples/dataset_3d_3cluster_5000000samples.csv 3
Dopo aver ottenuto i risultati dell'algoritmo, oltre che visualizzarli sulla console, è possibile validarli graficamente attraverso lo script Python check_results.py
python3 check_results.py -h
Usage: check_results.py [-h] dataset
Checking tool for K-Means algorithm results.
positional arguments:
datasetName Name of original CSV dataset including .csv extension
options:
-h, --help show this help message and exit
L'esecuzione dei test può essere effettuata specificando il nome del dataset, il numero di Mapper desiderato su cui eseguire l'algoritmo, e il numero di iterazioni sulle quali verranno calcolati i tempi medi:
cd test
./test MULTIPLE [numerOfMappers] [datasetName] [RUNS]
# è possibile testare l'esecuzione dell'algoritmo su ogni dataset presente nella directory `datasets/`
./test ALLDATA [numerOfMappers] [RUNS]