ICML 提交的“用于数据摘要的公平且快速 k-Center 聚类”的代码

这是我们对 ICML 论文[Angelidakis22a]中描述的快速隐私保护代表性 k-center (Priv-Rep-kC) 算法的 Rust 实现。对于最多由 k 个中心覆盖的 n 个数据点实例，此算法具有 $O(nk^2 + k^5)$ 的时间保证。

该代码是一个 Rust 库，实现了 Python 接口，从而有以下两种运行我们的算法的方式

• 可以将其导入其他 Rust 项目。
• 在安装了 Python 轮子后，可以从任何 Python 脚本或 Jupyter 笔记本中执行该算法。

由于 Python 接口最为方便，我们专注于这种方式来运行我们的代码。

要求

• python >=3.6
• matplotlib (可选)

Python 轮子的安装

使用包管理器 pip 安装 Python 轮子

pip install ff_k_center-1.2.2-cp36-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

此外，我们建议安装 matplotlib 以获取计算聚类的绘图

pip install matplotlib

通过 Python 接口使用

以下 Python 代码展示了 Python 接口的基本功能。

from ff_k_center import FFKCenter
import numpy as np

model = FFKCenter(4,1,[(1,13)]) # parameters: k, privacy_bound = 1, rep_intervals = []
pos = np.array([[1,2],[0,0],[6,7],[0,-1],[-2,-3],[0,-1.2],[1,3],[6,1]])
colors = np.array([0,0,0,1,1,0,0,1])


model.fit(pos, colors, verbose = 2, thread_count = 6, phase_2_rerun = False, phase_5_gonzalez = True) # positions of points; followed by colors; Optional: verbose (0: silent, 1: brief, 2: verbose; default: 1); thread_count (default: #cores); phase_2_rerun (default: True); phase_5_gonzalez (default: False);

print("\nr^*: ", model.radius) # the final radius of the assignment
print("C^*: ", model.centers) # Chosen centers by the point-index.
print("phi^*: ", model.assignment) # for each point the center it is assigned to.
print("running time: ", model.running_time) # running time in sec

完整的接口可以在 jupyter notebook showcase/showcase.ipynb 中看到，它也可以用作测试玩具示例的游乐场。

或者，您可以使用 experiments/computational_study.ipynb 重新创建我们的实验。（警告：由于我们在论文中通过迭代许多不同的参数值来创建绘图，这可能需要几个小时，尽管单个计算非常快。）手稿中使用的数据集包括在内，可以在 experiments/data/ 中找到。

通过运行 python_scripts/create_2d_space.py，可以通过左键单击图形轻松创建新的玩具示例。使用数字键 '0' 到 '9' 来更改颜色，使用 'Del' 进入删除模式。关闭窗口后，数据集将被保存。

卸载 Python 轮子

使用以下命令卸载 Python 轮子

pip uninstall ff_k_center

通过编译代码构建Python wheel

由于Python wheel已包含在提供的代码中，因此无需重新创建。不过，为了验证Python wheel确实对应于实际代码，我们在此提供有关如何从Rust代码编译它的信息。这可以通过工具maturin完成。

最方便的方法是使用Docker镜像pyo3/maturin

docker run --rm -v $(pwd):/io ghcr.io/pyo3/maturin build --release

之后，Python wheel可以在target/wheels/中找到。

Rust库的使用

在crates.io上有官方创建。要使用它，请确保提供的Rust crate已列在您的Cargo.toml中的dependencies下。

ff_k_center = "1.2.2"

您可以通过以下方式将所有功能加载到新的Rust项目中：

use ff_k_center::*;

以下代码示例创建了一个包含5000个随机点的数据集，并使用我们的算法解决了Priv-Rep-kC问题。

use ff_k_center::*;
fn main() {
    let n = 5_000;
    let k = 8;
    let space = SpaceND::new_random(n);
    let prob = ClusteringProblem{
        k, // number of centers;
        privacy_bound : n/k, // number of points to represent;
        rep_intervals : vec!((0,500),(0,500),(0,500)), // representation interval [a,b] for each color class; for color classes without interval we subsitute [0. inf]
    };
    let (clustering, total_time) = compute_privacy_preserving_representative_k_center(&space, &prob, None);
    println!("Radius: {}; Running time: {}s.", clustering.get_radius(), total_time);
}

有关如何加载数据集、保存计算的聚类、设置可选参数等更多详细信息，请参阅docs.rs。文档也可以本地生成并使用以下方式打开：

cargo doc --open