Cluster Analysis

VARIABILIX11 X12 … X1kX21 X22 … X2kOBJECTS … … … …Xn1 … … Xnk

Misura delle distanze

Il concetto di vicinanza (o lontananza) deve essere associato a una quantità misurabile e oggettiva (funzione distanza). Quest'ultima può essere associata a più variabili.

Proprietà delle distanze:

Dati due objects i e j:

• d(i,j) ≥ 0
• d(i,i) = 0
• d(i,j) = d(j,i)

Metrica – Disuguaglianza Triangolare

Una misura di distanza è una metrica se soddisfa quanto segue:

Dati tre objects i, i' e i'':

d(i,i') + d(i',i'') ≥ d(i,i'')

La distanza tra due oggetti è sempre minore della somma delle distanze tra tali oggetti e un terzo punto.

Questa proprietà naturale non è sempre verificata in alcuni spazi (vedi il paragrafo "Distanza Minkowski" pagina 3)

Distanza Euclidea

La distanza euclidea è quella con...

La quale sei abitualmente portato a ragionare, ovvero quella che rappresenta il cammino più breve che è possibile fare per raggiungere un determinato punto.

Banalmente, se noi vogliamo andare da Roma a Milano, possiamo percorrere il tragitto diretto ovvero, senza passare per Firenze.

Roma - Firenze - Milano

La distanza tra due punti nel piano cartesiano (distanza euclidea) si calcola come radice quadrata della somma tra il quadrato della differenza delle ascisse e il quadrato della differenza delle ordinate dei due punti.

I più attenti avranno capito che questa formula non è altro che la formula per calcolare l'ipotenusa di un triangolo rettangolo, visto semplicemente sotto un altro punto di vista.

La distanza tra due punti è per definizione non negativa; dunque, è positiva oppure nulla se i due punti coincidono.

• ≥d(i,j) 0 (Proprietà della non negatività)
• d(i,i) = 0
• d(i,j) = d(j,i) (Proprietà della commutatività)

simmetria)• ≤d(i,j) d(i,k) + d(k,j) (Proprietà della disuguaglianza triangolare)

Distanza Ultrametrica

Una distanza d(x, y) si dice distanza ultrametrica se gode, non solo le 4 proprietà appena menzionate, ma anche della seguente proprietà, detta disuguaglianza ultrametrica:

d(x, y) ≤ max {d(x, z), d(y, z)}

La disuguaglianza triangolare afferma che la distanza tra due punti deve essere sempre minore o uguale alla somma delle distanze tra ciascun punto e un terzo punto arbitrario.

Nel caso della distanza ultrametrica, tuttavia, la disuguaglianza triangolare è sostituita dalla disuguaglianza ultrametrica, che è una generalizzazione più forte. La disuguaglianza ultrametrica afferma che per tre punti A, B e C in uno spazio metrico, la distanza tra A e B è al più massima tra la distanza tra A e C e la distanza tra B e C.

In altre parole, la disuguaglianza ultrametrica dichiara che una delle distanze è "dominante".

Rispetto alle altre due. Per comprendere meglio il concetto di distanza ultrametrica, possiamo fare un esempio utilizzando una struttura chiamata albero di Galton-Watson.

In un albero di Galton-Watson, i nodi rappresentano le generazioni di una famiglia, e ogni nodo ha un certo numero di figli. La distanza tra due nodi nell'albero di Galton-Watson può essere definita come il numero di generazioni che separa i due nodi. Utilizzando questa definizione di distanza, si può dimostrare che la distanza nell'albero di Galton-Watson soddisfa la disuguaglianza ultrametrica.

La distanza ultrametrica ha diverse applicazioni pratiche. Ad esempio, viene utilizzata nella teoria dei grafi per rappresentare la similarità tra gli oggetti in modo più accurato di una semplice distanza euclidea o Manhattan.

La distanza Minkowski può essere considerata come la metrica che generalizza il concetto di distanza. Per particolari valori di "m" si ottengono altre distanze: m=1

Distanza Manhattan→- m=2 Distanza Euclidea→-Per m 1 la distanza di Minkowski è una metrica (in quanto soddisfa la disuguaglianza triangolare). ≥Curiosità: Sapete perché si chiama distanza Manhattan? Central Park Ponte di Brooklyn Time Square Perché per andare dal Central park al Time Square non è possibile andarci percorrendo il percorso meno lungo, ovvero il tratto obbliquo, ma bisogna passare necessariamente il Ponte di Brooklyn, a causa della struttura in cui sono organizzate le strade, ovvero a griglia. Pertanto, il tragitto complessivo sarà: (Central Park Ponte di Brooklyn) + (Ponte di Brooklyn Time Square). → →Questa metrica viene anche chiamata Metrica del Taxi. Problemi con le metriche È difficile selezionare la m corretta, questo perché: • i gruppi sono sconosciuti • la m corretta potrebbe essere diversa da gruppo a gruppo • È difficile stimare m sulla base di dati reali • il numero di

gruppi e di elementi ad essi appartenenti dipende da m (cerchio logico)

Distanza statistica

Una distanza statistica quantifica la distanza tra due oggetti statistici, che possono essere due variabili casuali, o due distribuzioni di probabilità o campioni, oppure la distanza può essere tra un singolo punto campione e una popolazione.

La matrice A dà un peso implicito alle variabili. Solitamente la trasformazione matriciale viene scelta allo scopo di standardizzare i dati e rendere lo spazio sferico.

Spazio sferico e rotazione

La rotazione si riferisce alla trasformazione dei dati da un sistema di coordinate ad un altro mediante una rotazione lineare. In altre parole, si può applicare una rotazione ai dati per cambiare l'orientamento degli assi del sistema di coordinate. Questo può essere utile nella Cluster Analysis per vari motivi. Ad esempio, se si hanno dati multidimensionali, la rotazione può essere utilizzata per individuare la

direzione principale di variabilità dei dati. Questo può semplificare l'interpretazione dei risultati e aiutare a individuare pattern o cluster nascosti nei dati. Lo spazio sferico, d'altra parte, si riferisce ad un tipo di spazio in cui i dati sono rappresentati come punti su una sfera. Nello spazio sferico, le coordinate dei punti sono solitamente specificate utilizzando la longitudine e la latitudine. Questo tipo di rappresentazione è spesso utilizzato quando si lavora con dati che hanno una componente circolare o periodica, come ad esempio dati geografici (ad esempio, posizioni geografiche) o dati temporali (ad esempio, misurazioni orarie). Nella Cluster Analysis, lo spazio sferico può essere utilizzato per raggruppare oggetti o dati che mostrano somiglianze in termini di direzione o posizione angolare. Ad esempio, si potrebbero raggruppare le posizioni geografiche che sono vicine tra loro sulla sfera terrestre. La distanza tra due punti nello spazio sferico può essere calcolata utilizzando apposite formule matematiche. può essere calcolata utilizzando una metrica apposita come la distanza geodetica o la distanza angolare. In sintesi, la rotazione e lo spazio sferico possono essere utilizzati nella per semplificare l'interpretazione dei dati multidimensionali o per raggruppare oggetti sulla base della loro posizione o direzione angolare. Distanza tra : - Distanza minima - Distanza massima - Distanza media - Distanza tra i centroidi dei due cluster (una sorta di baricentro del gruppo) - Distanza tra i medoidi dei due cluster (è essenzialmente un punto dati dal set di input, il quale risulta il meno dissimile rispetto a tutti gli altri oggetti del cluster) Decomposizione delle distanze: Quando si adotta la metrica euclidea, vale una regola di scomposizione delle distanze: le distanze totali (SST) di ogni punto dal baricentro massimo, vengono scomposte nella somma delle distanze interne (SSW)Il clustering è un metodo di analisi dei dati che permette di raggruppare gli elementi in base alle loro caratteristiche simili. Questo viene fatto calcolando le distanze tra gli elementi e creando dei cluster in cui gli elementi sono più simili tra loro rispetto agli elementi degli altri cluster. Il clustering può essere utile per diverse ragioni. Ad esempio, può essere utilizzato per identificare gruppi omogenei di clienti in base alle loro preferenze di acquisto, per individuare cluster di geni con espressione simile nel campo della biologia o per raggruppare documenti simili nel campo del text mining. Esistono diversi algoritmi di clustering, come il k-means, il hierarchical clustering e il DBSCAN. Ogni algoritmo ha i suoi vantaggi e svantaggi e può essere utilizzato in base alle specifiche esigenze dell'analisi dei dati. In conclusione, il clustering è un metodo di analisi dei dati che permette di raggruppare gli elementi in base alle loro caratteristiche simili. Questo può essere utile per diverse applicazioni e esistono diversi algoritmi di clustering disponibili.

Nella classificazione, l'obiettivo è classificare nuovi item in una delle classi date; il clustering ricade più all'interno del framework dell'analisi esplorativa dei dati, quando non si hanno informazioni a priori sulla struttura in classi dei dati. Gli item si indicano gli elementi di un insieme.

Algoritmi di cluster Analysis

Una categorizzazione dei principali metodi di Clustering (Per rispondere alla domanda "Algoritmi di cluster Analysis")

Esiste un gran numero di algoritmi di clustering. La scelta dell'algoritmo da utilizzare in un dato contesto dipende dal tipo di dati disponibili, dal particolare scopo e dall'applicazione. Se l'analisi dei cluster viene utilizzata come un tool descrittivo o esplorativo, è possibile provare diversi algoritmi sugli stessi dati per vedere cosa ciascuno di essi riesce a fare.

In generale, i principali metodi di clustering possono essere classificati come di seguito specificato.

Metodi di partizionamento.

Dato un database di n oggetti, un metodo di partizionamento costruisce k partizioni dei dati, dove ciascuna partizione rappresenta un cluster, e k ≤ n. In altre parole, l'algoritmo classifica i dati in k gruppi che, nel loro insieme, soddisfano i seguenti requisiti:

1. ciascun gruppo deve contenere almeno un oggetto;
2. ciascun oggetto deve appartenere esattamente ad un gruppo.

Il criterio generale di un buon partizionamento è che gli oggetti nello stesso cluster devono essere "vicini", o correlati, l'un l'altro, mentre gli oggetti di cluster differenti sono molto distanti tra loro.

Esistono vari altri criteri per giudicare la qualità delle partizioni:

Ottenere l'ottimalità globale nel clustering basato sul partizionamento richiederebbe l'enumerazione esaustiva di tutte le possibili combinazioni di partizioni, il che è computazionalmente costoso.