Il progetto consiste nell'implementazione e nella valutazione sperimentale di algoritmi per il problema del raggruppamento (clustering problem).
Nel problema del raggruppamento si hanno $n$ oggetti sui quali è definita una distanza $d$ che verifica le seguenti proprietà: (i) $d(a,b) \geq 0$, (ii) $d(a,b) = 0$ se e solo se $a = b$, (iii) $d(a,b) = d(b,a)$. Talvolta si assume anche la proprietà della disuguaglianza triangolare, cioè (iv) $d(a,c) \leq d(a,b) + d(b,c)$. Informalmente, il problema consiste nel definire una partizione di $k$ gruppi (cluster) di oggetti, con $k$ fissato, tale che oggetti nello stesso gruppo sono vicini e oggetti in gruppi diversi sono lontani rispetto alla distanza $d$.
Il problema del raggruppamento può essere affrontato con due approcci simmetrici: (A) minimizzo la distanza all'interno dei gruppi (intra-gruppo), (B) massimizzo la distanza tra gruppi diversi (inter-gruppo).
MinIntra (Gonzalez, 1985) è un algoritmo che segue l'approccio A. L'algoritmo crea una partizione di $k$ gruppi $G_1, \ldots, G_k$ durante $k-1$ fasi. Ogni gruppo viene identificato da un rappresentante membro del gruppo. Inizialmente tutti gli oggetti sono assegnati ad un unico gruppo $G_1$ e il rappresentante viene scelto in modo arbitrario. Durante la $i$-esima fase, alcuni elementi dei gruppi $G_1, \ldots, G_i$ vengono spostati in un nuovo gruppo $G_{i+1}$ nel seguente modo. Prima viene individuato l'oggetto $p$ appartenente ad uno dei primi $i$ gruppi $G_1, \ldots, G_i$ tale che la distanza che lo separa dal rappresentante del suo gruppo è massima. L'oggetto $p$ viene inserito nel nuovo gruppo $G_{i+1}$ come rappresentante. Successivamente si spostano nel gruppo $G_{i+1}$ tutti gli oggetti dei gruppi $G_1, \ldots, G_i$ la cui distanza dal rappresentante del gruppo di appartenentza è maggior o uguale alla distanza da $p$.
L'algorimo MinIntra ha complessità $O(k \cdot n)$. Supponiamo che la distanza $d$ soddisfi le quattro proprietà della distanza inclusa la disuguaglianza triangolare. Definiamo la distanza interna ad un gruppo come il massimo delle distanze tra coppie di oggetti del gruppo. Definiamo inoltre il costo di una partizione come il massimo tra le distanze interne ai gruppi della partizione (funzione obiettivo intra-gruppo). Si può dimostrare che:
MaxInter è un algoritmo che segue l'approccio B. L'algoritmo consiste nel trovare l'albero di supporto di costo minimo del grafo completo in cui i nodi sono gli oggetti e il peso degli archi è la distanza tra gli oggetti. Successivamente di rimuovono i $k-1$ archi più costosi, ottenendo una foresta di $k$ alberi. I gruppi della partizione restituita corrispondono ai nodi di ogni albero della foresta.
Il costo di MaxInter è quello dell'algoritmo di Kruskal (o di Prim) su un grafo completo, vale a dire $O(n^2 \cdot \log n)$. Definiamo il costo di una partizione come la minima distanza tra due oggetti appartenenti a gruppi diversi (funzione obiettivo inter-gruppo). Si può mostrare che la soluzione fornita dall'algoritmo MaxInter è la soluzione ottima del corrispondente problema di massimizzazione, vale a dire la soluzione con costo massimo.
Il progetto richiede di:
Negli esperimenti, usare come oggetti i punti sul piano bidimensionale dei numeri naturali e come distanza quella Euclidea. Visualizzare le partizioni ottenute usando grafici (scatterplot) generati con il programma R evidenziando ogni gruppo in modo differente.