A pinboard by
Behnam Tavakkol

PhD student, Rutgers, The State University of New Jersey


Cluster analysis is one of the main areas of research in data mining. In cluster analysis, clustering validity indices are the main tools of evaluating the quality of the formed clusters of data. In this study, we developed a few clustering validity indices for a type of data objects known as uncertain data. Uncertain data objects can be considered as probability density functions or samples of observations. To our best knowledge, in the existing literature, there is not any clustering validity index for uncertain data.


K-means clustering versus validation measures: a data-distribution perspective.

Abstract: K-means is a well-known and widely used partitional clustering method. While there are considerable research efforts to characterize the key features of the K-means clustering algorithm, further investigation is needed to understand how data distributions can have impact on the performance of K-means clustering. To that end, in this paper, we provide a formal and organized study of the effect of skewed data distributions on K-means clustering. Along this line, we first formally illustrate that K-means tends to produce clusters of relatively uniform size, even if input data have varied "true" cluster sizes. In addition, we show that some clustering validation measures, such as the entropy measure, may not capture this uniform effect and provide misleading information on the clustering performance. Viewed in this light, we provide the coefficient of variation (CV) as a necessary criterion to validate the clustering results. Our findings reveal that K-means tends to produce clusters in which the variations of cluster sizes, as measured by CV, are in a range of about 0.3-1.0. Specifically, for data sets with large variation in "true" cluster sizes (e.g., CV > 1.0), K-means reduces variation in resultant cluster sizes to less than 1.0. In contrast, for data sets with small variation in "true" cluster sizes (e.g., CV < 0.3), K-means increases variation in resultant cluster sizes to greater than 0.3. In other words, for the earlier two cases, K-means produces the clustering results which are away from the "true" cluster distributions.

Pub.: 20 Dec '08, Pinned: 27 Jun '17