Clustering Structured Data with the SPARE Library

摘要

In this paper we propose the SPARE C++ Library as a flexible tool for solving data driven modelling problems, where the domain space is not necessary constrained to be the set of real valued vectors. The. possibility to face Pattern Recognition problems directly on structured domains (multimedia data, strings, graphs) is fundamental to the effective solution of many interesting applications in the field of content based retrieval and Knowledge Discovery. As an instance of this particular characteristic of SPARE, we considered a clustering problem defined in the string domain, focusing on the problem of cluster representation in data domains where only a dissimilarity measure can be fixed. To this aim we propose to adopt the MinSOD (Minimum Sum of Distances) defined as the element of a cluster minimizing the sum of dissimilarities from all. the other elements in the considered set. Since the precise computation of the MinSOD have a high computational cost, we propose a suboptimal procedure consisting in computing the representative of the cluster considering only a reduced pool of samples, instead of the whole set of objects in the cluster. We have carried out some tests in order to ascertain the sensitivity of the clustering procedure with respect to the number of samples in the pool used to compute the MinSOD. Results show a good robustness of the proposed procedure. The implementation is available as part of the SPARE library, published as an open source project.