DESPOTA: un approccio basato sui test di permutazione per la ricerca della partizione su un dendrogramma

La classificazione gerarchica è uno dei metodi di classificazione mag- giormente utilizzati in molti contesti applicativi (Everitt et al., 2001). La pos- sibilità di scegliere tra differenti partizioni alternative in funzione del livello di omogeneità interno delle corrispondenti classi è sicuramente uno dei punti di maggiore interesse dei metodi gerarchici che spesso li porta a preferire ai tradizionali metodi di partizionamento. La naturale rappresentazione grafica dell’insieme delle partizioni risultanti da un algoritmo di classificazione ge- rarchica è il dendrogramma. Nella scelta della partizione si procede usual- mente utilizzando un taglio orizzontale del dendrogramma ma così facendo una serie di partizioni ospitate nell’albero non saranno mai esplorate. Tali partizioni potranno infatti essere individuate solo utilizzando un taglio su li- velli differenti. La proposta mira appunto ad esplorare l’intero insieme di partizioni disponibili e sfrutta i test di permutazione per effettuare tale ricerca partendo dalla radice dell’albero e scendendo fino agli elementi terminali dello stesso. Un ulteriore vantaggio dell’algoritmo proposto è l’individuazione automatica del numero di classi da scegliere, caratteristica questa che rende una tecnica implementabile agevolmente in sistemi di clas- sificazione automatica.