Abstract
Il clustering è una metodologia di apprendimento automatico che ha come obiettivo la suddivisione di un insieme iniziale di oggetti in sottoinsiemi detti, appunto, cluster. La suddivisione avviene facendo sì che gli oggetti in un cluster siano quanto più simili tra di loro, mentre gli oggetti in cluster diversi risulteranno essere quanto più differenti tra di loro. Il clustering è una metodologia di apprendimento detta
non supervisionata, poiché il raggruppamento degli oggetti in sottoinsiemi avviene in maniera totalmente automatica: l’informazione necessaria a tale raggruppamento è contenuta soltanto nei dati e nessun intervento esterno (umano) aggiunge informazione al fine di migliorare l’apprendimento.
I campi applicativi del clustering sono molteplici. Un esempio è il clustering di documenti di testo: l’obiettivo in questo caso è quello di formare gruppi di documenti correlati tra loro, ovvero che trattino il medesimo argomento.
L’obiettivo del presente lavoro di tesi è stato quello di studiare e approfondire tecniche di clustering innovative e/o sperimentali. Le metodologie prese in esame sono due. La prima è conosciuta come principio della Minimima Informazione di Bregman. Tale principio generalizza il classico schema di relocazione adottato dal K-means a una vasta gamma di funzioni di divergenza, dette appunto divergenze di Bregman. Sulla base di tale principio è possibile definire un nuovo, più astratto, schema di clustering. In aggiunta, è stato formulato anche uno schema di co-clustering sulla base di tale principio, che, come osserveremo nel seguito, generalizza ulteriormente il processo di clustering.
Il secondo approccio studiato e approfondito è il Support Vector Clustering. Si tratta di un processo di clustering che fa uso di macchine di apprendimento allo stato dell’arte: le Support Vector Machines. Il Support Vector Clustering è attualmente oggetto di ricerca attiva, poiché trattasi ancora di un metodo sperimentale. Tale metodo è stato analizzato a fondo e sono stati anche apportati alcuni contributi, che permettono ad esempio di diminuire il numero di iterazioni, di aumentare l’accuratezza e di ridurre la complessità computazionale totale.
I domini applicativi principali sono stati il text mining e l’astrophysics data mining. Nell’ambito di questi domini applicativi ci si è mossi nella verifica e nell’approfondimento delle proprietà di entrambe le strategie summenzionate attraverso esperimenti mirati.
Tra i risultati emersi vi sono la robustezza rispetto alla presenza dei cosiddetti missing values, la riduzione delle dimensionalità, la robustezza rispetto al rumore e ai cossiddetti outliers, la capacità di descrivere cluster di forma arbitraria.
Clustering is an automatic learning technique aimed at grouping a set of objects into subsets or clusters. The goal is to create clusters that are coherent internally, but substantially different from each other. In plain words, objects in the same cluster should be as similar as possible, whereas objects in one cluster should be as dissimilar as possible from objects in the other clusters.
Clustering is an unsupervised learning technique, because it groups objects in clusters without any additional information: only the information provided by data is used and no human operation adds bits of information to improve the learning.
The application domains are manifold. For example, the grouping of text documents: in this case the goal is the construction of groups of documents related to each other, i.e. documents treating the same argument.
The goal of this thesis is studying in depth state-of-the-art and experimental clustering techniques. We consider two techniques. The first is known as Minimum Bregman Information principle. Such a principle generalizes the classic relocation scheme adopted yet by K-means, in order to allow the employment of a rich gamma of divergence functions said just Bregman divergences. A new, more general, clustering scheme was developed on top of this principle. Moreover, a co-clustering scheme is formulated too. This leads to an important generalization, as we will see in the sequel.
The second approach is the Support Vector Clustering. It is a clustering process which relies on the state-of-the-art of the learning machines: the Support Vector Machines. The Support Vector Clustering is currently subject of active research, as it still is in early stage of development. We have accurately analyzed such a clustering method and we have also provided some contributions which allow allow a reduction in the number of iterations and in the computational complexity and a gain in accuracy.
The main application domains we have dealt to are the text mining and the astrophysics data mining. Within these application domains we have verified and accurately analyzed the properties of both methodologies, by means of dedicated experiments.
The results are given in terms of robustness w.r.t. the missing values, the dimensionality reduction, the robustness w.r.t. the noise and the outliers, the ability of describing clusters of arbitrary shapes.
