Συσταδοποίηση: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Vrlab (συζήτηση | συνεισφορές) προσθήκη σήμανσης για εμβόλιμες παραπομπές |
Vrlab (συζήτηση | συνεισφορές) προσθήκη σήμανσης για εμβόλιμες παραπομπές |
||
Γραμμή 1:
{{συγχώνευση|
{{χωρίς παραπομπές|16|04|2012}}
'''Ομαδοποίηση''' είναι η διαδικασία εκείνη κατά την οποία ένα σύνολο από «αντικείμενα», διαχωρίζονται σε ένα σύνολο από ''λογικές ομάδες''. Η καταχώρηση αντικειμένων σε ίδια ομάδα μεταφράζεται ως ''ομοιότητα'' των αντικειμένων αυτών και αντίστροφα (αντικείμενα που ανήκουν σε διαφορετικές ομάδες είναι ανόμοια). Η ομοιότητα ή μη, μεταξύ των αντικείμενων, ουσιαστικά εξαρτάται από το συγκεκριμένο πρόβλημα και τη μορφή των «αντικειμένων». Στη βιβλιογραφία συναντάται ως συσταδοποίηση και μη επιβλεπόμενη μάθηση. Τα αντικείμενα μπορούν να αναφερθούν και αυτά με διαφορετικούς όρους: πρότυπα, [[ διάνυσμα |διανύσματα]] (παρακάτω θα αναφέρονται ως διανύσματα).
==Ορισμός==
Δοθέντος ενός συνόλου διανυσμάτων X={x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>... x<sub>n</sub>} ζητούνται m σύνολα-ομάδες C<sub>1</sub>,C<sub>2</sub>...C<sub>m</sub>,με m<<n έτσι ώστε :<br />
C<sub>i </sub><math> \neq \oslash \forall </math> <small>i =1,2,3...m</small>
και οι m ομάδες αποτελούν [[διαμερισμός συνόλου | διαμέριση του συνόλου]] Χ. <br />
Ο ορισμός αυτός αναφέρεται στην αυστηρή ομαδοποίηση διότι κάθε διάνυσμα ανήκει σε μία και μόνο ομάδα. Εναλλακτικά μπορεί να οριστεί η ασαφής ομαδοποίηση .Κάνοντας χρήση των [[ασαφή σύνολα|ασαφών συνόλων]] μπορούμε να ορίσουμε m [[συνάρτηση |συναρτήσεις]] συμμετοχής
u<sub>j</sub>:X→[0,1] για j=1,2,...m. Οι συναρτήσεις u<math>(\cdot)</math> ''ποσοτικοποιούν την βεβαιότητα που έχουμε για το αν κάποιο διάνυσμα i ανήκει στην ομάδα j''.
Η διαδικασία της ομαδοποίησης μπορεί να αναλυθεί σε τρία βασικά χαρακτηριστικά:<br />
(<small>Προηγείται η διαδικασία σχηματισμού διανυσμάτων. Κατά την διαδικασία αυτή επιλέγονται τα κ –χαρακτηριστικά ενός διανύσματος με τέτοιο τρόπο ώστε να καθιστά τη διαδικασία της ομαδοποίησης εύκολη και δυνατή. Δηλαδή τα διανύσματα σχηματίζονται με σκοπό να μεταφέρουν την μέγιστη δυνατή πληροφορία, να χρησιμοποιούν την ελάχιστη δυνατή πληροφορία αναπαράστασης -κ ελάχιστο δυνατό ακέραιο και η αναπαράσταση τους να τα καθιστά εύκολα στην επεξεργασία.</small>)
* Εύρεση μίας συνάρτηση εγγύτητας η οποία ποσοτικοποιεί τους όρους όμοια και ανόμοια μεταξύ των διανυσμάτων. Συνήθως η συνάρτηση αυτή αποτελεί μετρική.
* Εύρεση ενός κριτηρίου με βάση το οποίο τα διάφορα αντικείμενα θα καταχωρούνται σε διάφορες ομάδες. ''Το κριτήριο αυτό αποτελεί οδηγό για τον αλγόριθμο ομαδοποίησης.'' Ένα απλό κριτήριο, για δεδομένο μέτρο ανομοιότητας d(·) μεταξύ διανύσματος και συνόλου διανυσμάτων, ένα διάνυσμα x<sub>i</sub> θα καταχωρείται στην ομάδα c<sub>j</sub> αν ισχύει: d(x<sub>i</sub>,c<sub>j</sub>)≤ d(x<sub>i</sub>,c<sub>q</sub> για κάθε άλλη ομάδα q.
* Τέλος, επιλογή ενός κατάλληλου αλγόριθμου ομαδοποίησης ο οποίος θα εμπεριέχει και θα κάνει χρήση των δύο παραπάνω εννοιών και θα έχει ως έξοδο το ζητούμενο: ένα σύνολο m ομάδων (έπεται η διαδικασία ελέγχου).
Οι συναρτήσεις εγγύτητας d:X×X <math>\rarr</math> R στην απλή τους μορφή μπορεί να είναι απλά μέτρα ανομοιότητας
∃ d<sub>0</sub> ∈ R :<br />
d(x,x)=d<sub>0</sub> ∀ x ∈ X,<br />
d(x,y)≥d<sub>0</sub>∀ x,y ∈ X<br />
d(x,y)=d(y,x) ∀ x,y ∈ X ή να αποτελούν [[μετρική]] ανομοιότητας (<small> μετατροπή σε ομοιότητα με κατάλληλες αλλαγές </small>).Σε κάθε περίπτωση η επιλογή της συνάρτησης αυτής εξαρτάται από την μορφή των διανυσμάτων, ''αν τα χαρακτηριστικά των διανυσμάτων ανήκουν σε συνεχή ή διακριτό χώρο, αν είναι αριθμητικά ή όχι…'' και υπάρχουν διαφορές επιλογές ([[απόσταση Milikowski]] η οποία εμπεριέχει και την [[ευκλείδεια μετρική| ευκλείδεια απόσταση]], [[απόσταση Hamming]]...). Επιπλέον μπορούμε να ορίσουμε και ανομοιότητα μεταξύ δύο συνόλων διανυσμάτων ή μεταξύ συνόλου διανυσμάτων και διανύσματος. Και εδώ όμως η <i> απόσταση</i> μεταξύ συνόλων <i> μετριέται με αποστάσεις </i> μεταξύ διανυσμάτων. Για κάθε σύνολο διανυσμάτων-ομάδα C, επιλέγουμε ένα διάνυσμα αντιπρόσωπο π.χ <b>το διάνυσμα ελάχιστης συνολικής απόστασης m<sub>c</sub> για το οποίο ισχύει </sub></b><br />
<math>\sum_{y \in C} d(m_c,y)\le \sum_{y \in X}{d(z,y)}</math> ∀ z ∈ C ή <b>το μέσο διάνυσμα m<sub>p</sub></b> το οποίο ορίζεται : <math>m_p =\frac {1}{n_c} \sum_{y \in C }</math> όπου n<sub>c</sub> ο [[πληθάριθμος]] της ομάδας C
είτε ένα ''σύνολο διανυσμάτων που το αντιπροσωπεύει με το σύνολο αυτό να έχει μία συγκεκριμένη μορφή στο χώρο π.χ ένα [[υπερεπίπεδο]], μία [[υπερσφαίρα]]''.
==Αλγόριθμοι Ομαδοποίησης==
Υπάρχει ένα μεγάλο πλήθος από αλγόριθμους ομαδοποίησης που έχουν προταθεί και ο καθένας τους βασίζεται σε διαφορετική φιλοσοφία. Σχεδόν όλοι τους δέχονται ένα σύνολο παραμέτρων που μπορεί να είναι το πλήθος των ομάδων, διανύσματα αρχικοποίησης που απαιτούνται από τον αλγόριθμο κάποιες υποθέσεις για την πυκνότητα των διανυσμάτων στο χώρο και άλλες διάφορες παραμέτρους. Διαφοροποιώντας αυτές τις παραμέτρους προκύπτει ένα σύνολο από αλγόριθμους σε κάθε βασική κατηγορία.
====K-means ====
Ο συγκεκριμένος αλγόριθμους είναι από τους πιο πολυεφαρμοσμένους και είναι η ρίζα για πολλούς άλλους. Ανήκει στην κατηγορία της επίπεδης ομαδοποίησης διότι παράγει ένα σύνολο ομαδοποιήσεων χωρίς να έχουν καμία ιδιαίτερη δομή-σχέση μεταξύ τους. Ο αλγόριθμος έχει ως στόχο την βελτιστοποιήση μίας συνάρτησης – της συνάρτησης κόστους.
Αρχικά έχουμε 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> είναι αμελητέες''. Σημαντικό σημείο του αλγορίθμου είναι η αρχικοποίηση των k-διανυσμάτων. Αν αντί για το μέσο διάνυσμα ένα διάνυσμα x<sub>j</sub>, με x<sub>j</sub> ∈ X, τότε έχουμε τον αλγόριθμο [[κ-εσωτερικών αντιπροσώπων]]<ref>[http://en.wikipedia.org/wiki/K-medoids k-medoids]</ref>. Η χρονική πολυπλοκότητα του αλγόριθμου είναι Ο(Νkq) όπου q ο αριθμός των επαναλήψεων που πρέπει να τρέξει ο αλγόριθμος για να τερματίσει.
====Ιεραρχικοί ====
Οι ιεραρχικοί αλγόριθμοι ομαδοποίησης παράγουν μια ιεραρχία εμφωλιασμένων ομαδοποιήσεων. Δύο ομαδοποιήσεις λέγονται εμφωλιασμένες <br /><math>E_p \sqsubset E_q</math> όταν ισχύει :∀ x<sub>i</sub>,x<sub>j</sub>,∈ C<sub>k</sub>,κατά την ομαδοποίηση Ε<sub>p</sub> → x<sub>i</sub>,x<sub>j</sub> ∈ C<sub>k'</sub> κατά την ομαδοποίηση Ε<sub>q</sub><br />
Οι αλγόριθμοι αυτοί διαχωρίζονται σε δύο υποκατηγορίες
::*στους συσσωρευτικούς
::* και στους διαιρετικούς.
*Οι συσσωρευτικοί ξεκινάνε με n ομάδες, Ε<sub>0</sub>= {C<sub>i</sub> = {x<sub>i</sub>}}, ∀ i=1,2,...,n. Σε κάθε βήμα του αλγορίθμου b, το πλήθος των ομάδων μειώνεται κατά ένα συγχωνεύοντας δύο σε μία ομάδα έως φτάσουμε σε μία μοναδική που να εμπεριέχει όλα τα διανύσματα. Η εξέλιξη του αλγορίθμου μπορεί να αναπαρασταθεί γραφικά με ένα [[δενδρόγραμμα]] ανομοιότητας. Το δενδρόγραμμα περιέχει n-1 επίπεδα με το κάθε επίπεδο να αποτελεί ένα βήμα του αλγορίθμου. Επιπλέον περιλαμβάνει και την ποσότητα ανομοιότητας μεταξύ των ομάδων που συγχωνεύονται. <br />
Γενικά στο βήμα b, συγχωνεύονται οι ομάδες οι οποίες είναι το λιγότερο ανόμοιες : <br />
d(C<sub>i</sub>,C<sub>i</sub>)=min(d(C<sub>k</sub>,C<sub>h</sub>) ,∀ C<sub>k</sub>,C<sub>h</sub> ∈ Ε<sub>b-1</sub> ομαδοποίηση και k≠h. Οι αλλαγές που γίνονται είναι :<br />
C<sub>q</sub> =C<sub>i</sub> ∪ C<sub>j</sub>,E<sub>b</sub>=(E<sub>b-1</sub>-{C<sub>j</sub>,C<sub>j</sub>}) ∪ {C<sub>q</sub>} ,<small>όπου d συνάρτηση ανομοιότητας μεταξύ συνόλων διανυσμάτων.</small><br />
Μετά την συγχώνευση στο επίπεδο b+1, η ανομοιότητα μεταξύ μίας ομάδας C<sub>s</sub> και της C<sub>q</sub> υπολογίζεται ως <br />d(C<sub>q</sub>,C<sub>s</sub>)=f(d(C<sub>i</sub>,C<sub>s</sub>),d(C<sub>j</sub>,C<sub>s</sub>),d(C<sub>i</sub>,C<sub>j</sub>).Γενικά η f μπορεί να είναι οποιαδήποτε αλλά μία απλή <i> μορφή </i> είναι:<br />
d(C<sub>q</sub>,C<sub>s</sub>)=ad(C<sub>i</sub>,C<sub>s</sub>)+cd(C<sub>j</sub>,C<sub>s</sub>)+wd(C<sub>i</sub>,C<sub>j</sub>)+ e|d(C<sub>i</sub>,C<sub>s</sub>)-d(C<sub>j</sub>,C<sub>s</sub>)|
Για την παραπάνω μορφή της f,<i> επιλέγοντας διαφορετικούς συντελεστές καταλήγουμε σε διαφορετικά μέτρα ανομοιότητας κάθε φορά με αποτέλεσμα η εξέλιξη του αλγορίθμου να διαφοροποιείται(<small> άρα και η έξοδος του αν ζητήσουμε μία ομαδοποίηση διαφορετική της τελευταίας και της πρώτης</small>)</i>.Τα <b> δύο άκρα</b> όταν η συνάρτηση ενημέρωσης είναι η παραπάνω είναι τα εξής : <br / >
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>).Για παράδειγμα ο [http://en.wikipedia.org/wiki/CURE_data_clustering_algorithm CURE] έχει πολυπλοκότητα Ο(n<sup>2</sup>lgn).
*Οι διαιρετικοί αλγόριθμοι ακολουθούν αντίστροφη διαδικασία. Ξεκινάνε από μία ομάδα η οποία εμπεριέχει όλα τα διανύσματα και σε κάθε βήμα μία ομάδα διασπάται σε δύο έως καταλήξουμε σε Ν ομάδες. Η πολυπλοκότητα τους είναι μεγαλύτερη από τους συσσωρευτικούς αφού η διάσπαση μίας ομάδας σε δύο μπορεί να γίνει κατά 2<sup>N-1</sup>-1 τρόπους και η επιλογή της βέλτιστης διάσπασης πρακτικά είναι αδύνατη ακόμα και για μικρό Ν.Στη πράξη αυτό που γίνεται ότι ο αλγόριθμος σε κάθε βήμα διασπά μία ομάδα αλλά όχι κατά βέλτιστο τρόπο.
<br />
====Ανταγωνιστικής Μάθησης ====
Οι συγκεκριμένοι αλγόριθμοι χρησιμοποιούν ένα σύνολο αντιπροσώπων w<sub>i</sub> για i=1,2…m. Αυτά είναι μία από τις παραμέτρους εισόδου του αλγόριθμου όπως και το μέγιστο πλήθος ομάδων ,το κριτήριο τερματισμού του αλγόριθμου… Η λογική του αλγόριθμου είναι η εξής,∀ i=1,2…N
*<i>τα διανύσματα εμφανίζονται ένα , ένα και οι αντιπρόσωποι w<sub>j</sub> για j=1,2…m ανταγωνίζονται για την διεκδίκηση τους. Αφού βρεθεί ο νικητής ,έστω w<sub>q</sub> (για το διάνυσμα b,κατά το βήμα b-τα διανύσματα εξετάζονται κατά διάταξη: x<sub>1</sub>,x<sub>2</sub>...x<sub>N</sub>.Η σειρά εξέτασης των διανυσμάτων είναι και αυτή μία παράμετρος που πρέπει να προσδιοριστεί) ,τότε «αυτός» μετακινείται προς το x<sub>b</sub> ενώ ή ηττημένοι κινούνται ελάχιστα –αν κινηθούν. Βέβαια ακόμα και η κίνηση του νικητή θα μπορούσε να γίνει υπό συνθήκες .Για παράδειγμα για δεδομένο κατώφλι ανομοιότητας Θ, μέγιστο πλήθος ομάδων μ και μέτρο ανομοιότητας d(·) ,αν ισχύει
**d(x<sub>b</sub>,w<sub>q</sub>)>Θ ∧(m<small>(οι υπάρχουσες ομάδες)</small> < μ ) τότε δημιουργείται καινούργια ομάδα με μοναδικό στοιχείο το διάνυσμα x<sub>b</sub> <b>αλλιώς γίνονται οι κατάλληλες κινήσεις των αντιπροσώπων </b><i>.<math>w_j(b)= \begin{cases}{w_j(b-1)+l\cdot h(x_b,w_j(b-1)) \gamma\iota\alpha j = q} \\ {w_j(b-1)+l'\cdot h(x_b,w_j(b-1)) \gamma\iota\alpha j \ne q}\end{cases}</math></i>
Οι παράμετροι <math>\mbox{ l, l}'</math> είναι οι ρυθμοί μάθησης των νικητών και των ηττημένων ενώ η h(·) είναι μια κατάλληλη ορισμένοι συνάρτηση .Οι ρυθμοί μάθησης μεταξύ των ηττημένων μπορούνε να είναι διαφορετικοί.</i>
Και πάλι για διαφορετικές παραμέτρους(<small>τιμές παραμέτρων</small>) προκύπτουν διαφορετικοί αλγόριθμοι .Για παράδειγμα το πλήθος των ομάδων θα μπορούσε να είναι σταθερό και να μην υπάρχουν οι -υπό συνθήκη- κινήσεις .<br />
==Εγκυρότητα==
Η εγκυρότητα ομαδοποίησης είναι η διαδικασία εκείνη κατά την οποία εκτιμάται ότι η έξοδος του αλγόριθμου είναι ουσιαστικά ένα σύνολο από ομάδες διανυσμάτων, οι οποίες πληρούν τον ορισμό της ομαδοποίησης καθώς και ορισμένα επιπλέον κριτήρια. Γενικά ο έλεγχος μπορεί να επιτευχθεί με τρεις διαφορετικούς τρόπους ανάλογα με τα κριτήρια που χρησιμοποιούμε:
#εσωτερικά
#εξωτερικά
#και σχετικά κριτήρια.
*ο έλεγχος ενός αλγορίθμου Α ,επιτυγχάνεται εμπεριέχοντας μόνο τα δεδομένα εισόδου του ,αυτά που χρησιμοποιήθηκαν για να επιτευχθεί η ομαδοποίηση. Για παράδειγμα αν ο Α αποτελεί έναν ιεραρχικό αλγόριθμο τότε η εκτίμηση του συγκεκριμένου αλγορίθμου μπορεί να γίνει αποκλειστικά από τον πίνακα εγγύτητας. Ένας τέτοιος δείκτης είναι ο τροποποιημένος στατιστικός δείκτης Γ του 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 κάτι που συνεπάγεται την <i> ορθότητα</i> του αλγορίθμου.
* Στη δεύτερη περίπτωση <i> υπολογίζεται μία δομή των διανυσμάτων Μ εξωτερικά από τον χρήστη</i>. Στη συνέχεια απλά γίνεται σύγκριση της ομαδοποίησης Μ={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
** FP= το πλήθος των διανυσμάτων που ανήκουν στην ίδια ομάδα κατά ομαδοποίησης C ενώ ανήκουν σε διαφορετικές ομάδες κατά την P
Ένας απλός δείκτης είναι o RI(Rand Index) <i>ο οποίος μετρά το ποσοστό της σωστής ομαδοποίησης</i>.<math>RI=\frac{TP+TN}{TP+TN+FN+FP}</math>.
Υπάρχουν διάφοροι άλλοι δείκτες ,οι περισσότεροι από αυτούς βασίζονται στους παραπάνω τέσσερις πληθάριθμους συνόλων.
*Τέλος υπάρχει και η διαδικασία ελέγχου που βασίζεται σε σχετικά κριτήρια. Στη συγκεκριμένη περίπτωση γίνονται αλλαγές των παραμέτρων εισόδου του αλγορίθμου και εκτιμάται η νέα ομαδοποίηση C'. Αυτό μπορεί να γίνει επαναληπτικά έτσι ώστε να καταλήξουμε στην καλύτερη δυνατή ομαδοποίηση. Οι αλλαγές που μπορούν να γίνουν είναι)(<small> υποθέτουμε ότι τα παρακάτω είναι παράμετροι εισόδου</small>) <i>η διαφορετική διάταξη των διανυσμάτων, διαφορετικό πλήθος ομάδων ομαδοποίησης, διαφορετικό διάστημα πλήθος ομαδοποιήσεων [m<sub>min</sub>,m<sub>max</sub>],διαφορετικοί αρχικοί αντιπρόσωποι(για παράδειγμα τα αρχικά μέσα διανύσματα που χρησιμοποιεί ο k-means...</i>
== Εφαρμογές ==
Η ομαδοποίηση ως έννοια σημαντική όχι μόνο σε πολλές επιστήμες όπως η κοινωνιολογία, η βιολογία και η στατιστική, αλλά και σε πολλούς τομείς της πληροφορικής όπως η [[Αναγνώριση προτύπων|αναγνώριση προτύπων]], η [[εξόρυξη δεδομένων|εξόρυξη γνώσης]], η [[ανάκτηση δεδομένων]], η [[τεχνητή νοημοσύνη]] και η [[μηχανική μάθηση]]. Όλοι αυτοί οι τομείς ουσιαστικά αναφέρονται και ορίζουν το ίδιο πρόβλημα με ''διαφορετική γλώσσα ορισμού''. Τα τελευταία χρόνια οι τομείς αυτοί αποκτούν όλο και περισσότερο ενδιαφέρον καθιστώντας έτσι την ομαδοποίηση αντικείμενο εντατικής έρευνας.
Για παράδειγμα στην ανάκτηση δεδομένων πέρα από το αποθηκευτικό κέρδος που μπορεί να αποφέρει η ομαδοποίηση η έννοια εφαρμόζεται ξεκάθαρα από μηχανές αναζήτησης[http://search.yippy.com/ yippy.com]. Εδώ ζητάτε να ομαδοποιηθούν τα έγγραφα απάντησης D ενός ερωτήματος q του χρήστη. Οι μηχανές αναζήτησης δίνουν και μία οπτικοποίηση της ομαδοποίησης, με την έννοια ότι τα έγγραφα απάντησης D μπορεί να αναπαρασταθούν γραφικά.
Σε ένα σύστημα αναγνώρισης προτύπων η ομαδοποίηση μαζί με την κατηγοριοποίηση αποτελούν της δύο βασικές διαδικασίες που πρέπει να ενσωματώνει ένα τέτοιο σύστημα. Το σύστημα αυτό μπορεί να είναι ένα σύστημα αυθεντικοποίησης-ταυτοποίησης μέσω ομιλίας ([[αναγνώριση ομιλητή]]), ένα σύστημα αναγνώρισης εικόνων.
Το πλήθος των δεδομένων που κυκλοφορούν στο διαδίκτυο είναι τεράστιο. Η γνώση που μπορεί να αντλήσουμε από αυτή την ψηφιακή πληροφορία προσφέρει ικανότητα για παροχή διάφορων υπηρεσιών που διαφορετικά δεν θα μπορούσαμε. Βέβαια η ικανότητα αυτή κατακτάται μέσω της εξόρυξης γνώσης, ενός τομέα που προσπαθεί να δημιουργήσει διαδικασίες έτσι ώστε η άντληση της γνώσης αυτής να γίνει αυτόματα.
== Παραπομπές ==
{{reflist}}
== Βιβλιογραφία ==
* '' Αναγνώριση Προτύπων '' , S.Theodoridis,K.Koutroumbas, Εκδόσεις Π.Χ.ΠΑΣΧΑΛΙΔΗΣ,[[ISBN]]:[http://www.inbooks.gr/ViewShopProduct.aspx?ProductId=280111&Name=Αναγνώριση 978-960-489-145-0].
* '' Εξόρυξη Γνώσης Από Βάσεις Δεδομένων Και Τον Παγκόσμιο Ιστό '' , Μ.Χαλκίδη , Μ.Βαζιργιάννης , Εκδόσεις ΤΥΠΩΘΗΤΩ,[[ISBN]]:[http://www.dardanosnet.gr/book_details.php?id=1118 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]]:[http://nlp.stanford.edu/IR-book/information-retrieval-book.html 052-186-571-9]
[[Κατηγορία:Μαθηματικά]]
|