Metodi di cluster analysis. metodi gerarchici. L'analisi dei cluster è un algoritmo per lo studio dei dati suddivisi in gruppi in base a caratteristiche simili.

Saluti!

Nella mia tesi, ho condotto una revisione e un'analisi comparativa degli algoritmi di clustering dei dati. Ho pensato che il materiale già raccolto ed elaborato potesse essere interessante e utile a qualcuno.
Su cosa sia il clustering, ha detto nell'articolo. Ripeterò in parte le parole di Alexander, in parte integrando. Sempre alla fine di questo articolo, chi fosse interessato può leggere i materiali ai link in bibliografia.

Ho anche cercato di portare lo stile di presentazione secco "diplomatico" a uno più giornalistico.

Il concetto di raggruppamento

Il clustering (o analisi dei cluster) è il compito di suddividere un insieme di oggetti in gruppi chiamati cluster. All'interno di ogni gruppo dovrebbero esserci oggetti "simili" e gli oggetti di gruppi diversi dovrebbero essere il più diversi possibile. La principale differenza tra clustering e classificazione è che l'elenco dei gruppi non è chiaramente definito ed è determinato nel corso dell'algoritmo.

Applicazione dell'analisi dei cluster in vista generale si riduce ai seguenti passaggi:

1. Selezione di un campione di oggetti per il clustering.
2. Definizione di un insieme di variabili in base alle quali verranno valutati gli oggetti del campione. Se necessario, normalizzare i valori delle variabili.
3. Calcolo dei valori delle misure di somiglianza tra gli oggetti.
4. Applicazione del metodo della cluster analysis per la creazione di gruppi di oggetti simili (cluster).
5. Presentazione dei risultati dell'analisi.

Dopo aver ricevuto e analizzato i risultati, è possibile regolare la metrica selezionata e il metodo di raggruppamento fino a ottenere un risultato ottimale.

Misure di distanza

Quindi, come determinare la "somiglianza" degli oggetti? Per prima cosa devi creare un vettore di caratteristiche per ogni oggetto: di norma, si tratta di un insieme di valori numerici, ad esempio l'altezza e il peso di una persona. Tuttavia, esistono anche algoritmi che funzionano con caratteristiche qualitative (le cosiddette categoriali).

Una volta determinato il vettore delle caratteristiche, possiamo normalizzarlo in modo che tutti i componenti contribuiscano allo stesso modo nel calcolo della "distanza". Durante il processo di normalizzazione, tutti i valori vengono ridotti a un intervallo, ad esempio [-1, -1] o .

Infine, per ogni coppia di oggetti, viene misurata la "distanza" tra loro, il grado di somiglianza. Ci sono molte metriche, ecco solo le principali:

La scelta della metrica spetta interamente al ricercatore, poiché i risultati del clustering possono differire in modo significativo quando si utilizzano misure diverse.

Classificazione degli algoritmi

Per quanto mi riguarda, ho identificato due classificazioni principali degli algoritmi di clustering.

1. Gerarchico e piatto.
   Gli algoritmi gerarchici (chiamati anche algoritmi di tassonomia) non costruiscono una singola partizione del campione in cluster disgiunti, ma un sistema di partizioni nidificate. Quello. all'uscita, otteniamo un albero a grappolo, la cui radice è l'intero campione e le foglie sono i grappoli più piccoli.
   Gli algoritmi flat costruiscono una partizione di oggetti in cluster.
2. Chiaro e sfocato.
   Algoritmi chiari (o non sovrapposti) assegnano un numero di cluster a ciascun oggetto campione, ad es. ogni oggetto appartiene a un solo cluster. Gli algoritmi fuzzy (o intersecanti) assegnano a ciascun oggetto un insieme di valori reali che mostrano il grado di relazione dell'oggetto con i cluster. Quelli. ogni oggetto appartiene a ciascun cluster con una certa probabilità.

Unione di cluster

Nel caso dell'utilizzo di algoritmi gerarchici, sorge la domanda su come combinare i cluster tra loro, come calcolare le "distanze" tra di loro. Ci sono diverse metriche:

1. Collegamento singolo (distanza del vicino più vicino)
   In questo metodo, la distanza tra due cluster è determinata dalla distanza tra i due oggetti più vicini (vicini più vicini) in cluster diversi. I cluster risultanti tendono a concatenarsi.
2. Collegamento completo (distanza dei vicini più lontani)
   In questo metodo, le distanze tra i cluster sono determinate dalla distanza maggiore tra due oggetti qualsiasi in cluster diversi (ovvero i vicini più distanti). Questo metodo di solito funziona molto bene quando gli oggetti provengono da gruppi separati. Se i grappoli sono allungati o il loro tipo naturale è "a catena", questo metodo non è adatto.
3. Media a coppie non ponderata
   In questo metodo, la distanza tra due diversi cluster viene calcolata come la distanza media tra tutte le coppie di oggetti in essi contenuti. Il metodo è efficace quando gli oggetti si formano vari gruppi, tuttavia, funziona altrettanto bene nei casi di cluster estesi ("tipo a catena").
4. Media pesata a coppie
   Il metodo è identico al metodo della media a coppie non ponderata, tranne per il fatto che la dimensione dei rispettivi cluster (ovvero il numero di oggetti che contengono) viene utilizzata come fattore di ponderazione nei calcoli. Pertanto, questo metodo dovrebbe essere utilizzato quando sono previste dimensioni di cluster diverse.
5. Metodo del centroide non ponderato
   In questo metodo, la distanza tra due ammassi è definita come la distanza tra i loro centri di gravità.
6. Metodo del centroide ponderato (mediana)
   Questo metodo è identico al precedente, tranne per il fatto che i calcoli utilizzano i pesi per tenere conto delle differenze tra le dimensioni dei cluster. Pertanto, se ci sono o si sospettano differenze significative nelle dimensioni dei cluster, questo metodo è preferibile al precedente.

Panoramica degli algoritmi

Algoritmi di clustering gerarchico

Esistono due tipi principali di algoritmi di clustering gerarchico: algoritmi ascendenti e discendenti. Gli algoritmi top-down funzionano su una base top-down: all'inizio, tutti gli oggetti sono collocati in un cluster, che viene poi suddiviso in cluster sempre più piccoli. Più comuni sono gli algoritmi bottom-up che collocano inizialmente ogni caratteristica in un cluster separato e quindi uniscono i cluster in cluster sempre più grandi fino a quando tutte le caratteristiche campionate sono contenute nello stesso cluster. Pertanto, viene costruito un sistema di partizioni nidificate. I risultati di tali algoritmi sono solitamente presentati sotto forma di un albero: un dendrogramma. Un classico esempio di tale albero è la classificazione di animali e piante.

Per calcolare le distanze tra i cluster, tutti utilizzano molto spesso due distanze: una connessione singola o una connessione completa (vedere la panoramica delle misure di distanza tra i cluster).

Lo svantaggio degli algoritmi gerarchici è il sistema di partizioni complete, che possono essere ridondanti nel contesto del problema da risolvere.

Algoritmi di errore quadratico

Il problema del clustering può essere considerato come la costruzione di una partizione ottimale degli oggetti in gruppi. In questo caso, l'ottimalità può essere definita come il requisito per minimizzare l'errore di partizionamento quadratico medio:

Dove cj- "centro di massa" dell'ammasso J(punto con valori medi delle caratteristiche per un dato cluster).

Gli algoritmi di errore quadratico sono del tipo di algoritmi piatti. L'algoritmo più comune in questa categoria è il metodo k-medie. Questo algoritmo costruisce un determinato numero di cluster situati il ​​più distanti possibile. Il lavoro dell'algoritmo è suddiviso in più fasi:

1. Scegli a caso K punti che sono i "centri di massa" iniziali degli ammassi.
2. Assegna ciascun oggetto all'ammasso con il "centro di massa" più vicino.
3. Ricalcolare i "centri di massa" degli ammassi in base alla loro attuale composizione.
4. Se il criterio per l'arresto dell'algoritmo non è soddisfatto, tornare al passaggio 2.

Come criterio per interrompere il funzionamento dell'algoritmo, viene solitamente scelta la variazione minima dell'errore quadratico medio. È anche possibile arrestare l'algoritmo se al passo 2 non c'erano oggetti che si sono spostati da un cluster all'altro.

Gli svantaggi di questo algoritmo includono la necessità di specificare il numero di cluster per la suddivisione.

Algoritmi sfocati

L'algoritmo di clustering fuzzy più popolare è l'algoritmo c-means. È una modifica del metodo k-means. Passaggi dell'algoritmo:

Questo algoritmo potrebbe non essere adatto se il numero di cluster non è noto in anticipo o se è necessario attribuire in modo univoco ciascun oggetto a un cluster.

Algoritmi basati sulla teoria dei grafi

L'essenza di tali algoritmi è che la selezione degli oggetti è rappresentata come un grafico SOL=(V, MI), i cui vertici corrispondono agli oggetti e i cui bordi hanno un peso pari alla "distanza" tra gli oggetti. Il vantaggio degli algoritmi di clustering di grafi è la visibilità, la relativa facilità di implementazione e la possibilità di apportare vari miglioramenti basati su considerazioni geometriche. Gli algoritmi principali sono l'algoritmo per l'estrazione di componenti connessi, l'algoritmo per la costruzione di un albero di copertura minimo (spanning) e l'algoritmo per il clustering a strati.

Algoritmo per l'estrazione di componenti connessi

Nell'algoritmo per l'estrazione dei componenti connessi, viene impostato il parametro di input R e nel grafico tutti i bordi per i quali le "distanze" sono maggiori di R. Solo le coppie di oggetti più vicine rimangono connesse. Lo scopo dell'algoritmo è trovare tale valore R, che si trova nell'intervallo di tutte le "distanze", in corrispondenza delle quali il grafico "si disgrega" in diverse componenti collegate. I componenti risultanti sono i cluster.

Per selezionare un parametro R di solito viene costruito un istogramma di distribuzioni di distanze a coppie. Nelle attività con una struttura dati cluster ben definita, l'istogramma avrà due picchi: uno corrisponde alle distanze intracluster, il secondo corrisponde alle distanze intercluster. Parametro Rè selezionato dalla zona di minimo tra questi picchi. Allo stesso tempo, è piuttosto difficile controllare il numero di cluster utilizzando la soglia della distanza.

Algoritmo dell'albero di copertura minimo

L'algoritmo dell'albero di copertura minimo crea prima un albero di copertura minimo sul grafico e quindi rimuove in sequenza i bordi con il peso più elevato. La figura mostra lo spanning tree minimo ottenuto per nove feature.

Rimuovendo il collegamento etichettato CD con una lunghezza di 6 unità (il bordo con la massima distanza), otteniamo due cluster: (A, B, C) e (D, E, F, G, H, I). Il secondo cluster può essere ulteriormente suddiviso in altri due cluster rimuovendo il bordo EF, che ha una lunghezza di 4,5 unità.

Raggruppamento a strati

L'algoritmo di clustering strato per strato si basa sulla selezione di componenti di grafi connessi a un certo livello di distanze tra gli oggetti (vertici). Il livello di distanza è impostato dalla soglia di distanza C. Ad esempio, se la distanza tra gli oggetti , Quello .

L'algoritmo di clustering a strati genera una sequenza di sottografi del grafico G, che riflettono le relazioni gerarchiche tra i cluster:

,

Dove SOL t = (V, E t)- grafico di livello con T,
,
con T– soglia di distanza t-esima,
m è il numero di livelli gerarchici,
SOL 0 = (V, o), o è l'insieme vuoto di archi del grafo ottenuto da t0 = 1,
SOL m = SOL, cioè un grafico di oggetti senza restrizioni sulla distanza (la lunghezza dei bordi del grafico), poiché tm = 1.

Modificando le soglie di distanza ( con 0 , …, con m), dove 0 = da 0 < da 1 < …< con m= 1, è possibile controllare la profondità della gerarchia dei cluster risultanti. Pertanto, l'algoritmo di clustering layer-by-layer è in grado di creare sia una partizione dati piatta che una partizione gerarchica.

Confronto tra algoritmi

Complessità computazionale degli algoritmi

Tabella comparativa degli algoritmi

Algoritmo di clustering	Forma dei cluster	Dati in ingresso	risultati
Gerarchico	Gratuito	Numero di cluster o soglia di distanza per il troncamento di una gerarchia	Albero binario dei cluster
k-significa	ipersfera	Numero di cluster	Centri di cluster
c-significa	ipersfera	Numero di cluster, grado di sfocatura	Centri cluster, matrice di appartenenza
Selezione dei componenti collegati	Gratuito	Soglia distanza R
Albero di copertura minimo	Gratuito	Numero di cluster o soglia di distanza per rimuovere i bordi	Struttura ad albero dei cluster
Raggruppamento a strati	Gratuito	Sequenza delle soglie di distanza	Struttura ad albero dei cluster con diversi livelli di gerarchia

Un po 'sull'applicazione

Nel mio lavoro, avevo bisogno di selezionare aree separate da strutture gerarchiche (alberi). Quelli. in sostanza, era necessario tagliare l'albero originale in diversi alberi più piccoli. Poiché un albero orientato è un caso speciale di un grafo, gli algoritmi basati sulla teoria dei grafi sono naturalmente adatti.

A differenza di un grafo completamente connesso, non tutti i vertici in un albero orientato sono collegati da archi e il numero totale di archi è n–1, dove n è il numero di vertici. Quelli. in relazione ai nodi dell'albero, il lavoro dell'algoritmo per l'estrazione dei componenti connessi sarà semplificato, poiché la rimozione di un numero qualsiasi di spigoli "dividerà" l'albero in componenti connessi (alberi separati). L'algoritmo dell'albero di copertura minimo in questo caso coinciderà con l'algoritmo per l'estrazione dei componenti connessi: rimuovendo i bordi più lunghi, l'albero originale viene suddiviso in più alberi. In questo caso è ovvio che la fase di costruzione dello spanning tree più minimale viene saltata.

Nel caso di utilizzo di altri algoritmi, dovrebbero tenere conto separatamente della presenza di relazioni tra oggetti, il che complica l'algoritmo.

Separatamente, voglio dire che per ottenere il miglior risultato è necessario sperimentare la scelta delle misure di distanza e talvolta anche modificare l'algoritmo. Non esiste un'unica soluzione.

analisi di gruppo

La maggior parte dei ricercatori è incline a credere che per la prima volta il termine "analisi dei cluster" (ing. grappolo- grappolo, coagulo, grappolo) è stato proposto dal matematico R. Trion. Successivamente sono emersi alcuni termini che oggi sono considerati sinonimi del termine "analisi dei cluster": classificazione automatica; botriologia.

L'analisi dei cluster è una procedura statistica multidimensionale che raccoglie dati contenenti informazioni su un campione di oggetti e quindi organizza gli oggetti in gruppi relativamente omogenei (cluster) (Q-clustering, o Q-technique, cluster analysis stessa). Cluster - un gruppo di elementi caratterizzati da una proprietà comune, l'obiettivo principale dell'analisi dei cluster è trovare gruppi di oggetti simili nel campione. La gamma di applicazioni della cluster analysis è molto ampia: viene utilizzata in archeologia, medicina, psicologia, chimica, biologia, pubblica amministrazione, filologia, antropologia, marketing, sociologia e altre discipline. Tuttavia, l'universalità dell'applicazione ha portato all'emergere di un gran numero di termini, metodi e approcci incompatibili che rendono difficile l'uso inequivocabile e l'interpretazione coerente dell'analisi dei cluster. Orlov A. I. suggerisce di distinguere come segue:

Compiti e condizioni

L'analisi dei cluster esegue quanto segue obiettivi principali:

• Sviluppo di una tipologia o classificazione.
• Esplorazione di schemi concettuali utili per raggruppare oggetti.
• Generazione di ipotesi basate sull'esplorazione dei dati.
• Test di ipotesi o ricerca per determinare se i tipi (gruppi) identificati in un modo o nell'altro sono effettivamente presenti nei dati disponibili.

Indipendentemente dall'argomento di studio, l'uso dell'analisi dei cluster comporta prossimi passi:

• Campionamento per il clustering. Resta inteso che ha senso raggruppare solo dati quantitativi.
• Definizione di un insieme di variabili in base alle quali verranno valutati gli oggetti nel campione, ovvero uno spazio delle caratteristiche.
• Calcolo dei valori di una o dell'altra misura di somiglianza (o differenza) tra oggetti.
• Applicazione del metodo della cluster analysis per creare gruppi di oggetti simili.
• Convalida dei risultati della soluzione cluster.

L'analisi dei cluster presenta quanto segue requisiti dei dati:

1. gli indicatori non dovrebbero essere correlati tra loro;
2. gli indicatori non dovrebbero contraddire la teoria delle misurazioni;
3. la distribuzione degli indicatori dovrebbe essere vicina alla normalità;
4. gli indicatori devono soddisfare il requisito di "stabilità", il che significa l'assenza di influenza sui loro valori da parte di fattori casuali;
5. il campione dovrebbe essere omogeneo, non contenere "valori anomali".

È possibile trovare una descrizione di due requisiti fondamentali per i dati: uniformità e completezza:

L'omogeneità richiede che tutte le entità rappresentate in una tabella siano della stessa natura. Il requisito per la completezza è che i set IO E J ha presentato una descrizione completa delle manifestazioni del fenomeno in esame. Se consideriamo una tabella in cui IOè una collezione, e J- l'insieme di variabili che descrivono questa popolazione, quindi dovrebbe essere un campione rappresentativo della popolazione studiata e il sistema di caratteristiche J dovrebbe fornire una rappresentazione vettoriale soddisfacente degli individui io dal punto di vista di un ricercatore.

Se l'analisi dei cluster è preceduta dall'analisi fattoriale, il campione non ha bisogno di essere "riparato" - i requisiti dichiarati vengono eseguiti automaticamente dalla stessa procedura di modellazione fattoriale (c'è un altro vantaggio: z-standardizzazione senza conseguenze negative per il campione; se viene eseguito direttamente per l'analisi dei cluster, può portare a una diminuzione della chiarezza della separazione dei gruppi). In caso contrario, il campione deve essere aggiustato.

Tipologia dei problemi di clustering

Tipi di input

IN scienza moderna Vengono utilizzati diversi algoritmi per l'elaborazione dei dati di input. Viene chiamata l'analisi confrontando oggetti basati su caratteristiche (più comune nelle scienze biologiche). Q- tipo di analisi, e nel caso di comparazione di caratteristiche, sulla base di oggetti - R- tipo di analisi. Esistono tentativi di utilizzare tipi di analisi ibridi (ad esempio, RQ analisi), ma questa metodologia non è stata ancora adeguatamente sviluppata.

Obiettivi del clustering

• Comprendere i dati identificando la struttura del cluster. La divisione del campione in gruppi di oggetti simili consente di semplificare ulteriormente l'elaborazione dei dati e il processo decisionale applicando il proprio metodo di analisi a ciascun cluster (la strategia "divide et impera").
• Compressione dati. Se il campione iniziale è eccessivamente grande, può essere ridotto, lasciando uno dei rappresentanti più tipici di ciascun cluster.
• rilevamento novità. rilevamento novità). Vengono selezionati oggetti atipici che non possono essere collegati a nessuno dei cluster.

Nel primo caso, cercano di ridurre il numero di cluster. Nel secondo caso, è più importante garantire un alto grado somiglianze di oggetti all'interno di ciascun cluster e può esserci un numero qualsiasi di cluster. Nel terzo caso, i singoli oggetti che non rientrano in nessuno dei cluster sono di maggiore interesse.

In tutti questi casi, è possibile applicare il clustering gerarchico, quando i cluster di grandi dimensioni vengono suddivisi in cluster più piccoli, che a loro volta vengono suddivisi in gruppi ancora più piccoli, ecc. Tali attività sono chiamate attività di tassonomia. Il risultato della tassonomia è una struttura gerarchica ad albero. Inoltre, ogni oggetto è caratterizzato da un'enumerazione di tutti i cluster a cui appartiene, solitamente dal grande al piccolo.

Metodi di clustering

Non esiste una classificazione generalmente accettata dei metodi di clustering, ma si può notare un solido tentativo di V. S. Berikov e G. S. Lbov. Se generalizziamo le varie classificazioni dei metodi di clustering, possiamo distinguere un numero di gruppi (alcuni metodi possono essere attribuiti a più gruppi contemporaneamente, e quindi si propone di considerare questa tipizzazione come un'approssimazione alla reale classificazione dei metodi di clustering):

1. Approccio probabilistico. Si assume che ogni oggetto in esame appartenga a una delle k classi. Alcuni autori (ad esempio, A. I. Orlov) lo credono questo gruppo non si riferisce affatto al raggruppamento e vi si oppone sotto il nome di "discriminazione", cioè la scelta di attribuire oggetti a uno dei band famose(campioni di allenamento).
2. Approcci basati su sistemi di intelligenza artificiale. Un gruppo molto condizionale, poiché ci sono molti metodi di intelligenza artificiale e metodicamente sono molto diversi.
3. approccio logico. La costruzione di un dendrogramma viene eseguita utilizzando un albero decisionale.
4. Approccio grafico-teorico.
   • Algoritmi di clustering di grafi
5. Approccio gerarchico. Si presuppone la presenza di gruppi nidificati (cluster di ordine diverso). Gli algoritmi, a loro volta, si dividono in agglomeranti (unificanti) e divisivi (separatori). In base al numero di caratteristiche, a volte si distinguono metodi di classificazione monotetici e politetici.
   • Raggruppamento gerarchico divisionale o tassonomia. I problemi di clustering sono considerati nella tassonomia quantitativa.
6. Altri metodi. Non incluso nei gruppi precedenti.
   • Algoritmi di clustering statistico
   • Insieme di clusterers
   • Algoritmi della famiglia KRAB
   • Algoritmo basato sul metodo di vagliatura
   • DBSCAN ecc.

Gli approcci 4 e 5 sono talvolta combinati sotto il nome di approccio strutturale o geometrico, che ha un concetto più formalizzato di prossimità. Nonostante le differenze significative tra i metodi elencati, si basano tutti sull'originale " Ipotesi di compattezza»: nello spazio oggetti, tutti gli oggetti vicini devono appartenere allo stesso cluster e tutti gli oggetti diversi, rispettivamente, devono trovarsi in cluster diversi.

Dichiarazione formale del problema del clustering

Sia un insieme di oggetti, sia un insieme di numeri (nomi, etichette) di cluster. La funzione della distanza tra gli oggetti è data. C'è un insieme di oggetti di addestramento finito. È necessario suddividere il campione in sottoinsiemi non sovrapposti, chiamati cluster, in modo che ogni cluster sia costituito da oggetti vicini in metric e gli oggetti di cluster diversi differiscano in modo significativo. In questo caso, a ciascun oggetto viene assegnato un numero di cluster.

Algoritmo di clusteringè una funzione che associa qualsiasi oggetto a un numero di cluster. L'insieme in alcuni casi è noto in anticipo, ma più spesso il compito è determinare il numero ottimale di cluster, dal punto di vista dell'uno o dell'altro criteri di qualità raggruppamento.

Il clustering (apprendimento non supervisionato) differisce dalla classificazione (apprendimento supervisionato) in quanto le etichette degli oggetti originali non sono inizialmente impostate e l'insieme stesso può anche essere sconosciuto.

La soluzione del problema del clustering è fondamentalmente ambigua e ci sono diverse ragioni per questo (secondo un certo numero di autori):

• non esiste inequivocabilmente il miglior criterio qualità di raggruppamento. Sono noti numerosi criteri euristici, nonché numerosi algoritmi che non hanno un criterio chiaramente definito, ma eseguono un raggruppamento abbastanza ragionevole "per costruzione". Tutti loro possono dare risultati diversi. Pertanto, per determinare la qualità del raggruppamento, è necessario un esperto nell'area disciplinare, che possa valutare la significatività della selezione dei cluster.
• il numero di cluster è solitamente sconosciuto in anticipo ed è fissato secondo alcuni criteri soggettivi. Questo è vero solo per i metodi di discriminazione, poiché nei metodi di clustering, i cluster vengono selezionati utilizzando un approccio formalizzato basato su misure di prossimità.
• il risultato del raggruppamento dipende in modo significativo dalla metrica, la cui scelta, di regola, è anch'essa soggettiva ed è determinata da un esperto. Ma vale la pena notare che ci sono una serie di raccomandazioni per la scelta di misure di prossimità per vari compiti.

Applicazione

In biologia

In biologia, il clustering ha molte applicazioni in un'ampia varietà di campi. Ad esempio, in bioinformatica, viene utilizzato per analizzare reti complesse di geni interagenti, a volte costituite da centinaia o addirittura migliaia di elementi. L'analisi dei cluster consente di identificare sottoreti, colli di bottiglia, hub e altre proprietà nascoste del sistema in esame, che alla fine consente di scoprire il contributo di ciascun gene alla formazione del fenomeno in esame.

Nel campo dell'ecologia, è ampiamente utilizzato per identificare gruppi spazialmente omogenei di organismi, comunità, ecc. Meno comunemente, i metodi di analisi dei cluster vengono utilizzati per studiare le comunità nel tempo. L'eterogeneità della struttura delle comunità porta all'emergere di metodi non banali di analisi dei cluster (ad esempio, il metodo Czekanowski).

In generale, vale la pena notare che storicamente, le misure di somiglianza sono più spesso utilizzate come misure di prossimità in biologia, piuttosto che come misure di differenza (distanza).

In sociologia

Quando si analizzano i risultati ricerca sociologica si consiglia di eseguire l'analisi utilizzando i metodi di una famiglia gerarchica agglomerativa, vale a dire il metodo Ward, in cui la varianza minima è ottimizzata all'interno dei cluster, di conseguenza vengono creati cluster di dimensioni approssimativamente uguali. Il metodo di Ward è il più riuscito per l'analisi dei dati sociologici. Come misura della differenza, la distanza euclidea quadratica è migliore, il che contribuisce ad aumentare il contrasto dei cluster. Il risultato principale dell'analisi gerarchica dei cluster è un dendrogramma o "diagramma a ghiacciolo". Nell'interpretarlo, i ricercatori devono affrontare un problema dello stesso tipo dell'interpretazione dei risultati dell'analisi fattoriale: la mancanza di criteri univoci per identificare i cluster. Si consiglia di utilizzare due metodi come i principali: analisi visiva del dendrogramma e confronto dei risultati del raggruppamento eseguito con metodi diversi.

L'analisi visiva del dendrogramma comporta il "taglio" dell'albero al livello ottimale di somiglianza degli elementi del campione. Il "ramo di vite" (terminologia di Oldenderfer M.S. e Blashfield R.K.) dovrebbe essere "troncato" a circa 5 sulla scala Rescaled Distance Cluster Combine, raggiungendo così un livello di somiglianza dell'80%. Se la selezione dei cluster con questa etichetta è difficile (diversi piccoli cluster si fondono in uno grande su di essa), puoi scegliere un'altra etichetta. Questa tecnica è proposta da Oldenderfer e Blashfield.

Ora si pone la questione della stabilità della soluzione cluster adottata. In effetti, il controllo della stabilità del clustering si riduce al controllo della sua affidabilità. C'è una regola empirica qui: una tipologia stabile viene preservata quando cambiano i metodi di clustering. I risultati dell'analisi gerarchica dei cluster possono essere verificati mediante l'analisi iterativa dei cluster k-means. Se le classificazioni confrontate dei gruppi di intervistati hanno una quota di coincidenze superiore al 70% (più di 2/3 delle coincidenze), viene presa una decisione di gruppo.

È impossibile verificare l'adeguatezza della soluzione senza ricorrere ad un altro tipo di analisi. Almeno teoricamente, questo problema non è stato risolto. La classica Cluster Analysis di Oldenderfer e Blashfield elabora e alla fine rifiuta cinque metodi di test di robustezza aggiuntivi:

Nell'informatica

• Clustering dei risultati di ricerca - utilizzato per il raggruppamento "intelligente" dei risultati durante la ricerca di file, siti Web, altri oggetti, consentendo all'utente di navigare rapidamente, selezionare un sottoinsieme che è ovviamente più rilevante ed esclude uno noto meno rilevante - che può aumentare l'usabilità dell'interfaccia rispetto all'output sotto forma di un semplice elenco ordinato per rilevanza .
  • Clusty - Il motore di ricerca di clustering di Vivísimo
  • Nigma - Motore di ricerca russo con raggruppamento automatico dei risultati
  • Quintura - raggruppamento visivo sotto forma di una nuvola di parole chiave
• Segmentazione delle immagini segmentazione dell'immagine) - Il clustering può essere utilizzato per suddividere un'immagine digitale in regioni distinte ai fini del rilevamento dei bordi. rilevamento dei bordi) o riconoscimento di oggetti.
• Estrazione dei dati estrazione dei dati)- Il clustering nel Data Mining diventa prezioso quando agisce come una delle fasi dell'analisi dei dati, costruendo una soluzione analitica completa. Spesso è più facile per un analista identificare gruppi di oggetti simili, studiarne le caratteristiche e costruire un modello separato per ciascun gruppo piuttosto che creare un modello generale per tutti i dati. Questa tecnica viene costantemente utilizzata nel marketing, evidenziando gruppi di clienti, acquirenti, merci e sviluppando una strategia separata per ciascuno di essi.

Guarda anche

Appunti

Collegamenti

In russo

• www.MachineLearning.ru - risorsa wiki professionale dedicata all'apprendimento automatico e al data mining

In inglese

• COMPACT - Pacchetto comparativo per la valutazione del clustering. Un pacchetto Matlab gratuito, 2006.
• P. Berkhin, Indagine sulle tecniche di data mining di clustering, Accumula software, 2002.
• Jain, Murty e Flynn: Clustering dei dati: una revisione, Comp. ACM Soprav., 1999.
• per un'altra presentazione di gerarchiche, k-medie e fuzzy c-medie vedere questa introduzione al clustering . Ha anche una spiegazione sulla miscela di gaussiane.
• Davide Dowe, Pagina di modellazione della miscela- altri collegamenti a clustering e modelli misti.
• un tutorial sul clustering
• Il libro di testo on-line: teoria dell'informazione, inferenza e algoritmi di apprendimento, di David J.C. MacKay include capitoli su clustering k-medie, clustering soft k-medie e derivazioni incluso l'algoritmo EM e il vista variazionale dell'algoritmo E-M.
• "The Self-Organized Gene", tutorial che spiega il clustering attraverso l'apprendimento competitivo e le mappe auto-organizzanti.
• kernlab - pacchetto R per l'apprendimento automatico basato su kernel (include l'implementazione del clustering spettrale)
• Tutorial - Tutorial con introduzione degli Algoritmi di Clustering (k-medie, fuzzy-c-medie, gerarchiche, miste di gaussiane) + alcune demo interattive (applet java)
• Software di data mining: il software di data mining utilizza spesso tecniche di clustering.
• Java Competive Learning Application Una suite di reti neurali non supervisionate per il clustering. Scritto in Java. Completo di tutto il codice sorgente.
• Software di apprendimento automatico: contiene anche molti software di clustering.

Spesso nelle aree di attività più diverse, dobbiamo fare i conti con un numero enorme di elementi in relazione ai quali dobbiamo agire.

E non possiamo nemmeno renderci conto di tutto questo volume, figuriamoci capirlo.

Qual è la via d'uscita? Beh, certo, "metti tutto sugli scaffali". In questo caso, la saggezza popolare acquisisce una formulazione scientifica ben definita.

L'analisi dei cluster è lo studio degli oggetti combinandoli in gruppi omogenei con caratteristiche simili. I suoi metodi sono applicabili letteralmente in tutti i campi: dalla medicina al Forex trading, dall'assicurazione auto all'archeologia. E per gli esperti di marketing e gli specialisti delle risorse umane, è semplicemente insostituibile.

Maggiori informazioni su questo nell'articolo.

Che cos'è un cluster

L'analisi dei cluster è progettata per dividere un insieme di oggetti in gruppi omogenei (cluster o classi). Questo è un compito di classificazione dei dati multivariata.

Esistono circa 100 diversi algoritmi di clustering, tuttavia, i più comunemente usati sono:

1. analisi dei cluster gerarchici,
2. k-significa raggruppamento.

Dove viene applicata l'analisi dei cluster:

• Nel marketing, questa è la segmentazione dei concorrenti e dei consumatori.
• Nella gestione:
  1. divisione del personale in gruppi con diversi livelli di motivazione,
  2. classificazione dei fornitori,
  3. individuazione di situazioni produttive simili in cui avviene il matrimonio.
• In medicina, la classificazione dei sintomi, dei pazienti, dei farmaci.
• In sociologia, la divisione degli intervistati in gruppi omogenei.

In effetti, l'analisi dei cluster si è dimostrata valida in tutte le sfere della vita umana. La bellezza di questo metodo è che funziona anche quando ci sono pochi dati e i requisiti per le normali distribuzioni non sono soddisfatti. variabili casuali e altri requisiti dei metodi classici di analisi statistica.

Cerchiamo di spiegare l'essenza dell'analisi dei cluster senza ricorrere a una terminologia rigorosa.

Supponiamo che tu abbia condotto un sondaggio tra i dipendenti e desideri determinare come puoi gestire nel modo più efficace il tuo personale. Cioè, vuoi dividere i dipendenti in gruppi e selezionare le leve di controllo più efficaci per ciascuno di essi. Allo stesso tempo, le differenze tra i gruppi dovrebbero essere evidenti e all'interno del gruppo gli intervistati dovrebbero essere il più simili possibile.

Per risolvere il problema, si propone di utilizzare l'analisi dei cluster gerarchici. Di conseguenza, otterremo un albero, osservando il quale dobbiamo decidere in quante classi (cluster) vogliamo dividere il pentagramma. Supponiamo di decidere di dividere il personale in tre gruppi, quindi per studiare gli intervistati che rientrano in ciascun gruppo, otteniamo un tablet con il seguente contenuto:

Spieghiamo come si forma la tabella sopra. La prima colonna contiene il numero del cluster, il gruppo i cui dati sono riportati nella riga. Ad esempio, il primo gruppo è composto per l'80% da maschi. Il 90% del primo cluster rientra nella fascia di età dai 30 ai 50 anni e il 12% degli intervistati ritiene che i benefit siano molto importanti. E così via.

Proviamo a fare dei ritratti degli intervistati di ciascun cluster:

1. Il primo gruppo è composto principalmente da uomini in età matura, che occupano posizioni di leadership. Il pacchetto sociale (MED, LGOTI, TIME tempo libero) non li interessa. Preferiscono ricevere un buon stipendio, piuttosto che l'aiuto del datore di lavoro.
2. Il gruppo due, al contrario, preferisce il pacchetto sociale. Consiste principalmente di persone "anziane" che occupano posizioni basse. Lo stipendio è sicuramente importante per loro, ma ci sono altre priorità.
3. Il terzo gruppo è il più "giovane". A differenza dei due precedenti, c'è un evidente interesse per l'apprendimento e le opportunità di crescita professionale. Questa categoria di dipendenti ha buone possibilità di rifornire presto il primo gruppo.

Pertanto, quando si pianifica una campagna per introdurre metodi efficaci di gestione del personale, è ovvio che nella nostra situazione è possibile aumentare il pacchetto sociale per il secondo gruppo a scapito, ad esempio, dei salari. Se parliamo di quali specialisti dovrebbero essere inviati per la formazione, possiamo sicuramente consigliare di prestare attenzione al terzo gruppo.

Fonte: "nickart.spb.ru"

L'analisi dei cluster è la chiave per comprendere il mercato

Un cluster è il prezzo di un asset in un certo periodo di tempo durante il quale sono state effettuate transazioni. Il volume risultante di acquisti e vendite è indicato da un numero all'interno del cluster. La barra di qualsiasi TF contiene, di norma, diversi cluster. Questo permette di vedere nel dettaglio i volumi degli acquisti, delle vendite e il loro saldo in ogni singola barra, per ogni livello di prezzo.

Costruire un grafico a grappolo

Una variazione del prezzo di un asset comporta inevitabilmente una catena di movimenti di prezzo anche su altri strumenti. Nella maggior parte dei casi, la comprensione del movimento di tendenza avviene già nel momento in cui si sta sviluppando rapidamente e l'ingresso nel mercato lungo la tendenza è irto di cadere in un'onda correttiva.

Per operazioni di successo, è necessario comprendere la situazione attuale ed essere in grado di anticipare i futuri movimenti dei prezzi. Questo può essere appreso analizzando il grafico a grappolo. Con l'aiuto dell'analisi dei cluster, puoi vedere l'attività dei partecipanti al mercato anche all'interno della barra dei prezzi più piccola.

Questa è l'analisi più accurata e dettagliata, in quanto mostra la distribuzione puntuale dei volumi delle transazioni per ogni livello di prezzo dell'asset. Il mercato confronta costantemente gli interessi di venditori e acquirenti. E ogni più piccolo movimento di prezzo (tick) è il passaggio a un compromesso - il livello di prezzo - che in questo momento si adatta a entrambe le parti.

Ma il mercato è dinamico, il numero di venditori e acquirenti è in continua evoluzione. Se a un certo punto il mercato era dominato dai venditori, il momento successivo, molto probabilmente, ci saranno gli acquirenti. Anche il numero di transazioni completate a livelli di prezzo vicini non è lo stesso.

Eppure, in primo luogo, la situazione del mercato si riflette sul volume totale delle transazioni e solo successivamente sul prezzo. Se vedi le azioni dei partecipanti al mercato dominante (venditori o acquirenti), puoi prevedere il movimento del prezzo stesso.

Per applicare correttamente l'analisi dei cluster, devi prima capire cosa sono un cluster e un delta:

• Un cluster è un movimento di prezzo, suddiviso in livelli in cui sono state effettuate transazioni con volumi noti.
• Il delta mostra la differenza tra l'acquisto e la vendita che si verificano in ciascun cluster.

grafico a grappolo

Ogni cluster, o gruppo di delta, ti consente di capire se gli acquirenti o i venditori dominano il mercato in un dato momento. Basta calcolare il delta totale sommando le vendite e gli acquisti. Se il delta è negativo, allora il mercato è ipervenduto, ci sono transazioni di vendita ridondanti. Quando il delta è positivo, il mercato è chiaramente dominato dagli acquirenti.

Il delta stesso può assumere un valore normale o critico. Il valore del volume delta eccedente il valore normale nel cluster è evidenziato in rosso. Se il delta è moderato, ciò caratterizza uno stato piatto nel mercato. A valore normale delta sul mercato, c'è un movimento di tendenza, ma il valore critico è sempre foriero di un'inversione di prezzo.

Trading Forex con CA

Per ottenere il massimo profitto, devi essere in grado di determinare la transizione del delta da un livello moderato a uno normale. In effetti, in questo caso, puoi notare l'inizio della transizione da un movimento piatto a uno di tendenza ed essere in grado di ottenere il massimo profitto.

Il grafico a grappolo è più visivo, ti consente di vedere livelli significativi di accumulo e distribuzione dei volumi, costruire livelli di supporto e resistenza.

Ciò consente al trader di trovare l'esatta entrata nel commercio. Utilizzando il delta, si può giudicare la predominanza delle vendite o degli acquisti nel mercato. L'analisi dei cluster consente di osservare le transazioni e tenere traccia dei loro volumi all'interno di una barra di qualsiasi TF. Ciò è particolarmente importante quando ci si avvicina a livelli significativi di supporto o resistenza. I giudizi di gruppo sono la chiave per comprendere il mercato.

Fonte: "orderflowtrading.ru"

Ambiti e caratteristiche di applicazione della cluster analysis

Il termine cluster analysis (introdotto per la prima volta da Tryon, 1939) include in realtà un insieme di diversi algoritmi di classificazione. Domanda generale, chiesto dai ricercatori in molti campi, è come organizzare i dati osservati in strutture visive, ad es. ampliare le tassonomie.

Ad esempio, i biologi mirano a irrompere negli animali diversi tipi per descrivere in modo significativo le differenze tra loro. Secondo il sistema moderno accettato in biologia, l'uomo appartiene a primati, mammiferi, amnioti, vertebrati e animali.

Si noti che in questa classificazione, maggiore è il livello di aggregazione, minore è la somiglianza tra i membri della classe corrispondente. L'uomo ha più somiglianze con altri primati (cioè le scimmie) che con i membri "lontani" della famiglia dei mammiferi (cioè i cani), e così via.

Si noti che la discussione precedente si riferisce agli algoritmi di clustering, ma non menziona nulla sui test per la significatività statistica. In effetti, l'analisi dei cluster non è tanto un metodo statistico ordinario quanto un "insieme" di vari algoritmi per "distribuire oggetti in cluster".

C'è un punto di vista secondo cui, a differenza di molte altre procedure statistiche, i metodi di analisi dei cluster vengono utilizzati nella maggior parte dei casi quando non si hanno ipotesi a priori sulle classi, ma si è ancora nella fase descrittiva della ricerca. Dovrebbe essere chiaro che l'analisi dei cluster determina la "decisione più significativa".

Pertanto, il test per la significatività statistica non è realmente applicabile qui, anche nei casi in cui i livelli p sono noti (come, ad esempio, nel metodo K-medie).

La tecnica del clustering è utilizzata in un'ampia varietà di campi. Hartigan (1975) ha fornito un'eccellente panoramica dei numerosi studi pubblicati contenenti risultati ottenuti con metodi di cluster analysis. Ad esempio, nel campo della medicina, il raggruppamento di malattie, il trattamento di malattie o sintomi di malattie porta a tassonomie ampiamente utilizzate.

Nel campo della psichiatria diagnosi corretta grappoli di sintomi come paranoia, schizofrenia, ecc. è fondamentale per il successo della terapia. In archeologia, utilizzando l'analisi dei cluster, i ricercatori stanno cercando di stabilire tassonomie di strumenti di pietra, oggetti funerari, ecc.

conosciuto ampie applicazioni analisi dei cluster in ricerca di marketing. In generale, ogniqualvolta sia necessario classificare “montagne” di informazioni in gruppi adatti ad ulteriori elaborazioni, la cluster analysis si rivela molto utile ed efficace.

Raggruppamento di alberi

Lo scopo dell'algoritmo di associazione (clustering ad albero) è combinare oggetti (ad esempio, animali) in cluster sufficientemente grandi utilizzando una certa misura di somiglianza o distanza tra gli oggetti. Un risultato tipico di tale raggruppamento è un albero gerarchico.

Considera un diagramma ad albero orizzontale. Il diagramma inizia con ogni oggetto della classe (sul lato sinistro del diagramma). Ora immagina di "indebolire" gradualmente (a passi molto piccoli) il tuo criterio per stabilire quali oggetti sono unici e quali no. In altre parole, si abbassa la soglia relativa alla decisione di unire due o più oggetti in un unico cluster.

Di conseguenza, colleghi sempre più oggetti insieme e aggreghi (combina) sempre più gruppi di elementi sempre più diversi. Infine, nell'ultimo passaggio, tutti gli oggetti vengono uniti insieme.

In questi grafici, gli assi orizzontali rappresentano la distanza di raggruppamento (nei dendrogrammi verticali, gli assi verticali rappresentano la distanza di raggruppamento). Quindi, per ogni nodo nel grafico (dove si forma un nuovo cluster), puoi vedere la quantità di distanza per la quale gli elementi corrispondenti sono collegati in un nuovo singolo cluster.

Quando i dati hanno una "struttura" chiara in termini di gruppi di oggetti simili tra loro, è probabile che questa struttura si rifletta nell'albero gerarchico attraverso vari rami. Come risultato di un'analisi riuscita con il metodo join, diventa possibile rilevare i cluster (rami) e interpretarli.

Misure di distanza

Il metodo di clustering dell'unione o dell'albero viene utilizzato nella formazione di cluster di dissomiglianza o distanza tra oggetti. Queste distanze possono essere definite nello spazio unidimensionale o multidimensionale. Ad esempio, se devi raggruppare i tipi di cibo in un bar, puoi tenere conto del numero di calorie in esso contenute, del prezzo, della valutazione soggettiva del gusto, ecc.

Il modo più diretto per calcolare le distanze tra oggetti in uno spazio multidimensionale è calcolare le distanze euclidee. Se hai uno spazio bidimensionale o tridimensionale, questa misura è la distanza geometrica effettiva tra gli oggetti nello spazio (come se le distanze tra gli oggetti fossero misurate con un metro a nastro).

Tuttavia, l'algoritmo di raggruppamento non "si preoccupa" se le distanze "fornite" siano reali o qualche altra misura di distanza derivata, che è più significativa per il ricercatore; e il compito dei ricercatori è trovare metodo corretto Per applicazioni specifiche.

1. distanza euclidea.

Questo sembra essere il massimo tipo generale distanze. È semplicemente una distanza geometrica nello spazio multidimensionale ed è calcolata come segue:

Si noti che la distanza euclidea (e il suo quadrato) è calcolata dai dati originali, non dai dati standardizzati. Questo è il modo abituale di calcolarlo, che presenta alcuni vantaggi (ad esempio, la distanza tra due oggetti non cambia quando viene introdotto nell'analisi un nuovo oggetto, che potrebbe rivelarsi un valore anomalo).

Tuttavia, le distanze possono essere notevolmente influenzate dalle differenze tra gli assi da cui vengono calcolate le distanze.

Ad esempio, se uno degli assi è misurato in centimetri e poi lo si converte in millimetri (moltiplicando i valori per 10), allora la distanza euclidea finale (o il quadrato della distanza euclidea) calcolata dalle coordinate sarà cambiano radicalmente e, di conseguenza, i risultati dell'analisi dei cluster possono essere molto diversi da quelli precedenti.

2. Il quadrato della distanza euclidea.

A volte potresti voler elevare al quadrato la distanza euclidea standard per dare più peso a oggetti più distanti. Questa distanza è calcolata come segue:

3. Distanza dall'isolato urbano (distanza da Manhattan).

Questa distanza è semplicemente la media delle differenze rispetto alle coordinate. Nella maggior parte dei casi, questa misura della distanza porta agli stessi risultati della solita distanza di Euclide.

Tuttavia, si noti che per questa misura l'influenza delle singole grandi differenze (valori anomali) diminuisce (poiché non sono quadrate). La distanza di Manhattan è calcolata utilizzando la formula:

4. Distanza Chebyshev.

Questa distanza può essere utile quando si desidera definire due oggetti come "diversi" se differiscono in una qualsiasi coordinata (qualsiasi dimensione). La distanza di Chebyshev è calcolata dalla formula:

5. Distanza di potere.

   Talvolta si desidera aumentare o diminuire progressivamente il peso relativo ad una dimensione per la quale gli oggetti corrispondenti sono molto diversi. Ciò può essere ottenuto utilizzando una distanza di legge di potenza. La distanza di potenza è calcolata dalla formula:

   dove r e p sono parametri definiti dall'utente.

   Alcuni esempi di calcoli possono mostrare come "funziona" questa misura:

   • Il parametro p è responsabile della ponderazione graduale delle differenze rispetto alle singole coordinate.
   • Il parametro r è responsabile della ponderazione progressiva di grandi distanze tra gli oggetti.
   • Se entrambi i parametri - r e p, sono uguali a due, allora questa distanza coincide con la distanza euclidea.
6. La percentuale di disaccordo.

Questa misura viene utilizzata quando i dati sono categorici. Questa distanza è calcolata dalla formula:

Associazione o regole di associazione

Nella prima fase, quando ogni oggetto è un cluster separato, le distanze tra questi oggetti sono determinate dalla misura scelta. Tuttavia, quando diversi oggetti sono collegati tra loro, sorge la domanda: come dovrebbero essere determinate le distanze tra i cluster?

In altre parole, è necessaria una regola di join o collegamento per due cluster. Ci sono varie possibilità qui: ad esempio, puoi collegare due cluster insieme quando due oggetti qualsiasi in due cluster amico più intimo tra loro rispetto alla corrispondente distanza di comunicazione.

In altre parole, si utilizza la "regola del vicino più vicino" per determinare la distanza tra i cluster; questo metodo è chiamato metodo a collegamento singolo. Questa regola crea cluster "fibrosi", ad es. grappoli "legati tra loro" solo da singoli elementi che risultano essere più vicini tra loro rispetto agli altri.

In alternativa, puoi usare i vicini nei cluster che sono più lontani l'uno dall'altro di tutte le altre coppie di caratteristiche. Questo metodo è chiamato metodo di collegamento completo. Esistono anche molti altri metodi per unire i cluster, simili a quelli discussi.

• Connessione singola (metodo del vicino più vicino).

Come descritto in precedenza, in questo metodo la distanza tra due cluster è determinata dalla distanza tra i due oggetti più vicini (vicini più vicini) in cluster diversi.

Questa regola deve, in un certo senso, mettere insieme gli oggetti per formare cluster, ei cluster risultanti tendono ad essere rappresentati da lunghe "stringhe".

• Connessione completa (metodo dei vicini più lontani).

In questo metodo, le distanze tra i cluster sono definite come la distanza massima tra due oggetti qualsiasi in cluster diversi (ovvero "vicini più distanti").

Questo metodo di solito funziona molto bene quando gli oggetti provengono effettivamente da "boschetti" molto diversi.

Se i grappoli sono in qualche modo allungati o il loro tipo naturale è "a catena", allora questo metodo non è adatto.

• Media a coppie non ponderata.

In questo metodo, la distanza tra due diversi cluster viene calcolata come la distanza media tra tutte le coppie di oggetti in essi contenuti. Il metodo è efficace quando gli oggetti formano effettivamente diversi "boschetti", ma funziona altrettanto bene nei casi di cluster estesi ("tipo catena").

Si noti che nel loro libro Sneath e Sokal (1973) introducono l'abbreviazione UPGMA per riferirsi a questo metodo come metodo del gruppo di coppie non ponderato che utilizza medie aritmetiche.

• Media pesata a coppie.
Il metodo è identico al metodo della media a coppie non ponderata, tranne per il fatto che la dimensione dei rispettivi cluster (ovvero il numero di oggetti che contengono) viene utilizzata come fattore di ponderazione nei calcoli. Pertanto, il metodo proposto dovrebbe essere utilizzato quando si ipotizzano dimensioni di cluster disuguali.


Sneath e Sokal (1973) introducono l'abbreviazione WPGMA per riferirsi a questo metodo come metodo del gruppo di coppie ponderato che utilizza medie aritmetiche.

• Metodo del centroide non ponderato.

In questo metodo, la distanza tra due ammassi è definita come la distanza tra i loro centri di gravità.

Sneath e Sokal (1973) usano l'acronimo UPGMC per riferirsi a questo metodo come metodo del gruppo di coppie non ponderato che utilizza la media del centroide.

• Metodo del centroide ponderato (mediana).

Questo metodo è identico al precedente, tranne per il fatto che i pesi vengono utilizzati nei calcoli per tenere conto della differenza tra le dimensioni dei cluster (ovvero il numero di oggetti in essi contenuti).

Pertanto, se ci sono (o si sospettano) differenze significative nelle dimensioni dei cluster, questo metodo è preferibile al precedente.

Sneath e Sokal (1973) hanno utilizzato l'abbreviazione WPGMC per riferirsi ad esso come metodo del gruppo di coppie ponderato utilizzando la media del centroide.

• Metodo Ward.

Questo metodo è diverso da tutti gli altri perché utilizza i metodi ANOVA per stimare le distanze tra i cluster. Il metodo minimizza la somma dei quadrati (SS) per ogni due (ipotetici) cluster che possono essere formati ad ogni passo.

I dettagli possono essere trovati in Ward (1963). In generale, il metodo sembra essere molto efficiente, ma tende a creare piccoli cluster.

unione a due vie

In precedenza questo metodo è stato discusso in termini di "oggetti" che dovrebbero essere raggruppati. In tutti gli altri tipi di analisi, la questione di interesse per il ricercatore è solitamente espressa in termini di osservazioni o variabili. Si scopre che il clustering, sia per osservazioni che per variabili, può portare a risultati piuttosto interessanti.

Ad esempio, immagina che un ricercatore medico stia raccogliendo dati su varie caratteristiche (variabili) delle condizioni (osservazioni) dei pazienti con malattie cardiache. L'investigatore potrebbe voler raggruppare le osservazioni (di pazienti) per identificare gruppi di pazienti con sintomi simili.

Allo stesso tempo, il ricercatore potrebbe desiderare di raggruppare le variabili per identificare gruppi di variabili associate a uno stato fisico simile. Dopo questa discussione sull'opportunità di raggruppare osservazioni o variabili, ci si potrebbe chiedere, perché non raggruppare in entrambe le direzioni?

Il modulo Cluster Analysis contiene un'efficiente procedura di join bidirezionale per fare proprio questo. Tuttavia, il pooling a due vie viene utilizzato (relativamente raramente) in circostanze in cui si prevede che sia le osservazioni che le variabili contribuiscano simultaneamente alla scoperta di cluster significativi.

Quindi, tornando all'esempio precedente, possiamo supporre che un ricercatore medico abbia bisogno di identificare cluster di pazienti simili in relazione a determinati cluster di caratteristiche della condizione fisica.

La difficoltà nell'interpretazione dei risultati ottenuti deriva dal fatto che le somiglianze tra cluster diversi possono derivare da (o essere la causa di) qualche differenza nei sottoinsiemi di variabili. Pertanto, i cluster risultanti sono intrinsecamente eterogenei.

Forse all'inizio sembra un po' confuso; infatti, rispetto ad altri metodi di analisi dei cluster descritti, il pooling a due vie è probabilmente il metodo meno comunemente utilizzato. Tuttavia, alcuni ricercatori ritengono che offra un potente strumento per l'analisi esplorativa dei dati (per ulteriori informazioni, vedere la descrizione di Hartigan di questo metodo (Hartigan, 1975)).

K significa metodo

Questo metodo di clustering differisce in modo significativo dai metodi di agglomerazione come Union (clustering ad albero) e Two-Way Union. Supponiamo di avere già ipotesi sul numero di cluster (per osservazione o per variabile).

Puoi dire al sistema di formare esattamente tre cluster in modo che siano il più diversi possibile. Questo è esattamente il tipo di problema che risolve l'algoritmo K-Means. In generale, il metodo K-mean costruisce esattamente K cluster distinti distanziati il ​​più possibile.

Nell'esempio della condizione fisica, un ricercatore medico può avere una "sospettazione" dalla sua esperienza clinica che i suoi pazienti generalmente rientrano in tre diverse categorie. Successivamente, potrebbe voler sapere se la sua intuizione può essere verificata numericamente, cioè, l'analisi dei cluster di K significa effettivamente produrre tre cluster di pazienti come previsto?

In tal caso, le medie delle varie misure dei parametri fisici per ogni cluster fornirebbero un modo quantitativo di rappresentare le ipotesi dello sperimentatore (ad esempio, i pazienti nel cluster 1 hanno un parametro alto pari a 1, un parametro inferiore pari a 2, ecc.).

Da un punto di vista computazionale, puoi pensare a questo metodo come un'analisi della varianza "al contrario".

Il programma inizia con K cluster selezionati casualmente, quindi modifica l'appartenenza degli oggetti ad essi per:

1. ridurre al minimo la variabilità all'interno dei cluster,
2. massimizzare la variabilità tra i cluster.

Questo metodo è simile all'analisi inversa della varianza (ANOVA) in quanto il test di significatività in ANOVA confronta la variabilità tra gruppi rispetto a quella all'interno del gruppo nel testare l'ipotesi che le medie di gruppo differiscano l'una dall'altra.

Nel clustering K-means, il programma sposta gli oggetti (ovvero le osservazioni) da un gruppo (cluster) a un altro per ottenere il risultato più significativo durante l'esecuzione dell'analisi della varianza (ANOVA). In genere, una volta ottenuti i risultati di un'analisi dei cluster K-means, è possibile calcolare le medie per ciascun cluster per ciascuna dimensione per valutare in che modo i cluster differiscono l'uno dall'altro.

Idealmente, dovresti ottenere medie molto diverse per la maggior parte, se non per tutte, delle misurazioni utilizzate nell'analisi. I valori della statistica F ottenuti per ciascuna dimensione sono un altro indicatore di quanto bene la dimensione corrispondente discrimina tra i cluster.

Fonte: biometrica.tomsk.ru

Classificazione degli oggetti in base alle loro caratteristiche

Analisi dei cluster (analisi dei cluster) - un insieme di metodi statistici multidimensionali per classificare gli oggetti in base alle loro caratteristiche, dividendo un insieme di oggetti in gruppi omogenei che sono vicini in termini di criteri di definizione, selezionando oggetti di un determinato gruppo.

Un cluster è un gruppo di oggetti identificati come risultato dell'analisi dei cluster basata su una data misura di somiglianza o differenza tra gli oggetti. L'oggetto sono le materie specifiche di studio che devono essere classificate. Gli oggetti nella classificazione sono, di regola, osservazioni. Ad esempio, i consumatori di prodotti, paesi o regioni, prodotti, ecc.

Sebbene sia possibile eseguire analisi dei cluster per variabili. La classificazione degli oggetti nell'analisi dei cluster multivariata avviene in base a diversi criteri contemporaneamente, che possono essere variabili sia quantitative che categoriali, a seconda del metodo di analisi dei cluster. Pertanto, l'obiettivo principale dell'analisi dei cluster è trovare gruppi di oggetti simili nel campione.

L'insieme dei metodi statistici multidimensionali dell'analisi dei cluster può essere suddiviso in metodi gerarchici (agglomeranti e divisivi) e non gerarchici (metodo k-means, analisi dei cluster a due stadi).

Tuttavia, non esiste una classificazione dei metodi generalmente accettata e i metodi di analisi dei cluster a volte includono anche metodi per la costruzione di alberi decisionali, reti neurali, analisi discriminante, regressione logistica.

L'ambito dell'analisi dei cluster, grazie alla sua versatilità, è molto ampio. L'analisi dei cluster è utilizzata in economia, marketing, archeologia, medicina, psicologia, chimica, biologia, pubblica amministrazione, filologia, antropologia, sociologia e altre aree.

Ecco alcuni esempi di applicazione dell'analisi dei cluster:

• medicina - classificazione delle malattie, loro sintomi, metodi di trattamento, classificazione dei gruppi di pazienti;
• marketing: i compiti di ottimizzazione della linea di prodotti dell'azienda, segmentazione del mercato per gruppi di beni o consumatori, identificazione di un potenziale consumatore;
• sociologia - divisione degli intervistati in gruppi omogenei;
• psichiatria: una corretta diagnosi dei gruppi di sintomi è cruciale per il successo della terapia;
• biologia - classificazione degli organismi per gruppo;
• economia - classificazione dei soggetti della Federazione Russa in base all'attrattiva degli investimenti.

Fonte: "statmethods.ru"

Informazioni generali sull'analisi dei cluster

L'analisi dei cluster include una serie di diversi algoritmi di classificazione. Una domanda comune posta dai ricercatori in molti campi è come organizzare i dati osservati in strutture visive.

Ad esempio, i biologi mirano a scomporre gli animali in specie diverse per descrivere in modo significativo le differenze tra loro.

Il compito dell'analisi dei cluster è dividere l'insieme iniziale di oggetti in gruppi di oggetti simili e vicini. Questi gruppi sono chiamati cluster.

In altre parole, l'analisi dei cluster è uno dei modi per classificare gli oggetti in base alle loro caratteristiche. È auspicabile che i risultati della classificazione abbiano un'interpretazione significativa.

I risultati ottenuti dai metodi di cluster analysis sono utilizzati in una varietà di aree:

1. Nel marketing, è la segmentazione dei concorrenti e dei consumatori.
2. In psichiatria, la corretta diagnosi di sintomi come paranoia, schizofrenia, ecc. è fondamentale per il successo della terapia.
3. Nella gestione è importante la classificazione dei fornitori, l'identificazione di situazioni produttive simili in cui si verifica il matrimonio.
4. In sociologia, la divisione degli intervistati in gruppi omogenei.
5. Negli investimenti di portafoglio, è importante raggruppare i titoli in base alla loro somiglianza nell'andamento del rendimento al fine di compilare, sulla base delle informazioni ottenute sul mercato azionario, un portafoglio di investimento ottimale che consenta di massimizzare il ritorno sugli investimenti per un dato grado di rischio .

In effetti, l'analisi dei cluster si è dimostrata valida in tutte le sfere della vita umana. In generale, ogniqualvolta sia necessario classificare una grande quantità di informazioni di questo genere e presentarle in una forma idonea ad ulteriori elaborazioni, la cluster analysis si rivela molto utile ed efficace.

L'analisi dei cluster consente di considerare una quantità piuttosto ampia di informazioni e di comprimere notevolmente grandi matrici di informazioni socio-economiche, rendendole compatte e visive.

L'analisi dei cluster è di grande importanza in relazione agli insiemi di serie temporali che caratterizzano sviluppo economico(ad esempio, congiuntura generale economica e delle merci).

Qui è possibile individuare i periodi in cui i valori degli indicatori corrispondenti erano abbastanza vicini, nonché determinare i gruppi di serie temporali, le cui dinamiche sono più simili. Nei problemi di previsione socio-economica, è molto promettente combinare l'analisi dei cluster con altri metodi quantitativi (ad esempio, con l'analisi di regressione).

Vantaggi e svantaggi

L'analisi dei cluster consente una classificazione obiettiva di tutti gli oggetti caratterizzati da una serie di caratteristiche. Ci sono una serie di vantaggi che ne derivano:

• I cluster risultanti possono essere interpretati, cioè per descrivere che tipo di gruppi esistono effettivamente.
• I singoli cluster possono essere abbattuti. Ciò è utile nei casi in cui sono stati commessi determinati errori nel set di dati, a seguito dei quali i valori degli indicatori per i singoli oggetti si discostano nettamente. Quando si applica l'analisi dei cluster, tali oggetti rientrano in un cluster separato.
• Per ulteriori analisi, possono essere selezionati solo quei cluster che hanno le caratteristiche di interesse.

Come qualsiasi altro metodo, l'analisi dei cluster presenta alcuni svantaggi e limiti. In particolare:

1. la composizione e il numero di cluster dipende dai criteri di partizionamento selezionati,
2. quando si riduce l'array di dati originale a una forma più compatta, possono verificarsi alcune distorsioni,
3. le singole caratteristiche dei singoli oggetti possono andare perse a causa della loro sostituzione con le caratteristiche dei valori generalizzati dei parametri del cluster.

Metodi

Attualmente sono noti più di cento diversi algoritmi di clustering. La loro diversità è spiegata non solo da diversi metodi computazionali, ma anche da diversi concetti alla base del clustering. È possibile fornire raccomandazioni per la scelta dell'uno o dell'altro metodo di raggruppamento solo in in termini generali, e il principale criterio di selezione è l'utilità pratica del risultato.

Il pacchetto STATISTICA implementa i seguenti metodi di clustering:

• Algoritmi gerarchici - clustering ad albero. Gli algoritmi gerarchici si basano sull'idea del clustering sequenziale. Nella fase iniziale, ogni oggetto viene considerato come un cluster separato. Nella fase successiva, alcuni dei cluster più vicini tra loro verranno combinati in un cluster separato.
• Metodo K-significa. Questo metodo è il più comunemente usato. Appartiene al gruppo dei cosiddetti metodi di riferimento della cluster analysis. Il numero di cluster K è impostato dall'utente.
• Associazione a due vie. Quando si utilizza questo metodo, il clustering viene eseguito simultaneamente sia per variabili (colonne) che per risultati di osservazione (righe).

La procedura di join a due vie viene eseguita quando ci si può aspettare che il clustering simultaneo su variabili e osservazioni fornisca risultati significativi.

I risultati della procedura sono statistiche descrittive per variabili e casi, nonché un grafico a colori bidimensionale su cui i valori dei dati sono codificati a colori. Dalla distribuzione del colore, puoi avere un'idea di gruppi omogenei.

Normalizzazione delle variabili

La divisione dell'insieme iniziale di oggetti in cluster è associata al calcolo delle distanze tra gli oggetti e alla scelta degli oggetti, la cui distanza è la più piccola possibile. La più comunemente usata è la distanza euclidea (geometrica) familiare a tutti noi. Questa metrica corrisponde a idee intuitive sulla vicinanza degli oggetti nello spazio (come se le distanze tra gli oggetti fossero misurate con un metro a nastro).

Ma per una data metrica, la distanza tra gli oggetti può essere fortemente influenzata dai cambiamenti nelle scale (unità di misura). Ad esempio, se una delle caratteristiche viene misurata in millimetri e quindi il suo valore viene convertito in centimetri, la distanza euclidea tra gli oggetti cambierà drasticamente. Ciò porterà al fatto che i risultati dell'analisi dei cluster potrebbero differire in modo significativo da quelli precedenti.

Se le variabili sono misurate in diverse unità di misura, allora è necessaria la loro normalizzazione preliminare, cioè la trasformazione dei dati iniziali, che li converte in quantità adimensionali.

La normalizzazione distorce fortemente la geometria dello spazio originale, che può modificare i risultati del raggruppamento. Nel pacchetto STATISTICA, qualsiasi variabile x è normalizzata secondo la formula:

Per fare ciò, fare clic con il tasto destro sul nome della variabile e selezionare la sequenza di comandi dal menu che si apre: Riempi/ Standardizza blocco/ Standardizza colonne. I valori della variabile normalizzata diventeranno uguali a zero e le varianze diventeranno uguali a uno.

Metodo K-significa in STATISTICA

Il metodo K-means suddivide un insieme di oggetti in un dato numero K di cluster diversi situati alla massima distanza possibile l'uno dall'altro. In genere, una volta ottenuti i risultati di un'analisi dei cluster K-means, è possibile calcolare le medie per ciascun cluster per ciascuna dimensione per valutare in che modo i cluster differiscono l'uno dall'altro.

Idealmente, dovresti ottenere medie molto diverse per la maggior parte delle misurazioni utilizzate nell'analisi. I valori della statistica F ottenuti per ciascuna dimensione sono un altro indicatore di quanto bene la dimensione corrispondente discrimina tra i cluster.

Ad esempio, consideriamo i risultati di un sondaggio condotto su 17 dipendenti di un'impresa sulla soddisfazione per gli indicatori di qualità della carriera. La tabella contiene le risposte alle domande del questionario su una scala di dieci punti (1 - punteggio minimo, 10 - massimo).

I nomi delle variabili corrispondono alle risposte alle seguenti domande:

1. SLT - una combinazione di obiettivi personali e obiettivi dell'organizzazione;
2. OSO - un senso di equità nei salari;
3. TBD - vicinanza territoriale alla casa;
4. PEW - un senso di benessere economico;
5. CR - crescita della carriera;
6. ZhSR: il desiderio di cambiare lavoro;
7. OSB è un senso di benessere sociale.

Utilizzando questi dati, è necessario suddividere i dipendenti in gruppi e selezionare per ciascuno di essi le leve di controllo più efficaci. Allo stesso tempo, le differenze tra i gruppi dovrebbero essere evidenti e all'interno del gruppo gli intervistati dovrebbero essere il più simili possibile.

Ad oggi, la maggior parte dei sondaggi sociologici fornisce solo una percentuale di voti: si considera il numero principale di risposte positive, ovvero la percentuale di coloro che sono insoddisfatti, ma questo problema non viene sistematicamente considerato. Molto spesso, il sondaggio non mostra le tendenze della situazione.

Le procedure di cluster analysis possono essere utilizzate per identificare, sulla base dei dati del sondaggio, alcune relazioni di caratteristiche realmente esistenti e generarne la tipologia su questa base. La presenza di eventuali ipotesi a priori di un sociologo durante il funzionamento delle procedure di analisi dei cluster non lo è condizione necessaria.

Nel programma STATISTICA, l'analisi dei cluster viene eseguita come segue.

1. Crea un file di dati.
2. Selezionare il modulo Statistiche/Tecniche esplorative multivariabili/Analisi dei cluster. Fare clic su OK, a seguito della quale verrà visualizzata una finestra di dialogo:

   

3. Nella finestra visualizzata, seleziona il metodo di clustering K-mean e fai clic su OK.
4. Nella finestra di dialogo che appare, imposta seguenti impostazioni:

   
   

   • Selezionare le variabili con il pulsante Variabili.
   • Seleziona gli oggetti di clustering: questi possono essere variabili - colonne (colonne variabili)) o osservazioni - righe (casi (righe)). Per prima cosa, raggruppiamo per righe (Casi(righe)).
   • Seleziona il numero di cluster.
     Questa scelta viene effettuata dall'utente in base alle proprie ipotesi sul numero di gruppi di oggetti simili.

     Quando si sceglie il numero di cluster, essere guidati da quanto segue:

     1. Il numero di cluster, se possibile, non dovrebbe essere troppo grande.
     2. La distanza alla quale gli oggetti di un dato ammasso sono stati uniti dovrebbe, se possibile, essere molto inferiore alla distanza alla quale qualcos'altro si unisce a questo ammasso.
     Quando si sceglie il numero di cluster, molto spesso ci sono diverse soluzioni corrette contemporaneamente. Siamo interessati, ad esempio, a come le risposte alle domande del questionario si correlano con i dipendenti ordinari e la gestione dell'impresa. Pertanto, scegliamo K=2. Per un'ulteriore segmentazione, puoi aumentare il numero di cluster.
     
   • Successivamente, è necessario selezionare la divisione iniziale degli oggetti in cluster (Centri cluster iniziali). Il pacchetto Statistica offre:
     1. selezionare le osservazioni con la massima distanza tra i centri degli ammassi;
     2. ordinare le distanze e selezionare le osservazioni a intervalli regolari (impostazione predefinita);
     3. prendi i primi centri di osservazione e attaccaci il resto degli oggetti.

     Per i nostri scopi, la prima opzione è adatta.

Molti algoritmi di clustering spesso “impongono” una struttura che non è inerente ai dati e disorientano il ricercatore. Pertanto, è estremamente necessario applicare diversi algoritmi di analisi dei cluster e trarre conclusioni basate su una valutazione generale dei risultati degli algoritmi.

I risultati dell'analisi possono essere visualizzati nella finestra di dialogo che appare:

Selezionando la scheda Grafico delle medie, verrà tracciato un grafico delle coordinate dei centri dei cluster:

Ogni linea tratteggiata su questo grafico corrisponde a uno dei cluster:

• Ogni divisione dell'asse orizzontale del grafico corrisponde a una delle variabili incluse nell'analisi.
• L'asse verticale corrisponde ai valori medi delle variabili per gli oggetti inclusi in ciascuno dei cluster.

Si può notare che ci sono differenze significative nell'atteggiamento dei due gruppi di persone nei confronti di una carriera di servizio su quasi tutte le questioni. Solo su una questione c'è completa unanimità - nel senso del benessere sociale (OSB), o meglio, della sua mancanza (2,5 punti su 10).

Si può presumere che:

1. il cluster 1 mostra lavoratori,
2. gruppo 2 - leadership:
   • I manager sono più soddisfatti dello sviluppo della carriera (CR), una combinazione di obiettivi personali e obiettivi organizzativi (SOL).
   • Hanno un maggiore senso di benessere economico (SEW) e un senso di equità salariale (SWA).
   • Sono meno preoccupati per la vicinanza a casa rispetto ai lavoratori, probabilmente a causa dei minori problemi di trasporto.
   • Inoltre, i manager hanno meno voglia di cambiare lavoro (JSR).

Nonostante il fatto che i lavoratori siano divisi in due categorie, danno relativamente le stesse risposte alla maggior parte delle domande. In altre parole, se qualcosa non si adatta al gruppo generale dei dipendenti, lo stesso non si adatta al senior management e viceversa.

L'armonizzazione dei grafici ci permette di concludere che il benessere di un gruppo si riflette nel benessere di un altro.

Il cluster 1 non è soddisfatto della vicinanza territoriale alla casa. Questo gruppo è la parte principale dei lavoratori che arrivano principalmente all'impresa da diverse parti della città. Pertanto, è possibile offrire al top management di destinare parte degli utili alla costruzione di alloggi per i dipendenti dell'impresa.

Esistono differenze significative nell'atteggiamento di due gruppi di persone nei confronti di una carriera di servizio:

1. Quei dipendenti che sono soddisfatti della crescita della carriera, che hanno un'alta coincidenza tra obiettivi personali e obiettivi dell'organizzazione, non hanno voglia di cambiare lavoro e provare soddisfazione per i risultati del proprio lavoro.
2. Al contrario, i dipendenti che desiderano cambiare lavoro e sono insoddisfatti dei risultati del proprio lavoro non sono soddisfatti degli indicatori di cui sopra.

L'alta dirigenza dovrebbe prestare particolare attenzione alla situazione attuale.

I risultati dell'analisi della varianza per ciascun attributo vengono visualizzati premendo il pulsante Analisi della varianza:

Produzione:

• somme dei quadrati della deviazione dell'oggetto dai centri dei cluster (SS Within),
• somme dei quadrati delle deviazioni tra i centri dei cluster (SS Between),
• Valori della statistica F,
• livelli di significatività pag.

Per il nostro esempio, i livelli di significatività per le due variabili sono piuttosto grandi, il che si spiega con il numero ridotto di osservazioni. Nella versione completa dello studio, che si trova nel paper, le ipotesi sull'uguaglianza delle medie per i centri cluster sono respinte a livelli di significatività inferiori a 0,01.

Il pulsante Salva classificazioni e distanze visualizza il numero di oggetti inclusi in ciascun cluster e le distanze degli oggetti dal centro di ciascun cluster.

La composizione di ciascun cluster e la distanza degli oggetti dal centro

Nella tabella sono riportati i numeri di caso (CASE_NO) che compongono i cluster con numeri CLUSTER e le distanze dal centro di ciascun cluster (DISTANCE).

Le informazioni sugli oggetti appartenenti ai cluster possono essere scritte in un file e utilizzate in ulteriori analisi. In questo esempio, un confronto dei risultati ottenuti con i questionari ha mostrato che il cluster 1 è costituito principalmente da lavoratori ordinari e il cluster 2 - da dirigenti.

Si può notare, quindi, che nell'elaborazione dei risultati dell'indagine, la cluster analysis si è rivelata un metodo potente che consente di trarre conclusioni che non possono essere raggiunte costruendo un istogramma di medie o calcolando la percentuale di soddisfatti di vari indicatori di la qualità della vita lavorativa.

Il clustering ad albero è un esempio di algoritmo gerarchico, il cui principio è raggruppare in sequenza prima gli elementi più vicini e poi sempre più distanti l'uno dall'altro in un cluster. La maggior parte di questi algoritmi parte da una matrice di similarità (distanze) e ogni singolo elemento è considerato inizialmente come un cluster separato.

Dopo aver caricato il modulo di analisi dei cluster e selezionato Joining (tree clustering), è possibile modificare i seguenti parametri nella finestra di immissione dei parametri di clustering:

1. Dati iniziali (Input). Possono essere sotto forma di matrice dei dati studiati (Raw data) e sotto forma di matrice di distanze (Distance matrix).
2. Clustering (Cluster) osservazioni (Casi (raw)) o variabili (Variabile (colonne)), che descrivono lo stato dell'oggetto.
3. Misure di distanza. Qui puoi scegliere tra le seguenti misure:
   • distanze euclidee,
   • Distanze euclidee al quadrato,
   • distanza degli isolati (distanza di Manhattan, distanza di un isolato (Manhattan)), distanza di Chebychev metrica,
   • distanza di potenza (Potenza…;),
   • Percentuale di disaccordo.
4. Metodo di clustering (regola di amalgama (collegamento)).
   Qui sono disponibili le seguenti opzioni:
   • collegamento singolo (metodo del vicino più vicino) (collegamento singolo),
   • collegamento completo (metodo dei vicini più distanti) (Complete Linkage),
   • media del gruppo di coppie non ponderata,
   • media ponderata del gruppo di coppie,
   • metodo del centroide non ponderato (centroide del gruppo di coppie non ponderato),
   • metodo del centroide ponderato (mediana) (centroide del gruppo di coppie ponderato (mediana)),
   • Il metodo di Ward.

Come risultato del clustering, viene costruito un dendrogramma orizzontale o verticale, un grafico su cui vengono determinate le distanze tra oggetti e cluster quando vengono combinati in sequenza.

La struttura ad albero del grafico consente di definire i cluster in base alla soglia selezionata, una data distanza tra i cluster.

Inoltre viene visualizzata la matrice delle distanze tra gli oggetti originari (Distance matrix); medie e deviazioni standard per ogni oggetto sorgente (statistiche distiptive). Per l'esempio considerato, eseguiremo un'analisi cluster di variabili con impostazioni predefinite. Il dendrogramma risultante è mostrato nella figura:

L'asse verticale del dendrogramma traccia le distanze tra oggetti e tra oggetti e cluster. Quindi, la distanza tra le variabili SEB e OSD è pari a cinque. Queste variabili nella prima fase vengono combinate in un cluster.

I segmenti orizzontali del dendrogramma sono disegnati a livelli corrispondenti alle distanze di soglia selezionate per un dato passo di raggruppamento.

Si può vedere dal grafico che la domanda "desiderio di cambiare lavoro" (JSR) forma un cluster separato. In generale, il desiderio di scaricare ovunque visita tutti allo stesso modo. Inoltre, un cluster separato è la questione della prossimità territoriale a casa (LHB).

In termini di importanza, è al secondo posto, il che conferma la conclusione sulla necessità di costruzione di alloggi, fatta secondo i risultati dello studio utilizzando il metodo K-means.

I sentimenti di benessere economico (PEW) e l'equità salariale (PWF) sono combinati: questo è un blocco di questioni economiche. Carriera(CR) e la combinazione di obiettivi personali e obiettivi organizzativi (SOL) sono combinati.

Altri metodi di raggruppamento, così come la scelta di altri tipi di distanze, non portano a un cambiamento significativo nel dendrogramma.

risultati

1. L'analisi dei cluster è un potente strumento per l'analisi esplorativa dei dati e la ricerca statistica in qualsiasi area tematica.
2. Il programma STATISTICA implementa metodi sia gerarchici che strutturali di cluster analysis. I vantaggi di questo pacchetto statistico sono dovuti alle loro capacità grafiche. Vengono fornite rappresentazioni grafiche bidimensionali e tridimensionali dei cluster ottenuti nello spazio delle variabili studiate, nonché i risultati della procedura gerarchica per il raggruppamento degli oggetti.
3. È necessario applicare diversi algoritmi di analisi dei cluster e trarre conclusioni basate su una valutazione generale dei risultati degli algoritmi.
4. L'analisi dei cluster può essere considerata riuscita se viene eseguita diversi modi, i risultati vengono confrontati e vengono trovati modelli generali, nonché cluster stabili indipendentemente dal metodo di clustering.
5. L'analisi dei cluster consente di identificare situazioni problematiche e delineare i modi per risolverli. Pertanto, questo metodo di statistica non parametrica può essere considerato come parte costitutiva analisi del sistema.

Tipi di input

• Descrizione indicativa degli oggetti. Ogni oggetto è descritto da un insieme delle sue caratteristiche, chiamato segni. Le funzionalità possono essere numeriche o non numeriche.
• Matrice delle distanze tra gli oggetti. Ogni oggetto è descritto dalle distanze rispetto a tutti gli altri oggetti nel campione di addestramento.

Matrice delle distanze può essere calcolato dalla matrice delle descrizioni delle caratteristiche degli oggetti un numero infinito modi, a seconda di come introdurre una funzione di distanza (metrica) tra le descrizioni delle caratteristiche. Si usa spesso la metrica euclidea, ma questa scelta nella maggior parte dei casi è euristica ed è dovuta solo a considerazioni di convenienza.

Il problema inverso - il ripristino delle descrizioni delle caratteristiche mediante la matrice delle distanze a coppie tra gli oggetti - nel caso generale non ha soluzione e la soluzione approssimativa non è unica e può contenere un errore significativo. Questo problema è risolto con metodi di ridimensionamento multidimensionale.

Pertanto, la formulazione del problema del clustering per matrice delle distanzeè più generale. D'altra parte, in presenza di descrizioni delle caratteristiche, spesso è possibile costruirne di più metodi efficaci raggruppamento.

Obiettivi del clustering

• Comprendere i dati identificando la struttura del cluster. La divisione del campione in gruppi di oggetti simili consente di semplificare ulteriormente l'elaborazione dei dati e il processo decisionale applicando il proprio metodo di analisi a ciascun cluster (la strategia "divide et impera").
• Compressione dati. Se il campione iniziale è eccessivamente grande, può essere ridotto, lasciando uno dei rappresentanti più tipici di ciascun cluster.
• Rilevamento di novità. Vengono selezionati oggetti atipici che non possono essere collegati a nessuno dei cluster.

Nel primo caso, cercano di ridurre il numero di cluster. Nel secondo caso, è più importante garantire un grado elevato (o fisso) di somiglianza degli oggetti all'interno di ciascun cluster e può esserci un numero qualsiasi di cluster. Nel terzo caso, i singoli oggetti che non rientrano in nessuno dei cluster sono di maggiore interesse.

In tutti questi casi, è possibile applicare il clustering gerarchico, quando i cluster di grandi dimensioni vengono suddivisi in cluster più piccoli, che a loro volta vengono suddivisi in gruppi ancora più piccoli, ecc. Tali attività sono chiamate attività di tassonomia.

Il risultato della tassonomia è una struttura gerarchica ad albero. Inoltre, ogni oggetto è caratterizzato da un'enumerazione di tutti i cluster a cui appartiene, solitamente dal grande al piccolo. Visivamente, la tassonomia è rappresentata come un grafico chiamato dendrogramma.

Un classico esempio di tassonomia basata sulla somiglianza è nomenclatura binomiale degli esseri viventi proposto da Carl Linnaeus a metà del XVIII secolo. Sistematizzazioni simili sono costruite in molte aree della conoscenza al fine di semplificare le informazioni su in gran numero oggetti.

Funzioni di distanza

Metodi di clustering

• Algoritmi di clustering statistico
• Raggruppamento gerarchico o tassonomia

Dichiarazione formale del problema del clustering

Sia un insieme di oggetti, sia un insieme di numeri (nomi, etichette) di cluster. La funzione della distanza tra gli oggetti è data. C'è un insieme di oggetti di addestramento finito. È necessario suddividere il campione in sottoinsiemi non sovrapposti, chiamati cluster, in modo che ogni cluster sia costituito da oggetti vicini in metric e gli oggetti di cluster diversi differiscano in modo significativo. In questo caso, a ciascun oggetto viene assegnato un numero di cluster.

Algoritmo di clusteringè una funzione che associa qualsiasi oggetto a un numero di cluster. L'insieme in alcuni casi è noto in anticipo, ma più spesso il compito è determinare il numero ottimale di cluster, dal punto di vista dell'uno o dell'altro criteri di qualità raggruppamento.

Il clustering (apprendimento non supervisionato) differisce dalla classificazione (apprendimento supervisionato) in quanto le etichette degli oggetti originali non sono inizialmente impostate e l'insieme stesso può anche essere sconosciuto.

La soluzione del problema del clustering è fondamentalmente ambigua e ci sono diverse ragioni per questo:

• Non esiste un criterio univocamente migliore per la qualità del clustering. Sono noti numerosi criteri euristici, nonché numerosi algoritmi che non hanno un criterio chiaramente definito, ma eseguono un raggruppamento abbastanza ragionevole "per costruzione". Tutti loro possono dare risultati diversi.
• Il numero di cluster è solitamente sconosciuto in anticipo ed è fissato secondo alcuni criteri soggettivi.
• Il risultato del clustering dipende in modo significativo dalla metrica, la cui scelta, di regola, è anche soggettiva ed è determinata da un esperto.

Collegamenti

• Vorontsov K.V. Metodi di insegnamento matematico per precedenti. Istituto di fisica e tecnologia di Mosca (2004), VMiK MGU (2007).
• Sergej Nikolenko. Slide delle lezioni "Clustering Algorithms 1" e "Clustering Algorithms 2". Corso "Sistemi di autoapprendimento".

Letteratura

1. Aivazyan S.A., Buchstaber V.M., Enyukov I.S., Meshalkin L.D. Statistica applicata: classificazione e riduzione delle dimensioni. - M.: Finanza e statistica, 1989.
2. Zhuravlev Yu.I., Ryazanov V.V., Senko O.V."Riconoscimento". Metodi matematici. Sistema informatico. Applicazioni pratiche. - M.: Fazis, 2006. .
3. Zagoruiko N.G. Metodi applicati di analisi dei dati e della conoscenza. - Novosibirsk: IM SO RAN, 1999. .
4. Mandel I. D. analisi di gruppo. - M.: Finanza e statistica, 1988. .
5. Shlesinger M., Glavach V. Dieci lezioni sul riconoscimento statistico e strutturale. - Kiev: Naukova Dumka, 2004. .
6. Hastie T., Tibshirani R., Friedman J. Gli elementi dell'apprendimento statistico. - Springer, 2001. .

Tipi di input

• Descrizione indicativa degli oggetti. Ogni oggetto è descritto da un insieme delle sue caratteristiche, chiamato segni. Le funzionalità possono essere numeriche o non numeriche.
• Matrice delle distanze tra gli oggetti. Ogni oggetto è descritto dalle distanze rispetto a tutti gli altri oggetti nel campione di addestramento.

Obiettivi del clustering

• Comprendere i dati identificando la struttura del cluster. La divisione del campione in gruppi di oggetti simili consente di semplificare ulteriormente l'elaborazione dei dati e il processo decisionale applicando il proprio metodo di analisi a ciascun cluster (la strategia "divide et impera").
• Compressione dati. Se il campione iniziale è eccessivamente grande, può essere ridotto, lasciando uno dei rappresentanti più tipici di ciascun cluster.
• rilevamento novità. rilevamento novità). Vengono selezionati oggetti atipici che non possono essere collegati a nessuno dei cluster.

Nel primo caso, cercano di ridurre il numero di cluster. Nel secondo caso, è più importante garantire un elevato grado di somiglianza degli oggetti all'interno di ciascun cluster e può esserci un numero qualsiasi di cluster. Nel terzo caso, i singoli oggetti che non rientrano in nessuno dei cluster sono di maggiore interesse.

In tutti questi casi, è possibile applicare il clustering gerarchico, quando i cluster di grandi dimensioni vengono suddivisi in cluster più piccoli, che a loro volta vengono suddivisi in gruppi ancora più piccoli, ecc. Tali attività sono chiamate attività di tassonomia.

Il risultato della tassonomia è una struttura gerarchica ad albero. Inoltre, ogni oggetto è caratterizzato da un'enumerazione di tutti i cluster a cui appartiene, solitamente dal grande al piccolo.

Un classico esempio di tassonomia basata sulla somiglianza è la nomenclatura binomiale degli esseri viventi proposta da Carlo Linneo a metà del XVIII secolo. Sistematizzazioni simili sono costruite in molti campi della conoscenza per organizzare le informazioni su un gran numero di oggetti.

Metodi di clustering

Dichiarazione formale del problema del clustering

Sia un insieme di oggetti, sia un insieme di numeri (nomi, etichette) di cluster. La funzione della distanza tra gli oggetti è data. C'è un insieme di oggetti di addestramento finito. È necessario suddividere il campione in sottoinsiemi non sovrapposti, chiamati cluster, in modo che ogni cluster sia costituito da oggetti vicini in metric e gli oggetti di cluster diversi differiscano in modo significativo. In questo caso, a ciascun oggetto viene assegnato un numero di cluster.

Algoritmo di clusteringè una funzione che associa qualsiasi oggetto a un numero di cluster. L'insieme in alcuni casi è noto in anticipo, ma più spesso il compito è determinare il numero ottimale di cluster, dal punto di vista dell'uno o dell'altro criteri di qualità raggruppamento.

Letteratura

1. Aivazyan S.A., Buchstaber V.M., Enyukov I.S., Meshalkin L.D. Statistica applicata: classificazione e riduzione delle dimensioni. - M.: Finanza e statistica, 1989.
2. Zhuravlev Yu.I., Ryazanov V.V., Senko O.V."Riconoscimento". Metodi matematici. Sistema informatico. Applicazioni pratiche. - M.: Fazis, 2006. ISBN 5-7036-0108-8.
3. Zagoruiko N.G. Metodi applicati di analisi dei dati e della conoscenza. - Novosibirsk: IM SO RAN, 1999. ISBN 5-86134-060-9.
4. Mandel I. D. analisi di gruppo. - M.: Finanza e statistica, 1988. ISBN 5-279-00050-7.
5. Shlesinger M., Glavach V. Dieci lezioni sul riconoscimento statistico e strutturale. - Kiev: Naukova Dumka, 2004. ISBN 966-00-0341-2.
6. Hastie T., Tibshirani R., Friedman J. Gli elementi dell'apprendimento statistico. - Springer, 2001. ISBN 0-387-95284-5.
7. Jain Murty Flynn Clustering dei dati: una revisione . // Calcolo ACM. Sopravvissuto 31 (3) , 1999

link esterno

In russo

• www.MachineLearning.ru - risorsa wiki professionale dedicata all'apprendimento automatico e al data mining
• S. Nikolenko. Diapositive della lezione sugli algoritmi di clustering

In inglese

• COMPACT - Pacchetto comparativo per la valutazione del clustering. Un pacchetto Matlab gratuito, 2006.
• P. Berkhin, Indagine sulle tecniche di data mining di clustering, Accumula software, 2002.
• Jain, Murty e Flynn: Clustering dei dati: una revisione, Comp. ACM Soprav., 1999.
• per un'altra presentazione di gerarchiche, k-medie e fuzzy c-medie vedere questa introduzione al clustering . Ha anche una spiegazione sulla miscela di gaussiane.
• Davide Dowe, Pagina di modellazione della miscela- altri collegamenti a clustering e modelli misti.
• un tutorial sul clustering
• Il libro di testo on-line: teoria dell'informazione, inferenza e algoritmi di apprendimento, di David J.C. MacKay include capitoli sul clustering k-medie, clustering soft k-medie e derivazioni tra cui l'algoritmo EM e la vista variazionale dell'algoritmo EM.
• "The Self-Organized Gene", tutorial che spiega il clustering attraverso l'apprendimento competitivo e le mappe auto-organizzanti.
• kernlab - pacchetto R per l'apprendimento automatico basato su kernel (include l'implementazione del clustering spettrale)
• Tutorial - Tutorial con introduzione degli Algoritmi di Clustering (k-medie, fuzzy-c-medie, gerarchiche, miste di gaussiane) + alcune demo interattive (applet java)
• Software di data mining: il software di data mining utilizza spesso tecniche di clustering.
• Java Competive Learning Application Una suite di reti neurali non supervisionate per il clustering. Scritto in Java. Completo di tutto il codice sorgente.