The idea of representation has been used in various fields of study from data analysis to political science. In this paper, we define representativeness and describe a method to isolate data points that can represent the entire data set. Also, we show how the minimum set of representative data points can be generated. We use data from GLOBE (a project to study the effects on Land Change based on a set of parameters that include temperature, forest cover, human population, atmospheric parameters and many other variables) to test & validate the algorithm. Principal Component Analysis (PCA) is used to reduce the dimensions of the multivariate data set, so that the representative points can be generated efficiently and its Representativeness has been compared against Random Sampling of points from the data set.
The k-means clustering algorithm is a widely used algorithm @cite_4 . This is a centroid or partition based clustering technique. The algorithm clusters all the data points into clusters. The algorithm starts by selecting an arbitrary set of centroids @math . It then assigns each point to the closest centroid @math . Once the points are clustered, it calculates the center of mass for each cluster to get a new set of centroids. The previous steps are then repeated for the new centroids. After each iteration the set of centroids moves closer to the final set such that the next iteration does not change the set of centroids chosen. This means the center of mass for the clusters calculated remains constant. The algorithm stops computing after this point. The worst case time complexity is @math @cite_4 where is the number of data points, is the number of clusters and the points are in a -dimensional space.
@cite_4
2132958733
The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e. O(nkd)) is, in general, exponential in the number of points (when kd=Ω(n log n)). Recently, Arthur and Vassilvitskii [2] showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to 2Ω(√n) with a construction in d=Ω(√n) dimensions. In [2] they also conjectured the existence of super-polynomial lower bounds for any d≥ 2. Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2Ω(n).