Condivisione della tecnologia

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

---

5. Valutazione della qualità del clustering

L'analisi dei cluster consiste nel scomporre un set di dati in sottoinsiemi, ciascun sottoinsieme è chiamato cluster e l'insieme di tutti i sottoinsiemi è chiamato cluster dell'insieme di oggetti. Un buon algoritmo di clustering dovrebbe produrre cluster di alta qualità e cluster di alta qualità, ovvero la somiglianza complessiva all'interno dei cluster è la più alta, mentre la somiglianza complessiva tra i cluster è la più bassa.Dato che molti algoritmi di clustering includono$K$-L'algoritmo di media, l'algoritmo DBSCAN, ecc. richiedono tutti che l'utente specifichi in anticipo il numero di cluster nel cluster$K$, pertanto, il metodo di stima semplice di k verrà discusso di seguito.

(1) Stima del numero di cluster

Molti algoritmi di clustering come $K$-Gli algoritmi di media, anche gli algoritmi DIANA, ecc., devono specificare in anticipo il numero di cluster$K$,E$K$Il valore di influenzerà notevolmente la qualità del clustering. Tuttavia, il numero di cluster deve essere determinato in anticipo.$K$ Non è un compito facile. Possiamo innanzitutto considerare due casi estremi.
(1) Inserisci l'intero set di dati$S$considerato come un cluster, cioè $K=1$, questo sembra semplice e conveniente, ma i risultati di questa analisi dei cluster non hanno alcun valore.
(2) Inserisci il set di dati$S$Ogni oggetto di viene trattato come un cluster, cioè let $K=|S|=N$ , producendo così il clustering a grana più fine. Pertanto, non vi è alcuna differenza all'interno del cluster in ciascun cluster e la somiglianza all'interno del cluster raggiunge il livello più elevato.Ma questo tipo di clustering non può essere utilizzato$S$fornire qualsiasi informazione in merito$S$una descrizione generale.
Si può vedere che il numero di cluster$K$dovrebbe almeno soddisfare $2\le K\le N-1$, ma il numero di cluster$K$Quale sia esattamente il valore più appropriato rimane ambiguo.
Generalmente considerato,$K$Il valore di può essere stimato dalla forma e dalla scala della distribuzione del set di dati, nonché dalla risoluzione del clustering richiesta dall'utente, e gli studiosi hanno molti metodi di stima diversi, come il metodo del gomito, il metodo di convalida incrociata e la teoria dell'informazione. metodi basati ecc.
Un semplice e comunemente usato$K$Il metodo di stima empirica del valore ritiene che per quelli con$N$Un set di dati di oggetti, il numero di cluster in cui è raggruppato$K$Scegliere $\begin{array}{r}\sqrt{\frac{N}{2}}\end{array}$ È appropriato.In questo momento, sotto l'aspettativa media, ogni cluster ha circa$\sqrt{2N}$ oggetti.Su questa base c'è chi ha proposto un'ulteriore restrizione aggiuntiva, ovvero il numero dei cluster$K<\sqrt{N}$。
Ad esempio, supponiamo$N=8$, quindi il numero di cluster $K=2$ è appropriato, e in media ci sono 4 punti per cluster, e secondo la formula empirica aggiuntiva$K<2.83$ .Utilizzando queste due informazioni sul numero di cluster$K$La formula empirica sembra essere spiegata da un lato, nell'Esempio 10-5 $K=2$ è il numero di cluster più appropriato.

(2) Valutazione esterna della qualità

Se abbiamo una buona stima del numero di cluster$K$, puoi utilizzare uno o più metodi di clustering, ad esempio$K$ -L'algoritmo medio, l'algoritmo gerarchico agglomerativo o l'algoritmo DBSCAN esegue l'analisi dei cluster su set di dati noti e ottiene una varietà di risultati di clustering diversi. La domanda ora è quale metodo offre risultati di clustering migliori o, in altre parole, come confrontare i risultati di clustering prodotti da metodi diversi. Questa è la valutazione della qualità del clustering.
Al momento, ci sono molti metodi tra cui scegliere per la valutazione della qualità del clustering, ma generalmente possono essere suddivisi in due categorie, vale a dire la valutazione della qualità esterna (estrinseca) e la valutazione della qualità interna (intrinseca).
La valutazione della qualità esterna presuppone che esista già un cluster ideale nel set di dati (solitamente costruito da esperti) e lo confronta come metodo di riferimento comunemente utilizzato con i risultati di clustering di un determinato algoritmo. La sua valutazione comparativa include principalmente l'entropia del clustering e il clustering sono due metodi comuni per la precisione della classe.

1. Metodo dell'entropia del clustering

insieme di dati ipotetici S = { X 1 , X 2 , … , X n } S={X_1,X_2,…,X_n}S={X1​,X2​,…,XN​},E T = {T1, T2, …, Tm} T={T_1,T_2,…,T_m}T={T1​,T2​,…,TM​} è il clustering standard ideale fornito dagli esperti e C = {C1, C2, …, Ck} C={C_1,C_2,…,C_k}C={C1​,C2​,…,CK​} è determinato da un algoritmo circa$S$Un cluster di , quindi per il cluster$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$Rispetto al clustering di base$T$L'entropia di clustering di è definita come
$$E(C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|T)=-\sum _{J=1}^M\frac{|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}\cap T_J|}{|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|}{\mathrm{IoG}}_2\frac{|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}\cap T_J|}{|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|}\text{\hspace{1em}(10-20)}$$ E$C$A proposito di benchmark$T$L'entropia complessiva del clustering è definita come tutti i cluster$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$A proposito di benchmark$T$La media ponderata dell'entropia del clustering, cioè
$$E(C)=\frac{1}{\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|}\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|\times E(C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|T)\text{\hspace{1em}(10-21)}$$ Il metodo dell’entropia del clustering ritiene che,$E(C)$ Minore è il valore, il$C$Rispetto al basale$T$Maggiore è la qualità del clustering.
Vale la pena notare che il denominatore del primo termine sul lato destro della formula (10-21)$\begin{array}{r}\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|\end{array}$ è la somma del numero di elementi in ciascun cluster e non può essere utilizzato$N$ Rimpiazzare.Perché, solo quando$C$Quando è un cluster di partizionamento, il denominatore è$N$e il denominatore dei metodi di clustering generali, come il clustering DBSCAN, potrebbe essere inferiore a$N$。

2. Precisione del clustering

L'idea di base della valutazione dell'accuratezza (precisione) del clustering è quella di utilizzare il maggior numero di categorie nel cluster come etichetta di categoria del cluster, ovvero per il cluster$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$,se esiste$T_J$Fare ∣ C i ∩ T j ∣ = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_j|=max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩TJ​∣=massimo{∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩T1​∣,∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩T2​∣,⋯,∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩TM​∣}, si ritiene che$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$La categoria è$T_J$ .Pertanto, il cluster$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$A proposito di benchmark$T$La precisione è definita come
J ( C i ∣ T ) = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } ∣ C i ∣ (10-22) J(C_i|T)=frac{max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}tag{10-22}J(Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∣T)=∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∣massimo{∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩T1​∣,∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩T2​∣,⋯,∣Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​∩TM​∣}​(10-22) E$C$A proposito di benchmark$T$La precisione complessiva di è definita per tutti i cluster$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$A proposito di benchmark$T$Cioè, la media ponderata dell'accuratezza del clustering
$$J(C)=\frac{1}{\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|}\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|\times J(C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|T)\text{\hspace{1em}(10-23)}$$ Il metodo dell'accuratezza del clustering ritiene che,$J(C)$ Maggiore è il valore, maggiore è il clustering$C$Rispetto al basale$T$Maggiore è la qualità del clustering.
Inoltre, in generale$1-J(C)$ chiamato$C$A proposito di benchmark$T$ tasso di errore complessivo.Pertanto, la precisione del clustering$J(C)$ Tasso di errore ampio o complessivo$1-J(C)$ Piccolo, mostra che l'algoritmo di clustering può raggruppare meglio oggetti di diverse categorie in cluster diversi, ovvero la precisione del clustering è elevata.

(3) Valutazione interna della qualità

Non sono noti parametri di riferimento esterni per la valutazione interna della qualità, vengono utilizzati solo set di dati$S$e raggruppamento$C$Valutare le caratteristiche intrinseche e le dimensioni di un cluster$C$ La qualità di. Cioè, l'effetto di clustering viene generalmente valutato calcolando la somiglianza media all'interno dei cluster, la somiglianza media tra i cluster o la somiglianza complessiva.
La valutazione della qualità interna è correlata all'algoritmo di clustering. L'indice di efficacia del clustering viene utilizzato principalmente per valutare la qualità dell'effetto di clustering o per giudicare il numero ottimale di cluster. L'effetto di clustering ideale è avere la distanza intra-cluster più piccola e il cluster più grande. Pertanto, l'efficacia del clustering è generalmente misurata da una qualche forma di rapporto tra la distanza intra-cluster e la distanza tra cluster. Gli indicatori comunemente usati di questo tipo includono l'indicatore CH, l'indicatore Dunn, l'indicatore I, l'indicatore Xie-eni, ecc.

1. Indicatore CH

L'indice CH è l'abbreviazione dell'indice Calinski-Harabasz Calcola prima la somma dei quadrati della distanza tra ciascun punto del cluster e il suo centro del cluster per misurare la vicinanza all'interno della classe, quindi calcola la somma dei quadrati della distanza tra ciascun punto centrale del cluster e il punto centrale del set di dati da misurare La separazione del set di dati e il rapporto tra separazione e vicinanza è l'indice CH.
impostare${\overline{X}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$rappresenta un cluster$C$punto centrale (media),$\overline{X}$rappresenta un set di dati$S$il punto centrale di$D({\overline{X}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},\overline{X})$ per${\overline{X}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$arrivare$\overline{X}$Una certa funzione di distanza di , quindi raggruppamento$C$La compattezza di un cluster medio è definita come
$$\text{Traccia}(UN)=\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K\sum _{X_J\in C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}}D(X_J,{\overline{X}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}{)}^2\text{\hspace{1em}(10-24)}$$ Pertanto, Traccia(A) è il cluster$C$ La somma delle distanze quadrate tra i centri dei cluster.E raggruppamento$C$Il grado di separazione è definito come
$$\text{Traccia}(B)=\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|D({\overline{X}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},\overline{X}{)}^2\text{\hspace{1em}(10-25)}$$ Cioè, Trace(B) sta raggruppando$C$Ogni punto centrale del cluster di$S$La somma ponderata delle distanze quadrate dal punto centrale di .
Da questo, se$\begin{array}{r}N=\sum _{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=1}^K|C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}|\end{array}$ Quindi l'indicatore CH può essere definito come
$$E_{\text{CH}}(K)=\frac{\text{Traccia}(B)/(K-1)}{\text{Traccia}(UN)/(N-K)}\text{\hspace{1em}(10-26)}$$ La formula (10-26) viene generalmente utilizzata nelle due situazioni seguenti:
(1) Valutare quale clustering ottenuto dai due algoritmi è migliore.
Supponiamo che vengano utilizzati due algoritmi per analizzare il set di dati$S$È stata eseguita l'analisi dei cluster e sono stati rilevati due cluster diversi (entrambi contenenti$K$cluster), il clustering corrispondente al valore CH più grande è migliore, perché maggiore è il valore CH significa che ogni cluster nel cluster è più vicino a se stesso e i cluster sono più dispersi.
(2) Valutare quale dei due cluster con numero diverso di cluster ottenuti dallo stesso algoritmo è migliore.
Supponiamo che un algoritmo abbia un set di dati$S$È stata eseguita l'analisi dei cluster e il numero di cluster è stato ottenuto come$K_1$E$B_2$ Dei due cluster, il risultato del clustering con un valore CH maggiore è migliore, il che significa anche che il numero di cluster corrispondente a questo cluster è più appropriato.Pertanto, applicando ripetutamente la formula (10-26), possiamo ottenere anche un set di dati$S$Il numero ottimale di cluster per il clustering.

2. Indicatore Dunn

L'indicatore Dunn utilizza i cluster$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$con grappolo$C_J$distanza minima tra $D_S(C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},C_J)$ per calcolare la separazione tra cluster utilizzando il diametro del cluster maggiore tra tutti i cluster max ⁡ {Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } max{varPhi(C_1), varPhi(C_2),...,varPhi(C_k)}massimo{Φ(C1​),Φ(C2​),...,Φ(CK​)} Per caratterizzare la tenuta all'interno di un cluster, l'indice di Dunn è il valore minimo del rapporto tra il primo e il secondo, ovvero
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)}}etichetta{10-27}ED​(K)=ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo=Jminimo​massimo{Φ(C1​),Φ(C2​),...,Φ(CK​)}DS​(Cioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo​,CJ​)​(10-27) Maggiore è il valore Dunn, maggiore è la distanza tra i cluster e migliore è il clustering corrispondente.Similmente all'indice di valutazione CH, l'indice di Dunn può essere utilizzato per valutare la qualità dei cluster ottenuti da algoritmi diversi, e può anche essere utilizzato per valutare quali cluster ottenuti dallo stesso algoritmo con un numero diverso di cluster sono migliori, ovvero può essere usato per cercare$S$il numero ottimale di cluster.

6. Estrazione anomala

I valori anomali sono dati speciali nel set di dati che si discostano in modo significativo dalla maggior parte dei dati. L'obiettivo degli algoritmi di data mining come la classificazione e il clustering introdotti in precedenza è quello di scoprire modelli regolari che si applicano alla maggior parte dei dati. Pertanto, molti algoritmi di data mining tentano di ridurre o eliminare l'impatto dei valori anomali e di trattare i valori anomali durante l'implementazione dei punti di data mining o ignorati come rumore, ma in molte applicazioni pratiche, le persone sospettano che la deviazione dei punti anomali non sia causata da fattori casuali, ma possa essere causata da altri meccanismi completamente diversi, che devono essere estratti per analisi e utilizzi speciali. Ad esempio, in campi applicativi come la gestione della sicurezza e il controllo dei rischi, il modello di identificazione dei valori anomali è più prezioso del modello dei dati normali.

(1) Panoramica delle questioni correlate

La parola Outlier viene solitamente tradotta come valore anomalo, ma anche come anomalia. Tuttavia, esistono molti alias in diverse situazioni applicative, come punti isolati, punti anomali, punti nuovi, punti di deviazione, punti di eccezione, rumore, dati anomali, ecc. L'estrazione di dati anomali ha termini simili come estrazione di dati di anomalie, rilevamento di dati di anomalie, estrazione di dati anomali, estrazione di dati di eccezioni ed estrazione di eventi rari nella letteratura cinese.

1. La generazione di valori anomali

(1) I dati provengono da anomalie causate da frodi, intrusioni, epidemie, risultati sperimentali insoliti, ecc. Ad esempio, la bolletta telefonica media di qualcuno è di circa 200 yuan, ma in un certo mese aumenta improvvisamente fino a diverse migliaia di yuan; la carta di credito di qualcuno di solito consuma circa 5.000 yuan al mese, ma in un certo mese il consumo supera i 30.000 yuan, ecc. Tali valori anomali sono generalmente relativamente interessanti nel data mining e rappresentano uno dei punti chiave di applicazione.
(2) Causato da cambiamenti intrinseci nelle variabili dei dati, che riflettono le caratteristiche naturali della distribuzione dei dati, come il cambiamento climatico, nuovi modelli di acquisto dei clienti, mutazioni genetiche, ecc. Anche una delle aree di interesse interessanti.
(3) Gli errori di misurazione e raccolta dei dati sono dovuti principalmente a errori umani, guasti alle apparecchiature di misurazione o presenza di rumore. Ad esempio, il voto -100 di uno studente in un determinato corso potrebbe essere dovuto al valore predefinito impostato dal programma; lo stipendio dei top manager di un'azienda è significativamente più alto dello stipendio dei dipendenti ordinari può sembrare un'anomalia, ma lo è Dati ragionevoli.

2. Problema di mining anomalo

Di solito, il problema del mining anomalo può essere scomposto in tre sottoproblemi da descrivere.
(1) Definire i valori anomali
Poiché gli outlier sono strettamente correlati a problemi pratici, definire chiaramente che tipo di dati sono outlier o dati anomali è la premessa e il compito principale dell'outlier mining. In generale, è necessario combinare l'esperienza e la conoscenza degli esperti del settore per fornire indicazioni in merito valori anomali. Fornire una descrizione o definizione appropriata.
(2) Valori anomali del mining
Dopo che i punti anomali sono stati chiaramente definiti, quale algoritmo utilizzare per identificare o estrarre in modo efficace i punti anomali definiti è il compito chiave dell'estrazione degli outlier. L'algoritmo di mining anomalo di solito fornisce agli utenti dati anomali sospetti dal punto di vista dei modelli che possono riflettersi nei dati, in modo da attirare l'attenzione dell'utente.
(3) Comprendere i valori anomali
Spiegazione ragionevole, comprensione e guida per l'applicazione pratica dei risultati del mining sono gli obiettivi del mining anomalo. Poiché il meccanismo mediante il quale vengono generati i valori anomali è incerto, se i "valori anomali" rilevati dall'algoritmo di mining dei valori anomali corrispondono effettivamente al comportamento anomalo effettivo non può essere spiegato e spiegato dall'algoritmo di mining dei valori anomali, ma può essere spiegato solo dall'algoritmo di mining dei valori anomali. Esperti del settore o del settore per comprendere e spiegare le istruzioni.

3. Relatività degli outlier

I valori anomali sono dati speciali nel set di dati che ovviamente si discostano dalla maggior parte dei dati, ma "ovviamente" e "principalmente" sono relativi, ovvero, sebbene i valori anomali siano diversi, sono relativi. Pertanto, ci sono diversi problemi da considerare quando si definiscono e si estraggono valori anomali.
(1) Valori anomali globali o locali
Un oggetto dati può essere un valore anomalo rispetto ai suoi vicini locali ma non rispetto all'intero set di dati. Ad esempio, uno studente alto 1,9 metri è un valore anomalo nella Classe 1 della specializzazione in matematica della nostra scuola, ma non è un valore anomalo tra le persone in tutto il paese, compresi i giocatori professionisti come Yao Ming.
(2) Numero di valori anomali
Sebbene il numero di punti anomali sia sconosciuto, il numero di punti normali dovrebbe superare di gran lunga il numero di punti anomali, ovvero il numero di punti anomali dovrebbe rappresentare una proporzione inferiore nell'insieme di dati di grandi dimensioni di punti anomali Dovrebbe essere inferiore al 5% o addirittura inferiore all'1%.
(3) Fattore anomalo del punto
Non è possibile utilizzare "sì" o "no" per segnalare se un oggetto è un valore anomalo, è invece necessario utilizzare il grado di deviazione dell'oggetto, ovvero il fattore anomalo (Outlier Factor) o il punteggio anomalo (Outlier Score). caratterizzare la deviazione di un dato dal grado del gruppo, quindi filtrare gli oggetti con fattori anomali superiori a una certa soglia, fornirli ai decisori o agli esperti del settore per la comprensione e la spiegazione e applicarli nel lavoro pratico.

(2) Metodo basato sulla distanza

1. Concetti di base

Definizione 10-11 C'è un numero intero positivo$K$, oggetto$X$Di $K$-La distanza del vicino più vicino è un numero intero positivo che soddisfa le seguenti condizioni $D_K(X)$：
(1) tranne$X$Inoltre, ce ne sono almeno$K$oggetti$E$soddisfare $D(X,E)\le D_K(X)$。
(2) tranne$X$Inoltre, ce ne sono al massimo $K-1$ oggetti$E$soddisfare $D(X,E)<D_K(X)$。
In$D(X,E)$ è un oggetto$X$E$E$una certa funzione di distanza tra loro.

di un oggetto $K$-Maggiore è la distanza del vicino più vicino, più è probabile che l'oggetto sia lontano dalla maggior parte dei dati, quindi l'oggetto può essere$X$Di $K$-distanza del vicino più vicino $D_K(X)$ come fattore anomalo.

Definizione 10-12 Fare D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)cuneo Y≠X}D(X,K)={E∣D(X,E)≤DK​(X)∧E=X}, quindi viene chiamato $D(X,K)$ SÌ$X$Di $K$-Vicino più vicino (dominio).

Dalla definizione 10-12 si può vedere che$D(X,K)$ SÌ$X$come centro, distanza$X$Non eccede $D_K(X)$ Oggetto$E$ La collezione composta da. Vale la pena prestare particolare attenzione,$X$non gli appartiene $K$-vicino più vicino, ad es. $X\notin D(X,K)$ . In particolare,$X$Di $K$-Il vicino più prossimo $D(X,K)$ Il numero di oggetti contenuti può superare di gran lunga$K$,Proprio adesso $|D(X,K)|\ge K$。

Definizione 10-13 C'è un numero intero positivo$K$, oggetto$X$Di $K$-Il fattore anomalo del vicino più vicino è definito come
$${\text{DI}}_1(X,K)=\frac{\sum _{E\in D(X,K)}D(X,E)}{|D(X,K)|}\text{\hspace{1em}(10-28)}$$

2. Descrizione dell'algoritmo

Per un dato set di dati e il numero di distanze del vicino più vicino$K$, possiamo usare la formula sopra per calcolare il$K$-Fattori anomali dei vicini più vicini e visualizzarli in ordine dal grande al piccolo. Tra questi, è più probabile che diversi oggetti con fattori anomali più grandi siano anomali. In genere, devono essere analizzati e giudicati da decisori o esperti del settore , Quali punti sono davvero anomali.

Algoritmo 10-8 Algoritmo di rilevamento dei valori anomali basato sulla distanza
Ingresso: set di dati$S$, il numero delle distanze del vicino più vicino$K$
Risultato: elenco decrescente di punti anomali sospetti e corrispondenti fattori anomali
（1）RIPETI
(2) Prendi$S$un oggetto non elaborato in$X$
(3)Va bene$X$Di$K$-Il vicino più prossimo$D(X,K)$
(4) Calcolo$X$Di$K$-fattore anomalo del vicino più vicino${\text{DI}}_1(X,K)$
（5）FINO A$S$Ogni punto è stato elaborato
(6) Sì${\text{DI}}_1(X,K)$Ordina in ordine decrescente e output$(X,{\text{DI}}_1(X,K))$

3. Esempi di calcolo

Esempio 10-12 Un set di dati bidimensionale con 11 punti$S$È dato dalla Tabella 10-10, lett$K=2$, utilizzare il calcolo della distanza euclidea al quadrato $X_7,X_{10},X_{11}$ Fattore anomalo rispetto a tutti gli altri punti.

sciogliere: Per comprendere intuitivamente il principio dell'algoritmo, lo faremo$S$Gli oggetti dati sono visualizzati sul piano nella Figura (10-27) di seguito.

I fattori anomali del punto specificato e degli altri punti vengono calcolati separatamente di seguito.

(1) Oggetto di calcolo$X_7$fattore anomalo
Come si può vedere dalla figura, la distanza$X_7=(6,8)$ Il punto più vicino è$X_{10}=(5,7)$,E $D(X_7,X_{10})=1.41$, potrebbero esserci altri punti più vicini $X_{11}=(5,2)$，$X_9=(3,2)$，$X_8=(2,4)$；
Calcolato$D(X_7,X_{11})=6.08$，$D(X_7,X_9)=6.71$，$D(X_7,X_8)=5.66$
Perché$K=2$,COSÌ $D_2(X_7)=5.66$, quindi secondo la definizione 10-11 abbiamo D(X7,2)={X10,X8}D(X7​,2)={X10​,X8​}
Secondo la formula (10-28),$X_7$fattore anomalo
$$\begin{array}{rl}{\text{DI}}_1(X_7,2)& =\frac{\sum _{E\in N(X_7,2)}D(X_7,E)}{|N(X_7,K)|}=\frac{D(X_7,X_{10})+D(X_7,X_8)}{2}\\ & =\frac{1.41+5.66}{2}=3.54\end{array}$$(2) Oggetto di calcolo$X_{10}$fattore anomalo ${\text{DI}}_1(X_{10},2)=2.83$

(3) Oggetto di calcolo$X_{11}$fattore anomalo ${\text{DI}}_1(X_{11},2)=2.5$

(4) Oggetto di calcolo$X_5$fattore anomalo ${\text{DI}}_1(X_5,2)=1$

Allo stesso modo, è possibile calcolare i fattori anomali degli oggetti rimanenti, vedere la tabella seguente (10-11).

4. Soglia del fattore anomalo

secondo$K$ -Secondo la teoria del vicino più vicino, maggiore è il fattore anomalo, maggiore è la probabilità che si tratti di un valore anomalo. Pertanto, è necessario specificare una soglia per distinguere gli outlier dai punti normali. Il metodo più semplice consiste nel specificare il numero di punti anomali, ma questo metodo è troppo semplice e a volte trascura alcuni punti anomali reali o attribuisce troppi punti normali a possibili punti anomali, il che rende difficile per gli esperti del settore o i decisori sorgere difficoltà nella comprensione e interpretazione dei valori anomali.
(1) Il metodo della soglia di segmentazione dei fattori anomali dispone innanzitutto i fattori anomali in ordine decrescente e allo stesso tempo rinumera gli oggetti dati in ordine crescente in base ai fattori anomali.
(2) Basato sul fattore anomalo${\text{DI}}_1(X,K)$ è l'ordinata e il numero di serie del fattore anomalo è l'ascissa, ovvero (numero di serie,${\text{DI}}_1$valore) sono contrassegnati sul piano e collegati per formare una polilinea non crescente, e il punto in cui la polilinea si interseca con un forte calo e un leggero calo corrisponde al fattore anomalo come soglia Oggetti con un fattore anomalo inferiore superiori o uguali a questa soglia sono oggetti normali, gli altri sono possibili valori anomali.

Esempio 10-13 Set di dati per l'esempio 10-12$S$ , i suoi fattori anomali sono riepilogati in ordine decrescente e numero di serie nella Tabella 10-11. Prova a trovare la soglia dei punti anomali in base al metodo della soglia di segmentazione del fattore anomalo.

sciogliere: Innanzitutto, utilizzare il (numero di serie, ${\text{DI}}_1$ valore) come punti sul piano, contrassegnati sul piano e collegati da polilinee. Come mostrato nella Figura 10-28 di seguito.

Poi guardando la Figura 10-28, possiamo scoprire che la polilinea a sinistra del quarto punto (4, 1.27) scende molto ripidamente, mentre la polilinea a destra scende molto dolcemente. Pertanto, il fattore anomalo 1.27 viene selezionato come soglia.Perché$X_7、X_{10}$ E$X_{11}$ I fattori anomali sono rispettivamente 3,54, 2,83 e 2,5, che sono tutti maggiori di 1,27. Pertanto, è molto probabile che questi tre punti siano punti anomali, mentre i punti rimanenti sono punti ordinari.
Osservando nuovamente la Figura 10-27, possiamo trovarlo$X_7、X_{10}$ E$X_{11}$ anzi molto lontano dalla densa maggioranza degli oggetti a sinistra, quindi trattali come un set di dati$S$I valori anomali sono ragionevoli.

5. Valutazione dell'algoritmo

Il più grande vantaggio del metodo di rilevamento dei valori anomali basato sulla distanza è che è semplice in linea di principio e facile da usare. I suoi difetti si riflettono principalmente nei seguenti aspetti.
(1) Parametri$K$La selezione manca di un metodo semplice ed efficace per determinare l'impatto dei risultati dei test sui parametri$K$Non esiste un risultato analitico universalmente accettato sul grado di sensibilità.
(2) La complessità temporale è$Lo(|S{|}^2)$, manca di scalabilità per set di dati su larga scala.
(3) A causa dell'uso di una soglia di fattore anomalo globale, è difficile estrarre valori anomali in set di dati con regioni di densità diverse.

(3) Metodo basato sulla densità relativa

Il metodo della distanza è un metodo di controllo dei valori anomali globali, ma non può gestire set di dati in aree di densità diverse, ovvero non può rilevare valori anomali in aree di densità locale. Nelle applicazioni pratiche, i dati non sono tutti distribuiti con un'unica densità. Quando il set di dati contiene più distribuzioni di densità o è una miscela di diversi sottoinsiemi di densità, i metodi di rilevamento dei valori anomali globali come la distanza di solito non funzionano bene, perché se un oggetto è un valore anomalo dipende non solo dalla sua relazione con i dati circostanti è legato alla densità del quartiere.

1. Il concetto di densità relativa

Dal punto di vista del quartiere di densità, i valori anomali sono oggetti in aree a bassa densità, pertanto, è necessario introdurre i concetti di densità di quartiere locale e densità relativa degli oggetti.

Definizione 10-14 (1) un oggetto$X$Di$K$-La densità locale del vicino più vicino (densità) è definita come
$$\text{DISTANZA}(X,K)=\frac{|D(X,K)|}{\sum _{E\in D(X,K)}D(X,E)}\text{\hspace{1em}(10-29)}$$ (2) un oggetto$X$Di$K$-Densità relativa locale del vicino più vicino (densità relativa)
$$\text{in ritardo}(X,K)=\frac{\sum _{E\in D(X,K)}\text{DISTANZA}(X,K)/|D(X,K)|}{\text{DISTANZA}(X,K)}\text{\hspace{1em}(10-30)}$$ In$D(X,K)$ E' l'oggetto$X$Di$K$- il vicino più prossimo (dato nella Definizione 10-12),$|D(X,K)|$ è il numero di oggetti nella raccolta.

2. Descrizione dell'algoritmo

di $\text{in ritardo}(X,K)$ come valore anomalo${\text{DI}}_2(X,K)$, il suo calcolo è diviso in due fasi
(1) In base al numero di vicini$K$, calcola ciascun oggetto$X$Di$K$-Densità locale del vicino più vicino $\text{DISTANZA}(X,K)$
(2) Calcolo$X$la densità media dei vicini più vicini e$K$-Densità relativa locale del vicino più vicino $\text{in ritardo}(X,K)$
Un set di dati è costituito da più cluster naturali. La densità relativa degli oggetti vicini al punto centrale all'interno del cluster è vicina a 1, mentre la densità relativa degli oggetti al bordo del cluster o all'esterno del cluster è relativamente grande. Pertanto, maggiore è il valore della densità relativa, maggiore è la probabilità che si tratti di un valore anomalo.

Algoritmo 10-9 Algoritmo di rilevamento dei valori anomali basato sulla densità relativa
Ingresso: set di dati$S$, il numero dei vicini più prossimi$K$
Risultato: elenco decrescente di punti anomali sospetti e corrispondenti fattori anomali
（1）RIPETI
(2) Prendi$S$un oggetto non elaborato in$X$
(3)Va bene$X$Di$K$-Il vicino più prossimo$D(X,K)$
(4) Utilizzo$D(X,K)$calcolare$X$Densità$\text{DISTANZA}(X,K)$
（5）FINO A$S$Ogni punto è stato elaborato
(6) RIPETI
(7) Prendi$S$primo oggetto in$X$
(8)Va bene$X$densità relativa di$\text{in ritardo}(X,K)$e assegnarlo a${\text{DI}}_2(X,K)$
（9）FINO A$S$Tutti gli oggetti sono stati elaborati
(10) Giusto${\text{DI}}_2(X,K)$Ordina in ordine decrescente e output$(X,{\text{DI}}_2(X,K))$

Esempio 10-14 Per il set di dati bidimensionale fornito nell'Esempio 10-12$S$ (Vedi Tabella 10-10 per i dettagli), quindi$K=2$, prova il calcolo della distanza euclidea $X_7,X_{10},X_{11}$ Fattore anomalo basato sulla densità relativa di oggetti uguali.

sciogliere:Perché$K=2$, quindi abbiamo bisogno della densità locale dei due vicini più vicini di tutti gli oggetti.

(1) Trovare i due vicini più vicini di ciascun oggetto dati nella Tabella 10-11 $D(X_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},2)$。
Secondo lo stesso metodo di calcolo dell'Esempio 10-12, possiamo ottenere
Italiano: 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 } $$begin{aligned} &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} end{aligned}$$ ​D(X1​,2)={X2​,X3​,X5​}，D(X2​,2)={X1​,X6​}，              D(X3​,2)={X1​,X4​}，D(X4​,2)={X3​,X5​}，       D(X5​,2)={X1​,X4​,X6​,X9​}，D(X6​,2)={X2​,X5​,X8​}，D(X7​,2)={X10​,X8​}，     D(X8​,2)={X2​,X6​}，               D(X9​,2)={X5​,X4​,X6​}，D(X10​,2)={X7​,X8​}，     D(X11​,2)={X9​,X5​}​

(2) Calcolare la densità locale di ciascun oggetto dati $\text{DISTANZA}(X_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},2)$：

① Calcola$X_1$Densità
Perché D(X1,2)={X2,X3,X5}D(X1​,2)={X2​,X3​,X5​}, quindi dopo il calcolo, abbiamo $D(X_1,X_2)=1$，$D(X_1,X_3)=1$，$D(X_1,X_5)=1$；
Secondo la formula (10-29), otteniamo:
$$\begin{array}{rl}\text{DISTANZA}(X_1,2)& =\frac{|D(X_1,2)|}{\sum _{E\in N(X_1,2)}D(X_1,E)}\\ & =\frac{|N(X_1,2)|}{D(X_1,X_2)+D(X_1,X_3)+D(X_1,X_5)}\\ & =\frac{3}{1+1+1}=1\end{array}$$

② Calcolo$X_2$Densità
Perché D(X2,2)={X1,X6}D(X2​,2)={X1​,X6​}, quindi il calcolato $D(X_2,X_1)=1$，$D(X_2,X_6)=1$；
Secondo la formula (10-29), otteniamo:
$$\begin{array}{rl}\text{DISTANZA}(X_2,2)& =\frac{|D(X_2,2)|}{\sum _{E\in N(X_2,2)}D(X_2,E)}=\frac{2}{1+1}=1\end{array}$$

La densità locale di altri oggetti dati può essere calcolata in modo simile, vedere la Tabella 10-12 di seguito.

(3) Calcola ciascun oggetto$X_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$densità relativa di $\text{in ritardo}(X_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},2)$e considerarlo un fattore anomalo ${\text{DI}}_2$。
① Calcola$X_1$densità relativa di
Utilizzando il valore di densità di ciascun oggetto nella Tabella 10-12, secondo la formula di densità relativa (10-30):
$$\begin{array}{rl}\text{in ritardo}(X_1,2)& =\frac{\sum _{E\in N(X_1,2)}\text{DISTANZA}(E,2)/|N(X_1,2)|}{\text{DISTANZA}(X_1,2)}\\ & =\frac{(1+1+1)/3}{1}=1={\text{DI}}_2(X_1,2)\end{array}$$

② È possibile ottenere un calcolo simile $X_2、X_3、\dots 、X_{11}$ valore di densità relativa.
Per esempio$X_5$La densità relativa di:
$$\begin{array}{rl}\text{in ritardo}(X_5,2)& =\frac{\sum _{E\in N(X_5,2)}\text{DISTANZA}(E,2)/|N(X_5,2)|}{\text{DISTANZA}(X_5,2)}\\ & =\frac{(1+1+1+0.79)/4}{1}=0.95={\text{DI}}_2(X_5,2)\end{array}$$ I risultati sono riassunti nelle Tabelle 10-13 di seguito.

Esempio 10-15 Considerato il set di dati mostrato nella Tabella 10-14, utilizzare la distanza euclidea da$K=2,3,5$, calcolare il valore di ciascun punto$K$-densità locale del vicino più vicino,$K$-Densità relativa locale del vicino più vicino (fattore anomalo${\text{DI}}_2$) e basato su$K$-Fattore anomalo per la distanza del vicino più vicino${\text{DI}}_1$。

sciogliere: (1) Per facilitare la comprensione, può essere$S$Le posizioni relative dei punti sono segnate sul piano bidimensionale (Figura 10-30).

(2) Utilizzare rispettivamente gli algoritmi 10-8 e 10-9 basati sulla distanza e sulla densità relativa.Calcola ciascun oggetto separatamente$K$-Densità locale del vicino più vicino$\text{DISTANZA}$、$K$-Densità relativa locale del vicino più vicino (fattore anomalo${\text{DI}}_2$) e basato su$K$-Fattore anomalo per la distanza del vicino più vicino${\text{DI}}_1$, i risultati sono riepilogati nella Tabella 10-15.

(3) Analisi semplice
① Come si può vedere dalla Figura 10-30,$X_{15}$E$X_{16}$SÌ$S$Esistono due evidenti valori anomali e i metodi basati sulla distanza e sulla densità relativa possono individuarli meglio;
② Da questo esempio, i due algoritmi hanno$K$non è così sensibile come previsto, forse è un valore anomalo.$X_{15}$E$X_{16}$La separazione dagli altri oggetti è molto evidente.
③Come si può vedere dalla Tabella 10-15, non importa$K$Prendine 2, 3 o 5,$X_1$della regione $\text{DISTANZA}$ i valori sono significativamente inferiori a$X_7$della regione $\text{DISTANZA}$ valore, che è coerente con la densità dell'area mostrata nella Figura 10-30.Ma il valore di densità relativa delle due regioni${\text{DI}}_2$ Ma non c’è quasi alcuna differenza evidente. Ciò è determinato dalla natura della densità relativa, ovvero, per punti dati distribuiti uniformemente, la densità relativa dei punti centrali è 1, indipendentemente dalla distanza tra i punti.

7. Altri metodi di clustering

1. Algoritmo di clustering migliorato

  （1）$K$-mod ($K$-modes) è l'algoritmo per$K$ -L'algoritmo medio è adatto solo per la limitazione degli attributi numerici e si propone di ottenere un rapido clustering di dati discreti.Perché$K$-L'algoritmo modulare utilizza un semplice metodo di corrispondenza 0-1 per calcolare la distanza tra due valori di attributo sotto lo stesso attributo discreto, che indebolisce la differenza tra i valori di attributo ordinali, ovvero non può riflettere completamente la differenza tra due valori di attributo ​​sotto lo stesso attributo ordinale C'è ancora spazio per miglioramenti e miglioramenti.
  （2）$K$-prototipo ($K$-Prototipo) algoritmo combinato con$K$-Algoritmo di media con$K$ -Il vantaggio dell'algoritmo modulare è che può raggruppare set di dati con attributi sia discreti che numerici (chiamati attributi misti).Richiede attributi discreti$K$-Oggetto di calcolo dell'algoritmo modulare$X$E$E$la distanza tra $D_1(X,E)$, per gli attributi numerici, utilizzare$K$-I metodi nell'algoritmo di media calcolano la distanza tra gli oggetti $D_2(X,E)$, e infine utilizzare il metodo della ponderazione, cioè $\alpha D_1(X,E)+(1-\alpha )D_2(X,E)$ come oggetto del set di dati$X$E$E$la distanza tra $D(X,E)$,In $\alpha \in [0,1]$ è il coefficiente di peso, di solito può essere$\alpha =0.5$。
(3) L'algoritmo BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) è un metodo di clustering gerarchico completo.Utilizza Clustering Features (CF) e Clustering Feature Tree (CF Tree, simile al B-tree) per riepilogare i cluster di cluster.$C_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$,In ${\text{CF}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}=(non,{\text{LS}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo},{\text{SS}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo})$ è una tripletta,$N_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$è il numero di oggetti nel cluster,${\text{LS}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$SÌ$N_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$somma lineare dei componenti dell'oggetto,${\text{SS}}_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$SÌ$N_{ioooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$La somma dei quadrati dei componenti di un oggetto.
(4) L'algoritmo CURE (Clustering Using Representatives) è per$K$ -Un altro miglioramento all'algoritmo di media. Molti algoritmi di clustering sono efficaci solo nel raggruppamento di cluster sferici, mentre alcuni algoritmi di clustering sono più sensibili ai punti isolati. Per risolvere i due problemi precedenti, l'algoritmo CURE è cambiato$K$-L'algoritmo di media utilizza la somma del centro del cluster$K$-L'algoritmo del punto centrale utilizza un singolo oggetto specifico per rappresentare un cluster, un metodo tradizionale, ma utilizza più oggetti rappresentativi nel cluster per rappresentare un cluster, in modo che possa adattarsi al raggruppamento di cluster non sferici e ridurre l'impatto di rumore sul clustering.
(5) L'algoritmo ROCK (RObust Clustering using linK) è un algoritmo di clustering proposto per set di dati di attributi binari o categoriali.
(6) L'algoritmo OPTICS (Ordering Points To Identification the Clustering Structure) viene utilizzato per ridurre la densità dell'algoritmo DBSCAN.$(\epsilon ,\text{Punti minimi})$ sensibilità dei parametri. Non genera esplicitamente cluster di risultati, ma genera una classificazione dei cluster aumentata per l'analisi dei cluster (ad esempio, un grafico di coordinate con la distanza raggiungibile come asse verticale e l'ordine di output dei punti campione come asse orizzontale). Questa classifica rappresenta la struttura di clustering basata sulla densità di ciascun punto campione.Possiamo ottenere da questo ordinamento in base a qualsiasi parametro di densità$(\epsilon ,\text{Punti minimi})$ Risultati del clustering dell'algoritmo DBSCAN.

2. Altri nuovi metodi di clustering

Utilizzare alcune nuove teorie o tecniche per progettare nuovi metodi di clustering.

(1) Metodo di clustering basato sulla griglia
Il metodo basato sulla griglia quantifica lo spazio dell'oggetto in un numero limitato di celle per formare una struttura a griglia e le informazioni sulla posizione dei punti di divisione in ciascuna dimensione vengono archiviate nell'array. Le linee di divisione attraversano l'intero spazio e tutto il clustering le operazioni vengono eseguite in Eseguite su questa struttura a griglia (cioè spazio di quantizzazione). Il vantaggio principale di questo metodo è che la sua velocità di elaborazione è molto elevata. La sua velocità di elaborazione è indipendente dal numero di oggetti dati ed è correlata solo al numero di celle in ciascuna dimensione dello spazio di quantificazione a scapito del raggruppamento dei risultati. A scapito della precisione. Poiché l'algoritmo di clustering della griglia presenta il problema della scala di quantificazione, di solito iniziamo a cercare prima i cluster da piccole unità, quindi aumentiamo gradualmente la dimensione delle unità e ripetiamo questo processo finché non vengono trovati cluster soddisfacenti.

(2) Metodo di clustering basato su modello
I metodi basati su modello presuppongono un modello per ciascun cluster e trovano la migliore corrispondenza dei dati con il modello fornito. I metodi basati su modelli tentano di ottimizzare l'adattabilità tra dati dati e determinati modelli di dati stabilendo funzioni di densità che riflettono la distribuzione spaziale dei campioni per individuare i cluster.

(3) Metodo di clustering basato sull'insieme fuzzy
In pratica, non esiste un valore di attribuzione rigoroso a cui appartiene la maggior parte degli oggetti. Esiste un intermediario o incertezza nel valore e nella forma di attribuzione, il che è adatto per il partizionamento morbido. Poiché l'analisi di clustering fuzzy ha il vantaggio di descrivere l'interezza dell'attribuzione del campione e può riflettere oggettivamente il mondo reale, è diventata uno dei punti caldi della ricerca odierna sull'analisi dei cluster.
L'algoritmo di clustering fuzzy è un metodo di apprendimento non supervisionato basato sulla teoria matematica fuzzy e su un metodo di clustering incerto. Una volta proposto, il clustering fuzzy ha ricevuto grande attenzione da parte della comunità accademica. Il clustering fuzzy è una grande "famiglia" di clustering e anche la ricerca sul clustering fuzzy è molto attiva.

(4) Metodo di clustering basato sull'insieme approssimativo
Il clustering approssimativo è un metodo di clustering incerto basato sulla teoria degli insiemi approssimativi. Dal punto di vista dell'accoppiamento tra insiemi approssimativi e algoritmi di clustering, i metodi di clustering approssimativo possono essere suddivisi in due categorie: clustering approssimativo con accoppiamento forte e clustering approssimativo con accoppiamento debole.
Naturalmente, le nuove direzioni di ricerca dell’analisi dei cluster sono molto più di queste. Ad esempio, gli algoritmi di data stream mining e clustering, i dati incerti e i relativi algoritmi di clustering, l’informatica quantistica e gli algoritmi di clustering genetico quantistico sono tutte tecnologie di clustering emerse negli ultimi anni. temi di ricerca all'avanguardia.

3. Altri metodi di mining anomali

I metodi di mining anomali introdotti in precedenza sono solo due rappresentanti del mining anomalo. Esistono molti metodi di mining anomali più maturi nelle applicazioni pratiche. Possono essere determinati dal tipo di tecnologia utilizzata nel metodo di mining o dall'uso delle conoscenze precedenti angoli: gradi.

(1) Tipo di tecnologia utilizzata
Esistono principalmente metodi statistici, metodi basati sulla distanza, metodi basati sulla densità, metodi basati sul clustering, metodi basati sulla deviazione, metodi basati sulla profondità, metodi basati sulla trasformazione wavelet, metodi basati su grafici, metodi basati su modelli e rete neurale. metodi, ecc.

(2) Utilizzo delle conoscenze pregresse
A seconda della disponibilità delle informazioni sulle classi normali o anomale, esistono tre approcci comuni:
① Metodo di rilevamento dei valori anomali non supervisionato, ovvero senza conoscenze preliminari come le etichette di categoria nel set di dati;
② Metodo di rilevamento dei valori anomali supervisionato, ovvero estrazione delle caratteristiche dei valori anomali attraverso l'esistenza di un set di addestramento contenente valori anomali e punti normali;
③ Metodo di rilevamento dei valori anomali semi-supervisionato I dati di addestramento contengono dati normali etichettati, ma non sono presenti informazioni sugli oggetti dati anomali.