The inclusion criterion for data clustering
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κορνελάκης, Νικόλαος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Η ομαδοποίηση (clustering) αποτελεί ένα από τα σημαντικότερα προβλήματα της ανάλυσης δεδομένων. Στόχος της ομαδοποίησης είναι η διαμέριση των δεδομένων σε ομάδες (clusters), έτσι ώστε να υπάρχει μεγάλη ομοιότητα μεταξύ των δεδομένων της ίδιας ομάδας και όσο το δυνατόν μικρότερη ομοιότητα με δεδομένα διαφορετικών ομάδων. Δύο από τις πιο διαδεδομένες τεχνικές ομαδοποίησης είναι οι αλγόριθμοι kmeans και spectral clustering. Και οι δύο όμως, απαιτούν ως είσοδο τον αριθμό των ομάδων, ο οποίος στις περισσότερες περιπτώσεις δεν είναι γνωστός. Προκύπτει λοιπόν η ανάγκη μετρικών/κριτηρίων έτσι ώστε να μπορεί αξιολογηθεί η ποιότητα της διαμέρισης που παράγεται από μία μέθοδο ομαδοποίησης. Τέτοια γνωστά κριτήρια αξιολόγησης της ποιότητας ομαδοποίησης είναι το silhouette και το modularity. Πρόσφατα έχει προταθεί το κριτήριο inclusion το οποίο παρουσιάζει καλές επιδόσεις. Όμως έχει οριστεί μόνο για δυαδικούς πίνακες ομοιότητας με δυαδικές τιμές (δηλαδή η ομοιότητα (similarity) μεταξύ των δεδομένων είναι ένα ή μηδέν), γεγονός που περιορίζει σημαντικά το πεδίο εφαρμογής του. Βασικός στόχος αυτής της εργασίας είναι η γενίκευση του κριτηρίου inclusion ώστε να μπορεί να χρησιμοποιηθεί σε προβλήματα όπου οι τιμές του πίνακα ομοιότητας λαμβάνουν τιμές στο διάστημα μεταξύ μηδέν και ένα. Προτείνονται διάφορες προσεγγίσεις για την επίτευξη του στόχου αυτού. Οι δύο πρώτες μέθοδοι βασίζονται στο μετασχηματισμό του πίνακα ομοιότητας σε δυαδικό χρησιμοποιώντας ixείτε κατωφλίωση είτε λαμβάνοντας υπόψη του κοντινότερους γείτονες κάθε δεδομένου. Στη συνέχεια αξιοποιείται το κριτήριο inclusion όπως έχει ήδη διατυπωθεί για δυαδικούς πίνακες ομοιότητας. Η σημαντικότερη ωστόσο συνεισφορά της εργασίας είναι μια νέα διατύπωση για το κριτήριο inclusion ώστε να μπορεί να χρησιμοποιηθεί για το γενικό πρόβλημα ομαδοποίησης, όπου η ομοιότητα μπορεί να λάβει οποιαδήποτε τιμή μεταξύ μηδέν και ένα. Ταυτόχρονα παρουσιάζεται μια άπληστη (greedy) μεθοδολογία για τη μεγιστοποίηση του προτεινόμενου κριτηρίου. Επιπλέον προτείνεται και μια τροποποίηση του κριτηρίου (που την ονομάζουμε nearest inclusion) η οποία λαμβάνει υπόψη μόνο την κοντινότερη ομάδα κάθε δεδομένου (εκτός της ομάδας στην οποία ήδη ανήκει) και όχι όλες τις υπόλοιπες ομάδες. Για την αξιολόγηση των κριτηρίων πραγματοποιήθηκαν πειράματα χρησιμοποιώντας τόσο τεχνητά όσο και πραγματικά σύνολα δεδομένων. Από τη σύγκριση με τα αποτελέσματα που προκύπτουν χρησιμοποιώντας τα γνωστά κριτήρια silhouette και modularity μπορούμε να συμπεράνουμε ότι οι προτεινόμενες μεθοδολογίες στις περισσότερες περιπτώσεις παρέχουν ομαδοποιήσεις συγκρίσιμης ή ανώτερης ποιότητας.
Η ομαδοποίηση (clustering) αποτελεί ένα από τα σημαντικότερα προβλήματα της ανάλυσης δεδομένων. Στόχος της ομαδοποίησης είναι η διαμέριση των δεδομένων σε ομάδες (clusters), έτσι ώστε να υπάρχει μεγάλη ομοιότητα μεταξύ των δεδομένων της ίδιας ομάδας και όσο το δυνατόν μικρότερη ομοιότητα με δεδομένα διαφορετικών ομάδων. Δύο από τις πιο διαδεδομένες τεχνικές ομαδοποίησης είναι οι αλγόριθμοι kmeans και spectral clustering. Και οι δύο όμως, απαιτούν ως είσοδο τον αριθμό των ομάδων, ο οποίος στις περισσότερες περιπτώσεις δεν είναι γνωστός. Προκύπτει λοιπόν η ανάγκη μετρικών/κριτηρίων έτσι ώστε να μπορεί αξιολογηθεί η ποιότητα της διαμέρισης που παράγεται από μία μέθοδο ομαδοποίησης. Τέτοια γνωστά κριτήρια αξιολόγησης της ποιότητας ομαδοποίησης είναι το silhouette και το modularity. Πρόσφατα έχει προταθεί το κριτήριο inclusion το οποίο παρουσιάζει καλές επιδόσεις. Όμως έχει οριστεί μόνο για δυαδικούς πίνακες ομοιότητας με δυαδικές τιμές (δηλαδή η ομοιότητα (similarity) μεταξύ των δεδομένων είναι ένα ή μηδέν), γεγονός που περιορίζει σημαντικά το πεδίο εφαρμογής του. Βασικός στόχος αυτής της εργασίας είναι η γενίκευση του κριτηρίου inclusion ώστε να μπορεί να χρησιμοποιηθεί σε προβλήματα όπου οι τιμές του πίνακα ομοιότητας λαμβάνουν τιμές στο διάστημα μεταξύ μηδέν και ένα. Προτείνονται διάφορες προσεγγίσεις για την επίτευξη του στόχου αυτού. Οι δύο πρώτες μέθοδοι βασίζονται στο μετασχηματισμό του πίνακα ομοιότητας σε δυαδικό χρησιμοποιώντας ixείτε κατωφλίωση είτε λαμβάνοντας υπόψη του κοντινότερους γείτονες κάθε δεδομένου. Στη συνέχεια αξιοποιείται το κριτήριο inclusion όπως έχει ήδη διατυπωθεί για δυαδικούς πίνακες ομοιότητας. Η σημαντικότερη ωστόσο συνεισφορά της εργασίας είναι μια νέα διατύπωση για το κριτήριο inclusion ώστε να μπορεί να χρησιμοποιηθεί για το γενικό πρόβλημα ομαδοποίησης, όπου η ομοιότητα μπορεί να λάβει οποιαδήποτε τιμή μεταξύ μηδέν και ένα. Ταυτόχρονα παρουσιάζεται μια άπληστη (greedy) μεθοδολογία για τη μεγιστοποίηση του προτεινόμενου κριτηρίου. Επιπλέον προτείνεται και μια τροποποίηση του κριτηρίου (που την ονομάζουμε nearest inclusion) η οποία λαμβάνει υπόψη μόνο την κοντινότερη ομάδα κάθε δεδομένου (εκτός της ομάδας στην οποία ήδη ανήκει) και όχι όλες τις υπόλοιπες ομάδες. Για την αξιολόγηση των κριτηρίων πραγματοποιήθηκαν πειράματα χρησιμοποιώντας τόσο τεχνητά όσο και πραγματικά σύνολα δεδομένων. Από τη σύγκριση με τα αποτελέσματα που προκύπτουν χρησιμοποιώντας τα γνωστά κριτήρια silhouette και modularity μπορούμε να συμπεράνουμε ότι οι προτεινόμενες μεθοδολογίες στις περισσότερες περιπτώσεις παρέχουν ομαδοποιήσεις συγκρίσιμης ή ανώτερης ποιότητας.
Περιγραφή
Λέξεις-κλειδιά
Data clustering, Inclusion
Θεματική κατηγορία
Data clustering
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Λύκας, Αριστείδης
Εξεταστική επιτροπή
Λύκας, Αριστείδης
Μπλέκας, Κωνσταντίνος
Βλάχος, Κωνσταντίνος
Μπλέκας, Κωνσταντίνος
Βλάχος, Κωνσταντίνος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 46-47
Ονόματα συντελεστών
Αριθμός σελίδων
48 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States