-
Notifications
You must be signed in to change notification settings - Fork 0
/
readme.txt
150 lines (92 loc) · 16.3 KB
/
readme.txt
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/* readme.txt */
==========================================
(α) ΣΤΟΙΧΕΙΑ ΦΟΙΤΗΤΩΝ
==========================================
ΚΩΝΣΤΑΝΤΙΝΟΣ ΤΣΙΚΟΥΡΗΣ | ΑΜ : 1115201800201
ΒΑΣΙΛΕΙΟΣ ΒΑΣΙΛΑΚΗΣ | ΑΜ : 1115201800018
==========================================
(β) ΤΙΤΛΟΣ ΚΑΙ ΠΕΡΙΓΡΑΦΗ ΠΡΟΓΡΑΜΜΑΤΟΣ
==========================================
ΕΥΡΕΣΗ ΠΛΗΣΙΕΣΤΕΡΩΝ ΓΕΙΤΟΝΩΝ ΚΑΙ ΣΥΣΤΑΔΟΠΟΙΗΣΗ ΠΟΛΥΔΙΑΣΤΑΤΩΝ ΔΕΔΟΜΕΝΩΝ
Το παρόν πρόγραμμα υλοποιεί αλγορίθμους εύρεσης πλησιέστερων γειτόνων τόσο προσεγγιστικούς (LSH, Hypercube, Range Search) όσο και ωμής βίας.
Επίσης υλοποίουνται αλγόριθμοι συσταδοποίησης, με βάση τον αλγόριθμο του Lloyd's, οι οποίοι βελτιώνουν τον βασικό αλγόριθμο ως προς
την αρχικοποίηση των κεντροειδών (kmeans++ initialization) και ως προς το βήμα της ανάθεσης (reverse assignment με χρήση LSH, Hypercube).
Τέλος υλοποιείται και μια μετρική για την αξιολόγηση της συσταδοποίησης (Silhouette).
==========================================
(γ) ΚΑΤΑΛΟΓΟΣ ΚΑΙ ΠΕΡΙΓΡΑΦΗ ΑΡΧΕΙΩΝ
==========================================
ΣΤΟΝ ΦΑΚΕΛΟ common :
- Στο params.hpp, δηλώνονται μερικές global παράμετροι των αλγορίθμων, για ευκολία.
- Τα input_check.cpp/.hpp περιέχουν συναρτήσεις που τσεκάρουν τα arguments από το command line και αρχικοποιούν τις παραμέτρους
του κάθε αλγορίθμου, και συναρτήσεις που διαβάζουν τα αρχεία δεδομένων (input/query file, config file) .
- Τα object.cpp/.hpp περιέχουν την κλάση που ορίζει, περιγράφει και αναπαριστά ένα d-διάστατο αντικείμενο-σημείο.
Επίσης ορίζονται βοηθητικές συναρτήσεις για τη διαχείριση αντικειμένων της κλάσης.
- Τα dataset.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει τη δομή που αποθηκεύει τη πληροφορία (ουσιαστικά δείκτες σε αντικείμενα-σημεία)
ενός αρχείου δεδομένων αντικειμένων-σημείων. Επίσης ορίζονται βοηθητικές συναρτήσεις για τη διαχείριση αντικειμένων της κλάσης.
- Τα h_hash.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει γενικά το H family συναρτήσεων (τις συναρτήσεις h των διαφανειών) .
____________________________________________________________________________________________________________________________________________
ΣΤΟΝ ΦΑΚΕΛΟ data :
Υπάρχει ένα cluster.conf αρχείο για το clustering, καθώς και τα αρχεία δεδομένων εκτός από το input_b_id.
____________________________________________________________________________________________________________________________________________
ΣΤΟΝ ΦΑΚΕΛΟ lsh_folder :
- Τα g_hash.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει τις amplified συναρτήσεις κατακερματισμού g.
- Τα hash.cpp/.hpp περιέχουν την κλάση που ορίζει και περιγράφει τη δομή ενός απλού πίνακα κατακερματισμού (hash-table),
ως πίνακα από συνδεδεμένες λίστες.
- Τα lsh_struct.cpp/.hpp περιέχουν την δομή που χρησιμοποιείται για το LSH (τα L hash-tables), καθώς και συναρτήσεις δημιουργίας/αρχικοποίσης/χειρισμού
της δομής. Επίσης εδώ ορίζονται και υλοποιούνται οι προσεγγιστικοί αλγόριθμοι εύρεσης πλησιέστερων γειτόνων με χρήση LSH (appr_nearest_neighbors, range_search), μέσω της μεθόδου execute που εκτελεί τα απαιτούμενα της εργασίας και εκτυπώνει τα κατάλληλα αποτελέσματα στο αρχείο.
____________________________________________________________________________________________________________________________________________
ΣΤΟΝ ΦΑΚΕΛΟ cluster_folder :
- Τα cluster_info.cpp/.hpp περιέχουν την κλάση που χρησιμοποιείται για να κρατήσει πληροφορία για την συσταδοποίηση (τα κεντροειδή και τα clusters).
Επίσης εδώ ορίζονται και υλοποιούνται όλες οι συναρτήσεις για την υλοποιήση των αλγορίθμων συσταδοποίησης (kmeans++ initialization, exact lloyd's,
reverse assignment using LSH or Hypercube range search, update των κεντροειδών, μετρική Silhouette).
____________________________________________________________________________________________________________________________________________
ΣΤΟΝ ΦΑΚΕΛΟ hypercube_folder :
- Τα f_hash.cpp/hpp περιέχουν την κλάση των συναρτήσεων f_hash που αναθέτουν ακεραίους με τυχαίο τρόπο στο σύνολο {0,1}.
- Τα hypercube_class.cpp/hpp περιέχουν την κλάση hypercube που δημιουργεί τον d'-διάστατο υπερκύβο, αποθηκεύει τα αντικείμενα-σημεία με τον τρόπο που έχουν περιεγραφεί οι διαφάνειες, καθώς και απαραίτητες μέθοδοι kNN, range search και η έκδοση της ωμής βίας επίλυσης του kNN για τον υπερκύβο και έχει την μέθοδο execute που εκτελεί τα απαιτούμενα της εργασίας και εκτυπώνει τα κατάλληλα αποτελέσματα.
____________________________________________________________________________________________________________________________________________
- To lsh.cpp, περιέχει τη main συνάρτηση για το LSH που υλοποιεί τη ζητούμενη λειτουργικότητα.
- Το cube.cpp περιέχει τον ίδιο κώδικα με το lsh.cpp απλά τώρα η δομή δεν είναι ένα lsh_struct αλλά ένα hypercube
- To cluster.cpp, περιέχει τη main συνάρτηση για το clustering που υλοποιεί τη ζητούμενη λειτουργικότητα.
=======================================
(δ) ΟΔΗΓΙΕΣ ΜΕΤΑΓΛΩΤΤΙΣΗΣ
=======================================
Η εντολή mv_objs μετακινεί όλα τα αντικειμενικά αρχεία .o σε έναν φάκελο για ευκολία.
Για τη δημιουργία του εκτελέσιμου στο LSH :
make lsh mv_objs
./lsh -i <input_file_path> -q <query_file_path> -k <int> -L <int> -o <output_file_path> -N <int> -R <int>
όπου οι παράμετροι είναι όπως ορίζονται στην εκφώνηση.
Για τη δημιουργία του εκτελέσιμου στο Clustering :
make cluster mv_objs
./cluster -i <input_file_path> -c <config_file_path> -o <output_file_path> -complete (optional) -m <method>
όπου οι παράμετροι είναι όπως ορίζονται στην εκφώνηση.
Για τη δημιουργία του εκτελέσιμου στο Hypercube :
make cube mv_objs
./cube -i <input_file_path> -q <query_file_path> -k <int> -M <int> -probes <int> -o <output_file_path> -N <int> -R <int>
Για το config_file_path μπορεί να χρησιμοποιηθεί το έτοιμο config_file που έχουμε στο data/cluster.conf.
============================================================================
(ε) ΟΔΗΓΙΕΣ ΧΡΗΣΗΣ / ΣΧΕΔΙΑΣΤΙΚΕΣ ΕΠΙΛΟΓΕΣ-ΠΑΡΑΔΟΧΕΣ / ΕΠΙΛΟΓΕΣ ΠΑΡΑΜΕΤΡΩΝ
============================================================================
Το τυχαίο διάνυσμα v στον ορισμό της συνάρτησης κατακερματισμού h, το κανονικοποιούμε (γιαυτό και τα w που επιλέγουμε είναι μικρά).
Για τα τυχαία ακέραια r_i στον ορισμό της συνάρτησης κατακερματισμού g, όπως ειπώθηκε στο φροντιστήριο δεν έχει
ιδιαίτερη αλγοριθμική σημασία το εύρος τους, και γιαυτό, για πράξεις με μικρότερους αριθμούς, τα επιλέγουμε στο [1,10000].
Για το lsh, πολύ καλά αποτελέσματα ** σε μικρό σχετικά χρόνο παρατηρήθηκαν για τιμές του w γύρω στο w = 30 με w = 40.
Μείωση του w οδηγεί σε ταχύτερους χρόνους αλλά σε προσεγγιστικά λιγότερο ακριβή αποτελέσματα, ενώ αύξηση του w
οδηγεί σε περισσότερο ακριβή αποτελέσματα, αλλά σε χειρότερους χρόνους.
Επίσης για συνδυασμούς των k, L, καλά αποτελέσματα δίνουν τα ζευγάρια k = 5, L = 7, αλλά και τα default k = 4, L = 5.
Για το cube για M = 200, probes = 10, k = 15 και w = 50 έχουν παρατηρηθεί καλά αποτελέσματα. Αυξάνοντας το w μπορεί να πέσει η μέση τιμή average AF κατά περίπου 0.1
αλλά αυτό έχει περίπου 0.3 με 0.4 αύξηση στο λόγο tCube/tTrue. η αύξηση του M ή του probes δεν βοηθάει ιδιαίτερα τα αποτελέσματα των μετρικών.
Όσον αφορά τις προκαθορισμένες παραμέτρους, ο λογος Sum dist true / Sum dist cube πέφτει κατά 0.2 μονάδες, η τιμή average AF από το 1.2-1.3 ανεβαίνει στο 1.7-2 αλλά
ο λόγος tCube/tTrue πέφτει περίπου στο 1/10 του χρόνου των προτεινόμενων παραμέτρων. Με άλλα λόγια, θυσιάζεται ακρίβεια για σημαντική αύξηση χρόνου, συνεπώς
οι προκαθορισμένες μετρικές μπορούν να φανούν χρήσιμες αν ο χρόνος έχει περισσότερη σημασία από την ακρίβεια των αποτελεσμάτων
** Βάσει κάποιων μετρικών που εξηγούμε παρακάτω και τυπώνουμε στο std::cout σε κάθε εκτέλεση.
Μετρικές που επιλέξαμε για να αξιολογήσουμε τις υπερπαραμέτρους:
Άθροισμα των dist_true / Άθροισμα των dist_appr , όπου το κάθε άθροισμα το παίρνουμε για όλα τα query points, appr είτε lsh, είτε cube.
maxAF = μέγιστο κλάσμα από τα dist_appr / dist_true, όπου appr είτε lsh είτε cube.
averageAF = μέσος όρος των κλασμάτων dist_appr / dist_true, για όλα τα query points
average time fraction = μέσος όρος των λόγων των χρόνων time_appr / time_brute_force, για όλα τα query points.
Για το clustering, σαν κριτήριο τερματισμού επιλέχθηκε η μέση μετατόπιση των κεντροειδών, μεταξύ δύο συνεχόμενων επαναλήψεων, να είναι
μικρότερη από μία μικρή θετική ποσότητα e. Σχετικά καλά αποτελέσματα σε λίγες επαναλήψεις, δίνει η τιμή e = 1, την οποία επιλέξαμε.
Στην υλοποίηση του αλγορίθμου range search στο lsh και στο hypercube υπάρχει μια επιπλέον παράπμετρος R2 που στα hpp αρχεία αρχικοποιείται στο 0 αν ο χρήστης δεν δώσει αυτό το όρισμα. Με αυτή την επιπλέον παράμετρο το range search δεν επιστρέφει όλα τα σημεία που βρίσκει που έχουν απόσταση dist από το query object με
dist < R αλλά επιστρέφει όλα τα σημεία των οποίων οι απόσταση dist οκανοποιεί τη σχέση R2 <= dist < R. Έτσι, αφού η προκαθορισμένη τιμή του R2 είναι το 0, η συνάρτηση range search τότε απλά θα υπολογίζει τομ κανονικό range search με ακτίνα R οπότε ηαυτή η γενίκευση του range search δεν επιρρεάζει το κώδικα του πρώτου ερωτήματος καθόλου. Ο λόγος που εισάγεται αυτή τη παράμετρος είναι επειδή στο reverse assignment δεν είναι επιθυμητό να ελέγχονται ξανά σημεία που έχουν ήδη υπολογιστεί σε προηγούμενη επανάληψη με ακτίνα R1 η μικρότερη. Έτσι, θέτοντας R2 = R1, δεν μπαίνουν στο set αυτά τα σημεία ξανά, βελτιώνοντας τον χρόνο στο reverse assignment
Επίσης, για το reverse assignment χρησιμοποιέται η δομή map η οποία αποθηκεύει τα αντικείμενα-σημεία μέσω του id τους μαζί με την απόσταση και το κεντροειδές που έχει τη μικρότερη απόσταση από αυτό. Όταν εκτελείται ένα range search για ένα κεντροειδές, θα επιστραφεί μια λίστα. Για κάθε σημείο-αντικείμενο της λίστας, κοιτάμε μέσω του id αν υπάρχει στο map η όχι. Αν δεν υπάρχει τότε αυτό σημαίνει ότι το σημείο αυτό βρέθηκε για πρώτη φορά άρα το κεντροειδές για το οποίο έτρεξε η range search είναι για εκείνη τη στιγμή το κοντινότερο. Διαφορετικά είναι ήδη στο map άρα απλα κοιτάμε να δούμε για το σημείο αυτό ποιο ήταν το κοντινότερο κεντροειδές και συγκρίνουμε αποστάσεις με το τωρινό κεντροειδές και ενημερώνουμε κατάλληλα τη τιμή του map
Στο makefile, πέρα από τη μεταγλώττιση των αρχείων υπάρχει και η εντολή make mv_objs όπου μεταφέρει όλα τα αντικειμενικά αρχεία σε ένα φάκελο objects. υπάρχουν και εντολές make για εκτελέσεις των εκτελέσιμων ανάλογο με το μέγεθος input, query και μεθόδου ανάλογα με το αν είναι το lsh, το hypercube η το cluster και με τις προκαθορισμένες παραμέτρους. Για το τελευταίο υπάρχει και ένα bash script το οποίο κάνει την ίδια δουλειά αλλά τώρα ο χρήστης μπορεί να προκαθορίσει και το ποιες θα είναι οι παράμετροι ανάλογα με το εκτελέσιμο.