Κοινή χρήση τεχνολογίας

Μέθοδος ανάλυσης συστάδων (3)

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina


5. Ποιοτική αξιολόγηση της ομαδοποίησης

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

(1) Εκτίμηση του αριθμού των συστάδων

Πολλοί αλγόριθμοι ομαδοποίησης όπως π.χ κκκ-Οι αλγόριθμοι υπολογισμού μέσου όρου, ακόμη και οι αλγόριθμοι DIANA κ.λπ., πρέπει να καθορίσουν εκ των προτέρων τον αριθμό των συστάδων κκκ,και κκκΗ τιμή του θα επηρεάσει σε μεγάλο βαθμό την ποιότητα της ομαδοποίησης, ωστόσο, ο αριθμός των συστάδων πρέπει να καθοριστεί εκ των προτέρων. κκκ Δεν είναι εύκολη υπόθεση. Μπορούμε πρώτα να εξετάσουμε δύο ακραίες περιπτώσεις.
(1) Βάλτε ολόκληρο το σύνολο δεδομένων SSμικρόθεωρείται ως ένα σύμπλεγμα, δηλαδή, k = 1 k=1κ=1, αυτό φαίνεται απλό και βολικό, αλλά τα αποτελέσματα αυτής της ανάλυσης συμπλέγματος δεν έχουν αξία.
(2) Βάλτε το σύνολο δεδομένων SSμικρόΚάθε αντικείμενο του αντιμετωπίζεται ως σύμπλεγμα, δηλαδή ας k = ∣ S ∣ = nk=|S|=nκ=μικρό=n , παράγοντας έτσι την πιο λεπτόκοκκη συστάδα. Επομένως, δεν υπάρχει διαφορά εντός συστάδας σε κάθε συστάδα και η ομοιότητα εντός συστάδας φτάνει στο υψηλότερο επίπεδο.Αλλά αυτό το είδος ομαδοποίησης δεν μπορεί να χρησιμοποιηθεί SSμικρόπαρέχετε οποιαδήποτε πληροφορία σχετικά με SSμικρόμια γενική περιγραφή.
Μπορεί να φανεί ότι ο αριθμός των συστάδων κκκπρέπει τουλάχιστον να ικανοποιεί 2 ≤ k ≤ n − 1 2≤k≤n-12κn1, αλλά ο αριθμός των συστάδων κκκΤο ποια ακριβώς τιμή είναι η καταλληλότερη παραμένει διφορούμενη.
Γενικά θεωρείται, κκκΗ τιμή του μπορεί να εκτιμηθεί από το σχήμα και την κλίμακα της κατανομής του συνόλου δεδομένων, καθώς και από την ανάλυση ομαδοποίησης που απαιτείται από τον χρήστη, και οι μελετητές έχουν πολλές διαφορετικές μεθόδους εκτίμησης, όπως η μέθοδος elbow, η μέθοδος διασταυρούμενης επικύρωσης και η θεωρία πληροφοριών- βασισμένες μεθόδους κλπ.
Ένα απλό και ευρέως χρησιμοποιούμενο κκκΗ μέθοδος εμπειρικής εκτίμησης αξίας πιστεύει ότι για όσους έχουν nnnΈνα σύνολο δεδομένων αντικειμένων, ο αριθμός των συμπλεγμάτων στα οποία συγκεντρώνεται κκκΔιαλέγω ν 2n2 2n Είναι κατάλληλο.Αυτή τη στιγμή, κάτω από τη μέση προσδοκία, κάθε σύμπλεγμα έχει περίπου 2 n sqrt{2n}2n αντικείμενα.Σε αυτή τη βάση, κάποιοι πρότειναν περαιτέρω πρόσθετους περιορισμούς, δηλαδή τον αριθμό των clusters κ &lt; νκκ<n
Για παράδειγμα, ας υποθέσουμε n = 8 n=8n=8, τότε ο αριθμός των συμπλεγμάτων k = 2 k=2κ=2 είναι κατάλληλο, και κατά μέσο όρο υπάρχουν 4 βαθμοί ανά ομάδα, και σύμφωνα με τον πρόσθετο εμπειρικό τύπο k &lt; 2,83 k&lt;2,83κ<2.83 .Χρησιμοποιώντας αυτές τις δύο πληροφορίες σχετικά με τον αριθμό των συστάδων κκκΟ εμπειρικός τύπος φαίνεται να εξηγείται από τη μία πλευρά, στο Παράδειγμα 10-5 k = 2 k=2κ=2 είναι ο καταλληλότερος αριθμός συστάδων.

(2) Εξωτερική αξιολόγηση ποιότητας

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

1. Μέθοδος εντροπίας ομαδοποίησης

υποθετικό σύνολο δεδομένων S = { X 1 , X 2 , … , X n } S={X_1,X_2,…,X_n}μικρό={Χ1,Χ2,,Χn},και T = { T 1 , T 2 , … , T m } T={T_1,T_2,…,T_m}Τ={Τ1,Τ2,,ΤΜ} είναι η ιδανική τυπική ομαδοποίηση που δίνεται από ειδικούς, και C = { C 1 , C 2 , … , C k } C={C_1, C_2,…, C_k}ντο={ντο1,ντο2,,ντοκ} καθορίζεται από έναν αλγόριθμο για SSμικρόΈνα σύμπλεγμα του , στη συνέχεια για το σύμπλεγμα C i C_iντοΕγώΣε σχέση με τη βασική ομαδοποίηση TTΤΗ εντροπία ομαδοποίησης του ορίζεται ως
E ( C i ∣ T ) = − ∑ j = 1 m ∣ C i ∩ T j ∣ ∣ C i ∣ log ⁡ 2 ∣ C i ∩ T j ∣ ∣ C i ∣ (10-20) E)(C) =-sum_{j=1}^mfrac{|C_icap T_j|}{|C_i|}log_2frac{|C_icap T_j|}{|C_i|}ετικέτα{10-20}μι(ντοΕγώΤ)=ι=1ΜντοΕγώντοΕγώΤιιδούσολ2ντοΕγώντοΕγώΤι(10-20) και CCντοΣχετικά με τα σημεία αναφοράς TTΤΗ συνολική εντροπία ομαδοποίησης ορίζεται ως όλα τα συμπλέγματα C i C_iντοΕγώΣχετικά με τα σημεία αναφοράς TTΤΟ σταθμισμένος μέσος όρος της εντροπίας ομαδοποίησης, δηλαδή
E ( C ) = 1 ∑ i = 1 k ∣ C i ∣ ∑ i = 1 k ∣ C i ∣ × E ( C i ∣ T ) (10-21) E(C) = frac{1}{mathop{sum }limits_{i=1}^k|C_i|}sum_{i=1}^k|C_i|times E(C_i|T)tag{10-21}μι(ντο)=Εγώ=1κντοΕγώ1Εγώ=1κντοΕγώ×μι(ντοΕγώΤ)(10-21) Η μέθοδος της εντροπίας ομαδοποίησης πιστεύει ότι, E ( C ) E(C)μι(ντο) Όσο μικρότερη είναι η τιμή, τόσο CCντοΣε σχέση με τη γραμμή βάσης TTΤΌσο υψηλότερη είναι η ποιότητα ομαδοποίησης.
Αξίζει να σημειωθεί ότι ο παρονομαστής του πρώτου όρου στη δεξιά πλευρά του τύπου (10-21) ∑ i = 1 k ∣ C i ∣κΕγώ=1|ντοΕγώ| Εγώ=1κντοΕγώ είναι το άθροισμα του αριθμού των στοιχείων σε κάθε σύμπλεγμα και δεν μπορεί να χρησιμοποιηθεί nnn αντικαθιστώ.Γιατί, μόνο όταν CCντοΌταν είναι ένα σύμπλεγμα διαμερισμάτων, ο παρονομαστής είναι nnnκαι ο παρονομαστής των γενικών μεθόδων ομαδοποίησης, όπως η ομαδοποίηση DBSCAN, μπορεί να είναι μικρότερος από nnn

2. Ακρίβεια ομαδοποίησης

Η βασική ιδέα της αξιολόγησης της ακρίβειας (ακρίβειας) ομαδοποίησης είναι να χρησιμοποιηθεί ο μεγαλύτερος αριθμός κατηγοριών στο σύμπλεγμα ως ετικέτα κατηγορίας του συμπλέγματος, δηλαδή για το σύμπλεγμα C i C_iντοΕγώ,αν υπαρχει T j T_jΤιφτιαχνω, κανω ∣ C i ∩ T j ∣ = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_| C_icap T_2|,cdots,|C_icap T_m|}ντοΕγώΤι=Μέγιστη{ντοΕγώΤ1,ντοΕγώΤ2,,ντοΕγώΤΜ}, θεωρείται ότι C i C_iντοΕγώΗ κατηγορία είναι T j T_jΤι .Επομένως, το σύμπλεγμα C i C_iντοΕγώΣχετικά με τα σημεία αναφοράς TTΤΗ ακρίβεια ορίζεται ως
J ( C i ∣ T ) = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } ∣ C i ∣ (10-2)| T)=frac{max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}ετικέτα{10-22}J(ντοΕγώΤ)=ντοΕγώΜέγιστη{ντοΕγώΤ1,ντοΕγώΤ2,,ντοΕγώΤΜ}(10-22) και CCντοΣχετικά με τα σημεία αναφοράς TTΤΗ συνολική ακρίβεια του ορίζεται για όλα τα clusters C i C_iντοΕγώΣχετικά με τα σημεία αναφοράς TTΤΟ σταθμικός μέσος όρος της ακρίβειας ομαδοποίησης, δηλαδή
J ( C ) = 1 ∑ i = 1 k ∣ C i ∣ ∑ i = 1 k ∣ C i ∣ × J ( C i ∣ T ) (10-23) J(C)=frac{1}{mathop{sum }limits_{i=1}^k|C_i|}sum_{i=1}^k|C_i|φορές J(C_i|T)tag{10-23}J(ντο)=Εγώ=1κντοΕγώ1Εγώ=1κντοΕγώ×J(ντοΕγώΤ)(10-23) Η μέθοδος ακρίβειας ομαδοποίησης πιστεύει ότι, J ( C ) J(C)J(ντο) Όσο μεγαλύτερη είναι η τιμή, τόσο η ομαδοποίηση CCντοΣε σχέση με τη γραμμή βάσης TTΤΌσο υψηλότερη είναι η ποιότητα ομαδοποίησης.
Επιπλέον, γενικά 1 − J ( C ) 1-J(C)1J(ντο) που ονομάζεται CCντοΣχετικά με τα σημεία αναφοράς TTΤ συνολικό ποσοστό σφάλματος.Επομένως, η ακρίβεια ομαδοποίησης J ( C ) J(C)J(ντο) Μεγάλο ή συνολικό ποσοστό σφάλματος 1 − J ( C ) 1-J(C)1J(ντο) Μικρό, δείχνει ότι ο αλγόριθμος ομαδοποίησης μπορεί να ομαδοποιήσει καλύτερα αντικείμενα διαφορετικών κατηγοριών σε διαφορετικά cluster, δηλαδή η ακρίβεια ομαδοποίησης είναι υψηλή.

(3) Εσωτερική αξιολόγηση ποιότητας

Δεν υπάρχουν γνωστά εξωτερικά κριτήρια αναφοράς για εσωτερική αξιολόγηση ποιότητας, χρησιμοποιούνται μόνο σύνολα δεδομένων SSμικρόκαι ομαδοποίηση CCντοΓια την αξιολόγηση των εγγενών χαρακτηριστικών και των μεγεθών ενός συμπλέγματος CCντο η ποιότητα του. Δηλαδή, το φαινόμενο ομαδοποίησης γενικά αξιολογείται με τον υπολογισμό της μέσης ομοιότητας εντός των συστάδων, της μέσης ομοιότητας μεταξύ των συστάδων ή της συνολικής ομοιότητας.
Η εσωτερική αξιολόγηση της ποιότητας σχετίζεται με τον αλγόριθμο της ομαδοποίησης Ως εκ τούτου, η αποτελεσματικότητα της ομαδοποίησης μετριέται γενικά με κάποια μορφή αναλογίας της απόστασης εντός του συμπλέγματος και της απόστασης μεταξύ των συστάδων. Οι κοινώς χρησιμοποιούμενοι δείκτες αυτού του τύπου περιλαμβάνουν δείκτη CH, δείκτη Dunn, δείκτη I, δείκτη Xie-eni κ.λπ.

1. Ένδειξη CH

Ο δείκτης CH είναι η συντομογραφία του δείκτη Calinski-Harabasz. Υπολογίζει πρώτα το άθροισμα των τετραγώνων της απόστασης μεταξύ κάθε σημείου συστάδας και του κέντρου του για να μετρήσει την εγγύτητα εντός της κλάσης μεταξύ κάθε κεντρικού σημείου συμπλέγματος και του κεντρικού σημείου του συνόλου δεδομένων προς μέτρηση Ο διαχωρισμός του συνόλου δεδομένων και ο λόγος διαχωρισμού προς την εγγύτητα είναι ο δείκτης CH.
στήνω X ‾ i overline{X}_iΧΕγώαντιπροσωπεύει ένα σύμπλεγμα CCντοκεντρικό σημείο (μέσο), X ‾ overline{X}Χαντιπροσωπεύει ένα σύνολο δεδομένων SSμικρότο κεντρικό σημείο του d ( X ‾ i , X ‾ ) d(overline{X}_i,overline{X})ρε(ΧΕγώ,Χ) Για X ‾ i overline{X}_iΧΕγώφθάνω X ‾ overline{X}ΧΜια ορισμένη συνάρτηση απόστασης του , στη συνέχεια ομαδοποίηση CCντοΗ συμπαγής μορφή ενός μεσαίου συμπλέγματος ορίζεται ως
Trace ( A ) = ∑ i = 1 k ∑ X j ∈ C id ( X j , X ‾ i ) 2 (10-24) text{Trace}(A)=sum_{i=1}^ksum_{X_jin C_i} d(X_j,overline{X}_i)^2tag{10-24}Ιχνος(ΕΝΑ)=Εγώ=1κΧιντοΕγώρε(Χι,ΧΕγώ)2(10-24) Επομένως, το Trace(A) είναι το σύμπλεγμα CCντο Το άθροισμα των τετραγωνικών αποστάσεων μεταξύ των κέντρων συστάδων.Και ομαδοποίηση CCντοΟ βαθμός διαχωρισμού ορίζεται ως
Trace ( B ) = ∑ i = 1 k ∣ C i ∣ d ( X ‾ i , X ‾ ) 2 (10-25) text{Trace}(B)=sum_{i=1}^k|C_i|d( overline{X}_i,overline{X})^2tag{10-25}Ιχνος(σι)=Εγώ=1κντοΕγώρε(ΧΕγώ,Χ)2(10-25) Δηλαδή, το Trace(B) είναι ομαδοποίηση CCντοΚάθε κέντρο του συμπλέγματος SSμικρόΤο σταθμισμένο άθροισμα των τετραγωνικών αποστάσεων από το κέντρο του .
Από αυτό, αν N = ∑ i = 1 k ∣ C i ∣Ν=κΕγώ=1|ντοΕγώ| Ν=Εγώ=1κντοΕγώ Τότε ο δείκτης CH μπορεί να οριστεί ως
V CH ( k ) = Trace ( B ) / ( k − 1 ) Trace ( A ) / ( N − k ) (10-26) V_{text{CH}}(k)=frac{text{Trace}(B )/(k-1)}{text{Trace}(A)/(Nk)}ετικέτα{10-26}VCH(κ)=Ιχνος(ΕΝΑ)/(Νκ)Ιχνος(σι)/(κ1)(10-26) Ο τύπος (10-26) χρησιμοποιείται γενικά στις ακόλουθες δύο περιπτώσεις:
(1) Αξιολογήστε ποια ομαδοποίηση που προκύπτει από τους δύο αλγόριθμους είναι καλύτερη.
Ας υποθέσουμε ότι χρησιμοποιούνται δύο αλγόριθμοι για την ανάλυση του συνόλου δεδομένων SSμικρόΠραγματοποιήθηκε ανάλυση συστάδων και δύο διαφορετικές συστάδες (και οι δύο περιείχαν κκκclusters), η ομαδοποίηση που αντιστοιχεί στη μεγαλύτερη τιμή CH είναι καλύτερη, επειδή όσο μεγαλύτερη είναι η τιμή CH σημαίνει ότι κάθε σύμπλεγμα στο σύμπλεγμα είναι πιο κοντά στον εαυτό της και οι συστάδες είναι πιο διασκορπισμένες.
(2) Αξιολογήστε ποια από δύο συστάδες με διαφορετικούς αριθμούς συστάδων που λαμβάνονται από τον ίδιο αλγόριθμο είναι καλύτερη.
Ας υποθέσουμε ότι ένας αλγόριθμος έχει ένα σύνολο δεδομένων SSμικρόΠραγματοποιήθηκε ανάλυση συστάδων και λήφθηκε ο αριθμός των συστάδων ως k 1 k_1κ1και b 2 b_2σι2 Από τις δύο συστάδες, το αποτέλεσμα ομαδοποίησης με μεγαλύτερη τιμή CH είναι καλύτερο, πράγμα που σημαίνει επίσης ότι ο αριθμός των συστάδων που αντιστοιχούν σε αυτό το σύμπλεγμα είναι καταλληλότερος.Επομένως, εφαρμόζοντας επανειλημμένα τον τύπο (10-26), μπορούμε επίσης να λάβουμε ένα σύνολο δεδομένων SSμικρόΟ βέλτιστος αριθμός συστάδων για ομαδοποίηση.

2. Ένδειξη Dunn

Ο δείκτης Dunn χρησιμοποιεί συμπλέγματα C i C_iντοΕγώμε συστάδα C j C_jντοιελάχιστη απόσταση μεταξύ ds ( C i , C j ) d_s(C_i,C_j)ρεμικρό(ντοΕγώ,ντοι) για τον υπολογισμό του διαχωρισμού μεταξύ συστάδων χρησιμοποιώντας τη μεγαλύτερη διάμετρο συστάδων μεταξύ όλων των συστάδων max ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } max{varPhi(C_1), varPhi(C_2),...,varPhi(C_k)}Μέγιστη{Φ(ντο1),Φ(ντο2),...,Φ(ντοκ)} Για να χαρακτηριστεί η στεγανότητα μέσα σε ένα σύμπλεγμα, ο δείκτης Dunn είναι η ελάχιστη τιμή του λόγου μεταξύ του πρώτου και του δεύτερου, δηλαδή
VD ( k ) = min ⁡ i ≠ jds ( C i , C j ) max ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } (10-27) V_D(k)=min_{i≠j}frac{d_s(C_i,C_j)}{max{varPhi(C_1), varPhi(C_2),...,varPhi (C_k)}}ετικέτα{10-27}Vρε(κ)=Εγώ=ιελάχΜέγιστη{Φ(ντο1),Φ(ντο2),...,Φ(ντοκ)}ρεμικρό(ντοΕγώ,ντοι)(10-27) Όσο μεγαλύτερη είναι η τιμή Dunn, τόσο μεγαλύτερη είναι η απόσταση μεταξύ των συστάδων και τόσο καλύτερη είναι η αντίστοιχη ομαδοποίηση.Παρόμοια με τον δείκτη αξιολόγησης CH, ο δείκτης Dunn μπορεί να χρησιμοποιηθεί για την αξιολόγηση της ποιότητας των συστάδων που λαμβάνονται από διαφορετικούς αλγόριθμους και μπορεί επίσης να χρησιμοποιηθεί για να αξιολογήσει ποιες συστάδες που λαμβάνονται από τον ίδιο αλγόριθμο με διαφορετικούς αριθμούς συστάδων είναι καλύτερες, δηλαδή, μπορεί να χρησιμοποιηθεί για την αναζήτηση SSμικρόο βέλτιστος αριθμός συστάδων.

6. Outlier mining

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

(1) Επισκόπηση σχετικών θεμάτων

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

1. Η γενιά των ακραίων

(1) Τα δεδομένα προέρχονται από ανωμαλίες που προκαλούνται από απάτη, εισβολή, εστίες ασθενειών, ασυνήθιστα πειραματικά αποτελέσματα κ.λπ. Για παράδειγμα, ο μέσος λογαριασμός τηλεφώνου κάποιου είναι περίπου 200 γιουάν, αλλά ξαφνικά αυξάνεται σε αρκετές χιλιάδες γιουάν σε έναν συγκεκριμένο μήνα, η πιστωτική κάρτα κάποιου συνήθως καταναλώνει περίπου 5.000 γιουάν το μήνα, αλλά σε έναν συγκεκριμένο μήνα η κατανάλωση υπερβαίνει τα 30.000 γιουάν, κ.λπ. Τέτοιες ακραίες τιμές είναι συνήθως σχετικά ενδιαφέροντες στην εξόρυξη δεδομένων και αποτελούν ένα από τα βασικά σημεία εφαρμογής.
(2) Προκαλείται από εγγενείς αλλαγές στις μεταβλητές δεδομένων, που αντικατοπτρίζουν τα φυσικά χαρακτηριστικά της διανομής δεδομένων, όπως η κλιματική αλλαγή, τα νέα μοντέλα αγορών πελατών, οι γενετικές μεταλλάξεις κ.λπ. Επίσης ένας από τους ενδιαφέροντες τομείς εστίασης.
(3) Τα σφάλματα μέτρησης και συλλογής δεδομένων οφείλονται κυρίως σε ανθρώπινο λάθος, αστοχία εξοπλισμού μέτρησης ή παρουσία θορύβου. Για παράδειγμα, ο βαθμός -100 ενός μαθητή σε ένα συγκεκριμένο μάθημα μπορεί να οφείλεται στην προεπιλεγμένη τιμή που ορίζει το πρόγραμμα ο μισθός των ανώτατων στελεχών μιας εταιρείας είναι σημαντικά υψηλότερος από τον μισθό των απλών υπαλλήλων, αλλά είναι ακραίος. Λογικά δεδομένα.

2. Πρόβλημα εξόρυξης εξόρυξης

Συνήθως, το ακραίο πρόβλημα εξόρυξης μπορεί να αναλυθεί σε τρία υποπροβλήματα για περιγραφή.
(1) Ορίστε ακραίες τιμές
Δεδομένου ότι τα ακραία στοιχεία σχετίζονται στενά με πρακτικά προβλήματα, ο ξεκάθαρος καθορισμός του είδους των δεδομένων είναι ακραία ή μη φυσιολογικά δεδομένα είναι η αρχή και η πρωταρχική αποστολή της εξόρυξης ακραίων τιμών Δώστε μια κατάλληλη περιγραφή ή ορισμό.
(2) ακραίες τιμές εξόρυξης
Αφού καθοριστούν με σαφήνεια τα ακραία σημεία, ποιος αλγόριθμος θα χρησιμοποιηθεί για τον αποτελεσματικό εντοπισμό ή την εξόρυξη των καθορισμένων ακραίων σημείων είναι το βασικό καθήκον της εξόρυξης ακραίων σημείων. Ο αλγόριθμος εξόρυξης outlier συνήθως παρέχει στους χρήστες ύποπτα ακραία δεδομένα από την προοπτική των μοτίβων που μπορούν να αντικατοπτρίζονται στα δεδομένα, έτσι ώστε να προσελκύσουν την προσοχή του χρήστη.
(3) Κατανοήστε τις ακραίες τιμές
Οι εύλογες εξηγήσεις, η κατανόηση και η καθοδήγηση της πρακτικής εφαρμογής των αποτελεσμάτων εξόρυξης είναι οι στόχοι της εξόρυξης ακραίων. Δεδομένου ότι ο μηχανισμός με τον οποίο δημιουργούνται τα ακραία στοιχεία είναι αβέβαιος, εάν τα «ακραία σημεία» που ανιχνεύονται από τον αλγόριθμο εξόρυξης ακραίων τιμών αντιστοιχούν πράγματι στην πραγματική ανώμαλη συμπεριφορά δεν μπορεί να εξηγηθεί και να εξηγηθεί από τον αλγόριθμο εξόρυξης ακραίων τιμών, αλλά μπορεί να εξηγηθεί μόνο από τον αλγόριθμο εξόρυξης ακραίων τιμών. Εμπειρογνώμονες του κλάδου ή του τομέα για να κατανοήσουν και να εξηγήσουν οδηγίες.

3. Σχετικότητα των ακραίων τιμών

Οι ακραίες τιμές είναι ειδικά δεδομένα στο σύνολο δεδομένων που προφανώς αποκλίνουν από τα περισσότερα δεδομένα, αλλά «προφανώς» και «κυρίως» είναι σχετικά, δηλαδή, αν και οι ακραίες τιμές είναι διαφορετικές, είναι σχετικές. Επομένως, υπάρχουν πολλά ζητήματα που πρέπει να ληφθούν υπόψη κατά τον καθορισμό και την εξόρυξη ακραίων τιμών.
(1) Παγκόσμια ή τοπικά ακραία στοιχεία
Ένα αντικείμενο δεδομένων μπορεί να είναι ακραίο σε σχέση με τους τοπικούς γείτονές του, αλλά όχι σε σχέση με ολόκληρο το σύνολο δεδομένων. Για παράδειγμα, ένας μαθητής που έχει ύψος 1,9 μέτρα είναι ακραίος στην Τάξη 1 της κύριας μαθηματικής του σχολείου μας, αλλά δεν είναι ακραίος μεταξύ των ανθρώπων σε όλη τη χώρα, συμπεριλαμβανομένων των επαγγελματιών παικτών όπως ο Γιάο Μινγκ.
(2) Αριθμός ακραίων τιμών
Αν και ο αριθμός των ακραίων σημείων είναι άγνωστος, ο αριθμός των κανονικών σημείων θα πρέπει να υπερβαίνει κατά πολύ τον αριθμό των ακραίων σημείων των ακραίων σημείων Θα πρέπει να είναι μικρότερο από 5% ή ακόμη λιγότερο από 1%.
(3) Ακριβής παράγοντας σημείου
Δεν μπορείτε να χρησιμοποιήσετε το "ναι" ή το "όχι" για να αναφέρετε εάν ένα αντικείμενο είναι ακραίο, αντ 'αυτού, θα πρέπει να χρησιμοποιήσετε τον βαθμό απόκλισης του αντικειμένου, δηλαδή τον παράγοντα ακραίου επιπέδου (Outlier Score). να χαρακτηρίσει την απόκλιση ενός δεδομένων από τον βαθμό και στη συνέχεια να φιλτράρει τα αντικείμενα με ακραίους παράγοντες υψηλότερους από ένα ορισμένο όριο, να τα παράσχει στους υπεύθυνους λήψης αποφάσεων ή στους ειδικούς του τομέα για κατανόηση και εξήγηση και να τα εφαρμόσει στην πρακτική εργασία.

(2) Μέθοδος με βάση την απόσταση

1. Βασικές έννοιες

Ορισμός 10-11 Υπάρχει ένας θετικός ακέραιος αριθμός κκκ, αντικείμενο XXΧτου κκκ-Η απόσταση του πλησιέστερου γείτονα είναι ένας θετικός ακέραιος που ικανοποιεί τις παρακάτω προϋποθέσεις dk ( X ) d_k(X)ρεκ(Χ)
(1) εκτός XXΧΕπιπλέον, υπάρχουν τουλάχιστον κκκαντικείμενα YYΥικανοποιώ d ( X , Y ) ≤ dk ( X ) d(X,Y)≤d_k(X)ρε(Χ,Υ)ρεκ(Χ)
(2) εκτός XXΧΕπιπλέον, υπάρχουν το πολύ k − 1 k-1κ1 αντικείμενα YYΥικανοποιώ d ( X , Y ) &lt; dk ( X ) d(X,Y)ρε(Χ,Υ)<ρεκ(Χ)
σε d ( X , Y ) d(X,Y)ρε(Χ,Υ) είναι ένα αντικείμενο XXΧκαι YYΥσυνάρτηση κάποιας απόστασης μεταξύ τους.

ενός αντικειμένου κκκ-Όσο μεγαλύτερη είναι η απόσταση του πλησιέστερου γείτονα, τόσο πιο πιθανό είναι το αντικείμενο να απέχει πολύ από τα περισσότερα δεδομένα, επομένως το αντικείμενο μπορεί να XXΧτου κκκ-πλησιέστερη απόσταση γείτονα dk ( X ) d_k(X)ρεκ(Χ) ως ακραίος παράγοντας του.

Ορισμός 10-12 φτιαχνω, κανω D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)σφήνα Y≠ Χ}ρε(Χ,κ)={Υρε(Χ,Υ)ρεκ(Χ)Υ=Χ}, τότε λέγεται D ( X , k ) D(X,k)ρε(Χ,κ) Ναί XXΧτου κκκ-Κοντινότερος Γείτονας (Domain).

Μπορεί να φανεί από τον ορισμό 10-12 ότι D ( X , k ) D(X,k)ρε(Χ,κ) Ναί XXΧως κέντρο, απόσταση XXΧΔεν υπερβαίνει dk ( X ) d_k(X)ρεκ(Χ) Αντικείμενο YYΥ Η συλλογή που αποτελείται από. Αξίζει να δοθεί ιδιαίτερη προσοχή, XXΧδεν ανήκει σε αυτήν κκκ-πλησιέστερος γείτονας δηλ. X ∉ D ( X , k ) Xnotin D(X,k)Χ/ρε(Χ,κ) . Συγκεκριμένα, XXΧτου κκκ-πλησιέστερος γείτονας D ( X , k ) D(X,k)ρε(Χ,κ) Ο αριθμός των αντικειμένων που περιέχονται μπορεί να υπερβαίνει κατά πολύ κκκ,Τώρα αμέσως ∣ D ( X , k ) ∣ ≥ k |D(X,k)|≥kρε(Χ,κ)κ

Ορισμός 10-13 Υπάρχει ένας θετικός ακέραιος αριθμός κκκ, αντικείμενο XXΧτου κκκ-Ο ακραίος παράγοντας πλησιέστερου γείτονα ορίζεται ως
OF 1 ( X , k ) = ∑ Y ∈ D ( X , k ) d ( X , Y ) ∣ D ( X , k ) ∣ (10-28) κείμενο{OF}_1(X,k)=frac{mathop {sum}limits_{Yin D(X,k)}d(X,Y)}{|D(X,k)|}tag{10-28}ΤΟΥ1(Χ,κ)=ρε(Χ,κ)Υρε(Χ,κ)ρε(Χ,Υ)(10-28)

2. Περιγραφή αλγορίθμου

Για ένα δεδομένο σύνολο δεδομένων και τον αριθμό των αποστάσεων του πλησιέστερου γείτονα κκκ, μπορούμε να χρησιμοποιήσουμε τον παραπάνω τύπο για να υπολογίσουμε το κκκ-Οι πλησιέστεροι ακραίοι παράγοντες, και οι εξόδους τους από μεγάλους σε μικρότερους, είναι πιο πιθανό να είναι ακραίοι παράγοντες , Ποια σημεία είναι πραγματικά ακραία.

Αλγόριθμος 10-8 Αλγόριθμος ανίχνευσης ακραίων τιμών με βάση την απόσταση
Εισαγωγή: σύνολο δεδομένων SSμικρό, ο αριθμός των αποστάσεων του πλησιέστερου γείτονα κκκ
Έξοδος: Φθίνουσα λίστα ύποπτων ακραίων σημείων και αντίστοιχων ακραίων παραγόντων
(1) ΕΠΑΝΑΛΗΨΗ
(2) Πάρτε SSμικρόένα μη επεξεργασμένο αντικείμενο μέσα XXΧ
(3) Εντάξει XXΧτου κκκ-πλησιέστερος γείτονας D ( X , k ) D(X,k)ρε(Χ,κ)
(4) Υπολογισμός XXΧτου κκκ-Εκτός παράγοντας πλησιέστερου γείτονα OF 1 ( X , k ) text{OF}_1(X,k)ΤΟΥ1(Χ,κ)
(5) ΜΕΧΡΙ SSμικρόΚάθε σημείο έχει υποστεί επεξεργασία
(6) Ναι OF 1 ( X , k ) text{OF}_1(X,k)ΤΟΥ1(Χ,κ)Ταξινόμηση με φθίνουσα σειρά και έξοδο ( X , OF 1 ( X , k ) ) (X,text{OF}_1(X,k))(Χ,ΤΟΥ1(Χ,κ))

3. Παραδείγματα υπολογισμού

Παράδειγμα 10-12 Ένα δισδιάστατο σύνολο δεδομένων με 11 σημεία SSμικρόΔίνεται από τον Πίνακα 10-10, ας k = 2 k=2κ=2, χρησιμοποιήστε τον υπολογισμό του τετραγώνου της Ευκλείδειας απόστασης X 7 , X 10 , X 11 X_7, X_{10}, X_{11}Χ7,Χ10,Χ11 Απώτερος παράγοντας σε όλα τα άλλα σημεία.

Εισαγάγετε την περιγραφή της εικόνας εδώ
λύνω: Για να κατανοήσουμε διαισθητικά την αρχή του αλγορίθμου, θα SSμικρόΤα αντικείμενα δεδομένων εμφανίζονται στο επίπεδο στο σχήμα (10-27) παρακάτω.

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

(1) Αντικείμενο υπολογισμού Χ 7 Χ_7Χ7ακραίος παράγοντας
Όπως φαίνεται από το σχήμα, η απόσταση X 7 = ( 6 , 8 ) X_7 = (6,8)Χ7=(6,8) Το πλησιέστερο σημείο είναι X 10 = ( 5 , 7 ) X_{10}=(5,7)Χ10=(5,7),και d ( X 7 , X 10 ) = 1,41 d (X_7, X_{10}) = 1,41ρε(Χ7,Χ10)=1.41, άλλα πλησιέστερα σημεία μπορεί να είναι X 11 = ( 5 , 2 ) X_{11}=(5,2)Χ11=(5,2) X 9 = ( 3 , 2 ) X_9 = (3,2)Χ9=(3,2) X 8 = ( 2 , 4 ) X_8 = (2,4)Χ8=(2,4)
Υπολογίστηκε d ( X 7 , X 11 ) = 6,08 d(X_7,X_{11})=6,08ρε(Χ7,Χ11)=6.08 d ( X 7 , X 9 ) = 6,71 d(X_7,X_9)=6,71ρε(Χ7,Χ9)=6.71 d ( X 7 , X 8 ) = 5,66 d(X_7,X_8)=5,66ρε(Χ7,Χ8)=5.66
επειδή k = 2 k=2κ=2,Έτσι d 2 ( X 7 ) = 5,66 d_2 (X_7) = 5,66ρε2(Χ7)=5.66, άρα σύμφωνα με τον ορισμό 10-11 έχουμε D ( X 7 , 2 ) = { X 10 , X 8 } D(X_7,2)={X_{10},X_8}ρε(Χ7,2)={Χ10,Χ8}
Σύμφωνα με τον τύπο (10-28), Χ 7 Χ_7Χ7ακραίος παράγοντας
OF 1 ( X 7 , 2 ) = ∑ Y ∈ N ( X 7 , 2 ) d ( X 7 , Y ) ∣ N ( X 7 , k ) ∣ = d ( X 7 , X 10 ) + d ( X 7 , X 8 ) 2 = 1,41 + 5,66 2 = 3,54ΤΟΥ1(Χ7,2)=ΥΝ(Χ7,2)ρε(Χ7,Υ)|Ν(Χ7,κ)|=ρε(Χ7,Χ10)+ρε(Χ7,Χ8)2=1.41+5.662=3.54 ΤΟΥ1(Χ7,2)=Ν(Χ7,κ)ΥΝ(Χ7,2)ρε(Χ7,Υ)=2ρε(Χ7,Χ10)+ρε(Χ7,Χ8)=21.41+5.66=3.54(2) Αντικείμενο υπολογισμού X 10 X_{10}Χ10ακραίος παράγοντας OF 1 ( X 10 , 2 ) = 2,83 text{OF}_1(X_{10},2)=2,83ΤΟΥ1(Χ10,2)=2.83

(3) Αντικείμενο υπολογισμού X 11 X_{11}Χ11ακραίος παράγοντας OF 1 ( X 11 , 2 ) = 2,5 text{OF}_1(X_{11},2)=2,5ΤΟΥ1(Χ11,2)=2.5

(4) Αντικείμενο υπολογισμού X 5 X_{5}Χ5ακραίος παράγοντας ΑΠΟ 1 ( X 5 , 2 ) = 1 κείμενο{OF}_1(X_{5},2)=1ΤΟΥ1(Χ5,2)=1

Ομοίως, οι ακραίοι συντελεστές των υπόλοιπων αντικειμένων μπορούν να υπολογιστούν, βλέπε τον ακόλουθο πίνακα (10-11).

Εισαγάγετε την περιγραφή της εικόνας εδώ
4. Όριο εξωγενούς παράγοντα

σύμφωνα με κκκ -Όσο μεγαλύτερη είναι η θεωρία του πλησιέστερου γείτονα, τόσο πιο πιθανό είναι να είναι ακραία σημεία. Η απλούστερη μέθοδος είναι να προσδιορίσετε τον αριθμό των ακραίων σημείων, αλλά αυτή η μέθοδος είναι πολύ απλή και μερικές φορές παραλείπει ορισμένα πραγματικά ακραία σημεία ή αποδίδει πάρα πολλά κανονικά σημεία σε πιθανά ακραία σημεία, γεγονός που καθιστά δύσκολο για τους ειδικούς του τομέα ή τους υπεύθυνους λήψης αποφάσεων να προκύψουν δυσκολίες στην κατανόηση και ερμηνεία των ακραίων στοιχείων.
(1) Η μέθοδος κατωφλίου τμηματοποίησης ακραίων παραγόντων ταξινομεί πρώτα τους ακραίους παράγοντες σε φθίνουσα σειρά και ταυτόχρονα επαναριθμεί τα αντικείμενα δεδομένων σε αύξουσα σειρά σύμφωνα με τους ακραίους παράγοντες.
(2) Με βάση τον ακραίο παράγοντα OF 1 ( X , k ) text{OF}_1(X,k)ΤΟΥ1(Χ,κ) είναι η τεταγμένη και ο αύξων αριθμός του ακραίου παράγοντα είναι η τετμημένη, δηλαδή (αριθμός σειράς, ΑΠΟ 1 κείμενο{OF}_1ΤΟΥ1τιμή) σημειώνονται στο επίπεδο και συνδέονται για να σχηματίσουν μια μη αυξανόμενη πολύγραμμη και το σημείο όπου η πολύγραμμη διασταυρώνεται με μια απότομη πτώση και μια ήπια πτώση αντιστοιχεί στον ακραίο παράγοντα ως το κατώφλι από ή ίσα με αυτό το όριο είναι κανονικά αντικείμενα, τα άλλα είναι πιθανά ακραία.

Παράδειγμα 10-13 Σύνολο δεδομένων για το Παράδειγμα 10-12 SSμικρό , οι ακραίοι συντελεστές του συνοψίζονται σε φθίνουσα σειρά και σειριακό αριθμό στον Πίνακα 10-11. Προσπαθήστε να βρείτε το όριο των ακραίων σημείων με βάση τη μέθοδο κατωφλίου τμηματοποίησης ακραίων παραγόντων.

λύνω: Αρχικά, χρησιμοποιήστε τον (σειριακό αριθμό, ΑΠΟ 1 κείμενο{OF}_1ΤΟΥ1 τιμή) ως σημεία στο επίπεδο, σημειωμένα στο επίπεδο και συνδεδεμένα με πολύγραμμες. Όπως φαίνεται στο Σχήμα 10-28 παρακάτω.

Εισαγάγετε την περιγραφή της εικόνας εδώ
Στη συνέχεια, κοιτάζοντας το Σχήμα 10-28, μπορούμε να βρούμε ότι η πολύγραμμη στα αριστερά του τέταρτου σημείου (4, 1.27) πέφτει πολύ απότομα, ενώ η πολύγραμμη στα δεξιά πέφτει πολύ απαλά, επομένως, ο συντελεστής ακραίας θέσης 1.27 επιλέγεται κατώφλι.επειδή X 7, X 10 X_7, X_{10}Χ7Χ10 και X 11 X_{11}Χ11 Οι ακραίες συντελεστές είναι 3,54, 2,83 και 2,5 αντίστοιχα, που είναι όλοι μεγαλύτεροι από 1,27, επομένως, αυτά τα τρία σημεία είναι πιο πιθανό να είναι ακραία σημεία, ενώ τα υπόλοιπα σημεία είναι συνηθισμένα.
Κοιτάζοντας ξανά το Σχήμα 10-27, μπορούμε να το βρούμε X 7, X 10 X_7, X_{10}Χ7Χ10 και X 11 X_{11}Χ11 όντως πολύ μακριά από την πυκνή πλειονότητα των αντικειμένων στα αριστερά, επομένως αντιμετωπίστε τα ως ένα σύνολο δεδομένων SSμικρόΟι ακραίες τιμές είναι λογικές.

5. Αξιολόγηση αλγορίθμου

Το μεγαλύτερο πλεονέκτημα της μεθόδου ανίχνευσης με βάση την απόσταση είναι ότι είναι απλή στην αρχή και εύκολη στη χρήση της.
(1) Παράμετροι κκκΗ επιλογή δεν διαθέτει μια απλή και αποτελεσματική μέθοδο για τον προσδιορισμό της επίδρασης των αποτελεσμάτων των δοκιμών στις παραμέτρους κκκΔεν υπάρχει καθολικά αποδεκτό αναλυτικό αποτέλεσμα για τον βαθμό ευαισθησίας.
(2) Η χρονική πολυπλοκότητα είναι O ( ∣ S ∣ 2 ) O(|S|^2)Ο(μικρό2), στερείται επεκτασιμότητας για σύνολα δεδομένων μεγάλης κλίμακας.
(3) Λόγω της χρήσης ενός συνολικού ορίου συντελεστών ακραίων τιμών, είναι δύσκολο να εξορυχθούν ακραίες τιμές σε σύνολα δεδομένων με περιοχές διαφορετικής πυκνότητας.

(3) Μέθοδος με βάση τη σχετική πυκνότητα

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

1. Η έννοια της σχετικής πυκνότητας

Από την άποψη της γειτονιάς πυκνότητας, τα ακραία σημεία είναι αντικείμενα σε περιοχές χαμηλής πυκνότητας, επομένως, είναι απαραίτητο να εισαχθούν οι έννοιες της τοπικής πυκνότητας γειτονιάς και της σχετικής πυκνότητας αντικειμένων.

Ορισμός 10-14 (1) ένα αντικείμενο XXΧτου κκκ-Η τοπική πυκνότητα πλησιέστερου γείτονα (πυκνότητα) ορίζεται ως
dsty ( X , k ) = ∣ D ( X , k ) ∣ ∑ Y ∈ D ( X , k ) d ( X , Y ) (10-29) text{dsty}(X,k)=frac{|D( X,k)|}{mathop{sum}limits_{Yin D(X,k)}d(X,Y)}tag{10-29}δστυ(Χ,κ)=Υρε(Χ,κ)ρε(Χ,Υ)ρε(Χ,κ)(10-29) (2) ένα αντικείμενο XXΧτου κκκ-Τοπική σχετική πυκνότητα πλησιέστερου γείτονα (σχετική πυκνότητα)
rdsty ( X , k ) = ∑ Y ∈ D ( X , k ) dsty ( X , k ) / ∣ D ( X , k ) ∣ dsty ( X , k ) (10-30) κείμενο{rdsty}(X,k )=frac{mathop{sum}limits_{Yin D(X,k)}text{dsty}(X,k)/|D(X,k)|}{text{dsty}(X,k)}tag{ 10-30}rdsty(Χ,κ)=δστυ(Χ,κ)Υρε(Χ,κ)δστυ(Χ,κ)/∣ρε(Χ,κ)(10-30) σε D ( X , k ) D(X,k)ρε(Χ,κ) Είναι το αντικείμενο XXΧτου κκκ- πλησιέστερος γείτονας (δίνεται στον ορισμό 10-12), ∣ D ( X , k ) ∣ |D(X,k)|ρε(Χ,κ) είναι ο αριθμός των αντικειμένων της συλλογής.

2. Περιγραφή αλγορίθμου

με rdsty ( X , k ) text{rdsty}(X,k)rdsty(Χ,κ) ως ακραίο στοιχείο OF 2 ( X , k ) text{OF}_2(X,k)ΤΟΥ2(Χ,κ), ο υπολογισμός του χωρίζεται σε δύο βήματα
(1) Σύμφωνα με τον αριθμό των γειτόνων κκκ, υπολογίστε κάθε αντικείμενο XXΧτου κκκ-Τοπική πυκνότητα πλησιέστερου γείτονα dsty ( X , k ) text{dsty}(X,k)δστυ(Χ,κ)
(2) Υπολογισμός XXΧη μέση πυκνότητα των πλησιέστερων γειτόνων και κκκ-Τοπική σχετική πυκνότητα πλησιέστερου γείτονα rdsty ( X , k ) text{rdsty}(X,k)rdsty(Χ,κ)
Ένα σύνολο δεδομένων αποτελείται από πολλαπλές φυσικές συστάδες Η σχετική πυκνότητα των αντικειμένων κοντά στο σημείο του πυρήνα μέσα στο σύμπλεγμα είναι κοντά στο 1, ενώ η σχετική πυκνότητα των αντικειμένων στην άκρη του συμπλέγματος ή εκτός του συμπλέγματος είναι σχετικά μεγάλη. Επομένως, όσο μεγαλύτερη είναι η τιμή της σχετικής πυκνότητας, τόσο πιο πιθανό είναι μια ακραία τιμή.

Αλγόριθμος 10-9 Αλγόριθμος ανίχνευσης ακραίων τιμών με βάση τη σχετική πυκνότητα
Εισαγωγή: σύνολο δεδομένων SSμικρό, ο αριθμός των πλησιέστερων γειτόνων κκκ
Έξοδος: Φθίνουσα λίστα ύποπτων ακραίων σημείων και αντίστοιχων ακραίων παραγόντων
(1) ΕΠΑΝΑΛΗΨΗ
(2) Πάρτε SSμικρόένα μη επεξεργασμένο αντικείμενο μέσα XXΧ
(3) Εντάξει XXΧτου κκκ-πλησιέστερος γείτονας D ( X , k ) D(X,k)ρε(Χ,κ)
(4) Αξιοποίηση D ( X , k ) D(X,k)ρε(Χ,κ)υπολογίζω XXΧΠυκνότητα dsty ( X , k ) text{dsty}(X,k)δστυ(Χ,κ)
(5) ΜΕΧΡΙ SSμικρόΚάθε σημείο έχει υποστεί επεξεργασία
(6) ΕΠΑΝΑΛΗΨΗ
(7) Πάρτε SSμικρόπρώτο αντικείμενο μέσα XXΧ
(8) Εντάξει XXΧσχετική πυκνότητα του rdsty ( X , k ) text{rdsty}(X,k)rdsty(Χ,κ), και να το αντιστοιχίσετε σε OF 2 ( X , k ) text{OF}_2(X,k)ΤΟΥ2(Χ,κ)
(9) ΜΕΧΡΙ SSμικρόΌλα τα αντικείμενα μέσα έχουν υποστεί επεξεργασία
(10) Σωστά OF 2 ( X , k ) text{OF}_2(X,k)ΤΟΥ2(Χ,κ)Ταξινόμηση με φθίνουσα σειρά και έξοδο ( X , OF 2 ( X , k ) ) (X,text{OF}_2(X,k))(Χ,ΤΟΥ2(Χ,κ))

Παράδειγμα 10-14 Για το δισδιάστατο σύνολο δεδομένων που δίνεται στο Παράδειγμα 10-12 SSμικρό (Βλ. Πίνακας 10-10 για λεπτομέρειες), οπότε k = 2 k=2κ=2, δοκιμάστε τον υπολογισμό της Ευκλείδειας απόστασης X 7 , X 10 , X 11 X_7, X_{10}, X_{11}Χ7,Χ10,Χ11 Ο ακραίος παράγοντας βασίζεται στη σχετική πυκνότητα ίσων αντικειμένων.

Εισαγάγετε την περιγραφή της εικόνας εδώ
λύνω:επειδή k = 2 k=2κ=2, οπότε χρειαζόμαστε την τοπική πυκνότητα 2-πλησιέστερου γείτονα όλων των αντικειμένων.

(1) Βρείτε τον 2-πλησιέστερο γείτονα κάθε αντικειμένου δεδομένων στον Πίνακα 10-11 D ( X i , 2 ) D(X_i,2)ρε(ΧΕγώ,2)
Σύμφωνα με την ίδια μέθοδο υπολογισμού στο Παράδειγμα 10-12, μπορούμε να πάρουμε
D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } , D ( X 2 , 2 ) = { X 1 , X 6 } , D ( X 3 , 2 ) = { X 1 , X 4 } , D ( X 4 , 2 ) = { X 3 , X 5 } , D ( X 5 , 2 ) = { X 1 , X 4 , X 6 , X 9 } , D ( X 6 , 2 ) = { X 2 , X 5 , X 8 } , D ( X 7 , 2 ) = { X 10 , X 8 } , D ( X 8 , 2 ) = { X 2 , X 6 } , D ( X 9 , 2 ) = { X 5 , X 4 , X 6 } , D ( X 10 , 2 ) = { X 7 , X 8 } , D ( X 11 , 2 ) = { X 9 , X 5 }ρε(Χ1,2)={Χ2,Χ3,Χ5}ρε(Χ2,2)={Χ1,Χ6}              ρε(Χ3,2)={Χ1,Χ4}ρε(Χ4,2)={Χ3,Χ5}       ρε(Χ5,2)={Χ1,Χ4,Χ6,Χ9}ρε(Χ6,2)={Χ2,Χ5,Χ8}ρε(Χ7,2)={Χ10,Χ8}     ρε(Χ8,2)={Χ2,Χ6}               ρε(Χ9,2)={Χ5,Χ4,Χ6}ρε(Χ10,2)={Χ7,Χ8}     ρε(Χ11,2)={Χ9,Χ5} ρε(Χ1,2)={Χ2,Χ3,Χ5}ρε(Χ2,2)={Χ1,Χ6}              ρε(Χ3,2)={Χ1,Χ4}ρε(Χ4,2)={Χ3,Χ5}       ρε(Χ5,2)={Χ1,Χ4,Χ6,Χ9}ρε(Χ6,2)={Χ2,Χ5,Χ8}ρε(Χ7,2)={Χ10,Χ8}     ρε(Χ8,2)={Χ2,Χ6}               ρε(Χ9,2)={Χ5,Χ4,Χ6}ρε(Χ10,2)={Χ7,Χ8}     ρε(Χ11,2)={Χ9,Χ5}

(2) Υπολογίστε την τοπική πυκνότητα κάθε αντικειμένου δεδομένων dsty ( X i , 2 ) text{dsty}(X_i,2)δστυ(ΧΕγώ,2)

① Υπολογίστε Χ 1 Χ_1Χ1Πυκνότητα
επειδή D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } D(X_1,2)={X_2,X_3,X_5}ρε(Χ1,2)={Χ2,Χ3,Χ5}, άρα μετά τον υπολογισμό, έχουμε d ( X 1 , X 2 ) = 1 d(X_1,X_2)=1ρε(Χ1,Χ2)=1 d ( X 1 , X 3 ) = 1 d(X_1,X_3)=1ρε(Χ1,Χ3)=1 d ( X 1 , X 5 ) = 1 d(X_1, X_5)=1ρε(Χ1,Χ5)=1
Σύμφωνα με τον τύπο (10-29), παίρνουμε:
dsty ( X 1 , 2 ) = ∣ D ( X 1 , 2 ) ∣ ∑ Y ∈ N ( X 1 , 2 ) d ( X 1 , Y ) = ∣ N ( X 1 , 2 ) ∣ d ( X 1 , X 2 ) + d ( X 1 , X 3 ) + d ( X 1 , X 5 ) = 3 1 + 1 + 1 = 1δστυ(Χ1,2)=|ρε(Χ1,2)|ΥΝ(Χ1,2)ρε(Χ1,Υ)=|Ν(Χ1,2)|ρε(Χ1,Χ2)+ρε(Χ1,Χ3)+ρε(Χ1,Χ5)=31+1+1=1 δστυ(Χ1,2)=ΥΝ(Χ1,2)ρε(Χ1,Υ)ρε(Χ1,2)=ρε(Χ1,Χ2)+ρε(Χ1,Χ3)+ρε(Χ1,Χ5)Ν(Χ1,2)=1+1+13=1

② Υπολογισμός Χ 2 Χ_2Χ2Πυκνότητα
επειδή D ( X 2 , 2 ) = { X 1 , X 6 } D(X_2,2)={X_1,X_6}ρε(Χ2,2)={Χ1,Χ6}, άρα το υπολογισμένο d ( X 2 , X 1 ) = 1 d(X_2,X_1) =1ρε(Χ2,Χ1)=1 d ( X 2 , X 6 ) = 1 d(X_2, X_6) =1ρε(Χ2,Χ6)=1
Σύμφωνα με τον τύπο (10-29), παίρνουμε:
dsty ( X 2 , 2 ) = ∣ D ( X 2 , 2 ) ∣ ∑ Y ∈ N ( X 2 , 2 ) d ( X 2 , Y ) = 2 1 + 1 = 1δστυ(Χ2,2)=|ρε(Χ2,2)|ΥΝ(Χ2,2)ρε(Χ2,Υ)=21+1=1 δστυ(Χ2,2)=ΥΝ(Χ2,2)ρε(Χ2,Υ)ρε(Χ2,2)=1+12=1

Η τοπική πυκνότητα άλλων αντικειμένων δεδομένων μπορεί να υπολογιστεί με παρόμοιο τρόπο, δείτε τον Πίνακα 10-12 παρακάτω.

Εισαγάγετε την περιγραφή της εικόνας εδώ
(3) Υπολογίστε κάθε αντικείμενο X i X_iΧΕγώσχετική πυκνότητα του rdsty ( X i , 2 ) text{rdsty}(X_i, 2)rdsty(ΧΕγώ,2), και το θεωρούν ως ακραίο παράγοντα OF 2 text{OF}_2ΤΟΥ2
① Υπολογίστε Χ 1 Χ_1Χ1σχετική πυκνότητα του
Χρησιμοποιώντας την τιμή πυκνότητας κάθε αντικειμένου στον Πίνακα 10-12, σύμφωνα με τον τύπο σχετικής πυκνότητας (10-30):
rdsty ( X 1 , 2 ) = ∑ Y ∈ N ( X 1 , 2 ) dsty ( Y , 2 ) / ∣ N ( X 1 , 2 ) ∣ dsty ( X 1 , 2 ) = ( 1 + 1 + 1 ) / 3 1 = 1 = ΑΠΟ 2 ( X 1 , 2 )rdsty(Χ1,2)=ΥΝ(Χ1,2)δστυ(Υ,2)/|Ν(Χ1,2)|δστυ(Χ1,2)=(1+1+1)/31=1=ΤΟΥ2(Χ1,2) rdsty(Χ1,2)=δστυ(Χ1,2)ΥΝ(Χ1,2)δστυ(Υ,2)/∣Ν(Χ1,2)=1(1+1+1)/3=1=ΤΟΥ2(Χ1,2)

② Παρόμοιος υπολογισμός μπορεί να ληφθεί X 2, X 3, … , X 11 X_2, X_3,…, X_{11}Χ2Χ3Χ11 σχετική τιμή πυκνότητας.
για παράδειγμα Χ 5 Χ_5Χ5Η σχετική πυκνότητα:
rdsty ( X 5 , 2 ) = ∑ Y ∈ N ( X 5 , 2 ) dsty ( Y , 2 ) / ∣ N ( X 5 , 2 ) ∣ dsty ( X 5 , 2 ) = ( 1 + 1 + 1 + 0,79 ) / 4 1 = 0,95 = ΑΠΟ 2 ( X 5 , 2 )rdsty(Χ5,2)=ΥΝ(Χ5,2)δστυ(Υ,2)/|Ν(Χ5,2)|δστυ(Χ5,2)=(1+1+1+0.79)/41=0.95=ΤΟΥ2(Χ5,2) rdsty(Χ5,2)=δστυ(Χ5,2)ΥΝ(Χ5,2)δστυ(Υ,2)/∣Ν(Χ5,2)=1(1+1+1+0.79)/4=0.95=ΤΟΥ2(Χ5,2) Τα αποτελέσματα συνοψίζονται στους Πίνακες 10-13 παρακάτω.

Εισαγάγετε την περιγραφή της εικόνας εδώ
Παράδειγμα 10-15 Δεδομένου του συνόλου δεδομένων που φαίνεται στον Πίνακα 10-14, χρησιμοποιήστε την Ευκλείδεια απόσταση έως k = 2, 3, 5 k=2,3,5κ=2,3,5, υπολογίστε την τιμή κάθε πόντου κκκ-τοπική πυκνότητα πλησιέστερου γείτονα, κκκ-Τοπική σχετική πυκνότητα πλησιέστερου γείτονα (ακριβής παράγοντας OF 2 text{OF}_2ΤΟΥ2) και με βάση κκκ-Εξώτερος παράγοντας για την κοντινότερη απόσταση γείτονα ΑΠΟ 1 κείμενο{OF}_1ΤΟΥ1

Εισαγάγετε την περιγραφή της εικόνας εδώ
λύνω: (1) Προκειμένου να διευκολυνθεί η κατανόηση, μπορεί να είναι SSμικρόΟι σχετικές θέσεις των σημείων σημειώνονται στο δισδιάστατο επίπεδο (Εικόνα 10-30).

Εισαγάγετε την περιγραφή της εικόνας εδώ
(2) Χρησιμοποιήστε αλγόριθμους που βασίζονται σε απόσταση και σχετική πυκνότητα 10-8 και 10-9 αντίστοιχα.Υπολογίστε κάθε αντικείμενο ξεχωριστά κκκ-Τοπική πυκνότητα πλησιέστερου γείτονα κείμενο dsty{dsty}δστυ κκκ-Τοπική σχετική πυκνότητα πλησιέστερου γείτονα (ακριβής παράγοντας OF 2 text{OF}_2ΤΟΥ2) και με βάση κκκ-Εξώτερος παράγοντας για την κοντινότερη απόσταση γείτονα ΑΠΟ 1 κείμενο{OF}_1ΤΟΥ1, τα αποτελέσματα συνοψίζονται στον Πίνακα 10-15.

Εισαγάγετε την περιγραφή της εικόνας εδώ
(3) Απλή ανάλυση
① Όπως φαίνεται από την Εικόνα 10-30, X 15 X_{15}Χ15και X 16 X_{16}Χ16Ναί SSμικρόΥπάρχουν δύο προφανείς ακραίες τιμές, και οι μέθοδοι που βασίζονται στην απόσταση και τη σχετική πυκνότητα μπορούν καλύτερα να τις ανακαλύψουν.
② Από αυτό το παράδειγμα, οι δύο αλγόριθμοι έχουν κκκδεν είναι τόσο ευαίσθητο όσο αναμενόταν, ίσως είναι ακραίο. X 15 X_{15}Χ15και X 16 X_{16}Χ16Ο διαχωρισμός από άλλα αντικείμενα είναι πολύ εμφανής.
③Όπως φαίνεται από τον Πίνακα 10-15, δεν έχει σημασία κκκΠάρτε 2, 3 ή 5, Χ 1 Χ_1Χ1της περιφέρειας κείμενο dsty{dsty}δστυ οι τιμές είναι σημαντικά χαμηλότερες από Χ 7 Χ_7Χ7της περιφέρειας κείμενο dsty{dsty}δστυ τιμή, η οποία είναι συνεπής με την πυκνότητα επιφάνειας που φαίνεται στο Σχήμα 10-30.Αλλά η σχετική τιμή πυκνότητας των δύο περιοχών OF 2 text{OF}_2ΤΟΥ2 Αλλά δεν υπάρχει σχεδόν καμία προφανής διαφορά. Αυτό καθορίζεται από τη φύση της σχετικής πυκνότητας, δηλαδή, για ομοιόμορφα κατανεμημένα σημεία δεδομένων, η σχετική πυκνότητα των σημείων του πυρήνα είναι 1, ανεξάρτητα από την απόσταση μεταξύ των σημείων.

7. Άλλες μέθοδοι ομαδοποίησης

1. Βελτιωμένος αλγόριθμος ομαδοποίησης

  (1) κκκ-mod ( κκκ-modes) ο αλγόριθμος είναι για κκκ -Ο μέσος αλγόριθμος είναι κατάλληλος μόνο για τον περιορισμό αριθμητικών χαρακτηριστικών και προτείνεται για την επίτευξη ταχείας ομαδοποίησης διακριτών δεδομένων.επειδή κκκ-Ο αρθρωτός αλγόριθμος χρησιμοποιεί μια απλή μέθοδο αντιστοίχισης 0-1 για τον υπολογισμό της απόστασης μεταξύ δύο τιμών χαρακτηριστικών κάτω από την ίδια διακριτή ιδιότητα, η οποία αποδυναμώνει τη διαφορά μεταξύ των τακτικών τιμών χαρακτηριστικών, δηλαδή δεν μπορεί να αντικατοπτρίζει πλήρως τη διαφορά μεταξύ δύο τιμών χαρακτηριστικών κάτω από την ίδια τακτική ιδιότητα Υπάρχει ακόμα χώρος για βελτίωση και βελτίωση.
  (2) κκκ-πρωτότυπο ( κκκ-Πρωτότυπο) αλγόριθμος σε συνδυασμό με κκκ-Μέσος αλγόριθμος με κκκ -Το πλεονέκτημα του αρθρωτού αλγορίθμου είναι ότι μπορεί να ομαδοποιήσει σύνολα δεδομένων τόσο με διακριτά όσο και με αριθμητικά χαρακτηριστικά (που ονομάζονται μικτά χαρακτηριστικά).Απαιτείται για διακριτές ιδιότητες κκκ-Αντικείμενο υπολογισμού αρθρωτών αλγορίθμων XXΧκαι YYΥτην απόσταση μεταξύ d 1 ( X , Y ) d_1 (X,Y)ρε1(Χ,Υ), για αριθμητικά χαρακτηριστικά, χρησιμοποιήστε κκκ-Μέθοδοι στον αλγόριθμο υπολογισμού μέσου όρου υπολογίζουν την απόσταση μεταξύ των αντικειμένων d 2 ( X , Y ) d_2 (X,Y)ρε2(Χ,Υ), και τέλος χρησιμοποιήστε τη μέθοδο στάθμισης, δηλαδή α d 1 ( X , Y ) + ( 1 − α ) d 2 ( X , Y ) άλφα d_1(X,Y)+(1-άλφα)d_2(X,Y)αρε1(Χ,Υ)+(1α)ρε2(Χ,Υ) ως αντικείμενο συνόλου δεδομένων XXΧκαι YYΥτην απόσταση μεταξύ d ( X , Y ) d(X,Y)ρε(Χ,Υ),σε α ∈ [ 0 , 1 ] αλφαίν[0,1]α[0,1] είναι ο συντελεστής βάρους, συνήθως μπορεί να είναι α = 0,5 άλφα=0,5α=0.5
(3) Ο αλγόριθμος BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) είναι μια ολοκληρωμένη μέθοδος ιεραρχικής ομαδοποίησης.Χρησιμοποιεί τα χαρακτηριστικά ομαδοποίησης (CF) και το δέντρο χαρακτηριστικών ομαδοποίησης (Δέντρο CF, παρόμοιο με το Β-δέντρο) για να συνοψίσει τα συμπλέγματα των συστάδων. C i C_iντοΕγώ,σε CF i = ( ni , LS i , SS i ) text{CF}_i=(ni, text{LS}_i,text{SS}_i)CFΕγώ=(ni,LSΕγώ,SSΕγώ) είναι τρίδυμο, ni n_inΕγώείναι ο αριθμός των αντικειμένων στο σύμπλεγμα, LS i text{LS}_iLSΕγώΝαί ni n_inΕγώγραμμικό άθροισμα συστατικών αντικειμένων, SS i κείμενο{SS}_iSSΕγώΝαί ni n_inΕγώΤο άθροισμα των τετραγώνων των συστατικών ενός αντικειμένου.
(4) Ο αλγόριθμος CURE (Clustering Using Representatives) είναι για κκκ -Άλλη μια βελτίωση στον αλγόριθμο υπολογισμού του μέσου όρου. Πολλοί αλγόριθμοι ομαδοποίησης είναι καλοί μόνο στη ομαδοποίηση σφαιρικών συστάδων, ενώ ορισμένοι αλγόριθμοι ομαδοποίησης είναι πιο ευαίσθητοι σε μεμονωμένα σημεία. Για την επίλυση των δύο παραπάνω προβλημάτων, ο αλγόριθμος CURE έχει αλλάξει κκκ-Ο αλγόριθμος μέσου όρου χρησιμοποιεί άθροισμα κέντρου συμπλέγματος κκκ-Ο αλγόριθμος κεντρικού σημείου χρησιμοποιεί ένα συγκεκριμένο αντικείμενο για να αναπαραστήσει ένα σύμπλεγμα, μια παραδοσιακή μέθοδο, αλλά χρησιμοποιεί πολλαπλά αντιπροσωπευτικά αντικείμενα στο σύμπλεγμα για να αναπαραστήσει ένα σύμπλεγμα, έτσι ώστε να μπορεί να προσαρμοστεί στη ομαδοποίηση μη σφαιρικών συστάδων και να μειώσει τον αντίκτυπο του θόρυβος κατά την ομαδοποίηση.
(5) Ο αλγόριθμος ROCK (RObust Clustering using linkK) είναι ένας αλγόριθμος ομαδοποίησης που προτείνεται για δυαδικά ή κατηγορικά σύνολα δεδομένων χαρακτηριστικών.
(6) Ο αλγόριθμος OPTICS (Ordering Points To Identify the Clustering Structure) χρησιμοποιείται για τη μείωση της πυκνότητας του αλγορίθμου DBSCAN. ( ε , MinPts ) (varepsilon,text{MinPts})(ε,MinPts) ευαισθησία παραμέτρων. Δεν δημιουργεί ρητά συμπλέγματα αποτελεσμάτων, αλλά δημιουργεί μια επαυξημένη κατάταξη συμπλέγματος για ανάλυση συμπλέγματος (για παράδειγμα, ένα γράφημα συντεταγμένων με προσβάσιμη απόσταση ως κατακόρυφο άξονα και τη σειρά εξόδου σημείου δείγματος ως οριζόντιος άξονας). Αυτή η κατάταξη αντιπροσωπεύει τη δομή ομαδοποίησης με βάση την πυκνότητα κάθε σημείου δείγματος.Μπορούμε να πάρουμε από αυτήν την ταξινόμηση με βάση οποιαδήποτε παράμετρο πυκνότητας ( ε , MinPts ) (varepsilon,text{MinPts})(ε,MinPts) Ομαδοποίηση αποτελεσμάτων του αλγόριθμου DBSCAN.

2. Άλλες νέες μέθοδοι ομαδοποίησης

Χρησιμοποιήστε μερικές νέες θεωρίες ή τεχνικές για να σχεδιάσετε νέες μεθόδους ομαδοποίησης.

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

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

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

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

3. Άλλες ακραίες μέθοδοι εξόρυξης

Οι ακραίες μέθοδοι εξόρυξης που εισήχθησαν προηγουμένως είναι μόνο δύο εκπρόσωποι της εξόρυξης ακραίων στοιχείων γωνίες: βαθμός.

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

(2) Αξιοποίηση προγενέστερων γνώσεων
Ανάλογα με τη διαθεσιμότητα κανονικών ή ακραίων πληροφοριών κατηγορίας, υπάρχουν τρεις κοινές προσεγγίσεις:
① Μέθοδος ανίχνευσης ακραίων στοιχείων χωρίς επίβλεψη, δηλαδή, δεν υπάρχει προηγούμενη γνώση, όπως ετικέτες κατηγορίας στο σύνολο δεδομένων.
② Εποπτευόμενη μέθοδος ανίχνευσης ακραίων σημείων, δηλαδή εξαγωγή των χαρακτηριστικών των ακραίων σημείων μέσω της ύπαρξης ενός συνόλου εκπαίδευσης που περιέχει ακραία σημεία και κανονικά σημεία.
③ Ημι-εποπτευόμενη μέθοδος ανίχνευσης ακραίων στοιχείων Τα δεδομένα εκπαίδευσης περιέχουν επισημασμένα κανονικά δεδομένα, αλλά δεν υπάρχουν πληροφορίες σχετικά με αντικείμενα ακραίων στοιχείων.