Descriviamo di seguito l’algoritmo per l’inserzione di un nuovo oggetto nel CF Tree. Per comodità denominiamo tale oggetto “Ent”.
1. Identificazione della foglia appropriata: Partendo dalla radice si per- corre tutto l’albero seguendo un cammino opportuno: ogni volta che si scende al livello inferiore, viene scelto il figlio più vicino, utilizzando come misura di distanza una delle metriche proposte (D0, D1, D2, D3, D4). Ci si ferma quando un nodo foglia è stato raggiunto.
2. Aggiornamento della foglia: Si cerca il campo più vicino ad “Ent” al- l’interno della foglia identificata come descritto nel punto precedente: supponiamo sia Li. A questo punto testiamo se Li può contenere “Ent” senza violare il vincolo sulla soglia: il nuovo cluster ottenuto dalla fusio- ne di “Ent” con Li deve avere diametro minore di T2. Se la condizione è rispettata, il vettore CF di Li è aggiornato per rispecchiare l’inseri- mento. Altrimenti si deve aggiungere alla foglia un nuovo campo per “Ent”. Se la foglia non ha spazio sufficiente per il nuovo campo dob- biamo dividere (split) il nodo foglia in due sotto-nodi. I due campi tra loro più lontani nella foglia costituiranno i generatori delle due nuove foglie e i campi rimanenti saranno distribuiti tra i due nodi in base al criterio di maggior vicinanza.
3. Aggiornamento del cammino dalla foglia alla radice: Dopo l’inse- rimento di “Ent” in una foglia dobbiamo aggiornare le informazioni di CF per ogni campo dei nodi non foglia sul cammino fino alla radice. 2Facciamo notare che la CF del nuovo cluster può essere calcolata sommando le CF di
Se lo split non si è verificato, è sufficiente eseguire somme di vettori CF per tenere in conto l’aggiunta di “Ent”. Se invece lo split della foglia si è verificato, è necessario inserire un nuovo campo nel nodo padre, per descrivere la nuova foglia generatasi. Se il nodo padre ha spazio per il nuovo campo, è sufficiente aggiornare i vettori CF nei livelli superiori. In generale comunque può essere necessario effettuare uno splitting an- che sul nodo padre e così via fino alla radice. Se anche la radice subisce uno split, la profondità del CF Tree risulta aumentata di uno.
4. Perfezionamento del processo di fusione: Gli split sono causati dal- la dimensione della pagina di memoria, che non dipende dalle proprietà di clustering dei dati. La presenza di un ordine sparso nei dati di ingres- so può degradare la qualità della classificazione e ridurre l’utilizzazione dello spazio. Un semplice passo di fusione addizionale aiuta ad attenua- re questo problema: supponiamo che si verifichi lo split di una foglia e che questo si propaghi ai livelli superiori fino ad arrestarsi ad un cer- to nodo Nj, il quale è quindi in grado di ospitare il campo aggiuntivo relativo allo split. A questo punto scansioniamo il nodo Nj alla ricer- ca dei due campi più vicini. Se tali campi non sono relativi allo split, cerchiamo di fonderli e di conseguenza di fondere i due corrispondenti nodi figli. Se il numero di campi contenuti nei due nodi figli è maggiore di quello che può essere contenuto in una pagina di memoria, effettuia- mo un nuovo split del risultato della fusione. Durante questo resplit, nel caso che uno dei due generatori attragga un numero di pagine suf- ficiente a riempire una pagina, inseriamo i campi rimanenti nel nodo dell’altro generatore. Ricapitolando, se i campi fusi assieme stanno su una singola pagina, abbiamo liberato un nodo, che può essere utilizzato con vantaggio in futuro, e creato lo spazio per un nuovo campo nel no- do Nj, migliorando l’utilizzazione della memoria e posponendo gli split futuri. In caso contrario abbiamo comunque migliorato la distribuzione dei campi sui due figli più vicini.
Poiché ogni nodo può contenere solo un numero limitato di campi, non sempre corrisponde a un cluster naturale. Può accadere che due sotto-cluster, che dovrebbero appartenere allo stesso cluster, risultino divisi su più nodi. A seconda dell’ordine con cui i dati in ingresso vengono presentati e in base al loro livello di dispersione, è anche possibile che due sotto-cluster, che non dovrebbero trovarsi nello stesso cluster, finiscano col trovarsi nello stesso nodo.
Queste anomalie, dovute alle dimensioni della pagina di memoria, occor- rono raramente, ma sono nondimeno indesiderate. Vi si può porre rimedio
Caricamento in memoria e costruzione dell’albero Fase 1 Fase 2 Opzionale Fase 3 Fase 4
Opzionale e off line
Condensazione in un range desiderabile al fine di costruire un albero CF più piccolo
Dati
Albero
Clustering Globale
Albero
Perfezionamento del clustering
Albero CF Iniziale
Albero CF più piccolo
Cluster di buona qualità
Cluster di ottima qualità
Figura 4.4: Overview di BIRCH
tramite un algoritmo globale (o semi-globale) che ridispone i campi delle foglie tra i nodi (vedi 4.4 pag. 54).
Un altro fenomeno indesiderato è quello dei dati duplicati: lo stesso punto può presentarsi più volte, ma in tempi diversi. Può accadere che esso sia in- serito in diversi campi di nodi foglia. Ovvero, nei casi in cui vi sia dispersione dei dati in ingresso, è possibile che un punto venga inserito in un campo di una foglia in cui non sarebbe dovuto entrare. Questo problema può essere risolto con dei passaggi algoritmici aggiuntivi sui dati (vedi fase 4, paragrafo
4.4, pag. 54).