Fractal Clustering

Clustering is a widely used knowledge discovery technique. Large-scale clustering has received a lot of attention recently. However, existing algorithms often do not scale with the size of the data and the number of dimensions, or fail to find arbitrary shapes of clusters or deal effectively with the presence of noise. In this book a new clustering algorithm based on self-similarity properties is discussed. Self-similarity is the property of being invariant with respect to the scale used to look at the data set. While fractals are self-similar at every scale, many data sets only exhibit self-similarity over a range of scales. Self- similarity can be measured using the fractal dimension. Our new clustering algorithm called Fractal Clustering (FC) places points incrementally in the cluster for which the change in the fractal dimension after adding the point is the least, so points in the same cluster have a great degree of self-similarity among them (and much less self- similarity with respect to points in other clusters). Two applications on projected clustering and tracking deviation in evolving data sets are also discussed.