Privacy-preserving clustering groups data points in an unsupervised manner
whilst ensuring that sensitive information remains protected. Previous
privacy-preserving clustering focused on identifying concentration of point
clouds. In this paper, we take another path and focus on identifying
appropriate separators that split a data set. We introduce the novel
differentially private clustering algorithm DPM that searches for accurate data
point separators in a differentially private manner. DPM addresses two key
challenges for finding accurate separators: identifying separators that are
large gaps between clusters instead of small gaps within a cluster and, to
efficiently spend the privacy budget, prioritising separators that split the
data into large subparts. Using the differentially private Exponential
Mechanism, DPM randomly chooses cluster separators with provably high utility:
For a data set $D$, if there is a wide low-density separator in the central
$60\%$ quantile, DPM finds that separator with probability $1 -
\exp(-\sqrt{|D|})$. Our experimental evaluation demonstrates that DPM achieves
significant improvements in terms of the clustering metric inertia. With the
inertia results of the non-private KMeans++ as a baseline, for $\varepsilon =
1$ and $\delta=10^{-5}$ DPM improves upon the difference to the baseline by up
to $50\%$ for a synthetic data set and by up to $62\%$ for a real-world data
set compared to a state-of-the-art clustering algorithm by Chang and Kamath.

通过优化数据集的分割器，以差分隐私方式搜索准确的数据点分隔符的差分隐私聚类算法 DPM 在聚类度量不变性方面取得了显著的改善。