2009 · 94 citations · 5 references
ComputingComputer ScienceData ScienceAlgorithmsData MiningSet TheoryClustered Data AnalysisData PartitioningCluster AnalysisCluster Evaluation MetricsClusteringClustering AnalysisNp-hardness
We investigate measures of the clusterability of data sets. Namely, ways to define how ‘strong ’ or ‘conclusive ’ is the clustering structure of a given data set. We address this issue with generality, aiming for conclusions that apply regardless of any particular clustering algorithm or any specific data generation model. We survey several notions of clusterability that have been discussed in the literature, as well as propose a new notion of data clusterability. Our comparison of these notions reveals that, although they all attempt to evaluate the same intuitive property, they are pairwise inconsistent. Our analysis discovers an interesting phenomenon; Although most of the common clustering tasks are NP-hard, finding a closeto-optimal clustering for well clusterable data sets is easy (computationally). We prove instances of this general claim with respect to the various clusterability notions that we discuss. Finally, we investigate how hard it is to determine the clusterability value of a given data set. In most cases, it turns out that this is an NP-hard problem. 1
5
Property testing and its connection to learning and approximation
Oded Goldreich, Shari Goldwasser, Dana Ron · Journal of the ACM · 1998 · 1.1K citations · Full text
Clustering Large Graphs via the Singular Value Decomposition
Petros Drineas, Alan Frieze, Ravi Kannan et al. · Machine Learning · 2004 · 477 citations · Full text