Συσταδοποίηση: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ →Εγκυρότητα: Προσθήκη παραπομπής για τον δείκτη Γ του Hubert. |
αφαιρεση παραπ σε ΒΠ |
||
Γραμμή 36:
# Κατά τη φάση της διαμέρισης γίνεται προσπέλαση των διανυσμάτων και για κάθε διάνυσμα βρίσκουμε την απόστασή του από (ανομοιότητα με) τις υπάρχουσες ομάδες. Η απόσταση μεταξύ ενός διανύσματος και μίας ομάδας είναι η [[Ευκλείδεια μετρική|ευκλείδεια απόσταση]] από το μέσο (m<sub>p</sub>) διάνυσμα. Για i=1,2...N υπολογίζουμε τις αποστάσεις ως εξής: <math>d(x_i,C_j)=\|x_i - m_j\|^2 </math> <br /> ∀ j=1,2,3...k. Προσδιορίζονται Ν αριθμοί q, έτσι ώστε να ισχύει: d(x<sub>i</sub>,C<sub>q</sub>) ≤ d(x<sub>i</sub>,C<sub>j</sub>) ∀ j=1,2,3...k. Κατά την ολοκλήρωση αυτού του βήματος σχηματίζονται k-σύνολα διανυσμάτων, ένα σύνολο για κάθε ομάδα.
# Κατά τη φάση της ενημέρωσης, γίνονται οι κατάλληλες τροποποιήσεις στα μέσα διανύσματα, δηλαδή ∀ j=1,2...m: υπολογίζονται ξανά τα μέσα διανύσματα m<sub>i</sub> για i=1,2...κ. Στον υπολογισμό του νέου m<sub>i</sub> συνεισφέρει το αντίστοιχο σύνολο διανυσμάτων που υπολογίστηκε κατά το παραπάνω βήμα.
Ο αλγόριθμος ολοκληρώνεται ''όταν οι ενημερώσεις που γίνονται σε κάθε m<sub>i</sub> είναι αμελητέες''. Σημαντικό σημείο του αλγορίθμου είναι η αρχικοποίηση των k-διανυσμάτων. Αν αντί για το μέσο διάνυσμα χρησιμοποιήσουμε ένα διάνυσμα x<sub>j</sub>, με x<sub>j</sub> ∈ X, τότε έχουμε τον αλγόριθμο k-εσωτερικών αντιπροσώπων
=== Ιεραρχικοί ===
Γραμμή 52 ⟶ 53 :
d(C<sub>q</sub>,C<sub>s</sub>) = min(d(C<sub>i</sub>,C<sub>q</sub>) για a=1, c=1, e=-1/2, [[αλγόριθμος απλού δεσμού]] <br />
d(C<sub>i</sub>,C<sub>i</sub>) = max(d(C<sub>k</sub>,C<sub>h</sub>) για a=1 ,c=1, e=1/2, [[αλγόριθμος πλήρους δεσμού]] <br />. Μπορούμε να προσαρμόσουμε τη μορφή του δενδρογράμματος ενός αλγόριθμου ,σε μία από τις δύο παραπάνω μορφές με κατάλληλη επιλογή τιμών των συντελεστών. <br /><small> Όλα αυτά είναι αποτελέσματα χρήσης του πίνακα ανομοιότητας , μία μήτρα το οποίο το a<sub>ij</sub> στοιχείο δηλώνει την ανομοιότητα των i,j διανυσμάτων. Μπορούν να μεταφερθούν εύκολα από την θεωρία πινάκων στη [[θεωρία γράφων]] .Γενικά υπάρχει ολόκληρη κατηγορία αλγορίθμων που βασίζονται στους γράφους, κατευθυνόμενους ή μη ).</small>
H χρονική πολυπλοκότητα των συσσωρευτικών αλγόριθμων είναι Ο(n<sup>3</sup>).H πολυπλοκότητα αυτή μπορεί να κατέβει κοντά στο Ο(n<sup>2</sup>).Για παράδειγμα ο
*Οι διαιρετικοί αλγόριθμοι ακολουθούν αντίστροφη διαδικασία. Ξεκινούν από μία ομάδα η οποία εμπεριέχει όλα τα διανύσματα και σε κάθε βήμα μία ομάδα διασπάται σε δύο μέχρι να καταλήξουμε σε Ν ομάδες. Η πολυπλοκότητα τους είναι μεγαλύτερη από τους συσσωρευτικούς αφού η διάσπαση μίας ομάδας σε δύο μπορεί να γίνει κατά 2<sup>N-1</sup>-1 τρόπους και η επιλογή της βέλτιστης διάσπασης πρακτικά είναι αδύνατη ακόμα και για μικρό Ν. Στην πράξη αυτό που γίνεται ότι ο αλγόριθμος σε κάθε βήμα διασπά μία ομάδα αλλά όχι κατά βέλτιστο τρόπο.
| |||