Federated clustering (FC) is an emerging and important topic that clustering all the data from many different heterogeneous clients/devices while prohibiting clients from sharing raw data. However, for existing works, there are some problems: (1) federated learning performs well in independent and identically distributed (IID) scenarios, but for Non-IID scenarios (Non-Identical class distribution), it is hard to collaboratively train a clustering algorithm based on global similarity measure while keeping all data local. (2) Some federated clustering algorithms have good performance, but their communication costs are high. It is difficult to balance communication costs and clustering effectiveness. In this paper, we propose new federated k-means clustering framework to solve the above two problems and balance communication costs and clustering effectiveness. (1) For the clients, we use cluster centers (representative points) genearate by K-means to represent the corresponding clusters because these representative points form density backbone of clusters and can effectively preserve the structure of the local data. (2) For the server, we propose two methods to reprocess these uploaded encrypted representative points to obtain better final cluster centers, one uses K-means and the other takes the improved density peaks (density cores) as final centers, and then send them back to the clients. Finally, each client assign local data to the nearest centers. The experimental results show that the proposed method performs better than some centralized (non-federated) classical clustering algorithms (K-means, DBSCAN and density peak clustering) and state-of-the-art (SOTA) centralized clustering algorithms in most cases. In particular, the proposed algorithms performs better than SOTA federated clustering framework k-FED (ICML2021) and MUFC (ICLR2023).

Clustering is an important unsupervised knowledge acquisition method, which divides the unlabeled data into different groups \cite{atilgan2021efficient,d2021automatic}. Different clustering algorithms make different assumptions on the cluster formation, thus, most clustering algorithms are able to well handle at least one particular type of data distribution but may not well handle the other types of distributions. For example, K-means identifies convex clusters well \cite{bai2017fast}, and DBSCAN is able to find clusters with similar densities \cite{DBSCAN}. Therefore, most clustering methods may not work well on data distribution patterns that are different from the assumptions being made and on a mixture of different distribution patterns. Taking DBSCAN as an example, it is sensitive to the loosely connected points between dense natural clusters as illustrated in Figure~\ref{figconnect}. The density of the connected points shown in Figure~\ref{figconnect} is different from the natural clusters on both ends, however, DBSCAN with fixed global parameter values may wrongly assign these connected points and consider all the data points in Figure~\ref{figconnect} as one big cluster.