Στατιστική ταξινόμηση

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

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

Συχνά, οι επιμέρους παρατηρήσεις αναλύονται σε ένα σύνολο μετρήσιμων ιδιοτήτων, γνωστές ποικιλοτρόπως ως επεξηγηματικές μεταβλητές ή χαρακτηριστικά. Αυτές οι ιδιότητες μπορεί ποικιλοτρόπως να είναι κατηγορικές (π.χ. "Α", "Β", "ΑΒ" ή "O", για την ομάδα αίματος), διατεταγμένες (π.χ. "μεγάλες", "μεσαίες" ή "μικρές"), ακέραιος αριθμός (π.χ. ο αριθμός των εμφανίσεων ενός τμήματος μιας λέξης σε ένα μήνυμα ηλεκτρονικού ταχυδρομείου) ή πραγματικός (π.χ. μια μέτρηση της πίεσης του αίματος). Άλλοι ταξινομητές λειτουργούν συγκρίνοντας τις δεδομένες παρατηρήσεις μέσω μιας συνάρτησης ομοιότητας ή απόστασης.

Ένας αλγόριθμος που υλοποιεί την ταξινόμηση, ειδικά σε μια συγκεκριμένη εφαρμογή, είναι γνωστός ως ταξινομητής. Ο όρος «ταξινομητής» μερικές φορές επίσης αναφέρεται στην μαθηματική συνάρτηση, που υλοποιείται από έναν αλγόριθμο ταξινόμησης, που χαρτογραφεί την εισαγωγή δεδομένων σε μια κατηγορία.

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

Σχέση με άλλα προβλήματα

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

Μια κοινή υποκατηγορία της ταξινόμησης είναι η πιθανολογική ταξινόμηση.Αλγόριθμοι αυτού του είδους χρησιμοποιούν στατιστική συμπερασματολογία για να βρουν την καλύτερη κατηγορία για κάθε δεδομένη περίσταση.Σε αντίθεση με άλλους αλγορίθμους,οι οποίοι δίνουν απλά ως έξοδο μια "καλύτερη" κατηγορία,οι πιθανολογικοί αλγόριθμοι δίνουν ως έξοδο μια πιθανότητα για παράδειγμα να είναι μέλος της κάθε μια από τις πιθανές κατηγορίες.Η καλύτερη κατηγορία συνήθως επιλέγεται ως αυτή με την υψηλότερη πιθανότητα .Ωστόσο,ένας τέτοιος αλγόριθμος έχει πολλά πλεονεκτήματα σε σχέση με μη-πιθανολογικούς ταξινομητές:

Μπορεί να εξάγει μια σίγουρη τιμή που σχετίζεται με την επιλογή του (γενικά,ένας ταξινομητής που μπορεί να το κάνει αυτό είναι γνωστός ως ένας σίγουρα σταθμισμένος ταξινομητής).
Αντίστοιχα,μπορεί να απόσχει από την εμπιστοσύνη της επιλογής όταν κάποια συγκεκριμένη παραγωγή είναι πολύ χαμηλή.
Λόγω των πιθανοτήτων που προκύπτουν,οι πιθανολογικοί ταξινομητές μπορούν να ενσωματωθούν πιο αποτελεσματικά σε μεγαλύτερες εργασίες μηχανικής μάθησης,με έναν τρόπο που αποφεύγει μερικώς ή πλήρως το πρόβλημα της διάδοσης των σφαλμάτων.

Συχνοτικές διαδικασίες

Οι πρώτες εργασίες για τη στατιστική ταξινόμηση πραγματοποιήθηκαν από τον Φίσερ,^[2]^[3] στο πλαίσιο των προβλημάτων των δύο ομάδων,που οδηγεί σε συνάρτηση γραμμική διακρίνουσα Φίσερ όπως ο κανόνας για την ανάθεση μιας ομάδας σε μια νέα παρατήρηση.^[4] Αυτές οι πρώτες εργασίες υποθέτουμε ότι τα δεδομένα-τιμές σε κάθε μία από τις δύο ομάδες είχαν μια πολυμεταβλητή κανονική κατανομή. Η επέκταση αυτού του πλαισίου σε περισσότερες από δύο ομάδες εξετάστηκαν επίσης με περιορισμούς που επιβάλουν ο κανόνας ταξινόμησης να είναι γραμμικός.^[4]^[5] Αργότερα το έργο για την πολυμεταβλητή κανονική κατανομή επέτρεψε στον ταξινομητή να είναι μη γραμμικός:^[6] αρκετοί από τους κανόνες ταξινόμησης μπορούν να προκύψουν με βάση ελαφρώς διαφορετικές ρυθμίσεις της απόστασης Mahalanobis,με μια νέα παρατήρηση που αποδόθηκε στην ομάδα της οποίας το κέντρο έχει τη χαμηλότερη ρυθμισμένη απόσταση από την παρατήρηση.

Διαδικασίες του Μπέυζ

Σε αντίθεση με τις συχνοτικές διαδικασίες,οι διαδικασίες ταξινόμησης του Μπέυζ παρέχουν ένα φυσικό τρόπο να συμπεριληφθούν τυχόν διαθέσιμες πληροφορίες σχετικά με τα σχετικά μεγέθη των υπο-πληθυσμών που συνδέονται με τις διάφορες ομάδες εντός του συνολικού πληθυσμού.^[7] OI διαδικασίες του Μπέυζ τείνουν να είναι υπολογιστικά ακριβές και,κατά τις ημέρες πριν αναπτυχθεί ο υπολογισμός Markov chain Monte Carlo,επινοήθηκαν προσεγγίσεις για τους κανόνες ομαδοποίησης του Μπέυζ.^[8]

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

Δυαδική και πολυ κατάταξη ταξινόμηση

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

Χαρακτηριστικά διανυσμάτων

Οι περισσότεροι αλγόριθμοι περιγράφουν ένα μεμονωμένο υπόδειγμα του οποίου η κατηγορία είναι να προβλεφθεί χρησιμοποιώντας ένα διάνυσμα χαρακτηριστικών του ατόμου,μετρήσιμες ιδιότητες της περίπτωσης.Κάθε ιδιότητα ορίζεται ως χαρακτηριστικό,επίσης είναι γνωστή στις στατιστική ως ερμηνευτική μεταβλητή (ή ανεξάρτητη μεταβλητή, αν και τα χαρακτηριστικά μπορεί να είναι ή να μην είναι στατιστικά ανεξάρτητες).Τα Χαρακτηριστικά μπορεί ποικιλοτρόπως να είναι δυαδικά (Π.χ. «αρσενικό» ή «θηλυκό»)? κατηγορηματικός (Π.χ. "Α", "Β", "ΑΒ" ή "O", για τον τύπο του αίματος)? τακτικός (π.χ. "μεγάλα", "μέσο" ή "μικρό")? ακέραια-τιμή (π.χ. ο αριθμός εμφανίσεων μιας συγκεκριμένης λέξης σε ένα e-mail)? ή πραγματική τιμή (π.χ. μια μέτρηση της αρτηριακής πίεσης).Αν το παράδειγμα είναι μια εικόνα, οι χαρακτηριστικές τιμές θα μπορούσαν να αντιστοιχούν στα πίξελ μιας εικόνας? αν η περίπτωση είναι ένα κομμάτι από κείμενο,οι χαρακτηριστικές τιμές θα μπορούσαν να είναι συχνότητες εμφάνισης από διαφορετικές λέξεις.Μερικοί αλγόριθμοι λειτουργούν μόνο από την άποψη των διακριτών στοιχείων και απαιτούν πραγματικές τιμές ή τα δεδομένα των ακέραιων-τιμών να διακριθούν σε ομάδες (Π.χ. λιγότερο από 5, μεταξύ 5 και 10, ή μεγαλύτερο από 10)

Γραμμικοί ταξινομητές

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

$\operatorname {score} (\mathbf {X} _{i},k)={\boldsymbol {\beta }}_{k}\cdot \mathbf {X} _{i},$

Όπου X_i είναι ένα χαρακτηριστικό διάνυσμα για παράδειγμα i, β_k είναι το διάνυσμα των βαρών που αντιστοιχεί στην κατηγορία k,και score(x_i,k) είναι το σκορ που σχετίζεται με την ανάθεση παραδείγματος I της κατηγορίας k.Σε διακριτή επιλογή θεωρίας όπου οι περιπτώσεις αντιπροσωπεύουν τους ανθρώπους και οι κατηγορίες αντιπροσωπεύουν τις επιλογές, το σκορ θεωρείται το βοηθητικό πρόγραμμα που σχετίζεται με το πρόσωπο i επιλέγοντας την κατηγορία k.Αλγόριθμοι με αυτή τη βασική ρύθμιση είναι γνωστοί ως γραμμικοί ταξινομητές. Αυτό που τους διακρίνει είναι η διαδικασία για τον καθορισμό (εκπαίδευση) των βέλτιστων βαρών/συντελεστών και τον τρόπου που το σκορ ερμηνεύεται.

Παραδείγματα τέτοιων αλγορίθμων είναι

Αλγόριθμοι

Παραδείγματα αλγορίθμων ταξινόμησης περιλαμβάνουν:

Αξιολόγηση

Η απόδοση της ταξινομητής εξαρτάται σε μεγάλο βαθμό από τα χαρακτηριστικά των δεδομένων που πρέπει να ταξινομηθούν.Δεν υπάρχει μοναδικός ταξινομητής που λειτουργεί καλύτερα για όλα τα προβλήματα που δίνονται (Ένα φαινόμενο που μπορεί να εξηγηθεί από το θεώρημα no-free-lunch ).Διάφορες εμπειρικές δοκιμές έχουν διεξαχθεί για να συγκρίνουν τις επιδόσεις της ταξινόμησης και να βρει τα χαρακτηριστικά των στοιχείων που καθορίζουν την απόδοση της ταξινόμησης.Καθορίζοντας ενός κατάλληλου ταξινομητή για ένα δεδομένο πρόβλημα είναι όμως ακόμα περισσότερο μια τέχνη παρά επιστήμη.

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

Ως μέτρηση απόδοσης,ο συντελεστής αβεβαιότητας έχει το πλεονέκτημα έναντι της απλής ακρίβειας από το γεγονός ότι δεν επηρεάζεται από τα σχετικά μεγέθη των διαφόρων κατηγοριών.^[11] Περαιτέρω, δεν θα τιμωρήσει έναν αλγόριθμο για την απλή αναδιάταξη των κατηγοριών.

Πεδία εφαρμογών

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

Υπολογιστική όραση
- Ιατρικής απεικόνισης και ανάλυσης ιατρικής εικόνας
- Οπτική αναγνώριση χαρακτήρων
- Παρακολούθηση βίντεο
Ανάπτυξη και ανακάλυψη φαρμάκων
- Τοξικογονιδιωματικής
- Σχέση ποσοτικής δομής-δραστικότητας
Γεωστατιστική
Αναγνώριση ομιλίας
Αναγνώριση χειρογράφου
Βιομετρική ταυτοποίηση
Βιολογική ταξινόμηση
Στατιστική επεξεργασία φυσικής γλώσσας
Κατάταξη εγγράφων
Μηχανές αναζήτησης στο διαδίκτυο
Ποσοστά επιτυχίας
Αναγνώριση μοτίβου
Ταξινόμηση των μικροσυστοιχιών

Παραπομπές

↑ Alpaydin, Ethem (2010). Εισαγωγή στη Μηχανική Μάθηση. MIT Press. σελ. 9. ISBN 978-0-262-01243-0.
↑ Fisher R.A. (1936) "Η χρήση πολλαπλών μετρήσεων σε ταξινομικά προβλήματα",Annals of Eugenics, 7, 179–188
↑ Fisher R.A. (1938) "Η στατιστική αξιοποίηση των πολλαπλών μετρήσεων", Annals of Eugenics, 8, 376–386
↑ ^4,0 ^4,1 Gnanadesikan, R. (1977) Μέθοδοι Στατιστικής Ανάλυσης Δεδομένων Πολυμεταβλητών Παρατηρήσεις, Wiley. ISBN 0-471-30845-5 (p. 83–86)
↑ Rao, C.R. (1952)Σύνθετες Στατιστικές Μέθοδοι στην πολυπαραγοντική ανάλυση , Wiley. (τμήμα 9γ)
↑ Anderson,T.W. (1958)Εισαγωγή στην Πολυμεταβλητή Στατιστική Ανάλυση , Wiley.
↑ Binder, D.A. (1978) "Μπεϋζιανή ανάλυση συμπλέγματος", Biometrika , 65, 31–38.
↑ Binder, D.A. (1981) "Προσεγγίσεις για τους κανόνες ομαδοποίησης κατά Bayes ", Biometrika, 68, 275–285.
↑ Har-Peled, S., Roth, D., Zimak, D. (2003) "Περιορισμούς ταξινόμησης πολυ κατάταξης και βαθμολογία." In: Becker, B., Thrun, S., Obermayer, K. (Eds) Οι πρόοδοι στα Νευρωνικά Πληροφοριακών Συστημάτων Επεξεργασίας 15: Πρακτικά του Συνεδρίου του 2002, MIT Press. ISBN 0-262-02550-7
↑ "Ασαφής ελάχιστο-μέγιστο Νευρωνικό Δίκτυο" (PDF). Reza Davtalab, Mostafa Parchami,κ.α.
↑ Peter Mills (2011). "Αποτελεσματική στατιστική ταξινόμηση των δορυφορικών μετρήσεων". Διεθνές περιοδικό της Τηλεπισκόπησης. doi:10.1080/01431161.2010.507795

[1] Alpaydin, Ethem (2010). Εισαγωγή στη Μηχανική Μάθηση. MIT Press. σελ. 9. ISBN 978-0-262-01243-0.

[2] Fisher R.A. (1936) "Η χρήση πολλαπλών μετρήσεων σε ταξινομικά προβλήματα",Annals of Eugenics, 7, 179–188

[3] Fisher R.A. (1938) "Η στατιστική αξιοποίηση των πολλαπλών μετρήσεων", Annals of Eugenics, 8, 376–386

[:0-4] 4,0 ^4,1 Gnanadesikan, R. (1977) Μέθοδοι Στατιστικής Ανάλυσης Δεδομένων Πολυμεταβλητών Παρατηρήσεις, Wiley. ISBN 0-471-30845-5 (p. 83–86)

[5] Rao, C.R. (1952)Σύνθετες Στατιστικές Μέθοδοι στην πολυπαραγοντική ανάλυση , Wiley. (τμήμα 9γ)

[6] Anderson,T.W. (1958)Εισαγωγή στην Πολυμεταβλητή Στατιστική Ανάλυση , Wiley.

[7] Binder, D.A. (1978) "Μπεϋζιανή ανάλυση συμπλέγματος", Biometrika , 65, 31–38.

[8] Binder, D.A. (1981) "Προσεγγίσεις για τους κανόνες ομαδοποίησης κατά Bayes ", Biometrika, 68, 275–285.

[9] Har-Peled, S., Roth, D., Zimak, D. (2003) "Περιορισμούς ταξινόμησης πολυ κατάταξης και βαθμολογία." In: Becker, B., Thrun, S., Obermayer, K. (Eds) Οι πρόοδοι στα Νευρωνικά Πληροφοριακών Συστημάτων Επεξεργασίας 15: Πρακτικά του Συνεδρίου του 2002, MIT Press. ISBN 0-262-02550-7

[10] "Ασαφής ελάχιστο-μέγιστο Νευρωνικό Δίκτυο" (PDF). Reza Davtalab, Mostafa Parchami,κ.α.

[11] Peter Mills (2011). "Αποτελεσματική στατιστική ταξινόμηση των δορυφορικών μετρήσεων". Διεθνές περιοδικό της Τηλεπισκόπησης. doi:10.1080/01431161.2010.507795

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]