Clustering, a fundamental task in data science and machine learning, groups a set of objects in such a way that objects in the same cluster are closer to each other than to those in other clusters. In this paper, we consider a well-known structure, so-called @math -nets, which rigorously captures the properties of clustering. We devise algorithms that improve the run-time of approximating @math -nets in high-dimensional spaces with @math and @math metrics from @math to @math , where @math . These algorithms are also used to improve a framework that provides approximate solutions to other high dimensional distance problems. Using this framework, several important related problems can also be solved efficiently, e.g., @math -approximate @math th-nearest neighbor distance, @math -approximate Min-Max clustering, @math -approximate @math -center clustering. In addition, we build an algorithm that @math -approximates greedy permutations in time @math where @math is the spread of the input. This algorithm is used to @math -approximate @math -center with the same time complexity.
An approach on hierarchical clustering was presented by @cite_6 . They construct an algorithm based on furthest first traversal, which is essentially building a greedy permutation and then traversing the permutation in order.
@cite_6
2769245605
We show that for any data set in any metric space, it is possible to construct a hierarchical clustering with the guarantee that for every k, the induced k-clustering has cost at most eight times that of the optimal k-clustering. Here the cost of a clustering is taken to be the maximum radius of its clusters. Our algorithm is similar in simplicity and efficiency to popular agglomerative heuristics for hierarchical clustering, and we show that these heuristics have unbounded approximation factors.