Coordinate Descent for k-Means with Differential Privacy

In recent years, Lloyd’s heuristic has become one of the most useful methods to solve k-means problem due to its simplicity. However, Lloyd’s heuristic suffers from the bad local minimum and the privacy issues which make it not proper to be used in the privacy-preserving scenarios. In this paper, we propose a differentially private framework for k-means clustering by using the coordinate descent method. Firstly, we propose an approximate version of the updating functions of the indicator matrix which claims each point’s assignment. Then we ensure differential privacy for k-means clustering by using exponential mechanism to perturb the indicator matrix. Finally, we conduct several experiments based on multiple real-world datasets. Our experimental results show that our algorithm outperforms state of the art in terms of the trade-off between utility and privacy.