A Federated Fuzzy -means Clustering Algorithm

Abstract

Traditional clustering algorithms require data to be centralized on a single machine or in a datacenter. Due to privacy issues and trafic limitations, in several real applications data cannot be transferred, thus hampering the efectiveness of traditional clustering algorithms, which can operate only on locally stored data. In the last years a new paradigm has been gaining popularity: Federated Learning (FL). FL enables the collaborative training of data mining models and, at the same time, preserves data locally at the data owners' places, decoupling the ability to perform machine learning from the need to transfer data. In this context, we propose the federated version of the popular fuzzy -means clustering algorithm. We first describe this version through pseudo-code and then demonstrate that the clusters obtained by the federated approach coincide with those generated by the classical algorithm executed on the union of all the local datasets. We also present an analysis on how privacy is preserved. Finally, we show some experimental results on the performance of the federated version when only a number of clients are involved in the clustering process.

Keywords

• eol>Federated Learning
• Federated Clustering
• Federated Fuzzy c-Means

1. Introduction

The performance of a machine learning (ML) model may benefit from the exploitation of data from multiple sources. However, the conventional approach of collecting data and storing them in a centralised server introduces severe communication overheads, and, most importantly, violates the privacy and security requirements that are often paramount to data owners [ 1 ].

As an alternative paradigm to data centralization, Federated Learning (FL) [ 2 ] has recently been proposed for the collaborative training of an ML model, and it can represent a key enabler in the framework of computational collective intelligence. In an FL system, data owners are not required to expose their own data to other parties; instead, they learn a shared model via the aggregation of locally-computed updates.

Early works that introduced the concept of FL [ 1, 3 ] primarily focused on supervised learning approaches. For example, the seminal algorithm federated averaging (FedAvg) [ 1 ] allows for the collaborative training of deep neural networks for image classification and language modeling by iterating over the following steps: (i) the server sends out the global model to the data owners; (ii) each data owner updates the model using its local data and sends it back to the server; (iii) the server takes the average of the locally updated models, weighted according to the number of examples, to obtain a new global model.

The unprecedented performance levels achieved by deep neural networks on a variety of supervised learning tasks likely motivates the emphasis on adapting such models to the federated environment; conversely, much less consideration has been devoted to other ML techniques, and specifically in the field of cluster analysis [ 4 ]. However, there exist several applications that require to determine groups of objects without sharing local data with a central server: this setting prevents the use of classical clustering algorithms, and asks for novel algorithms properly designed for a federated environment. Thus, the reshaping of the most efective clustering algorithms to reap the benefits of FL is of particular importance from a practical perspective.

A recent review [ 5 ] has highlighted how the mathematical representation of uncertainty provided by fuzzy set theory has historically found considerable popularity in cluster analysis. The Fuzzy -means (FCM) [ 6 ] algorithm certainly is the most popular fuzzy clustering method: it partitions data objects into clusters, where is fixed by the user.

In this paper we discuss the adaptation of FCM algorithm to the federated setting, considering the scenario of horizontally partitioned data, where objects are spread over multiple distinct nodes, and all of them are described by the same set of attributes.

The paper is organized as follows: Section 2 reports related works. Section 3 describes the background related to FL and the general setting of our investigation. Section 4 introduces our Federated FCM. Section 5 describes the experimental setup and results. Section 6 draw concluding remarks.

2. Related Works

The FCM algorithm and its crisp counterpart -means [ 7 ] are among the most popular and widely used clustering algorithms. Since their introduction, a number of works have extended and adapted the original algorithms to diferent application scenarios. This section can only provide some insights by describing how some more recent works relate to our proposal.

As discussed in a survey paper [ 8 ], several works have provided contributions around privacypreserving -means clustering algorithm: although complete zero-knowledge (i.e., each party knows nothing except its input and output) cannot be achieved due to the iterative nature of the algorithm, private implementations have been proposed both for horizontally [ 9 ] and vertically [ 10 ] partitioned data. However, the adoption of cryptography and Secure Multi-Party Computation primitives introduces a severe computation overhead and hinders the scalability of the approaches [ 11 ]. In a recent remarkable proposal for privacy-preserving collaborative fuzzy clustering [ 11 ], each data owner transforms its own data by first applying a non linear function and then performing a random projection onto a lower dimensional space. This perturbation is independent of the subsequent clustering algorithm (specifically, FCM is used). Furthermore, it is assumed that the central server may collude with some of the participants and may conduct specific attacks to violate user’s privacy. The authors show how resistance or mitigation of these attacks is achieved at a limited cost in terms of accuracy loss.

Compared to the representative works mentioned above, we assume a semi-honest central server: the server can try to retrieve private raw data based on the updates communicated by the data owners, but it does so by adhering to the protocol defined for the execution of the ML algorithm. This is a typical assumption for the horizontal partitioning [ 2 ]; however, clustering under such weak privacy model has not been extensively investigated yet in FL literature. To the best of our knowledge, only one recent work [ 12 ] follows an approach related to ours, from the point of view of privacy model, data partitioning, and communication topology: in a federated version of FCM, the author proposes to determine the cluster centers by means of a gradient-based optimization procedure. Although it is shown that such a federated version of FCM obtains similar results (and not equal, as in our case) compared to the traditional FCM algorithm applied to the overall dataset, the gradient-based optimization procedure difers from the classical, iterative, two-step minimization, in which the membership matrix and the centroids are alternately optimized. On the contrary, our proposal is inspired by the optimization procedure adopted in the traditional FCM algorithm: by only communicating aggregated data, it enables federated clustering without violating the privacy of participants.

3. Background and Problem Statement

A thorough overview on FL has recently been presented in several surveys, such as [ 2, 4, 13 ]. A general definition of FL can be found in [ 2 ]. Let { 1, 2, . . . , } be parties, i.e. data owners, who wish to train an ML model by consolidating their respective data {1, 2, . . . , }, where = {x1, x2, . . . , x } and x is an object stored in the m-th party. In an FL process the parties collaboratively learn a model Model fed without exposing their private data to others. The accuracy of Model fed should be close to the one achieved by a model Model sum learned on the union of the local datasets sum = ⋃︀ . Specifically, given a non-negative real number =1 , the FL algorithm is said to have -accuracy loss if |Accfed − Accsum | < , where Accfed and Accsum are the accuracies of Model fed and Model sum , respectively.

The above definition is quite general and covers a wide spectrum of FL applications. Indeed, FL systems can be coarsely categorized based on two aspects: data partitioning and communication topology [ 13 ]. Data partitioning relates to how data are distributed across the various parties and can be categorized in horizontal and vertical FL. Let be the feature space and the sample ID space of the data held by the -th data owner. As per horizontal FL, the dataset is said to be sample-partitioned. Horizontal FL can be formalized as follows: (1) (2) = , ̸= , ∀, , ̸=

As per Vertical FL, the dataset is said to be feature-partitioned. Vertical FL can be formalized as follows: ̸= , = , ∀, , ̸=

FL systems can be categorized according to their communication topology, thus discriminating between centralized and fully-decentralized FL. The former entails a server that orchestrates the learning process by aggregating the updates computed by diferent parties; most FL implementations assume this communication topology. The latter does not require the presence of a central server: information is shared in a peer-to-peer fashion.

In this paper, we focus on the scenario of horizontal FL with a centralized communication topology. parties wish to obtain a partitioning of their data, taking advantage of a clustering model to be built collaboratively, but with no need to share their private raw data. Let 1 = {︀ x11, x12, . . . , x11 }︀ , 2 = {︀ x21, x22, . . . , x22 }︀ , . . ., = {︁x1 , x2 , . . . , x }︁ be the M private datasets we are considering, each of them with a variable number of objects. Instances from all the datasets are represented in the same -dimensional attribute space: x = {︁,1, ,2, . . . , , }︁. We assume that both the number of clusters and the domain of definition of the attributes are known a-priori, and, specifically, they are also known to the server. As per the privacy model, we assume honest participants and a semi-honest, or honest-but-curious, central server [ 2 ].

4. Federated FCM

The original FCM algorithm by Bezdek [ 6 ] has been later reworked to improve its eficiency [ 14 ]. Our federated proposal for FCM stems from such a version [ 14 ], which adopts an eficient reorganization of the update procedure for the cluster centers: no storing of the membership matrix (i.e. the matrix that contains the degree of membership of each object to each cluster) is required, thus the asymptotic runtime is significantly reduced.

Algorithm 1: Federated FCM(, , ). Algorithm 2: LocalSums( (), , ) Given: - number of clusters Given: - fuzziness factor Given: - tolerance value for the stop condition

Initialization stage

Server: 1: Randomly selects cluster centers. (0) =

{︁v1(0), v2(0), . . . , v(0)}︁ 2: Transmits the fuzziness factor to each data owner

Execution stage 3: At each round , with starting from 0

Server: 4: Transmits () to each data owner

Each data owner : 5: (),, WS (), = LocalSums( (), , ) 6: Transmit ( (),, WS (),) to the server

Server: 7: Update cluster centers evaluating (+1) as per

Eq. 3. 8: if || (+1) − ()|| < then 9: Terminate 10: else 11: Proceed with the next round (line 4) 12: end if Given: () - array of C cluster centers Given: - -th dataset Given: - fuzziness factor 1: WS (), ← zeros(C × F ) 2: (), ← zeros(C ) 3: for x ∈ do: 4: denom = 0 65:: fornueamchercclu=ste‖rxd− o:v()‖ −2 1 7: denom = denom + num1erc 8: end for 9: for each cluster do: 10: , = (numerc * denom)− 1 11: ws(), = ws(), + , x 12: (), = (), + , 13: end for 14: end for 15: return (),, WS (),

The pseudocode of the Federated FCM algorithm is reported in Algorithms 1 and 2. Federated FCM is structured in successive rounds. For the sake of clarity, the communication and synchronization details for this round-based organization is omitted.

The initialization stage of the Federated FCM algorithm is up to the server and involves the initialization of all the cluster centers. The server transmits to each data owner the coordinates of the centers and the fuzziness parameter . Subsequently, during the execution stage, at each round, each data owner computes both (), and WS (), as described in Algorithm 2. is an array with elements, and the -th element is the sum of the membership degrees of the objects in to cluster , each raised to the -th power. More formally, = {1, 2, . . . , } and = ∑︀ =1 , . WS is a × matrix, whose -th row is the sum of the data objects, weighted by the membership degree of the objects to cluster . More formally, = {ws1, ws2, . . . , ws} and ws = ∑︀ =1 , x. Then, each data owner transmits (), and WS (), to the server, so that it can update the coordinates of the centers as follows: v(+1) = ∑︀

=1 ws(), ∑︀ =1 Uc(t),m ∀ ∈ {1, . . . , } The updated center of the -th cluster is the weighted average of the objects assigned to the cluster: the weights are the membership degree of the objects to the cluster, raised to the -th power. With M mutually disjoint sets, as it typically occurs in real-world horizontal data partitions, Eq. 4 (centralized setting) and Eq. 3 (federated setting) lead to the same result. In fact, for each cluster , =1 ∑︁ , x (),sum = ∑︁ ws(),

(5) =1 =1 ∑︁ , = ∑︁ Uc(t),m =1

The server evaluates the stopping condition (Algorithm 1, line 8): if the Frobenius norm of the diference in the cluster centers between two consecutive rounds is lower than the given threshold , the execution terminates. In other words, we check whether the centers move less than the imposed tolerance. Otherwise, the server transmits the new centers to the data owners, thereby initiating the next round.

The rationale behind the LocalSums (Algorithm 2) is detailed in [ 14 ]; unlike the original paper, we are considering the scenario of horizontal FL, where data are scattered over multiple data owners. Notably, each data owner does not need to store the × membership matrix.

4.1. Equivalence with FCM executed on the overall dataset

In this sub-section, we show that the Federated FCM algorithm generates the same clusters that would be produced by the classical FCM algorithm applied to the overall dataset obtained by the union of the local datasets. Under the assumption that all data are stored in the central server, in the classical FCM algorithm at each iteration the cluster centers are updated as follows: v(+1) = ∑︀=1 , x

(),sum ∑︀ =1 , ∀ ∈ {1, . . . , } (3) (4) (6)

Specifically, both terms are sums of elements. In the federated setting each sum is performed in two steps: first, on a per-owner basis and then aggregated by the central server.

Finally, since the termination condition (Algorithm 1 line 8) depends only on the position of the cluster centers, it can be applied equivalently in the two scenarios.

4.2. Privacy analysis

The federated approach allows the collaborative evaluation of the FCM algorithm with no need for individual data owners to expose their data. Nevertheless, the server can infer the value of the attributes of each single object under certain circumstances. At each round, each data owner reveals the following information: for each , the sum U(), of the membership degrees, each raised to the -th power, and the array ws(), of the weighted sum of the objects assigned to . The first information U(), can be represented by the following equations: ⎧⎪ 1,1 + 1,2 + · · · + 1, = 1 ⎪⎪⎨ 2,1 + 2,2 + · · · + 2, = 2 ⎪. . . ⎪ ⎪ ⎩ ,1 + ,2 + · · · + , = The second information ws(), leads to the following equations for each attribute : ⎪⎧1, 1,1 + 2, 1,2 + · · · + , 1, = 1, ⎪⎪⎨1, 2,1 + 2, 2,2 + · · · + , 2, = 2, ⎪. . . ⎪ ⎪⎩1, ,1 + 2, ,2 + · · · + , , = ,

Specifically, the server receives from each data owner the value for each cluster , and the , value for each cluster and for each feature . By definition, we have that , = 1

2 ∑︀ ︁( ‖x− v‖ )︁ − 1

=1 ‖x− v‖

Thus, we can consider that the only unknown variables are the coordinates , . To derive these coordinates for the objects stored in party , the server must solve the overall system of equations, composed by Eqs. 7 and 8, replacing the values of , by using Eq. 9. The number of unknown variables is × and the number of equations is + × . If the server was aware of the number of objects that produced the statistics U(), and ws(),, it could empirically derive the solution unless the number of unknown variables was greater than the number of equations, that is, if > × ( +1) . We highlight that the server does not know and therefore this is a strong restrictive condition. Nevertheless, it does not appear too limiting since it requires that the number of objects is greater than the number of clusters plus / . Therefore, we might decide to let the party transmit the locally aggregated data (Algorithm 1, line 6) only if > × ( +1) . Although the server may be able to retrieve some data information from the aggregated measurements submitted by each data owner, it cannot determine the exact raw data values. (7) (8) (9)

5. Experimental setup and results discussion

A preliminary evaluation of the performance of Federated FCM has been carried out. We considered the following setting: all participants have roughly the same amount and the same distribution of objects (IID setting). The total number of participants has been set to 20; however, as in the original FedAvg algorithm [ 1 ], we introduce a parameter (fraction of data owners) for random sampling among participants at the beginning of each FL round. The main objective of our analysis is to compare the results obtained with Federated FCM (with diferent values for ) and those obtained with classical FCM algorithm applied to the overall dataset sum . Specifically, fed ( ) and sum represents the final array of cluster centers obtained with Federated FCM and with classical FCM (centralized setting), respectively.

Overall, we employed four datasets: xclara and s-set1 from the clustering benchmark repository1, waveform v1 and pendigits from the UCI Machine Learning Repository2. For each dataset, the number of classes , objects and attributes is reported in Table 1 (first column).

We set the fuzziness factor = 2, the tolerance value = 0.005 and the maximum number of rounds to 30, as we observed that convergence generally requires far fewer rounds. Further the number of clusters was set coherently with the number of classes . We varied in {0.25, 0.5, 0.75, 1}: notably, in the case of = 1 (i.e., all clients participate to FL procedure), we aim to experimentally verify the equivalence between federated and centralized settings, as theoretically demonstrated in Section 4.1. We performed 10 repetitions varying the seed for random center initialization and participant sampling; for each repetition, the same center initialization was used for the Federated FCM and the centralized FCM algorithms.

Due to the space limit, Fig. 1 reports only the results obtained on the xclara dataset. The convergence of Federated FCM (Algorithm 1, line 8) is reported in Fig. 1a: the Frobenius norm of the diference in the cluster centers between two consecutive rounds reaches a plateau after around 7 rounds, regardless of the value of . However, convergence w.r.t. the tolerance value is achieved only for high values of (namely, 0.75 and 1); intuitively, when fewer participants are sampled, the centers keep slightly shifting over time, since it is less likely that the same participants are selected in subsequent rounds.

Figure 1b shows the Frobenius norm ||( ) − sum || of the diference between cluster centers computed by Federated and centralized versions of FCM; notably, we consider the permutation of the centers in ( ) that minimizes ||( ) − sum || . When = 1 (all 20 clients are involved in the procedure) the federated version of the algorithm is equivalent to the original one executed on the overall dataset, as previously demonstrated. As decreases, the distance between the centers increases. To assess whether this afects clustering performance, we apply an external measure of clustering quality, namely the Adjusted Rand Index (ARI) [ 15 ]. Given the centers fed ( ) computed by the federated version, we evaluated the fuzzy partition matrix on the dataset sum , assigned each object to the cluster with the highest membership degree, and computed ARI, which measures the consistency between clustering results and the available ground truth labels. Table 1 reports the results for all datasets, along with the value ||( ) − sum || . We observe that, in the case < 1, the centers computed in the 1https://github.com/deric/clustering-benchmark 2https://archive.ics.uci.edu/ml/datasets.php federated setting slightly deviates from those determined in the centralized case. As expected, this deviation decreases with the increase of . However, such deviation does not induce a significant variation in the ARI values, thus highlighting that the clusters generated by Federated and centralized versions are very similar even when only a fraction of participants is involved in the FL procedure. This outcome is particularly relevant in scenarios where clients have an unstable connection, which can prevent them to communicate with the central server at each round, or when it is mandatory to reduce the communication overhead over the network.

6. Conclusion

ARI( ) While ML is widely employed in a great variety of application domains, there is a growing interest in the need to protect the privacy of data during the collaborative learning of ML models. Federated learning is emerging as one of the key paradigms to address this challenge. In this paper we have proposed a federated version of the popular fuzzy -means clustering algorithm. We have focused on the scenario of horizontally partitioned data and relaxed privacy requirements. We have shown that our version achieves the same results obtained by the classical clustering algorithm applied to the overall merged datasets, while preserving privacy of data owners. Further, we carried out a preliminary experimental analysis: under the assumption of IID data over clients, the federated version of the algorithm is substantially equivalent to the centralized one, even when only a fraction of clients participate to the FL process. Future works will investigate the selection of the proper number of clusters in the federated setting and the implementation of the algorithm for vertically partitioned data.

Acknowledgments

This work has been partly funded by the European Commission through the H2020 project Hexa-X (Grant Agreement no. 101015956) and by the Italian Ministry of Education and Research (MIUR) in the framework of the CrossLab project (Departments of Excellence).

References

[1] B. McMahan , E. Moore , D. Ramage , S. Hampson , B. A. y Arcas , Communication-eficient learning of deep networks from decentralized data , in: Artificial Intelligence and Statistics , PMLR, 2017 , pp. 1273 - 1282 .

[2] Q. Yang , Y. Liu , T. Chen , Y. Tong, Federated machine learning: Concept and applications , ACM T. Intel. Sysy. Tec. 10 ( 2019 ) 1 - 19 .

[3] J. Konečný , H. B. McMahan , F. X. Yu , P. Richtarik , A. T. Suresh , D. Bacon , Federated Learning: Strategies for Improving Communication Eficiency , in: NIPS Workshop on Private Multi-Party Machine Learning , 2016 .

[4] P. Kairouz , H. B. McMahan , B. Avent , A. Bellet , M. Bennis , et al., Advances and open problems in federated learning , arXiv preprint arXiv: 1912 . 04977 ( 2019 ).

[5] E. H. Ruspini , J. C. Bezdek , J. M. Keller, Fuzzy clustering: A historical perspective , IEEE Comput. Intell. M. 14 ( 2019 ) 45 - 55 .

[6] J. C. Bezdek , Fuzzy mathematics in pattern classification, Ph. D. Dissertation , Applied Mathematics, Cornell University ( 1973 ).

[7] S. Lloyd , Least squares quantization in PCM , IEEE T. Inform. Theory 28 ( 1982 ) 129 - 137 .

[8] F. Meskine , S. N. Bahloul , Privacy preserving k-means clustering: a survey research ., Int. Arab J. Inf. Technol . 9 ( 2012 ) 194 - 200 .

[9] S. Jha , L. Kruger , P. McDaniel , Privacy preserving clustering , in: European symposium on research in computer security , Springer, 2005 , pp. 397 - 417 .

[10] J. Vaidya , C. Clifton , Privacy-preserving k-means clustering over vertically partitioned data , in: Proc. 9th ACM SIGKDD Int'l Conf. on KDD , 2003 , pp. 206 - 215 .

[11] L. Lyu , J. C. Bezdek , Y. W. Law , X. He , M. Palaniswami , Privacy-preserving collaborative fuzzy clustering , Data Knowl. Eng . 116 ( 2018 ) 21 - 41 .

[12] W. Pedrycz , Federated fcm: Clustering under privacy requirements , IEEE T. Fuzzy Syst . ( 2021 ) 1 - 1 .

[13] V. Mothukuri , R. M. Parizi , S. Pouriyeh , Y. Huang , A. e. a. Dehghantanha , A survey on security and privacy of federated learning , Future Gener. Comp. Sy . 115 ( 2021 ) 619 - 640 .

[14] J. F. Kolen , T. Hutcheson, Reducing the time complexity of the fuzzy c-means algorithm , IEEE T. Fuzzy Syst . 10 ( 2002 ) 263 - 267 .

[15] L. Hubert , P. Arabie , Comparing partitions , Journal of Classification 2 ( 1985 ) 193 - 218 .