Paper Info
Title
Towards Obtaining Upper Bound on Sensitivity Computation Process for Cluster Validity Measures.
Abstract
Cluster validity indices are proposed in the literature to measure the goodness of a clustering result. The validity measure provides a value which shows how good or bad the obtained clustering result is, as compared to the actual clustering result. However, the validity measures are not arbitrarily generated. A validity measure should satisfy some of the important properties. However, there are cases when in-spite of satisfying these properties, a validity measure is not able to differentiate the two clustering results correctly. In this regard, sensitivity as a property of validity measure is introduced to capture the differences between the two clustering results. However, sensitivity computation is a computationally expensive task as it requires to explore all the possible combinations of clustering results which are very large in number and these are growing exponentially. So, it is required to compute the sensitivity efficiently. As the possible combinations of clustering results grow exponentially, so it is required to first obtain an upper bound on this possible number of combinations which will be sufficient to compute the value of the sensitivity. In this paper, we obtain an upper bound on the number of possible combinations of clustering results. For this purpose, a generic approach which is suitable for various validity measures and a specific approach which is applicable for two validity measures are proposed. It is also shown that this upper bound is sufficient to compute the sensitivity of various validity measures. This upper bound is very less as compared to the total number of possible combinations of clustering results.
Year
DOI
Venue
2018
10.3233/FI-2018-1749
FUNDAMENTA INFORMATICAE
Keywords
Field
DocType
Clustering algorithm,sensitivity,cluster validity measure
Discrete mathematics,Upper and lower bounds,Mathematics,Computation
Journal
Volume
Issue
ISSN
163
4
0169-2968
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Sumit Mishra1125.94
Samrat Mondal210018.02
Sriparna Saha31064106.07