Συσταδοποίηση: Διαφορά μεταξύ των αναθεωρήσεων

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Paren8esis (συζήτηση | συνεισφορές)
Paren8esis (συζήτηση | συνεισφορές)
μ →‎Εγκυρότητα: Προσθήκη παραπομπής για τον δείκτη Γ του Hubert.
Γραμμή 64: Γραμμή 64:
==Εγκυρότητα==
==Εγκυρότητα==
Η εγκυρότητα συσταδοποίησης είναι η διαδικασία εκείνη κατά την οποία εκτιμάται ότι η έξοδος του αλγόριθμου είναι ουσιαστικά ένα σύνολο από ομάδες διανυσμάτων, οι οποίες πληρούν τον ορισμό της συσταδοποίησης καθώς και ορισμένα επιπλέον κριτήρια. Γενικά ο έλεγχος μπορεί να επιτευχθεί με τρεις διαφορετικούς τρόπους ανάλογα με τα κριτήρια που χρησιμοποιούμε:
Η εγκυρότητα συσταδοποίησης είναι η διαδικασία εκείνη κατά την οποία εκτιμάται ότι η έξοδος του αλγόριθμου είναι ουσιαστικά ένα σύνολο από ομάδες διανυσμάτων, οι οποίες πληρούν τον ορισμό της συσταδοποίησης καθώς και ορισμένα επιπλέον κριτήρια. Γενικά ο έλεγχος μπορεί να επιτευχθεί με τρεις διαφορετικούς τρόπους ανάλογα με τα κριτήρια που χρησιμοποιούμε:
#'''Εσωτερικά κριτήρια'''. Ο έλεγχος ενός αλγορίθμου Α επιτυγχάνεται λαμβάνοντας υπ' όψη μόνο τα δεδομένα εισόδου του, αυτά που χρησιμοποιήθηκαν για να επιτευχθεί η συσταδοποίηση. Για παράδειγμα, αν ο Α αποτελεί έναν ιεραρχικό αλγόριθμο, τότε η εκτίμηση του συγκεκριμένου αλγορίθμου μπορεί να γίνει αποκλειστικά από τον πίνακα εγγύτητας. Ένας τέτοιος δείκτης είναι ο τροποποιημένος στατιστικός δείκτης Γ του Hubert: <math>\Gamma=\frac{1}{M}\cdot\sum_{i=1}^{N-1} \sum_{j=i+1}^N P(i,j)Q(i,j)</math> όπου P ο πίνακας εγγύτητας μεταξύ των διανυσμάτων, Q ο πίνακας εγγύτητας μεταξύ των αντιπροσώπων, δηλαδή Q(i,j) = d(w<sub>g</sub>,w<sub>r</sub>) με x<sub>i</sub>∈C<sub>g</sub> , x<sub>j</sub>∈C<sub>r</sub> και M=N·(N-1)/2. Οι συμμετρικοί πίνακες P,Q σχηματίζονται χρησιμοποιώντας το ίδιο μέτρο απόστασης d(·). Υψηλές τιμές του Γ μεταφράζονται ως ομοιότητα μεταξύ πινάκων P,Q, κάτι που συνεπάγεται την'' ορθότητα'' του αλγορίθμου.
#'''Εσωτερικά κριτήρια'''. Ο έλεγχος ενός αλγορίθμου Α επιτυγχάνεται λαμβάνοντας υπ' όψη μόνο τα δεδομένα εισόδου του, αυτά που χρησιμοποιήθηκαν για να επιτευχθεί η συσταδοποίηση. Για παράδειγμα, αν ο Α αποτελεί έναν ιεραρχικό αλγόριθμο, τότε η εκτίμηση του συγκεκριμένου αλγορίθμου μπορεί να γίνει αποκλειστικά από τον πίνακα εγγύτητας. Ένας τέτοιος δείκτης είναι ο τροποποιημένος στατιστικός δείκτης Γ του Hubert <ref>{{Cite journal|url=http://onlinelibrary.wiley.com/doi/10.1111/j.2044-8317.1976.tb00714.x/abstract|title=Quadratic Assignment as a General Data Analysis Strategy|last=Hubert|first=Lawrence|last2=Schultz|first2=James|date=1976-11-01|journal=British Journal of Mathematical and Statistical Psychology|issue=2|doi=10.1111/j.2044-8317.1976.tb00714.x|volume=29|pages=190–241|language=en|issn=2044-8317}}</ref>: <math>\Gamma=\frac{1}{M}\cdot\sum_{i=1}^{N-1} \sum_{j=i+1}^N P(i,j)Q(i,j)</math> όπου P ο πίνακας εγγύτητας μεταξύ των διανυσμάτων, Q ο πίνακας εγγύτητας μεταξύ των αντιπροσώπων, δηλαδή Q(i,j) = d(w<sub>g</sub>,w<sub>r</sub>) με x<sub>i</sub>∈C<sub>g</sub> , x<sub>j</sub>∈C<sub>r</sub> και M=N·(N-1)/2. Οι συμμετρικοί πίνακες P,Q σχηματίζονται χρησιμοποιώντας το ίδιο μέτρο απόστασης d(·). Υψηλές τιμές του Γ μεταφράζονται ως ομοιότητα μεταξύ πινάκων P,Q, κάτι που συνεπάγεται την'' ορθότητα'' του αλγορίθμου.
#'''Εξωτερικά κριτήρια'''. Σε αυτή την περίπτωση ''υπολογίζεται μία δομή των διανυσμάτων Μ εξωτερικά από τον χρήστη''. Στη συνέχεια απλά γίνεται σύγκριση της συσταδοποίησης Μ={m<sub>1</sub>, m<sub>2</sub>… m<sub>s</sub>} με την έξοδο του αλγορίθμου C={ c<sub>1</sub>, c<sub>2</sub>… c<sub>k</sub>} . Για παράδειγμα έστω
#'''Εξωτερικά κριτήρια'''. Σε αυτή την περίπτωση ''υπολογίζεται μία δομή των διανυσμάτων Μ εξωτερικά από τον χρήστη''. Στη συνέχεια απλά γίνεται σύγκριση της συσταδοποίησης Μ={m<sub>1</sub>, m<sub>2</sub>… m<sub>s</sub>} με την έξοδο του αλγορίθμου C={ c<sub>1</sub>, c<sub>2</sub>… c<sub>k</sub>} . Για παράδειγμα έστω
#*TP = το πλήθος των διανυσμάτων που ανήκουν σε ίδια ομάδα κατά τη συσταδοποίηση C και P
#*TP = το πλήθος των διανυσμάτων που ανήκουν σε ίδια ομάδα κατά τη συσταδοποίηση C και P

Έκδοση από την 18:43, 5 Μαΐου 2016

Συσταδοποίηση είναι η διαδικασία εκείνη κατά την οποία ένα σύνολο από «αντικείμενα», διαχωρίζονται σε ένα σύνολο από λογικές ομάδες. Η καταχώρηση αντικειμένων σε ίδια ομάδα μεταφράζεται ως ομοιότητα των αντικειμένων αυτών και αντίστροφα (αντικείμενα που ανήκουν σε διαφορετικές ομάδες είναι ανόμοια). Η ομοιότητα ή μη, μεταξύ των αντικείμενων, ουσιαστικά εξαρτάται από το συγκεκριμένο πρόβλημα και τη μορφή των «αντικειμένων». Στη βιβλιογραφία συναντάται ως ομαδοποίηση και μη επιβλεπόμενη μάθηση. Τα αντικείμενα μπορούν να αναφερθούν και αυτά με διαφορετικούς όρους: πρότυπα, διανύσματα (παρακάτω θα αναφέρονται ως διανύσματα).

Ορισμός

Δοθέντος ενός συνόλου διανυσμάτων X = {x1,x2,x3... xn} ζητούνται m σύνολα-ομάδες C1,C2...Cm,με m<<n έτσι ώστε :
Ci i =1,2,3...m και οι m ομάδες αποτελούν διαμέριση του συνόλου Χ.
Ο ορισμός αυτός αναφέρεται στην αυστηρή συσταδοποίηση διότι κάθε διάνυσμα ανήκει σε μία και μόνο ομάδα. Εναλλακτικά μπορεί να οριστεί η ασαφής συσταδοποίηση. Κάνοντας χρήση των ασαφών συνόλων μπορούμε να ορίσουμε m συναρτήσεις συμμετοχής uj:X→[0,1] για j=1,2,...m. Οι συναρτήσεις u ποσοτικοποιούν την βεβαιότητα που έχουμε για το αν κάποιο διάνυσμα i ανήκει στην ομάδα j.

Η διαδικασία της συσταδοποίησης ακολουθεί τα τρία βασικά βήματα:[1][2]

  • Επιλογή χαρακτηριστικών γνωρισμάτων. Ο στόχος είναι να επιλεγούν τα καταλληλότερα γνωρίσματα στα οποία πρόκειται να εφαρμοστεί η συσταδοποίηση ώστε να επιτυγχάνεται η βέλτιστη ομοιογένεια σε κάθε συστάδα. Έτσι η προεπεξεργασία των δεδομένων πριν την εφαρμογή της διαδικασίας συσταδοποίησης κρίνεται απαραίτητη.
  • Αλγόριθμοι συσταδοποίησης. Σε αυτό το στάδιο γίνεται η επιλογή ενός αλγορίθμου που θα οδηγήσει σε ένα καλό σχήμα συσταδοποίησης για ένα σύνολο δεδομένων. Για τη επιλογή του αλγορίθμου χρησιμοποιείται το μέτρο γειτνίασης και το κριτήριο συσταδοποίησης τα οποία ορίζουν απόλυτα τον αλγόριθμο, καθώς επίσης και η δυνατότητά του να καθορίσει ένα σχήμα συσταδοποίησης που να προσαρμόζεται στο συγκεκριμένο σύνολο δεδομένων.
  1. Το μέτρο γειτνίασης (proximity measure) αναφέρεται στην ομοιότητα δύο αντικειμένων (δηλαδή διανύσματα γνωρισμάτων). Η επιλογή των γνωρισμάτων πρέπει να γίνεται προσεχτικά ώστε η συμβολή τους να είναι ίση κατά τον υπολογισμό του μέτρου γειτνίασης και να μην υπερισχύει το ένα έναντι του άλλου.
  2. Το κριτήριο συσταδοποίησης (clustering criterion) εκφράζεται βάσει μιας συνάρτησης κόστους ή κάποιου άλλου τύπου κανόνων. Είναι σημαντικό να γνωρίζουμε τον τύπο των συστάδων που θα προκύψουν στο σύνολο δεδομένων, για να διαλέξουμε το κατάλληλο κριτήριο που θα ταιριάζει στο σύνολο δεδομένων και θα έχει ως αποτέλεσμα μία επιτυχημένη τμηματοποίηση.
  • Επικύρωση αποτελεσμάτων. Σε αυτή τη φάση αξιολογούνται τα αποτελέσματα του αλγορίθμου συσταδοποίησης σύμφωνα με κατάλληλα κριτήρια ορθότητας συσταδοποίησης και τεχνικές. Παράδειγμα ενός τέτοιου κριτηρίου είναι η σύγκριση των αποτελεσμάτων της ανάλυσης με κάποια ήδη γνωστά αποτελέσματα ή η σύγκριση των αποτελεσμάτων δύο διαφορετικών συσταδοποιήσεων. Η ποιότητα της συσταδοποίησης εξαρτάται από την ομοιότητα(δηλαδή μεγάλη ομοιότητα εντός της συστάδας - μικρή ομοιότητα μεταξύ των συστάδων) και την μέθοδο υλοποίησης της συσταδοποίησης.
  • Ερμηνεία των αποτελεσμάτων. Αποτελεί το τελευταίο στάδιο της διαδικασίας συσταδοποίησης, όπου οι αναλυτές καλούνται να εξάγουν γνώση από τις παραχθείσες συστάδες, συνδυάζοντας κι άλλα στοιχεία, αναλύσεις, με σκοπό το καλύτερο και εγκυρότερο αποτέλεσμα.

Οι συναρτήσεις εγγύτητας d:X×X R στην απλή τους μορφή μπορεί να είναι απλά μέτρα ανομοιότητας ∃ d0 ∈ R :
d(x,x) = d0 ∀ x ∈ X,
d(x,y) ≥ d0∀ x,y ∈ X
d(x,y) = d(y,x) ∀ x,y ∈ X ή να αποτελούν μετρική ανομοιότητας ( μετατροπή σε ομοιότητα με κατάλληλες αλλαγές ).Σε κάθε περίπτωση η επιλογή της συνάρτησης αυτής εξαρτάται από την μορφή των διανυσμάτων, αν τα χαρακτηριστικά των διανυσμάτων ανήκουν σε συνεχή ή διακριτό χώρο, αν είναι αριθμητικά ή όχι… και υπάρχουν διαφορές επιλογές (απόσταση Milikowski η οποία εμπεριέχει και την ευκλείδεια απόσταση, απόσταση Hamming...). Επιπλέον μπορούμε να ορίσουμε και ανομοιότητα μεταξύ δύο συνόλων διανυσμάτων ή μεταξύ συνόλου διανυσμάτων και διανύσματος. Και εδώ όμως η απόσταση μεταξύ συνόλων μετριέται με αποστάσεις μεταξύ διανυσμάτων. Για κάθε σύνολο διανυσμάτων-ομάδα C, επιλέγουμε ένα διάνυσμα αντιπρόσωπο π.χ το διάνυσμα ελάχιστης συνολικής απόστασης mc για το οποίο ισχύει
∀ z ∈ C ή το μέσο διάνυσμα mp το οποίο ορίζεται : όπου nc ο πληθάριθμος της ομάδας C είτε ένα σύνολο διανυσμάτων που το αντιπροσωπεύει με το σύνολο αυτό να έχει μία συγκεκριμένη μορφή στο χώρο π.χ ένα υπερεπίπεδο, μία υπερσφαίρα.

Αλγόριθμοι συσταδοποίησης

Υπάρχει ένα μεγάλο πλήθος από αλγόριθμους συσταδοποίησης που έχουν προταθεί και ο καθένας τους βασίζεται σε διαφορετική φιλοσοφία. Σχεδόν όλοι τους δέχονται ένα σύνολο παραμέτρων που μπορεί να είναι το πλήθος των ομάδων, διανύσματα αρχικοποίησης που απαιτούνται από τον αλγόριθμο κάποιες υποθέσεις για την πυκνότητα των διανυσμάτων στο χώρο και άλλες διάφορες παραμέτρους. Διαφοροποιώντας αυτές τις παραμέτρους προκύπτει ένα σύνολο από αλγόριθμους σε κάθε βασική κατηγορία.

K-means

Ο συγκεκριμένος αλγόριθμος είναι από τους πιο πολυεφαρμοσμένους και είναι η ρίζα για πολλούς άλλους. Ανήκει στην κατηγορία της επίπεδης συσταδοποίησης διότι παράγει ένα σύνολο συσταδοποιήσεων οι οποίες δεν έχουν κάποια ιδιαίτερη δομή-σχέση μεταξύ τους. Ο αλγόριθμος έχει ως στόχο τη βελτιστοποιήση μίας συνάρτησης – της συνάρτησης κόστους.

K-means

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

  1. Κατά τη φάση της διαμέρισης γίνεται προσπέλαση των διανυσμάτων και για κάθε διάνυσμα βρίσκουμε την απόστασή του από (ανομοιότητα με) τις υπάρχουσες ομάδες. Η απόσταση μεταξύ ενός διανύσματος και μίας ομάδας είναι η ευκλείδεια απόσταση από το μέσο (mp) διάνυσμα. Για i=1,2...N υπολογίζουμε τις αποστάσεις ως εξής:
    ∀ j=1,2,3...k. Προσδιορίζονται Ν αριθμοί q, έτσι ώστε να ισχύει: d(xi,Cq) ≤ d(xi,Cj) ∀ j=1,2,3...k. Κατά την ολοκλήρωση αυτού του βήματος σχηματίζονται k-σύνολα διανυσμάτων, ένα σύνολο για κάθε ομάδα.
  2. Κατά τη φάση της ενημέρωσης, γίνονται οι κατάλληλες τροποποιήσεις στα μέσα διανύσματα, δηλαδή ∀ j=1,2...m: υπολογίζονται ξανά τα μέσα διανύσματα mi για i=1,2...κ. Στον υπολογισμό του νέου mi συνεισφέρει το αντίστοιχο σύνολο διανυσμάτων που υπολογίστηκε κατά το παραπάνω βήμα.

Ο αλγόριθμος ολοκληρώνεται όταν οι ενημερώσεις που γίνονται σε κάθε mi είναι αμελητέες. Σημαντικό σημείο του αλγορίθμου είναι η αρχικοποίηση των k-διανυσμάτων. Αν αντί για το μέσο διάνυσμα χρησιμοποιήσουμε ένα διάνυσμα xj, με xj ∈ X, τότε έχουμε τον αλγόριθμο k-εσωτερικών αντιπροσώπων.[3] Η χρονική πολυπλοκότητα του αλγόριθμου είναι Ο(Νkq) όπου q ο αριθμός των επαναλήψεων που πρέπει να εκτελέσει ο αλγόριθμος για να τερματίσει.

Ιεραρχικοί

Οι ιεραρχικοί αλγόριθμοι συσταδοποίησης παράγουν μια ιεραρχία εμφωλιασμένων συσταδοποιήσεων . Δύο συσταδοποίησεις λέγονται εμφωλιασμένες
όταν ισχύει :∀ xi,xj,∈ Ck,κατά την συσταδοποίηση Εp → xi,xj ∈ Ck' κατά την συσταδοποίηση Εq
Οι αλγόριθμοι αυτοί διαχωρίζονται σε δύο υποκατηγορίες

  • στους συσσωρευτικούς
  • και στους διαιρετικούς.
  • Οι συσσωρευτικοί ξεκινάνε με n ομάδες, Ε0= {Ci = {xi}}, ∀ i=1,2,...,n. Σε κάθε βήμα του αλγορίθμου b, το πλήθος των ομάδων μειώνεται κατά ένα συγχωνεύοντας δύο σε μία ομάδα έως φτάσουμε σε μία μοναδική που να εμπεριέχει όλα τα διανύσματα. Η εξέλιξη του αλγορίθμου μπορεί να αναπαρασταθεί γραφικά με ένα δενδρόγραμμα ανομοιότητας. Το δενδρόγραμμα περιέχει n-1 επίπεδα με το κάθε επίπεδο να αποτελεί ένα βήμα του αλγορίθμου. Επιπλέον περιλαμβάνει και την ποσότητα ανομοιότητας μεταξύ των ομάδων που συγχωνεύονται.

Γενικά στο βήμα b, συγχωνεύονται οι ομάδες οι οποίες είναι το λιγότερο ανόμοιες :
d(Ci,Ci)=min(d(Ck,Ch) ,∀ Ck,Ch ∈ Εb-1 συσταδοποίηση και k≠h. Οι αλλαγές που γίνονται είναι :
Cq =Ci ∪ Cj,Eb=(Eb-1-{Cj,Cj}) ∪ {Cq}, όπου d συνάρτηση ανομοιότητας μεταξύ συνόλων διανυσμάτων.
Μετά την συγχώνευση στο επίπεδο b+1, η ανομοιότητα μεταξύ μίας ομάδας Cs και της Cq υπολογίζεται ως
d(Cq,Cs) = f(d(Ci,Cs),d(Cj,Cs),d(Ci,Cj). Γενικά η f μπορεί να είναι οποιαδήποτε αλλά μία απλή μορφή είναι:

d(Cq,Cs) =a d(Ci,Cs)+cd(Cj,Cs)+wd(Ci,Cj)+ e|d(Ci,Cs)-d(Cj,Cs)| 

Για την παραπάνω μορφή της f, επιλέγοντας διαφορετικούς συντελεστές καταλήγουμε σε διαφορετικά μέτρα ανομοιότητας κάθε φορά με αποτέλεσμα η εξέλιξη του αλγορίθμου να διαφοροποιείται( άρα και η έξοδος του αν ζητήσουμε μία συσταδοποίηση διαφορετική της τελευταίας και της πρώτης).Τα δύο άκρα όταν η συνάρτηση ενημέρωσης είναι η παραπάνω είναι τα εξής :
d(Cq,Cs) = min(d(Ci,Cq) για a=1, c=1, e=-1/2, αλγόριθμος απλού δεσμού
d(Ci,Ci) = max(d(Ck,Ch) για a=1 ,c=1, e=1/2, αλγόριθμος πλήρους δεσμού
. Μπορούμε να προσαρμόσουμε τη μορφή του δενδρογράμματος ενός αλγόριθμου ,σε μία από τις δύο παραπάνω μορφές με κατάλληλη επιλογή τιμών των συντελεστών.
Όλα αυτά είναι αποτελέσματα χρήσης του πίνακα ανομοιότητας , μία μήτρα το οποίο το aij στοιχείο δηλώνει την ανομοιότητα των i,j διανυσμάτων. Μπορούν να μεταφερθούν εύκολα από την θεωρία πινάκων στη θεωρία γράφων .Γενικά υπάρχει ολόκληρη κατηγορία αλγορίθμων που βασίζονται στους γράφους, κατευθυνόμενους ή μη ). H χρονική πολυπλοκότητα των συσσωρευτικών αλγόριθμων είναι Ο(n3).H πολυπλοκότητα αυτή μπορεί να κατέβει κοντά στο Ο(n2).Για παράδειγμα ο CURE έχει πολυπλοκότητα Ο(n2lgn).

  • Οι διαιρετικοί αλγόριθμοι ακολουθούν αντίστροφη διαδικασία. Ξεκινούν από μία ομάδα η οποία εμπεριέχει όλα τα διανύσματα και σε κάθε βήμα μία ομάδα διασπάται σε δύο μέχρι να καταλήξουμε σε Ν ομάδες. Η πολυπλοκότητα τους είναι μεγαλύτερη από τους συσσωρευτικούς αφού η διάσπαση μίας ομάδας σε δύο μπορεί να γίνει κατά 2N-1-1 τρόπους και η επιλογή της βέλτιστης διάσπασης πρακτικά είναι αδύνατη ακόμα και για μικρό Ν. Στην πράξη αυτό που γίνεται ότι ο αλγόριθμος σε κάθε βήμα διασπά μία ομάδα αλλά όχι κατά βέλτιστο τρόπο.

Ανταγωνιστικής Μάθησης

Οι συγκεκριμένοι αλγόριθμοι χρησιμοποιούν ένα σύνολο αντιπροσώπων wi για i=1,2…m. Αυτά είναι μία από τις παραμέτρους εισόδου του αλγόριθμου όπως και το μέγιστο πλήθος ομάδων ,το κριτήριο τερματισμού του αλγόριθμου… Η λογική του αλγόριθμου είναι η εξής,∀ i=1,2…N

  • τα διανύσματα εμφανίζονται ένα , ένα και οι αντιπρόσωποι wj για j=1,2…m ανταγωνίζονται για την διεκδίκηση τους. Αφού βρεθεί ο νικητής ,έστω wq (για το διάνυσμα b,κατά το βήμα b-τα διανύσματα εξετάζονται κατά διάταξη: x1,x2...xN.Η σειρά εξέτασης των διανυσμάτων είναι και αυτή μία παράμετρος που πρέπει να προσδιοριστεί) ,τότε «αυτός» μετακινείται προς το xb ενώ ή ηττημένοι κινούνται ελάχιστα –αν κινηθούν. Βέβαια ακόμα και η κίνηση του νικητή θα μπορούσε να γίνει υπό συνθήκες .Για παράδειγμα για δεδομένο κατώφλι ανομοιότητας Θ, μέγιστο πλήθος ομάδων μ και μέτρο ανομοιότητας d(·) ,αν ισχύει
    • d(xb,wq)>Θ ∧(m(οι υπάρχουσες ομάδες) < μ ) τότε δημιουργείται καινούργια ομάδα με μοναδικό στοιχείο το διάνυσμα xb αλλιώς γίνονται οι κατάλληλες κινήσεις των αντιπροσώπων .

Οι παράμετροι είναι οι ρυθμοί μάθησης των νικητών και των ηττημένων ενώ η h(·) είναι μια κατάλληλα ορισμένη συνάρτηση .Οι ρυθμοί μάθησης μεταξύ των ηττημένων μπορούνε να είναι διαφορετικοί. Και πάλι για διαφορετικές παραμέτρους(τιμές παραμέτρων) προκύπτουν διαφορετικοί αλγόριθμοι .Για παράδειγμα το πλήθος των ομάδων θα μπορούσε να είναι σταθερό και να μην υπάρχουν οι -υπό συνθήκη- κινήσεις .

Εγκυρότητα

Η εγκυρότητα συσταδοποίησης είναι η διαδικασία εκείνη κατά την οποία εκτιμάται ότι η έξοδος του αλγόριθμου είναι ουσιαστικά ένα σύνολο από ομάδες διανυσμάτων, οι οποίες πληρούν τον ορισμό της συσταδοποίησης καθώς και ορισμένα επιπλέον κριτήρια. Γενικά ο έλεγχος μπορεί να επιτευχθεί με τρεις διαφορετικούς τρόπους ανάλογα με τα κριτήρια που χρησιμοποιούμε:

  1. Εσωτερικά κριτήρια. Ο έλεγχος ενός αλγορίθμου Α επιτυγχάνεται λαμβάνοντας υπ' όψη μόνο τα δεδομένα εισόδου του, αυτά που χρησιμοποιήθηκαν για να επιτευχθεί η συσταδοποίηση. Για παράδειγμα, αν ο Α αποτελεί έναν ιεραρχικό αλγόριθμο, τότε η εκτίμηση του συγκεκριμένου αλγορίθμου μπορεί να γίνει αποκλειστικά από τον πίνακα εγγύτητας. Ένας τέτοιος δείκτης είναι ο τροποποιημένος στατιστικός δείκτης Γ του Hubert [4]: όπου P ο πίνακας εγγύτητας μεταξύ των διανυσμάτων, Q ο πίνακας εγγύτητας μεταξύ των αντιπροσώπων, δηλαδή Q(i,j) = d(wg,wr) με xi∈Cg , xj∈Cr και M=N·(N-1)/2. Οι συμμετρικοί πίνακες P,Q σχηματίζονται χρησιμοποιώντας το ίδιο μέτρο απόστασης d(·). Υψηλές τιμές του Γ μεταφράζονται ως ομοιότητα μεταξύ πινάκων P,Q, κάτι που συνεπάγεται την ορθότητα του αλγορίθμου.
  2. Εξωτερικά κριτήρια. Σε αυτή την περίπτωση υπολογίζεται μία δομή των διανυσμάτων Μ εξωτερικά από τον χρήστη. Στη συνέχεια απλά γίνεται σύγκριση της συσταδοποίησης Μ={m1, m2… ms} με την έξοδο του αλγορίθμου C={ c1, c2… ck} . Για παράδειγμα έστω
    • TP = το πλήθος των διανυσμάτων που ανήκουν σε ίδια ομάδα κατά τη συσταδοποίηση C και P
    • TN = το πλήθος των διανυσμάτων που ανήκουν σε διαφορετική ομάδα κατά τη συσταδοποίηση C και P
    • FN = το πλήθος των διανυσμάτων που ανήκουν σε διαφορετική ομάδα κατά τη συσταδοποίηση C, ενώ ανήκουν στην ίδια ομάδα κατά την P
    • FP = το πλήθος των διανυσμάτων που ανήκουν στην ίδια ομάδα κατά τη συσταδοποίηση C, ενώ ανήκουν σε διαφορετικές ομάδες κατά την P Ένας απλός δείκτης είναι o RI (Rand Index) ο οποίος μετρά το ποσοστό της σωστής συσταδοποίησης. . Υπάρχουν διάφοροι άλλοι δείκτες, οι περισσότεροι από τους οποίους βασίζονται στους παραπάνω τέσσερις πληθάριθμους συνόλων.
  3. Σχετικά κριτήρια. Τέλος υπάρχει και η διαδικασία ελέγχου που βασίζεται σε σχετικά κριτήρια. Στη συγκεκριμένη περίπτωση γίνονται αλλαγές των παραμέτρων εισόδου του αλγορίθμου και εκτιμάται η νέα συσταδοποίηση C'. Αυτό μπορεί να γίνει επαναληπτικά έτσι ώστε να καταλήξουμε στην καλύτερη δυνατή συσταδοποίηση. Οι αλλαγές που μπορούν να γίνουν είναι (υποθέτουμε ότι τα παρακάτω είναι παράμετροι εισόδου): διαφορετική διάταξη των διανυσμάτων, διαφορετικό πλήθος ομάδων συσταδοποίησης, διαφορετικό διάστημα πλήθους συσταδοποιήσεων [mmin, mmax], διαφορετικοί αρχικοί αντιπρόσωποι (για παράδειγμα τα αρχικά μέσα διανύσματα που χρησιμοποιεί ο k-means), κλπ.

Εφαρμογές

Η συσταδοποίηση ως έννοια είναι σημαντική όχι μόνο σε πολλές επιστήμες όπως η κοινωνιολογία, η βιολογία και η στατιστική, αλλά και σε πολλούς τομείς της πληροφορικής όπως η αναγνώριση προτύπων, η εξόρυξη γνώσης, η ανάκτηση δεδομένων, η τεχνητή νοημοσύνη και η μηχανική μάθηση. Επίσης όσον αφορά την επεξεργασία δεδομένων η συσταδοποίηση μπορεί να συμβάλει στην μείωση των δεδομένων, στην παραγωγή και έλεγχο μίας υπόθεσης και στην πραγματοποίηση μίας πρόβλεψης βασισμένη στις συστάδες. Όλα αυτά ουσιαστικά αναφέρονται και ορίζουν το ίδιο πρόβλημα με διαφορετική γλώσσα ορισμού. Τα τελευταία χρόνια οι τομείς αυτοί αποκτούν όλο και περισσότερο ενδιαφέρον καθιστώντας έτσι την συσταδοποίηση αντικείμενο εντατικής έρευνας.

Για παράδειγμα στην ανάκτηση δεδομένων πέρα από το αποθηκευτικό κέρδος που μπορεί να αποφέρει η συσταδοποίηση η έννοια εφαρμόζεται ξεκάθαρα από μηχανές αναζήτησης yippy.com. Εδώ ζητάτε να ομαδοποιηθούν τα έγγραφα απάντησης D ενός ερωτήματος q του χρήστη. Οι μηχανές αναζήτησης δίνουν και μία οπτικοποίηση της συσταδοποίησης, με την έννοια ότι τα έγγραφα απάντησης D μπορεί να αναπαρασταθούν γραφικά.

Σε ένα σύστημα αναγνώρισης προτύπων η συσταδοποίηση μαζί με την κατηγοριοποίηση αποτελούν της δύο βασικές διαδικασίες που πρέπει να ενσωματώνει ένα τέτοιο σύστημα. Το σύστημα αυτό μπορεί να είναι ένα σύστημα αυθεντικοποίησης-ταυτοποίησης μέσω ομιλίας (αναγνώριση ομιλητή), ένα σύστημα αναγνώρισης εικόνων.

[1] Στην μείωση των δεδομένων η συσταδοποίηση μπορεί να χρησιμοποιηθεί με σκοπό την συμπίεση των δεδομένων. Στην περίπτωση δηλαδή ενός μεγάλου συνόλου δεδομένων, η συσταδοποίηση δύναται αρχικά να το τμηματοποιείσει σε συστάδες, και ύστερα να επεξεργαστεί τους αντιπροσώπους των συστάδων, αντί τα δεδομένα ξεχωριστά.

[1] Στην παραγωγή υπόθεσης η συσταδοποίηση εφαρμόζεται, με σκοπό την διαπίστωση τυχόν υποθέσεων που μπορεί να προκύψουν μετά από την επεξεργασία ενός συνόλου δεδομένων. Για παράδειγμα, είναι δυνατό να βρεθούν δύο μεγάλες συστάδες πελατών, με βάση την ηλικία τους και την χρονική στιγμή που κάνουν τις αγορές τους. Έτσι, μπορούμε να διαπιστώσουμε ότι λ.χ. «οι νέοι προτιμούν να κάνουν τα ψώνια τους τις βραδυνές ώρες», ενώ «οι μεγαλύτεροι σε ηλικία κάνουν τα ψώνια τους κυρίως τις πρωινές ώρες».

[1] Στον έλεγχο υπόθεσης μπορεί να χρησιμοποιηθεί η ανάλυση συστάδων για την εξακρίβωση και την αξιολόγηση μίας υπόθεσης. Για παράδειγμα, εάν θέλουμε να εξετάσουμε την υπόθεση «οι μεγαλύτεροι σε ηλικία κάνουν τα ψώνια τους κυρίως τις πρωινές ώρες», πρέπει να συλλέξουμε ένα αντιπροσωπευτικό σύνολο καταστημάτων, τα οποία διθέτουν στοιχεία των πελατών τους. Άν το αποτέλεσμα της συσταδοποίησης είναι η υπόθεση «οι μεγαλύτεροι σε ηλικία κάνουν τα ψώνια τους κυρίως τις πρωινές ώρες», τότε η υπόθεση επαληθεύεται και από την ανάλυση συστάδων.

Και τέλος, μία πρόβλεψη βασισμένη σε συστάδες υλοποιείται με την εφαρμογή της συσταδοποίησης , όπου οι συστάδες που προκύπτουν, χαρακτηρίζονται από τα χαρακτηριστικά των προτύπων που ανήκουν σε αυτές τις συστάδες. Αυτά τα πρότυπα μπορούν αργότερα να ταξινομηθούν στις προσδιοριζόμενες συστάδες με βάση την ομοιότητά τους στα χαρακτηριστικά των συστάδων.Κατά συνέπεια, προκύπτει χρήσιμη γνώση από τα δεδομένα. Παραδείγματος χάριν, εφαρμόζουμε την διαδικασία της συσταδοποίησης σε ένα σύνολο δεδομένων που αφορά ασθενείς μιας συγκεκριμένης νόσου. Το επιθυμητό αποτέλεσμα θα είναι συστάδες ασθενών με βάση την αντίδρασή τους στα ίδια φάρμακα. Έτσι, είναι δυνατό για έναν νέο ασθενή να κατηγοριοποιηθεί στην κατάλληλη συστάδα και να πάρει την σωστή φαρμακευτική αγωγή.

Το πλήθος των δεδομένων που κυκλοφορούν στο διαδίκτυο είναι τεράστιο. Η γνώση που μπορεί να αντλήσουμε από αυτή την ψηφιακή πληροφορία προσφέρει ικανότητα για παροχή διάφορων υπηρεσιών που διαφορετικά δεν θα μπορούσαμε. Βέβαια η ικανότητα αυτή κατακτάται μέσω της εξόρυξης γνώσης, ενός τομέα που προσπαθεί να δημιουργήσει διαδικασίες έτσι ώστε η άντληση της γνώσης αυτής να γίνει αυτόματα.

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

Παραπομπές

  1. 1,0 1,1 1,2 1,3 Μιχάλης Βαζιργιάννης, Μαρία Χαλκίδη, Εξόρυξη Γνώσης από Βάσεις Δεδομένων και τον Παγκόσμιο Ιστό, Εκδ. Gutenberg.
  2. Κουρής Ν. Γιάννης.,(2006).Εφαρμογή Τεχνικών Data Mining σε Συστήματα Ηλεκτρονικού Εμπορίου.Ανακτήθηκε στις 19 Ιουλίου από http://nemertes.lis.upatras.gr/jspui/bitstream/10889/1610/1/Nimertis_Kouris.pdf
  3. k-medoids
  4. Hubert, Lawrence; Schultz, James (1976-11-01). «Quadratic Assignment as a General Data Analysis Strategy» (στα αγγλικά). British Journal of Mathematical and Statistical Psychology 29 (2): 190–241. doi:10.1111/j.2044-8317.1976.tb00714.x. ISSN 2044-8317. http://onlinelibrary.wiley.com/doi/10.1111/j.2044-8317.1976.tb00714.x/abstract. 

Βιβλιογραφία

  • Αναγνώριση Προτύπων , S.Theodoridis,K.Koutroumbas, Εκδόσεις Π.Χ.ΠΑΣΧΑΛΙΔΗΣ,ISBN:978-960-489-145-0.
  • Εξόρυξη Γνώσης Από Βάσεις Δεδομένων Και Τον Παγκόσμιο Ιστό , Μ.Χαλκίδη , Μ.Βαζιργιάννης , Εκδόσεις ΤΥΠΩΘΗΤΩ,ISBN:978-960-402-116-8.
  • An Introduction to Information Retrieval , Christopher D. Manning ,Prabhakar Raghavan,Hinrich Schütz ,Online edition (c)2009 Cambridge University Press ,ISBN:052-186-571-9