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

μ
 
==Εγκυρότητα==
Η εγκυρότητα συσταδοποίησης είναι η διαδικασία εκείνη κατά την οποία εκτιμάται ότι η έξοδος του αλγόριθμου είναι ουσιαστικά ένα σύνολο από ομάδες διανυσμάτων, οι οποίες πληρούν τον ορισμό της συσταδοποίησης καθώς και ορισμένα επιπλέον κριτήρια. Γενικά ο έλεγχος μπορεί να επιτευχθεί με τρεις διαφορετικούς τρόπους ανάλογα με τα κριτήρια που χρησιμοποιούμε:
*ο#'''Εσωτερικά κριτήρια'''. Ο έλεγχος ενός αλγορίθμου Α ,επιτυγχάνεται εμπεριέχονταςλαμβάνοντας υπ' όψη μόνο τα δεδομένα εισόδου του , αυτά που χρησιμοποιήθηκαν για να επιτευχθεί η συσταδοποίηση. Για παράδειγμα, αν ο Α αποτελεί έναν ιεραρχικό αλγόριθμο, τότε η εκτίμηση του συγκεκριμένου αλγορίθμου μπορεί να γίνει αποκλειστικά από τον πίνακα εγγύτητας. Ένας τέτοιος δείκτης είναι ο τροποποιημένος στατιστικός δείκτης Γ του 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, κάτι που συνεπάγεται την '' ορθότητα'' του αλγορίθμου.
#εσωτερικά
*#'''Εξωτερικά Στηκριτήρια'''. δεύτερηΣε αυτή την περίπτωση '' υπολογίζεται μία δομή των διανυσμάτων Μ εξωτερικά από τον χρήστη''. Στη συνέχεια απλά γίνεται σύγκριση της συσταδοποίησης Μ={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
#και σχετικά κριτήρια.
*#* TN = το πλήθος των διανυσμάτων που ανήκουν σε διαφορετική ομάδα, κατά τηντη συσταδοποίηση C και P
 
*#* FN = το πλήθος των διανυσμάτων που ανήκουν σε διαφορετική ομάδα κατά τηντη συσταδοποίηση C , ενώ ανήκουν στηστην ίδια ομάδα κατά την P
*ο έλεγχος ενός αλγορίθμου Α ,επιτυγχάνεται εμπεριέχοντας μόνο τα δεδομένα εισόδου του ,αυτά που χρησιμοποιήθηκαν για να επιτευχθεί η συσταδοποίηση. Για παράδειγμα αν ο Α αποτελεί έναν ιεραρχικό αλγόριθμο τότε η εκτίμηση του συγκεκριμένου αλγορίθμου μπορεί να γίνει αποκλειστικά από τον πίνακα εγγύτητας. Ένας τέτοιος δείκτης είναι ο τροποποιημένος στατιστικός δείκτης Γ του 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 κάτι που συνεπάγεται την '' ορθότητα'' του αλγορίθμου.
#* FP = το πλήθος των διανυσμάτων που ανήκουν στην ίδια ομάδα κατά τη συσταδοποίηση C, ενώ ανήκουν σε διαφορετικές ομάδες κατά την P Ένας απλός δείκτης είναι o RI (Rand Index) ''ο οποίος μετρά το ποσοστό της σωστής συσταδοποίησης''. <math>RI=\frac{TP+TN}{TP+TN+FN+FP}</math>. Υπάρχουν διάφοροι άλλοι δείκτες, οι περισσότεροι από τους οποίους βασίζονται στους παραπάνω τέσσερις πληθάριθμους συνόλων.
* Στη δεύτερη περίπτωση '' υπολογίζεται μία δομή των διανυσμάτων Μ εξωτερικά από τον χρήστη''. Στη συνέχεια απλά γίνεται σύγκριση της συσταδοποίησης Μ={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>} . Για παράδειγμα έστω
*#'''Σχετικά κριτήρια'''. Τέλος υπάρχει και η διαδικασία ελέγχου που βασίζεται σε σχετικά κριτήρια. Στη συγκεκριμένη περίπτωση γίνονται αλλαγές των παραμέτρων εισόδου του αλγορίθμου και εκτιμάται η νέα συσταδοποίηση C'. Αυτό μπορεί να γίνει επαναληπτικά έτσι ώστε να καταλήξουμε στην καλύτερη δυνατή συσταδοποίηση. Οι αλλαγές που μπορούν να γίνουν είναι) (<small> υποθέτουμε ότι τα παρακάτω είναι παράμετροι εισόδου</small>): ''η διαφορετική διάταξη των διανυσμάτων, διαφορετικό πλήθος ομάδων συσταδοποίησης, διαφορετικό διάστημα πλήθοςπλήθους συσταδοποιήσεων [m<sub>min</sub>, m<sub>max</sub>], διαφορετικοί αρχικοί αντιπρόσωποι (για παράδειγμα τα αρχικά μέσα διανύσματα που χρησιμοποιεί ο k-means..), κλπ.''
**TP= το πλήθος των διανυσμάτων που ανήκουν σε ίδια ομάδα, κατά την συσταδοποίηση C και P
** TN= το πλήθος των διανυσμάτων που ανήκουν σε διαφορετική ομάδα, κατά την συσταδοποίηση C και P
** FN= το πλήθος των διανυσμάτων που ανήκουν σε διαφορετική ομάδα κατά την συσταδοποίηση C ενώ ανήκουν στη ίδια ομάδα κατά την P
** FP= το πλήθος των διανυσμάτων που ανήκουν στην ίδια ομάδα κατά συσταδοποίησης C ενώ ανήκουν σε διαφορετικές ομάδες κατά την P
Ένας απλός δείκτης είναι o RI(Rand Index) ''ο οποίος μετρά το ποσοστό της σωστής συσταδοποίησης''.<math>RI=\frac{TP+TN}{TP+TN+FN+FP}</math>.
Υπάρχουν διάφοροι άλλοι δείκτες ,οι περισσότεροι από αυτούς βασίζονται στους παραπάνω τέσσερις πληθάριθμους συνόλων.
*Τέλος υπάρχει και η διαδικασία ελέγχου που βασίζεται σε σχετικά κριτήρια. Στη συγκεκριμένη περίπτωση γίνονται αλλαγές των παραμέτρων εισόδου του αλγορίθμου και εκτιμάται η νέα συσταδοποίηση C'. Αυτό μπορεί να γίνει επαναληπτικά έτσι ώστε να καταλήξουμε στην καλύτερη δυνατή συσταδοποίηση. Οι αλλαγές που μπορούν να γίνουν είναι)(<small> υποθέτουμε ότι τα παρακάτω είναι παράμετροι εισόδου</small>) ''η διαφορετική διάταξη των διανυσμάτων, διαφορετικό πλήθος ομάδων συσταδοποίησης, διαφορετικό διάστημα πλήθος συσταδοποιήσεων [m<sub>min</sub>,m<sub>max</sub>], διαφορετικοί αρχικοί αντιπρόσωποι (για παράδειγμα τα αρχικά μέσα διανύσματα που χρησιμοποιεί ο k-means...''
 
== Εφαρμογές ==
56

επεξεργασίες