Abstract
差分プライバシーK-meansクラスタリングは、個人のプライバシーを保護しつつ、データセットから導出されたクラスタ中心を公開することを可能にする。私的ヒストグラムに基づく非インタラクティブなクラスタリング手法は、公開されたデータ要約が追加のプライバシー損失なしに他の下流タスクで再利用できるため、魅力的である。データ点を離散化するためのグリッド数の選択は重要であり、それは量子化バイアスと、プライバシーを保つために注入されるノイズ量を直接制御する。広く採用されている戦略は、クラスタ数とは独立なグリッドサイズを選び、さらに経験的な調整に依存している。本研究ではこの選択を見直し、K-meansの目的関数における期待される偏差の上界を最小化することで導かれる、改良されたグリッドサイズ選択則を提案する。これにより、非インタラクティブなプライベートクラスタリングのための、より原理に基づいた離散化戦略が得られる。先行研究と比べて、提案するグリッド分解能は、そのクラスタ数への依存の点だけでなく、データセットサイズおよびプライバシーバジェットとのスケーリングの点でも異なる。広範な数値実験により、提案戦略は、厳しいプライバシーバジェット下でも、最先端の手法と比べて高精度なクラスタリングを実現することが示される。
