Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/30760Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Κορνελάκης, Νικόλαος | el |
| dc.date.accessioned | 2021-04-06T10:56:59Z | - |
| dc.date.available | 2021-04-06T10:56:59Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/30760 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.10599 | - |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Data clustering | en |
| dc.subject | Inclusion | en |
| dc.title | The inclusion criterion for data clustering | en |
| dc.title | Το κριτήριο inclusion για ομαδοποίηση δεδομένων | el |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Data clustering | - |
| heal.dateAvailable | 2021-04-06T10:57:59Z | - |
| heal.language | en | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2021 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 46-47 | el |
| heal.abstract | Evaluating the quality of clustering solutions is a significant task in data analysis, since it allows the comparison among partitions with different number of clusters. In this way the difficult problem of estimating the true number of clusters can be tackled. A clustering quality measure called ‘inclusion’ has been proposed in the context of community detection, ie. partitioning the nodes of graph into clusters (communities), with many edges joining nodes of the same cluster and comparatively few edges joining nodes of different clusters. The inclusion quality measure evaluates how well each node is ‘included’ in its community by considering both its existing and its non-existing edges. However, it is restricted to the case of binary graphs, where each edge is either zero or one. We introduce an extension of the inclusion definition for the case of general edge matrices where the weight of each edge could take any value between zero and one. Such a wide extension allows the proposed inclusion criterion to be used for any clustering problem given the similarity matrix between data objects. Two methods are considered to exploit the proposed criterion. The first is a greedy approach that starts with every data object in a separate cluster and tries to improve the inclusion of the partitioning by moving each time a single data object to another cluster. The second method relies on using spectral clustering to obtain solutions with different number of clusters and keeping the best solution according to the inclusion criterion. An alternative inclusion definition (called ‘nearest inclusion’) is also proposed that computes inter-cluster similarity as the similarity to the nearest cluster only, instead of considering the similarity to all other clusters. Experiments have been conducted using synthetic and real world datasets to compare inclusion with well-known criteria of clustering quality, such as modularity and silhouette. | en |
| heal.abstract | Η ομαδοποίηση (clustering) αποτελεί ένα από τα σημαντικότερα προβλήματα της ανάλυσης δεδομένων. Στόχος της ομαδοποίησης είναι η διαμέριση των δεδομένων σε ομάδες (clusters), έτσι ώστε να υπάρχει μεγάλη ομοιότητα μεταξύ των δεδομένων της ίδιας ομάδας και όσο το δυνατόν μικρότερη ομοιότητα με δεδομένα διαφορετικών ομάδων. Δύο από τις πιο διαδεδομένες τεχνικές ομαδοποίησης είναι οι αλγόριθμοι kmeans και spectral clustering. Και οι δύο όμως, απαιτούν ως είσοδο τον αριθμό των ομάδων, ο οποίος στις περισσότερες περιπτώσεις δεν είναι γνωστός. Προκύπτει λοιπόν η ανάγκη μετρικών/κριτηρίων έτσι ώστε να μπορεί αξιολογηθεί η ποιότητα της διαμέρισης που παράγεται από μία μέθοδο ομαδοποίησης. Τέτοια γνωστά κριτήρια αξιολόγησης της ποιότητας ομαδοποίησης είναι το silhouette και το modularity. Πρόσφατα έχει προταθεί το κριτήριο inclusion το οποίο παρουσιάζει καλές επιδόσεις. Όμως έχει οριστεί μόνο για δυαδικούς πίνακες ομοιότητας με δυαδικές τιμές (δηλαδή η ομοιότητα (similarity) μεταξύ των δεδομένων είναι ένα ή μηδέν), γεγονός που περιορίζει σημαντικά το πεδίο εφαρμογής του. Βασικός στόχος αυτής της εργασίας είναι η γενίκευση του κριτηρίου inclusion ώστε να μπορεί να χρησιμοποιηθεί σε προβλήματα όπου οι τιμές του πίνακα ομοιότητας λαμβάνουν τιμές στο διάστημα μεταξύ μηδέν και ένα. Προτείνονται διάφορες προσεγγίσεις για την επίτευξη του στόχου αυτού. Οι δύο πρώτες μέθοδοι βασίζονται στο μετασχηματισμό του πίνακα ομοιότητας σε δυαδικό χρησιμοποιώντας ixείτε κατωφλίωση είτε λαμβάνοντας υπόψη του κοντινότερους γείτονες κάθε δεδομένου. Στη συνέχεια αξιοποιείται το κριτήριο inclusion όπως έχει ήδη διατυπωθεί για δυαδικούς πίνακες ομοιότητας. Η σημαντικότερη ωστόσο συνεισφορά της εργασίας είναι μια νέα διατύπωση για το κριτήριο inclusion ώστε να μπορεί να χρησιμοποιηθεί για το γενικό πρόβλημα ομαδοποίησης, όπου η ομοιότητα μπορεί να λάβει οποιαδήποτε τιμή μεταξύ μηδέν και ένα. Ταυτόχρονα παρουσιάζεται μια άπληστη (greedy) μεθοδολογία για τη μεγιστοποίηση του προτεινόμενου κριτηρίου. Επιπλέον προτείνεται και μια τροποποίηση του κριτηρίου (που την ονομάζουμε nearest inclusion) η οποία λαμβάνει υπόψη μόνο την κοντινότερη ομάδα κάθε δεδομένου (εκτός της ομάδας στην οποία ήδη ανήκει) και όχι όλες τις υπόλοιπες ομάδες. Για την αξιολόγηση των κριτηρίων πραγματοποιήθηκαν πειράματα χρησιμοποιώντας τόσο τεχνητά όσο και πραγματικά σύνολα δεδομένων. Από τη σύγκριση με τα αποτελέσματα που προκύπτουν χρησιμοποιώντας τα γνωστά κριτήρια silhouette και modularity μπορούμε να συμπεράνουμε ότι οι προτεινόμενες μεθοδολογίες στις περισσότερες περιπτώσεις παρέχουν ομαδοποιήσεις συγκρίσιμης ή ανώτερης ποιότητας. | el |
| heal.advisorName | Λύκας, Αριστείδης | el |
| heal.committeeMemberName | Λύκας, Αριστείδης | el |
| heal.committeeMemberName | Μπλέκας, Κωνσταντίνος | el |
| heal.committeeMemberName | Βλάχος, Κωνσταντίνος | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 48 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΗΥΠ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΚΟΡΝΕΛΑΚΗΣ ΝΙΚΟΛΑΟΣ 2021.pdf | 1.59 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
