# Clustering Algorithm with a Greedy Agglomerative Heuristic and Special Distance Measures
## 1 Introduction  
The search for a clustering algorithm that has both high accuracy and stability of the result, and, at the same time, a high speed of operation, is one of the problems of cluster analysis. The clustering result depends on the initially selected number of subsets, as well as the selected measure of similarity (dissimilarity) [1]. One of the most famous automatic grouping models is the k-means model [2], which was proposed by [PERSON] [3]. The goal of the k-means problem is to find \(k\) points (centers, centroids) \(X_{1}\),..., \(X_{k}\) in an \(M\)-dimensional space, such that the sum of the squared distances from the known points (data vectors) \(A_{1}\),..., \(A_{m}\) to the nearest of the required points reaches a minimum:  
\[\arg\min F(X_{1},\ldots,X_{k})=\sum_{j\in\{1,k\}}\min\lVert X_{j}-A_{i}\rVert^{ 2}. \tag{1}\]  
Optimization model (1) can be considered as a location problem, where the points \(X_{j}\) have to be placed in an optimal way. Location theory has been developing for a long time separately from cluster analysis while solving very close or completely identical problems. [PERSON] proposed an iterative procedure for solving the Weber problem, one of the simplest location problems, based on an iterative weighted least squares method [4]. This algorithm determines a set of weights that are inversely proportional to the distances from the current estimate to the sample points and creates a new estimate that is the weightedaverage of the sample according to these weights. In specific situations, [PERSON]'s algorithm is very slow and does not always converge. Local search methods for solving location problems are used in Ref. [5]. The standard local descent algorithm starts with an initial solution \(S=\{X_{1},\ldots,X_{k}\}\), chosen randomly or with the help of some auxiliary algorithm. At each step of the local descent, there is a transition from the current solution to a neighboring solution with a smaller value of the objective function until the local optimum is reached. The key problem here is to find the set of neighboring solutions \(n(S)\). At each step of the local search, the neighborhood function \(n(S)\) specifies a set of possible search directions. Neighborhood functions can be very diverse, and the neighborhood relation is not always symmetrical. Local search algorithms are widely used to solve NP-hard discrete optimization problems. However, simple local descent does not allow the finding of the global optimum of the problem. Local search methods were further developed in so-called metaheuristics, in particular in the search algorithm with variable neighborhoods (variable neighborhoods search, VNS). Its main idea is to systematically change the neighborhood function and the corresponding change in the landscape during the local search. The k-means problem was algorithmically implemented by [PERSON] [6]. For the observation vector X, the k-means algorithm is designed to determine \(k\) centers and assign data points (objects) to each center to form clusters \(C_{j}\), \(j=1\,\ldots\,k\) while minimizing the difference between the objects within the cluster. In the k-means algorithm, it is necessary to initially predict the number of groups (clusters). In addition, the result obtained depends on the initial choice of centers, which is one of the main disadvantages of the algorithm. The modern literature offers many approaches to setting the initial centroids for the k-means algorithm, which are basically various evolutionary and random search methods. One of the most popular methods is the k-means++ algorithm [7], where the first centroid is chosen randomly and further selection goes with a certain probability. Moreover, in Ref. [8], a similar method is developed based on finding areas with maximum density. In Ref. [9], the authors propose a brute-force approach to the initialization of the k-means algorithm. [PERSON] et al. in Ref. [10] introduce three algorithms (merging, construction and separation) to create starting solutions of the k-means problem. In Ref.