IJPAM: Volume 68, No. 2 (2011)

A FRACTAL DIMENSION STANDPOINT
TO THE CLUSTER VALIDATION PROBLEM
Dvora Toledano-Kitai$^1$, Renata Avros$^2$, Zeev Volkovich$^3$
$^{1,2,3}$Software Engineering Department
ORT Braude College
P.O. Box 78, Karmiel, 21982, ISRAEL
$^1$e-mail: [email protected]
$^2$e-mail: r_ [email protected]
$^3$e-mail: [email protected]

Abstract. The article proposes a new standpoint to the cluster validation problem based on a fractal dimension cluster quality model. The suggested method uses the fractal property to describe cluster geometrical configuration. This notion is applied for further exploration of cluster validity, assuming that its low variability, calculated via different samples, can indicate stable partitions. In the framework of this model, the goodness of a partition is characterized by the quality of mixing two random samples within the partition's clusters. It is implicitly assumed that the quality of a cluster is reflected by its fractal dimensionality estimated via different samples. Valid results are obtained by repeating these calculations on sufficiently large amount of samples drawn. Hence, empirical distributions of the absolute values of the fractal dimension differences are constructed. The distribution most concentrated at the origin is proposed to indicate the true number of clusters. Numerical experiments are presented for various datasets.

Received: January 20, 2011
AMS Subject Classification: 28A80, 13F60
Key Words and Phrases: cluster validation problem, fractal dimension cluster quality model, empirical distributions, fractal dimension, numerical experiments


Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2011
Volume: 68
Issue: 2