Incremental clustering

Abstract

The generation of the objective information catalogue that enables further image mining functions needs the application of a similarity measure to group the points in the feature space. The generated clusters shall contain robust information on image-signal classes, and preserves an image and a spatial index. Due to the large volumes of data and to the incremental nature of the catalogue generation, "classical" clustering algorithms are limited in their use. For a new dataset we need to process all data set, the new and the old too. For these reasons we need a new algorithm compatible with the imposed conditions. We propose an algorithm for incremental clustering using grouping based on similarity of the local fractal dimension. By embedding the data set in an n-dimensional grid, we can compute the frequency with which data point fall into cell, and compute the fractal dimension. The fractal dimension is computed by box counting algorithm. The main concept of the algorithm is to add points incrementally to existing clusters, based on how they affect the fractal dimension of the cluster. The algorithm has two steps: initialization and cluster update. In the initialization step it is better if we have a sample of the dataset that is significant overall the feature space as that we can get a significant clustering (number and form), but we can work as well with a normal dataset. If the dataset used for initialization step does not reflect the true clusters structure, it is needed to do additional operations to optimize the groups of existing clusters, like splitting and merging. The algorithm requires one scan of the data, can cope with large dataset, needs only small space to describe the cluster (number of points of the box to use box counting algorithm), and is incremental.