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

μ
Αρχικά έχουμε k-ομάδες, με την κάθε ομάδα ''να αντιπροσωπεύεται από το μέσο διάνυσμα''. Ο αλγόριθμος λειτουργεί σε δύο βήματα:
# Κατά τη φάση της διαμέρισης γίνεται προσπέλαση των διανυσμάτων και για κάθε διάνυσμα βρίσκουμε την απόστασή του από (ανομοιότητα με) τις υπάρχουσες ομάδες. Η απόσταση μεταξύ ενός διανύσματος και μίας ομάδας είναι η [[Ευκλείδεια μετρική|ευκλείδεια απόσταση]] από το μέσο (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> για i=1,2...κ. Στον υπολογισμό του νέου m<sub>i</sub> συνεισφέρει το αντίστοιχο σύνολο διανυσμάτων που υπολογίστηκε κατά το παραπάνω βήμα.
 
Ο αλγόριθμος ολοκληρώνεται ''όταν οι ενημερώσεις που γίνονται σε κάθε m<sub>i</sub> είναι αμελητέες''. Σημαντικό σημείο του αλγορίθμου είναι η αρχικοποίηση των k-διανυσμάτων. Αν αντί για το μέσο διάνυσμα χρησιμοποιήσουμε ένα διάνυσμα x<sub>j</sub>, με x<sub>j</sub> ∈ X, τότε έχουμε τον αλγόριθμο k-εσωτερικών αντιπροσώπων.<ref>[http://en.wikipedia.org/wiki/K-medoids k-medoids]</ref> Η χρονική πολυπλοκότητα του αλγόριθμου είναι Ο(Νkq) όπου q ο αριθμός των επαναλήψεων που πρέπει να εκτελέσει ο αλγόριθμος για να τερματίσει.
 
56

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