K-Nearest Neighbors (KNN) Algorithm Implementation

Άννα Γώγουλα / Βασίλης Μιχαλέας / Αταλάντη Παπαδάκη /

Παραδοτέο 3 - 14/01/2024

Αντικείμενα που ασχοληθήκαμε:

• Ανακατασκευάσαμε την ευκλείδεια απόσταση χρησιμοποιώντας την τετραγωνική απόσταση για την εξοικονόμηση υπολογιστικού χρόνου.

• Χρησιμοποιήσαμε Projection Trees για την αρχικοποίηση των ακμών στον γράφο, προσφέροντας έναν αποδοτικό τρόπο εύρεσης γειτόνων.

• Παραλληλοποίσαμε τον αλγόριθμο.

• Δημιουργήσαμε την αναφορά, στην οποία υπάρχουν περισσότερες λεπτομέρειες για την εργασία.

• Makefiles

  • Στο Makefile στον φάκελο main προσθέσαμε τις παρασκάτω εντολές.
  1. run-euclidean-improved
  2. run-accuration

---

Παραδοτέο 2 - 04/12/2023

Αντικείμενο που ασχολήθηκε κάθε μέλος της ομάδας:

• Δημιουργήσαμε ένα καινούργιο αρχείο για τα improvements και σταδιακά κάναμε τις απαραίτητες ενέργειες ώστε να υλοποιηθούν.

  • local_join: Η συνάρτηση εκτελεί λειτουργίες local join για έναν δοσμένο κόμβο. Λαμβάνει υπόψη τους γείτονές του και εκτελεί υπολογισμούς απόστασης για την εντοπισμό νέων γειτόνων, διατρέχοντας στους γείτονες και στους αντίστροφους γείτονες του κόμβου. (Δημιουργήθηκε απο την Αταλάντη)

    • Εφόσον όλες οι βελτιστοποιήσεις χρησιμοποιούνται:
      • Η συνάρτηση χρησιμοποιεί τη μέθοδο sampling για τη δημιουργία λίστας δειγματοληψίας.
      • Διατρέχει τους γείτονες και τους αντίστροφους γείτονες του κόμβου για την εντοπισμό πιθανών νέων γειτόνων.
      • Η συνάρτηση incrementalSearch χρησιμοποιείται για να ελέγξει τις σημαίες των κόμβων πριν από την εκτέλεση της local join.
      • Αν εντοπιστεί μια έγκυρη τοπική σύνδεση, η συνάρτηση addCost χρησιμοποιείται για την ενημέρωση των κοστών.

  • incrementalSearch: Η συνάρτηση εκτελεί μια αναζήτηση σημείο προς σημείο συγκρίνοντας τις σημαίες δύο γειτόνων και καθορίζει εάν η τοπική σύνδεση επιτρέπεται. Επιστρέφοντας 0: Εάν τουλάχιστον μια σημαία είναι ψευδής, υποδεικνύοντας ότι η τοπική σύνδεση δεν επιτρέπεται και 1: Εάν και οι δύο σημαίες είναι αληθείς, υποδεικνύοντας ότι η τοπική σύνδεση επιτρέπεται. (Δημιουργήθηκε απο την Άννα)

  • sampling: εκτελεί δειγματοληψία ελέγχοντας τις σημαίες των κόμβων και επιστρέφοντας μια λίστα με δειγματοληπτικούς κόμβους. Η συνάρτηση επαναλαμβάνεται μέσω των γειτόνων, προσθέτει κόμβους με αληθείς σημαίες σε μια νέα λίστα και μειώνει τον αριθμό δειγμάτων. (Υλοποιήθηκε απο την Αταλάντη και την Άννα)

  • Η υλοποίηση του early termination: Στην συνάρτηση knn_improved_algorithm, εκτελώντας επαναλαμβανόμενες λειτουργίες local join έως ότου το ποσοστό των αλλαγών πέσει κάτω από ένα καθορισμένο όριο. (Εκτελέστηκε απο τον Βασίλη)

  • changeNeighbors: Επαναλαμβάνεται μέσω των κόμβων στο γράφημα και ενημερώνει τους γείτονές τους με βάση τις αλλαγές που έγιναν κατά το local join. (Δημιουργήθηκε απο την Αταλάντη, βοήθησε λίγο και η Άννα)

  • git Actions: Ο Βασιλής ασχολήθηκε με την δημιουργία και την σωστή λειτουργία των git actions. Παρέχοντας αυτοματοποιημένα σενάρια που εκτελούνται με βάση συγκεκριμένες συνθήκες. Αυτά τα σενάρια εκτελούνται κάθε φορά που γίνεται η υποβολή νέου κώδικα.

• Unit tests: Δημιουργήθηκαν unit tests για την εξέταση του καινούργιου κώδικά (από την Άννα και τον Βασίλη).

Κύρια Branches

• main και K23-NNS-Project-v2: Σε αυτά τα branch υπάρχουν όλα τα αρχεία για τις δύο πρώτες εργασίες (ΚΝΝ και ΚΝΝ με βελτιώσεις).

• K23-NNS-Project-v1: Σε αυτό το branch υπάρχουν όλα τα αρχεία για την πρώτη εργασία, τα οποία τροποποιήθηκαν σύμφωνα με τις οδηγίες που μας δώθηκαν.

Makefiles

Οι εντολές είναι ίδιες με αυτές στο 1ο παραδοτέο και μόνο στο Makefile στον φάκελο tests προστέθηκε έξτρα:

• Με make runKNN_imp: τρέχουν τα τεστ για τις συναρτήσεις του knn_improvements.

Extra

1. Για να τρέξει ο αλγόριθμος της 1ης εργασίας, πρέπει απλά στο αρχείο main.c να βγεί από το σχόλιο η γραμμή 25 και να μπει σε σχόλιο η γραμμή 24.
2. Υπάρχει και ένα αρχείο times.txt, όπου αναφέρονται οι χρόνοι αλλά και η ακρίβεια των αλγορίθμων ΚΝΝ και ΚΝΝ με βελτιώσεις για Ευκλείδια και για Manhattan αποστάσεις.

---

Παραδοτέο 1 - 06/11/2023

Αντικείμενο που ασχολήθηκε κάθε μέλος της ομάδας:

• Δημιουργία της Δομής του Γράφου:

  • Αρχικά, όλα τα μέλη της ομάδας συνεργαστήκαμε για τη δημιουργία της δομής του γράφου. Ξεκινήσαμε με τα structs και κάθε ένας ανέλαβε την υλοποίηση μιας δομής (Διαστάσεις, Κόμβοι, Γείτονες) για υλοποίηση. Κατά τη διάρκεια αυτής της υλοποίησης, εντοπίσαμε διάφορα λάθη και κάναμε βελτιώσεις στις δομές.

• Υλοποίηση του Αλγορίθμου ΚΝΝ:

  • Αφού δημιουργήσαμε τη δομή του γράφου, αρχίσαμε να μελετάμε τον τρόπο με τον οποίο θα υλοποιήσουμε τον αλγόριθμο ΚΝΝ. Μελετήσαμε το paper που μας δώθηκε για τον αλγόριθμο ΚΝΝ. Η Αταλάντη και η Άννα υλοποίησαν τη συνάρτηση KRandomNodes. Στη συνέχεια, κάναμε review την υπάρχουσα υλοποίηση και συνεχίσαμε στην υλοποίηση του υπόλοιπου αλγορίθμου. Ο βασικός αλγόριθμος ΚΝΝ υλοποιήθηκε από όλα τα μέλη της ομάδας. Επιπλέον, ο Βασίλης υλοποίησε τον "brute force" αλγόριθμο για την εύρεση των πραγματικών γειτόνων κάθε κόμβου, προκειμένου να γίνει σύγκριση με τα αποτελέσματα του αλγορίθμου ΚΝΝ.

• Unit Tests:

  • Δημιουργήσαμε μονάδικά unit tests για την εξέταση του κώδικά μας. Κάθε μέλος της ομάδας ανέλαβε να δημιουργήσει unit tests για τα κομμάτια του κώδικά που ανέπτυξε. Αυτά τα tests είναι σημαντικά για την αξιολόγηση και την εξασφάλιση της σωστής λειτουργίας του κώδικά μας.

Σχεδιαστικές επιλογές:

• Δομή του Γράφου: Για την αναπαράσταση του γράφου, χρησιμοποιήσαμε δομές δεδομένων που περιλαμβάνουν τα ακόλουθα στοιχεία:

  • Nodes: Αναπαριστά έναν κόμβο στο γράφο. Κάθε κόμβος περιλαμβάνει ένα λίστα διαστάσεων, μια λίστα γειτόνων και μία λίστα αντίστροφών γειτόνων.

  • Dimension: Αναπαριστά τις διαστάσεις κάθε κόμβου, τις οποίες χρησιμοποιούμε για την υπολογισμό των αποστάσεων.

  • Neighbors: Αναπαριστά τους γείτονες κάθε κόμβου, είναι μια ταξινομημένη συνδεδεμένη λίστα γειτόνων (ως προς τα κόστη) που κρατάει τις αποστάσεις προς αυτούς.

  • MathematicalFunctions: Περιλαμβάνει μαθηματικές συναρτήσεις που χρησιμοποιούνται στον αλγόριθμο. Έχουν υλοποιηθεί οι συναρτήσεις που υπολογίζουν τις αποστάσεις manhattan και ευκλείδια.

• Υλοποίηση του Αλγορίθμου KNN περιλαμβάνει:

  • Δημιουργούμε και αρχικοποιούμε τη δομή δεδομένων του γράφου από ένα δυαδικό αρχείο (συνάρτηση createGraphFromBinaryFile). Στα datasets υπάρχουν τα αρχεία που χρησιμοποιούνται για την δημιουργία του γράφου αλλά και στα tests.

  • Εισαγωγή αρχικών γειτόνων (συνάρτηση KRandomNodes): Η συνάρτηση αυτή δημιουργεί αρχικούς γείτονες για κάθε κόμβο με τυχαίο τρόπο, καθώς αυτό είναι το αρχικό βήμα του αλγορίθμου.

  • Υπολογισμός των K-πλησιέστερων γειτόνων (συνάρτηση knn_algorithm): Ο κώδικας υπολογίζει τους K-πλησιέστερους γείτονες για κάθε κόμβο. Συγκρίνουμε τους γείτονες των γειτόνων, τους αντίστροφους των γειτόνων, τους γείτονες των αντίστροφων και τους αντίστροφους των αντίστροφων με τους υπάρχον γείτονες του κάθε κόμβου και κρατάει αυτούς με τα λιγότερα κόστη.

  • Ενημέρωση των γειτόνων και επανάληψη: Ο αλγόριθμος ενημερώνει τους γείτονες και επαναλαμβάνεται για να εντοπίσει περισσότερους γείτονες έως ότου δεν υπάρχουν άλλες αλλαγές.

• Makefiles

  • Το Makefile στον φάκελο main χρησιμοποιείται για να τρέξει ο αλγόριθμος knn που υλοποιήσαμε.

    1. Με make run-euclidean: τρέχει ο αλγόριθμος υπολογίζοντας τις αποστάσεις με Ευκλείδια.
    2. Με make run-manhattan: τρέχει ο αλγόριθμος υπολογίζοντας τις αποστάσεις με Manhattan.

  • Το Makefile στον φάκελο tests χρησιμοποιείται για να τρέξουν τα τεστ για τις συναρτήσεις του αλγορίθμου.

    1. Με make runKNN: τρέχουν τα τεστ για τις συναρτήσεις του knn.c
    2. Με make runG: τρέχουν τα τεστ για τις συναρτήσεις του Graph.c
    3. Με make runN: τρέχουν τα τεστ για τις συναρτήσεις του Node.c
    4. Με make runD: τρέχουν τα τεστ για τις συναρτήσεις του Dimension.c
    5. Με make runMath: τρέχουν τα τεστ για τις συναρτήσεις του MathematicalFunctions.c
    6. Με make runNEI: τρέχουν τα τεστ για τις συναρτήσεις του Neighbors.c
    7. Με make run-all: τρέχουν τα τεστ για όλε τις συναρτήσεις

  • Γενικο Makefile Όπως και παραπάνω οι make εντολές είναι ίδιες, και υπάρχουν έξτρα οι εντολές:

    1. make all: τρέχoυν και ο αλγόριθμος αλλά και τα τεστ.
    2. main-all: τρέχει ο αλγόριθμος με Ευκλείδια απόσταση αλλά και Manhattan
    3. run-all-tests: τρέχουν μόνο τα τεστ.