Data mining- Classificazione non gerarchica

Classificazione non gerarchica

Effettuiamo l’analisi del modello k-means, che consiste in un metodo di classificazione non gerarchica. Questo metodo richiede la determinazione a priori del numero di classi che definiscono la partizione. L’algoritmo è convergente e il numero di iterazioni richieste è generalmente limitato: ciò rende questo metodo utilizzabile anche a grossi insiemi di dati.

La soluzione ottenuta non rappresenta la soluzione ottimale ma solo una delle tante possibili, ottenuta avendo determinato a priori quel numero di classi e avendo scelto quelle unità iniziali. La miglior partizione in k classi avrà infatti un'inerzia entro le classi sicuramente superiore alla migliore partizione in k+1 classi, fino al limite della partizione banale in cui ogni individuo costituisce una classe a sé; l’inerzia tra i gruppi è massima, mentre l’inerzia entro i gruppi è nulla.

L’obiettivo è raggruppare le n unità in k classi in modo da ottenere classi quanto più possibile omogenee al loro interno e separate l'una dall'altra. Il criterio k-means, presentato da Mac Queen, è una generalizzazione del metodo delle nubi dinamiche. Si definiscono inizialmente k nuclei. I centroidi dei gruppi non restano fissi lungo tutto un ciclo iterativo ma si modificano e vengono aggiornati dopo la classificazione di ogni unità.

La scelta dei nuclei iniziali non consente la definizione della partizione ottima, fornendo soluzioni vincolate alle scelte iniziali. Nel metodo dei k-means le partizioni ottenute costituiscono degli ottimi locali che dipendono fortemente dalle scelte iniziali. Per ovviare a tali scelte iniziali, è possibile ricorrere a più estrazioni casuali iniziali, confrontando poi le partizioni finali ottenute. Gli individui che sono sempre classificati insieme costituiscono le “forme forti” e rappresentano le parti realmente omogenee dell’insieme.

Vantaggi e svantaggi della CNG e CAG

I metodi non gerarchici forniscono risultati la cui lettura è generalmente più semplice perché costituiti da un’unica partizione. Nel caso dell’analisi gerarchica la lettura dei risultati si presenta più complessa ma anche più ricca di possibili approfondimenti. Un’analisi gerarchica consente una strutturazione dei dati in maniera più analitica che richiede una maggiore attenzione in sede di interpretazione.

Il vantaggio di una rappresentazione del criterio gerarchico è che il numero che rappresenta la partizione ottimale può essere determinato tagliando l’albero a vari livelli: più il livello è elevato, più le parti raggruppate sono eterogenee. Le tecniche gerarchiche possono risultare meno efficaci di quelle non gerarchiche, in particolare di quelle che usano metodi di aggregazione che costituiscono partizioni caratterizzate da gruppi con forte omogeneità interna.

Un possibile svantaggio del metodo k-medie consiste nella presenza di notevoli distorsioni dei risultati nel caso in cui nei dati vi fossero dei valori anomali o outliers. In questo caso l’utilizzo di un numero di gruppi molto elevato costituisce un buon esercizio per verificare l’esistenza di questi valori poiché, con molta probabilità, le unità non anomale tenderanno a concentrarsi in pochi gruppi, mentre gli outliers rimarranno isolati nella classificazione formando dei gruppi anche contenenti un solo elemento.

Potendo confrontare i risultati ottenuti, in seguito a una diversa logica di partizione, possiamo individuare quelle parti realmente omogenee dell’insieme che costituiscono le cosiddette forme forti. Quest’ultime sono rappresentate da quegli elementi che risultano classificati sempre insieme, non risentendo della casualità delle estrazioni iniziali.

Differenze tra classificazione gerarchica e non gerarchica

• 1) Quando si hanno molte unità n, il costo computazionale delle tecniche gerarchiche è sempre inferiore rispetto a quello delle tecniche non gerarchiche. La tecnica gerarchica richiede più risorse, in termini di tempo di calcolo e di memoria richiesta dalla tecnica non gerarchica.
• 2) Maggiore rigidità dovuta ad eventuali aggregazioni improprie per il metodo di classificazione gerarchica; infatti se un individuo viene assegnato a un gruppo in modo non propriamente opportuno in una fase, vi rimarrà per tutte le fasi successive. Mentre per quanto riguarda i metodi non gerarchici, l’assegnazione di un individuo a un gruppo può cambiare fino a quando non si raggiunge una partizione soddisfacente.
• 3) Se per la classificazione gerarchica arriviamo a stabilire il numero dei gruppi a nostro piacere, attraverso la scelta del livello di ‘taglio’ del dendrogramma, per la classificazione non gerarchica il numero dei gruppi viene fissato a priori.

L'algoritmo dei centri mobili

Fu proposto da Forgy. Si consideri lo spazio R definito dalle p variabili osservate su un insieme di n individui: l’obiettivo è raggruppare le n unità in k classi in modo da ottenere classi quanto più possibile omogenee al loro interno e separate l'una dall'altra.

Si definisce il numero k di classi e si scelgono in modo casuale k elementi che costituiscono i nuclei provvisori delle k classi. Si calcolano le distanze di ciascuno di questi al gruppo rappresentato dal nucleo più vicino. Si definiscono i nuovi nuclei delle classi, individuati nei baricentri delle classi stesse. Si calcolano le distanze degli individui dai nuovi nuclei e si definisce la nuova partizione. Si ripetono i passi 2 e 3 finché due iterazioni successive definiscono la stessa partizione, la riduzione dell’inerzia...