Hierarchical topological clustering

Il paper propone un algoritmo di clustering topologico gerarchico, applicabile con qualsiasi metrica di distanza, capace di identificare cluster di forma arbitraria e outlier in dataset complessi come immagini, dati medici ed economici.

L'essenziale

Il "Rilevatore di Pecore Nere": Capire il caos attraverso la forma

Immaginate di essere in una piazza affollatissima durante un festival. C'è un gran caos: gente che balla in cerchio, gruppi di amici che chiacchierano, persone che corrono da una parte all'altra e, magari, un singolo artista di strada isolato in un angolo.

Se chiedessi a un computer di "raggruppare le persone", la maggior parte dei programmi farebbe un pasticcio. Alcuni cercherebbero di dividere la folla in cerchi perfetti (ma i gruppi di amici sono spesso allungati o irregolari); altri cercherebbero di contare quante persone ci sono in un metro quadro (ma un gruppo di persone che balla può essere molto sparso e sembra "poco denso" anche se è un gruppo unito).

In questo studio, Ana Carpio e Gema Duro propongono un nuovo metodo chiamato HTC (Hierarchical Topological Clustering). Invece di guardare solo "quanto sono vicine le persone", questo metodo guarda la "forma" che la folla crea.

1. La metafora del "Filo Invisibile" (Come funziona l'algoritmo)

Immaginate che ogni persona nella piazza abbia un rotolo di filo colorato. L'algoritmo inizia con un filo cortissimo: a questa distanza, nessuno è connesso a nessuno. Ognuno è un'isola.

Poi, iniziamo ad allungare il filo, un centimetro alla volta:

• Fase 1: Il filo è corto. Vediamo migliaia di puntini isolati.
• Fase 2: Allungiamo il filo. Improvvisamente, i membri di un gruppo di amici si toccano con il filo. Si forma una "macchia" di colore.
• Fase 3: Allunghiamo ancora. Le macchie iniziano a toccarsi tra loro e si fondono in gruppi più grandi.

Il segreto dell'HTC: L'algoritmo non si ferma a un solo livello. Lui osserva tutta la storia di come queste macchie si sono formate e fuse. Questo crea una sorta di "albero genealogico" dei gruppi (chiamato gerarchia).

2. Perché è speciale? (Il potere della "Persistenza")

La vera magia sta nel distinguere il rumore dalle cose importanti.

• Il Rumore: Immaginate un passante che cammina da solo. Appena allunghiamo il filo di un millimetro, si unisce a un gruppo. La sua "esistenza come individuo" è durata pochissimo. È un evento passeggero, probabilmente rumore.
• L'Outlier (La Pecora Nera): Immaginate ora un artista di strada in un angolo remoto. Anche quando il filo diventa lungo, lui resta isolato. Deve diventare lunghissimo prima di toccare il gruppo principale. Poiché la sua "solitudine" è durata a lungo (in matematica si dice che ha una alta persistenza), l'algoritmo ci dice: "Ehi, guarda che questo non è un errore, questo è un elemento importante e diverso!"

3. A cosa serve nella vita reale?

Gli autori hanno testato questo "rilevatore di forme" in tre campi molto diversi:

• In Medicina (Il confine tra salute e malattia): Immaginate di guardare una foto di cellule sane e cellule tumorali. Le cellule tumorali spesso non formano un blocco compatto, ma "invadono" il tessuto sano come piccole isole sparse. I vecchi metodi vedevano solo un caos di punti. L'HTC, invece, riesce a vedere queste "isole" e a capire quanto profondamente il tumore sta penetrando, proprio perché riconosce la loro forma specifica.
• Nell'Economia (I partner commerciali): Analizzando il commercio tra la Spagna e l'Europa, l'algoritmo non si limita a dire "questi paesi scambiano molto". Riesce a isolare i "giganti" (come Francia o Germania) che restano separati dal resto del gruppo per molto tempo, identificandoli come i veri motori dell'economia.
• Nell'Analisi dei Geni (La ricerca del cancro): Nei dati genetici, alcuni geni si comportano in modo strano rispetto agli altri. L'HTC riesce a isolare quei geni "ribelli" che persistono come outlier, aiutando i ricercatori a capire quali potrebbero essere i bersagli migliori per una terapia contro il cancro.

In sintesi

Se i metodi tradizionali sono come guardare una foto e contare quanti pixel ci sono, l'HTC è come guardare un film che ci mostra come le forme nascono, crescono e si fondono. Questo permette di non perdere di vista le "pecore nere" e le strutture più complesse che i metodi classici ignorano.

Sommario tecnico

Riassunto Tecnico: Hierarchical Topological Clustering (HTC)

Titolo: Hierarchical topological clustering
Autori: Ana Carpio e Gema Duro
Data: 6 Gennaio 2026 (arXiv:2601.00892v1)

---

1. Il Problema (Problem)

L'analisi del clustering mira a categorizzare oggetti in gruppi basati sulla loro affinità. Tuttavia, i metodi tradizionali presentano limiti significativi in presenza di rumore e outlier (valori anomali):

• Metodi basati su partizioni (es. K-means, K-medoids): Falliscono nell'identificare cluster non convessi poiché assegnano i punti al centroide più vicino.
• Clustering gerarchico classico: Può produrre soluzioni subottimali soggette a scelte arbitrarie di linkage.
• Metodi basati sulla densità (es. DBSCAN): Richiedono la scelta non banale di parametri critici (soglie di densità e distanza) che spesso non sono intuitivi.
• Limiti degli outlier: Molti algoritmi non distinguono tra "rumore" (errori casuali da scartare) e "outlier significativi" (elementi rari ma parte integrante del fenomeno studiato).

2. Metodologia (Methodology)

Gli autori propongono un nuovo algoritmo denominato Hierarchical Topological Clustering (HTC), basato sulla persistenza dell'omologia ($H_0$), uno strumento della Topological Data Analysis (TDA).

Il processo si articola come segue:

1. Scelta della metrica: L'algoritmo può essere implementato con qualsiasi scelta di distanza (Euclidea, Wasserstein, Fermat, ecc.).
2. Costruzione della Filtrazione: Si utilizza una filtrazione di complessi simpliciali (tipicamente la filtrazione di Vietoris-Rips). Si parte da un parametro di distanza $r=0$ (dove ogni punto è un cluster isolato) e si aumenta progressivamente $r$.
3. Evoluzione dei Cluster: Man mano che $r$ aumenta, vengono aggiunti archi tra i punti. I punti connessi formano componenti connesse che rappresentano i cluster.
4. Gerarchia Topologica: L'algoritmo tiene traccia di come i cluster si fondono tra loro al variare di $r$. La "persistenza" di un cluster o di un outlier è determinata per quanto tempo rimane isolato prima di fondersi con la componente principale.
5. Complessità: L'algoritmo ha una complessità massima di $MN^2$, rendendolo efficiente per dataset di piccole e medie dimensioni.

3. Contributi Chiave (Key Contributions)

• Flessibilità Geometrica: A differenza di K-means, l'HTC identifica cluster di forma arbitraria.
• Identificazione Automatica degli Outlier: Gli outlier (singoli o collettivi) emergono naturalmente come componenti che si fondono con il cluster principale solo per valori molto alti di $r$.
• Assenza di Parametri "Ciechi": Non richiede la scelta arbitraria di una soglia di densità come DBSCAN; la struttura gerarchica fornisce una visione completa a diverse scale.
• Integrazione tra TDA e Clustering: Mentre molti studi TDA usano i diagrammi di persistenza per raggruppare dataset, l'HTC usa l'informazione omologica per raggruppare gli elementi interni al dataset stesso.

4. Risultati (Results)

L'efficacia dell'algoritmo è dimostrata su quattro ambiti diversi:

• Biologia (Fronti frammentati): L'HTC distingue con successo l'interfaccia tra cellule sane e maligne e identifica le "isole" di cellule cancerose che migrano nel tessuto sano. Metodi come K-means e DBSCAN falliscono nel catturare questa geometria.
• Elaborazione Immagini (Quality Assessment): Utilizzando la distanza di Wasserstein, l'HTC identifica automaticamente immagini con difetti (es. una linea nera aggiunta) o eccessivamente compresse, distinguendole dalle immagini originali o da quelle con compressione accettabile.
• Economia (Dati commerciali): Analizzando il commercio tra Spagna ed Europa, l'algoritmo identifica i partner commerciali dominanti (es. Francia, Germania, Italia) come outlier persistenti, separandoli chiaramente dai paesi con bassi volumi di scambio.
• Genetica (Espressione genica): Applicato ai dati del cancro al seno (TGCA), l'HTC identifica geni specifici (es. CCNE1, CDKN2A) che persistono come outlier, confermando la loro rilevanza clinica come bersagli terapeutici o indicatori prognostici.

5. Significato e Conclusioni (Significance)

L'HTC rappresenta un avanzamento significativo perché trasforma la teoria della persistenza topologica in uno strumento pratico di clustering. La sua capacità di fornire una interpretazione geometrica dei dati e di distinguere tra rumore e outlier significativi lo rende estremamente utile in settori dove la forma dei dati e la rilevanza degli elementi rari sono cruciali, come la medicina di precisione, l'analisi economica e il controllo qualità delle immagini.