Distributed K-means Clustering Using Topological Relationships

Data partitioning, also known as cluster analysis, is the process of finding groups in data that are ideally characterised by high internal similarity and significant differences between groups [1]. Today, the rapid growth of acquisition and storage technologies has led to an increase in the amount of data available in various fields [2]. This data is often geographically dispersed across different locations and can be used to extract meaningful insights, dependencies or correlations; traditional centralised clustering algorithms are impractical due to data volume, processing capacity and privacy concerns associated with data aggregation [3].

Distributed clustering algorithms address this by building the overall model without requiring access to data from different locations. Two architectures are used [4]: synchronous, where all nodes build the global model together, requiring extensive data exchange, with communication either direct between pairs of nodes [5], circular between all nodes [6], or following a hierarchical structure [7]. Asynchronous methods, where each node builds a local model and sends it to a central location to be combined into a global model [8]. This method is more privacy friendly as only local models are shared.

K-means [9, 10] is one of the most extensively studied and widely used clustering algorithms, favoured for its conceptual simplicity and computational efficiency for clustering large datasets [11]. Numerous distributed variants of the k-means algorithm have been proposed, they differ in the way they communicate and combine the local results [12]. In order to reduce communication between the different sites, a Peer-to-Peer (P2P) architecture has been proposed by Datta et al. [13] where each node of the network calculates the clusters of local data, and exchanges the centroids with its neighbors. Each neighbor recalculates its centroids, using its local data, and the centroids obtained from its neighbors. However, no proof of convergence nor indication on the speed of convergence of the algorithm was provided.

Ng [14] proposed to perform a two-level classification. The first one on the local data of each node, and the second on the local partitions generated by the previous step by performing another clustering of their centroids.

Jin et al. [15] proposed a distributed fast and exact k-means clustering (DFEKM) that uses data sampling to improve performance. Each site sends a sample of its data to a central site where it is grouped using k-means method. After a complete run through all data, the centers are calculated, and the convergence is determined based on a metric called the confidence radius estimated in the previous step. The disadvantage of the proposed method is that the data set is sampled, the results strongly depend on the samples drawn (its size and content) and that in some cases, groups present in data may not exist in the sample. The best sample is detailed by Broder et al. [16].

In the study of Durut et al. [17], a master/slave architecture is used to distribute the first step of k-means. On each iteration, all nodes perform the assignment step and calculate partial averages using their local data. Then they transmit the results to a master node, which calculates the overall average and outputs it to the other nodes. The same approach was used by Benchara and Youssfi [18] on Cloud micro-services.

Qin et al. [19] proposed a distributed k-means which each step is executed in distributed manner. The initial centroids are chosen by collaborating all sites. After local data are affected to the closest centroid iteratively, the average consensus algorithm is used to calculate the new clusters and the convergence is reached the centroids are unchanged.

The algorithm proposed by Kotary and Nanda [20] solve the distributed clustering problem as a constrained optimization using Lagrange multipliers. It aims to make uniform the number of groups on all nodes by sharing the cluster centers between neighbors. They assumed that the cluster centers are very similar after convergence at each node. No proof of convergence has been provided for the proposed method. The solution may vary if the data is not uniformly distributed.

Xia et al. [21] used the differential privacy technology local differential privacy (LDP) [22] in their distributed k-means solution. At each iteration a central site broadcasts the centroids to all the sites. The latter take care of the data assignment step and send to the central site the perturbed data according to the LDP principle and its membership group. The site recalculates the new centroids until the convergence. This solution is very greedy in term of communication because each site sends all these data at each iteration.

Soliman et al. [3] presented an asynchronous decentralized k-means clustering algorithm for independently and identically distributed (IID) data, which is not the case (Non-IID Data) as defined by Rodríguez-Barroso et al. [23]. The process begins by generating local model by k-means and iteratively share their result, at each node. The received local models are clustered using k-means to find the centers to be combined. Next, a weighted averaging is applied using the estimated cardinalities by HyperLogLog counters.

In recent years, the integration of topology and geometry opens up new perspectives for data mining and allows for more reliable and richer results [24]. These approaches make it possible to analyse complex data and create abstract representations of all the characteristics of the data, which makes it possible to reveal intrinsic structures that are not easily identifiable with traditional statistical techniques [25]. The promising results from the application of these methods across various domains, such as biology and image processing, highlight their potential as powerful tools for data analysis [26].

In the present article, we propose an asynchronous approach considering that distributed clustering is performed in three stages. First, each site searches for the clusters (models) of its local data and transmit them to a central site. Secondly, a central site analyses and searches for the partition of the set (the global model) based on the notion of the topological relationship between the different components of the local models.

Aggregation using topological relationships allows only subgroups that share data to be merged, so clusters that are included are merged first as they represent maximum data sharing and overlap second, while disjoint subgroups are not merged. distance-based methods do not allow this distinction, especially in a distributed context. Finally, we search for the right number of groups for the global model.

Privacy is ensured by the fact that there is no sharing of data samples between nodes. Nodes process data locally and share only relevant information, such as local models. The isolation of data samples contributes to the confidentiality and privacy of the information being processed. This is a significant advantage over other distributed clustering methods that share data across multiple nodes.

The paper is structured as follows: Section 2 presents some preliminary notations necessary for the presentation and better understanding of our work. The proposed approach is detailed in Section 3, followed by a time complexity and convergence analysis in Section 4. The experimental procedure is then described in Section 5. Section 6 is dedicated to the evaluation and discussion of the obtained experimental results. Finally, some concluding remarks are given in Section 7.

The proposed approach (see algorithm (2)) is based on an asynchronous model that considers the distributed clustering is achieved in two stages (plus one for the choice of the global number of groups). First, each site realizes the search for the local models of its local data (local partitions), at the end of this step, we retain for each group $C_i$ two characteristics, the number of instances $N_i$ and the radius $R_i$. These data (groups, number of instances and radius) are sent to a central site that analyzes and searches for the partition of the distributed data (global model).

The union of the local partitions constitutes a first model of the distributed data which the number of groups is equal to the sum of the numbers of local groups $\left(N\_total =\sum k_i\right)$. This raw model is characterized by a large number of subgroups that are gradually refined using the three operations mentioned (replacement, fusion, and selection).

The refine algorithm proceeds to eliminate the redundancy by replacing the included groups with those that cover them until no inclusion relationship is found or the fixed number of groups is reached. If the latter is not reached, we use the merging operation where we merge the overlapping groups. We start with the closest, if the number of groups is not obtained, we choose the $n$ centers among the remainder that increase the separability (the selection operation).

Therefore, the aggregation is performed in a hierarchical way using a sophisticated strategy that prioritizes the merging of subgroups based on their data sharing; similarity criteria are also considered to guarantee an efficient merging. As a consequence, subgroups with the highest degree of data sharing (inclusion) and similarity are merged first, followed by overlapping subgroups. Disjoint subgroups are not combined since they are fundamentally distinct and unrelated groups.

The third step is to determine the overall number of groups. We generate partitions with the number of groups from 2 to N_total (N_total is the sum of the numbers of local groups) and ship them to the other sites where they are evaluated on their local data. The best partition is the one with the best quality indexes average.

The convergence of the algorithm is guaranteed by the design of the algorithm itself. Since the number of subgroups is limited, as well as the number of included and overlapping relations, it is guaranteed that the algorithm will stop after a finite number of iterations, rather than running forever and eventually converging to a solution.

In experimental phase, we seek to determine the efficiency of our approach to find the closest partition to the one obtained with the dataset from its subsets. The datasets used in our experiments come from the UCI Machine Learning Repository, a widely used and publicly available collection of benchmark datasets for machine learning research. We chose to use the following datasets: High Time Resolution Universe (HTRU2) [28] and Tamil Nadu Electricity Board hourly readings [29]. These datasets were obtained in their pre-processed form provided by the repository. We also used the image shown in Figure 3.

3.jpg

Figure 3. Tulip image divided into 4 and 16 delimited by dotted lines

The HTRU2 is a dataset that describes a sample of candidate pulsars, each one characterized by eight continuous variables and one to designate the membership class. It contains 17898 instances distributed into two classes, 1639 known as true pulsars and 16259 identified by human annotators as noise caused by radio interference.

Tamil Nadu electricity board hourly readings represent the electricity consumption collected in real time every hour in residential, commercial, industrial and agricultural areas around Thanjavur City. This dataset has five attributes (forkva, forkw, type, sector and service). We chose to use three attributes:

• For classification: Forkva and forkw attributes.
• For the label: Sector attribute (integer value from 0 to 4) for the label.

These data are divided and distributed randomly over 2, 4, 8 and 16 sites (except the Tulip image dataset which is divided into 4 and 16 sites). Each site uses k-means clustering for local data clustering. We used an initialization algorithm based on the misclassified instance [30]. The latter has the advantage of ensuring the same expected results and to guarantee good quality by initially maximizing the inter-class inertia compared to a random initialization.

In order to determine the locally optimal number of groups k, we varied k=2, ..., 16. For each value of k, we calculated the silhouette index (Si) [31]. The appropriate number of groups is the one that maximizes this value [32].

On the central site, the refine procedure is launched to generate partitions where the number of groups varies from 2 to N_total. In order to determine the optimal partition, we evaluated the generated partitions on each site. The evaluation of the generated partitions is based on the same index of quality silhouette and we used the Mean Square Error (MSE) to compare partitions with the same number of groups (compactness). Then, we compared the chosen partition with the one obtained from the entire dataset to measure their resemblance. For this purpose, we use F-measure [33], Jaccard index [34] and variation of information (VI) [35].