基于分层分离树HST的可扩展差分隐私聚类hst_clustering 实现与实战指南【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research导读本文围绕 hst_clustering 模块讲解 KDD22 论文Scalable Differentially Private Clustering via Hierarchically Separated TreesarXiv:2206.08646的官方开源实现。该模块以Apache Beam 流水线构建差分隐私DP下的分层分离树Hierarchically Separated Tree, HST并配合动态规划求解 k-median 聚类问题在保护数据隐私的同时实现大规模聚类。读完本文你将掌握如何准备输入数据、理解全部命令行参数、跑通端到端聚类流程以及从源码层面理解 HST 构建、高斯阈值机制与 DP 动态规划的核心原理。1. 模块定位与论文背景hst_clustering 是 Google Research 中专门承载 DP 聚类算法的模块对应论文Scalable Differentially Private Clustering via Hierarchically Separated TreesKDD 2022arXiv:2206.08646。其核心思想是不直接在高维原始数据上做隐私聚类通常代价高昂而是先用分层分离树把数据空间递归切分成多层次的网格单元cell统计每个单元内的点数量并施加差分隐私噪声再在这棵已加噪的树上用动态规划挑选出最优的 k 个聚类中心。由于树结构天然支持并行化该算法通过 Apache Beam 可以扩展到大规模数据集这正是可扩展Scalable一词的来源。模块包含 11 个文件职责划分清晰文件职责run_clustering.py命令行入口串联 HST 构建与 DP 求解两个阶段dp_hst.pyBeam 流水线负责构建差分隐私 HSTdynamic_program.pyHST 数据结构与 k-median 动态规划求解gaussian_thresholding.py高斯阈值机制Gaussian Thresholding参数计算io.py数据读写、HST 文件解析为树对象dp_one_median.py差分隐私 1-median 求解供中心选择与后处理使用kvariates.py并行的 k-variates 机制论文中的对比/备选聚类方法kmedian_plus_plus.pyk-means 风格初始化与 Lloyd 迭代工具experiment_config.py各算法的 dataclass 参数配置kvariates_test.pykvariates 相关单元测试requirements.txt运行依赖清单2. 环境准备与依赖运行本模块需要以下依赖见 requirements.txtabsl-py1.2.0 numpy1.21.5 pandas1.5.0 scipy1.9.1 apache-beam2.46.0其中absl-py用于命令行参数解析flagsnumpy/pandas/scipy负责数值计算、数据帧解析与高斯机制中的优化/统计运算apache-beam是整套 HST 构建流水线的执行引擎。建议使用虚拟环境安装pip install -r hst_clustering/requirements.txt3. 输入数据格式入口脚本 run_clustering.py 对输入文件格式有明确约定制表符分隔Tab-separated的文本文件第一列为样本编号其余各列是该点在 R^d 空间中的坐标。仓库内置的示例数据集 s1_random-standarized.txt 正是这一格式前几行如下0 1.3994608666813209 0.6072888469790971 1 0.7093077080912279 0.615079819640638 2 1.4307569787257732 0.3337015180302204该数据集包含 5000 个样本点、2 个特征维度 d2所有坐标值均落在区间[0, 2]内——这与 README 示例中--min_value_entry0 --max_value_entry2 --dimensions2的参数设定严格对应。在 dp_hst.py 的CreateVectorFromTextDoFn 中每个点会做两层校验维度校验element.split()[1:]去掉首列样本编号后向量长度必须等于--dimensions指定的值否则抛出ValueError并提示设置正确的--dimensions取值边界校验每个维度的坐标值必须在min_value_entry与max_value_entry之间越界同样抛错。注意边界参数min/max value entry不只是校验用它同时定义了 HST 根节点的包围盒bounding box是树切分的起点因此必须正确设置。4. 运行端到端聚类完整命令与输出解析README 给出了在 google_research 仓库根目录下的标准运行方式。结合源码补充完整的参数说明后完整命令如下OUTPUT_DIRsome/directory python3 -m hst_clustering.run_clustering \ --raw_datahst_clustering/s1_random-standarized.txt \ --output_dir${OUTPUT_DIR} \ --dimensions2 \ --min_value_entry0 \ --max_value_entry2 \ --k_params10 \ --alsologtostderr4.1 全部命令行参数所有参数均在 run_clustering.py 中以 absl flags 定义含义与默认值如下参数类型默认值说明--raw_datastring空必填原始数据文件路径Tab 分隔首列为样本编号--output_dirstring空必填输出目录脚本会自动创建--k_paramsint10聚类中心数量 k--dimensionsintNone必填输入点的维度 d--layersint10HST 的层数递归切分深度--epsilonfloat1.0差分隐私 ε 参数--deltafloat0.00001差分隐私 δ 参数--seedint0HST 切分所用的随机种子--min_value_entryfloatNone必填各维度取值下界--max_value_entryfloatNone必填各维度取值上界--runnerenumNoneBeam 执行器DirectRunner本地或DataflowRunner云端--num_buckets_beamint100Beam Reshuffle 时使用的桶数量其中--runner的选择体现了模块的可扩展设计本地调试用DirectRunner大规模数据可切换DataflowRunner将流水线部署到云端分布式执行。使用 Dataflow 时run_clustering.py 会自动设置save_main_session True确保远端 worker 能访问全局命名空间中的变量与导入。脚本执行前的参数断言见 run_clustering.py可帮助你快速排查配置错误raw_data、output_dir非空dimensions 0k_params 0layers 0epsilon 0delta 0min_value_entry max_value_entrynum_buckets_beam 0。4.2 运行的两个阶段与输出产物main函数分两个阶段执行run_clustering.py阶段一Beam 流水线构建 DP HST输出写入${OUTPUT_DIR}/hst.csv实际为hst.csv-*分片文件。流水线见 dp_hst.pyReadFromText → CreateVectorFromText → Reshuffle → MapToCellId → CombinePerKey → GaussianThresholdMechansimFn → OutputAsString → WriteToText阶段二动态规划求解并评估产出两个文件${OUTPUT_DIR}/results.txtk-median 目标函数得分所有点到最近中心的距离之和通过dynamic_program.eval_hst_solution计算${OUTPUT_DIR}/centers.npynumpy 格式的聚类中心数组一行一个中心。注意 run_clustering.py 中LLOYD_ITERS 0即默认不执行 Lloyd 迭代后处理如需提升精度可参考 dynamic_program.py 中lloyd_iters 0的路径该路径会将每次迭代的隐私预算叠加需要用户自行核算总 ε。4.3 数据读取的细节约定io.py 的ReadRawData使用pd.read_csv(..., index_col0, sepr\s, headerNone)读取原始数据——这意味着首列被视为索引样本编号被丢弃空白字符包括制表符与多空格均可作为分隔符。而LoadFilesIntoDataFrameio.py则按 CSV 规则解析 HST 输出文件列结构固定为id, right_child, left_child, diameter, weight, 0, 1, ..., d-1其中id是二进制字符串形式的单元编号0..d-1为各维度的单元中心坐标特征列。5. 源码深度剖析HST 是如何被构建的5.1 逐层切分MapToCellId树的核心构建逻辑在 MapToCellId。每个输入点从根节点的包围盒出发逐层、逐维度地递归细分根节点先用全局min_value_entry/max_value_entry构造 d 维包围盒产出根单元记录(diameter, center, 1.0)每一层 × 每一维度调用layer_dimension_threshold计算该层该维度的确定性切分阈值阈值来源是f{seed}|{layer}|{dimension}字符串的 MD5 哈希再映射到[1/3, 2/3]区间内的相对位置(random.random() 1.0) / 3.0对应论文中分层分离树1/3-2/3的分离性质源码注释明确指出这里使用弱随机数生成器是可接受的因为它只影响近似保证不影响隐私保证dp_hst.py判定分支若点在该维度的坐标小于阈值cell_id追加False子节点 id 追加0并将该维度上界更新为阈值否则追加True追加1下界更新为阈值逐层产出每一层都yield当前点的单元记录因此一个点总共产生1 layers × dimensions条记录根 每层每维一个单元这也是下文 L0 敏感度的由来。单元记录由 get_diameter_center_one_count_tuple 生成diameter ||max - min||₂欧氏直径center (max - min)/2 min几何中心第三个元素1.0表示该点对该单元的贡献为 1。5.2 加噪与裁剪高斯阈值机制GaussianThresholdMechansimFndp_hst.py对每个单元执行差分隐私处理灵敏度分析每个点最多影响layers × dimensions个单元即 L0 灵敏度见 dp_hst.py每单元贡献上限为 1L∞ 上限调用 gaussian_thresholding.py 的get_gaussian_thresholding_params计算噪声标准差sigma与裁剪阈值thresholdL2 灵敏度max_bucket_contribution × sqrt(max_num_buckets_contributed)σ由 Analytic Gaussian MechanismB / B- 辅助函数与root_scalar数值求逆精确计算见find_gaussian_multiplier与find_sigma阈值1 √2 · σ · Φ⁻¹(1 - 2δ / l0)其中Φ⁻¹为标准正态分位数gaussian_threshold执行对每个单元的真实计数施加N(0, σ²)噪声仅当加噪计数 ≥ 阈值时才输出该单元见process中的if copy_t[2] self.threshold。这一步同时完成两件事丢弃稀疏/空单元以节省空间并保证未知分区unknown partitions下的差分隐私。最终的输出格式output_as_string为cell_id,left_child,right_child,diameter,dp_weight,center_0,...,center_{d-1}5.3 从输出文件恢复树DataFrameToTreeio.py 的DataFrameToTree将流水线产物解析回dynamic_program.HST对象处理逻辑包括将负权重单元权重截断为 0加噪后可能出现的负值识别叶子节点左右子节点都不存在并挂载补齐缺失子节点当某内部节点只有一个子节点存在于输出中时会创建一个权重为 0、直径为父节点 2/3 的空节点补全二叉树——这是因为阈值为 0 的单元可能被高斯机制过滤掉而 DP 求解需要一个完整的树结构根节点 id 为空字符串ROOT_ID由tree.add_root标记。随后 run_clustering.py 调用tree.validate_tree(True)校验树结构自动移除不可达节点再执行tree.solve_dp(k)。6. 树上动态规划求解差分隐私 k-median6.1 动态规划递推HST.solve_dp 在整棵树上求解 k-median 目标最小化Σ distance(p, 最近中心)。核心递推见_solve_dpdynamic_program.py对每个节点计算cost_matrix[kprime]在该子树内放置 k 个中心的代价k 0不放置中心代价 2 × diameter^exp × weight惩罚性上界叶子节点代价 diameter^exp × weight即该单元内所有点以直径距离近似到中心内部节点枚举左右子树中心数分配k1 k2 k取两子树代价之和的最小值并记录最优分解到left_optimal/right_optimal数组供回溯使用。递推完成后recover_dp_solution 通过_recover_solutiondynamic_program.py沿最优分解路径回溯得到选中的叶子单元集合。6.2 中心映射回原始空间选中的叶子单元 id 需映射回原始空间的坐标。_get_center 的处理方式是若该单元 id 存在于 HST 输出数据帧中直接取对应行特征列若不存在单元被阈值过滤则回溯到其父节点去掉 id 最后一位直到找到存在记录的祖先单元——这保证了最终总能输出合法中心。最终由get_centers_from_hst汇总为k × d的中心矩阵。6.3 评估与可选的后处理eval_hst_solutiondynamic_program.py以原始数据评估解的质量由 HST 恢复中心若lloyd_iters 0执行指定轮数的 Lloyd 迭代精化kmedian_plus_plus.py 中的lloyd_iter内部使用privacy_params保证隐私max_num_points20000限制单次处理规模计算并返回 k-median 目标得分与中心。隐私提示源码 docstring 明确警告——若启用 Lloyd 迭代最终 ε 保证需要按lloyd_iters × privacy_params.epsilon自行核算dynamic_program.py。默认入口不启用该后处理。7. 扩展模块DP 1-median 与 kvariates除主流程外模块还附带两类论文中涉及的聚类工具可在相关实验中独立使用DP 1-mediandp_one_median.py通过**目标扰动objective perturbation**求解单中心问题。private_k_med_objective基于 DP 凸优化框架论文引用 TPDPCO核心要素包括用平滑参数lambd构造光滑近似范数smooth_norm_conj范数小于2·lambd时用二次近似否则用真实范数减lambd添加正则项p·β/(e1-e3)与高斯扰动向量b1、b2用scipy.optimize.minimize(methodtrust-ncg)优化收敛梯度阈值gtolgamma——gamma是隐私保证成立的先决条件梯度范数必须小于 gamma在 Beam 中心选择器中还会按gamma/n·√d缩放见one_median_dp_beam。kvariateskvariates.py论文提出的并行 k-variates 机制。它先把数据按 simhash 等分裂策略simhash_split划分到多个 worker然后迭代式地每个 worker 基于本地数据与全局已选中心计算采样概率距离越大概率越高按概率选出候选中心再由select_center全局汇总挑选最终中心create_pipeline与iteration。配套的 kvariates_test.py 覆盖了 simhash 哈希正确性、随机分裂与距离计算等核心函数的单元测试。8. 常见问题排查ValueError: invalid dimensions in vectors输入文件每行特征数去掉首列编号后与--dimensions不一致。检查--dimensions是否等于文件的实际列数减 1。ValueError: Each dimension should be between min_value_entry and max_value_entry数据中存在超出[min_value_entry, max_value_entry]的坐标。这两个参数同时决定了 HST 根包围盒务必覆盖全量数据范围README 示例数据集即满足[0, 2]。Dataflow 运行报错找不到变量/导入--runnerDataflowRunner下脚本会自动开启save_main_session请确保所有自定义依赖在远端环境可用见 run_clustering.py。输出 hst.csv 分片Beam 的WriteToText会生成hst.csv-00000-of-xxxxx形式的分片文件后续LoadFilesIntoDataFrame使用 glob 模式hst.csv*自动加载全部分片见 run_clustering.py无需手动合并。9. 小结hst_clustering 模块完整复现了 KDD22 论文的 DP 聚类方案以 Apache Beam 为执行引擎将构建差分隐私 HST这一核心步骤拆解为可并行的数据变换链读取 → 切分 → 计数 → 高斯阈值加噪 → 写出再通过 dynamic_program.py 的树上动态规划求解 k-median 目标最终输出聚类中心与目标得分。理解本文涉及的参数语义layers、epsilon/delta、seed、min/max_value_entry、两级流水线Beam 构建 DP 求解以及高斯阈值机制与隐私预算的关系即可将该实现迁移到自己的数据集上并依据论文框架进一步扩展实验。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 基于分层分离树（HST）的可扩展差分隐私聚类：hst_clustering 实现与实战指南
基于分层分离树HST的可扩展差分隐私聚类hst_clustering 实现与实战指南【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research导读本文围绕 hst_clustering 模块讲解 KDD22 论文Scalable Differentially Private Clustering via Hierarchically Separated TreesarXiv:2206.08646的官方开源实现。该模块以Apache Beam 流水线构建差分隐私DP下的分层分离树Hierarchically Separated Tree, HST并配合动态规划求解 k-median 聚类问题在保护数据隐私的同时实现大规模聚类。读完本文你将掌握如何准备输入数据、理解全部命令行参数、跑通端到端聚类流程以及从源码层面理解 HST 构建、高斯阈值机制与 DP 动态规划的核心原理。1. 模块定位与论文背景hst_clustering 是 Google Research 中专门承载 DP 聚类算法的模块对应论文Scalable Differentially Private Clustering via Hierarchically Separated TreesKDD 2022arXiv:2206.08646。其核心思想是不直接在高维原始数据上做隐私聚类通常代价高昂而是先用分层分离树把数据空间递归切分成多层次的网格单元cell统计每个单元内的点数量并施加差分隐私噪声再在这棵已加噪的树上用动态规划挑选出最优的 k 个聚类中心。由于树结构天然支持并行化该算法通过 Apache Beam 可以扩展到大规模数据集这正是可扩展Scalable一词的来源。模块包含 11 个文件职责划分清晰文件职责run_clustering.py命令行入口串联 HST 构建与 DP 求解两个阶段dp_hst.pyBeam 流水线负责构建差分隐私 HSTdynamic_program.pyHST 数据结构与 k-median 动态规划求解gaussian_thresholding.py高斯阈值机制Gaussian Thresholding参数计算io.py数据读写、HST 文件解析为树对象dp_one_median.py差分隐私 1-median 求解供中心选择与后处理使用kvariates.py并行的 k-variates 机制论文中的对比/备选聚类方法kmedian_plus_plus.pyk-means 风格初始化与 Lloyd 迭代工具experiment_config.py各算法的 dataclass 参数配置kvariates_test.pykvariates 相关单元测试requirements.txt运行依赖清单2. 环境准备与依赖运行本模块需要以下依赖见 requirements.txtabsl-py1.2.0 numpy1.21.5 pandas1.5.0 scipy1.9.1 apache-beam2.46.0其中absl-py用于命令行参数解析flagsnumpy/pandas/scipy负责数值计算、数据帧解析与高斯机制中的优化/统计运算apache-beam是整套 HST 构建流水线的执行引擎。建议使用虚拟环境安装pip install -r hst_clustering/requirements.txt3. 输入数据格式入口脚本 run_clustering.py 对输入文件格式有明确约定制表符分隔Tab-separated的文本文件第一列为样本编号其余各列是该点在 R^d 空间中的坐标。仓库内置的示例数据集 s1_random-standarized.txt 正是这一格式前几行如下0 1.3994608666813209 0.6072888469790971 1 0.7093077080912279 0.615079819640638 2 1.4307569787257732 0.3337015180302204该数据集包含 5000 个样本点、2 个特征维度 d2所有坐标值均落在区间[0, 2]内——这与 README 示例中--min_value_entry0 --max_value_entry2 --dimensions2的参数设定严格对应。在 dp_hst.py 的CreateVectorFromTextDoFn 中每个点会做两层校验维度校验element.split()[1:]去掉首列样本编号后向量长度必须等于--dimensions指定的值否则抛出ValueError并提示设置正确的--dimensions取值边界校验每个维度的坐标值必须在min_value_entry与max_value_entry之间越界同样抛错。注意边界参数min/max value entry不只是校验用它同时定义了 HST 根节点的包围盒bounding box是树切分的起点因此必须正确设置。4. 运行端到端聚类完整命令与输出解析README 给出了在 google_research 仓库根目录下的标准运行方式。结合源码补充完整的参数说明后完整命令如下OUTPUT_DIRsome/directory python3 -m hst_clustering.run_clustering \ --raw_datahst_clustering/s1_random-standarized.txt \ --output_dir${OUTPUT_DIR} \ --dimensions2 \ --min_value_entry0 \ --max_value_entry2 \ --k_params10 \ --alsologtostderr4.1 全部命令行参数所有参数均在 run_clustering.py 中以 absl flags 定义含义与默认值如下参数类型默认值说明--raw_datastring空必填原始数据文件路径Tab 分隔首列为样本编号--output_dirstring空必填输出目录脚本会自动创建--k_paramsint10聚类中心数量 k--dimensionsintNone必填输入点的维度 d--layersint10HST 的层数递归切分深度--epsilonfloat1.0差分隐私 ε 参数--deltafloat0.00001差分隐私 δ 参数--seedint0HST 切分所用的随机种子--min_value_entryfloatNone必填各维度取值下界--max_value_entryfloatNone必填各维度取值上界--runnerenumNoneBeam 执行器DirectRunner本地或DataflowRunner云端--num_buckets_beamint100Beam Reshuffle 时使用的桶数量其中--runner的选择体现了模块的可扩展设计本地调试用DirectRunner大规模数据可切换DataflowRunner将流水线部署到云端分布式执行。使用 Dataflow 时run_clustering.py 会自动设置save_main_session True确保远端 worker 能访问全局命名空间中的变量与导入。脚本执行前的参数断言见 run_clustering.py可帮助你快速排查配置错误raw_data、output_dir非空dimensions 0k_params 0layers 0epsilon 0delta 0min_value_entry max_value_entrynum_buckets_beam 0。4.2 运行的两个阶段与输出产物main函数分两个阶段执行run_clustering.py阶段一Beam 流水线构建 DP HST输出写入${OUTPUT_DIR}/hst.csv实际为hst.csv-*分片文件。流水线见 dp_hst.pyReadFromText → CreateVectorFromText → Reshuffle → MapToCellId → CombinePerKey → GaussianThresholdMechansimFn → OutputAsString → WriteToText阶段二动态规划求解并评估产出两个文件${OUTPUT_DIR}/results.txtk-median 目标函数得分所有点到最近中心的距离之和通过dynamic_program.eval_hst_solution计算${OUTPUT_DIR}/centers.npynumpy 格式的聚类中心数组一行一个中心。注意 run_clustering.py 中LLOYD_ITERS 0即默认不执行 Lloyd 迭代后处理如需提升精度可参考 dynamic_program.py 中lloyd_iters 0的路径该路径会将每次迭代的隐私预算叠加需要用户自行核算总 ε。4.3 数据读取的细节约定io.py 的ReadRawData使用pd.read_csv(..., index_col0, sepr\s, headerNone)读取原始数据——这意味着首列被视为索引样本编号被丢弃空白字符包括制表符与多空格均可作为分隔符。而LoadFilesIntoDataFrameio.py则按 CSV 规则解析 HST 输出文件列结构固定为id, right_child, left_child, diameter, weight, 0, 1, ..., d-1其中id是二进制字符串形式的单元编号0..d-1为各维度的单元中心坐标特征列。5. 源码深度剖析HST 是如何被构建的5.1 逐层切分MapToCellId树的核心构建逻辑在 MapToCellId。每个输入点从根节点的包围盒出发逐层、逐维度地递归细分根节点先用全局min_value_entry/max_value_entry构造 d 维包围盒产出根单元记录(diameter, center, 1.0)每一层 × 每一维度调用layer_dimension_threshold计算该层该维度的确定性切分阈值阈值来源是f{seed}|{layer}|{dimension}字符串的 MD5 哈希再映射到[1/3, 2/3]区间内的相对位置(random.random() 1.0) / 3.0对应论文中分层分离树1/3-2/3的分离性质源码注释明确指出这里使用弱随机数生成器是可接受的因为它只影响近似保证不影响隐私保证dp_hst.py判定分支若点在该维度的坐标小于阈值cell_id追加False子节点 id 追加0并将该维度上界更新为阈值否则追加True追加1下界更新为阈值逐层产出每一层都yield当前点的单元记录因此一个点总共产生1 layers × dimensions条记录根 每层每维一个单元这也是下文 L0 敏感度的由来。单元记录由 get_diameter_center_one_count_tuple 生成diameter ||max - min||₂欧氏直径center (max - min)/2 min几何中心第三个元素1.0表示该点对该单元的贡献为 1。5.2 加噪与裁剪高斯阈值机制GaussianThresholdMechansimFndp_hst.py对每个单元执行差分隐私处理灵敏度分析每个点最多影响layers × dimensions个单元即 L0 灵敏度见 dp_hst.py每单元贡献上限为 1L∞ 上限调用 gaussian_thresholding.py 的get_gaussian_thresholding_params计算噪声标准差sigma与裁剪阈值thresholdL2 灵敏度max_bucket_contribution × sqrt(max_num_buckets_contributed)σ由 Analytic Gaussian MechanismB / B- 辅助函数与root_scalar数值求逆精确计算见find_gaussian_multiplier与find_sigma阈值1 √2 · σ · Φ⁻¹(1 - 2δ / l0)其中Φ⁻¹为标准正态分位数gaussian_threshold执行对每个单元的真实计数施加N(0, σ²)噪声仅当加噪计数 ≥ 阈值时才输出该单元见process中的if copy_t[2] self.threshold。这一步同时完成两件事丢弃稀疏/空单元以节省空间并保证未知分区unknown partitions下的差分隐私。最终的输出格式output_as_string为cell_id,left_child,right_child,diameter,dp_weight,center_0,...,center_{d-1}5.3 从输出文件恢复树DataFrameToTreeio.py 的DataFrameToTree将流水线产物解析回dynamic_program.HST对象处理逻辑包括将负权重单元权重截断为 0加噪后可能出现的负值识别叶子节点左右子节点都不存在并挂载补齐缺失子节点当某内部节点只有一个子节点存在于输出中时会创建一个权重为 0、直径为父节点 2/3 的空节点补全二叉树——这是因为阈值为 0 的单元可能被高斯机制过滤掉而 DP 求解需要一个完整的树结构根节点 id 为空字符串ROOT_ID由tree.add_root标记。随后 run_clustering.py 调用tree.validate_tree(True)校验树结构自动移除不可达节点再执行tree.solve_dp(k)。6. 树上动态规划求解差分隐私 k-median6.1 动态规划递推HST.solve_dp 在整棵树上求解 k-median 目标最小化Σ distance(p, 最近中心)。核心递推见_solve_dpdynamic_program.py对每个节点计算cost_matrix[kprime]在该子树内放置 k 个中心的代价k 0不放置中心代价 2 × diameter^exp × weight惩罚性上界叶子节点代价 diameter^exp × weight即该单元内所有点以直径距离近似到中心内部节点枚举左右子树中心数分配k1 k2 k取两子树代价之和的最小值并记录最优分解到left_optimal/right_optimal数组供回溯使用。递推完成后recover_dp_solution 通过_recover_solutiondynamic_program.py沿最优分解路径回溯得到选中的叶子单元集合。6.2 中心映射回原始空间选中的叶子单元 id 需映射回原始空间的坐标。_get_center 的处理方式是若该单元 id 存在于 HST 输出数据帧中直接取对应行特征列若不存在单元被阈值过滤则回溯到其父节点去掉 id 最后一位直到找到存在记录的祖先单元——这保证了最终总能输出合法中心。最终由get_centers_from_hst汇总为k × d的中心矩阵。6.3 评估与可选的后处理eval_hst_solutiondynamic_program.py以原始数据评估解的质量由 HST 恢复中心若lloyd_iters 0执行指定轮数的 Lloyd 迭代精化kmedian_plus_plus.py 中的lloyd_iter内部使用privacy_params保证隐私max_num_points20000限制单次处理规模计算并返回 k-median 目标得分与中心。隐私提示源码 docstring 明确警告——若启用 Lloyd 迭代最终 ε 保证需要按lloyd_iters × privacy_params.epsilon自行核算dynamic_program.py。默认入口不启用该后处理。7. 扩展模块DP 1-median 与 kvariates除主流程外模块还附带两类论文中涉及的聚类工具可在相关实验中独立使用DP 1-mediandp_one_median.py通过**目标扰动objective perturbation**求解单中心问题。private_k_med_objective基于 DP 凸优化框架论文引用 TPDPCO核心要素包括用平滑参数lambd构造光滑近似范数smooth_norm_conj范数小于2·lambd时用二次近似否则用真实范数减lambd添加正则项p·β/(e1-e3)与高斯扰动向量b1、b2用scipy.optimize.minimize(methodtrust-ncg)优化收敛梯度阈值gtolgamma——gamma是隐私保证成立的先决条件梯度范数必须小于 gamma在 Beam 中心选择器中还会按gamma/n·√d缩放见one_median_dp_beam。kvariateskvariates.py论文提出的并行 k-variates 机制。它先把数据按 simhash 等分裂策略simhash_split划分到多个 worker然后迭代式地每个 worker 基于本地数据与全局已选中心计算采样概率距离越大概率越高按概率选出候选中心再由select_center全局汇总挑选最终中心create_pipeline与iteration。配套的 kvariates_test.py 覆盖了 simhash 哈希正确性、随机分裂与距离计算等核心函数的单元测试。8. 常见问题排查ValueError: invalid dimensions in vectors输入文件每行特征数去掉首列编号后与--dimensions不一致。检查--dimensions是否等于文件的实际列数减 1。ValueError: Each dimension should be between min_value_entry and max_value_entry数据中存在超出[min_value_entry, max_value_entry]的坐标。这两个参数同时决定了 HST 根包围盒务必覆盖全量数据范围README 示例数据集即满足[0, 2]。Dataflow 运行报错找不到变量/导入--runnerDataflowRunner下脚本会自动开启save_main_session请确保所有自定义依赖在远端环境可用见 run_clustering.py。输出 hst.csv 分片Beam 的WriteToText会生成hst.csv-00000-of-xxxxx形式的分片文件后续LoadFilesIntoDataFrame使用 glob 模式hst.csv*自动加载全部分片见 run_clustering.py无需手动合并。9. 小结hst_clustering 模块完整复现了 KDD22 论文的 DP 聚类方案以 Apache Beam 为执行引擎将构建差分隐私 HST这一核心步骤拆解为可并行的数据变换链读取 → 切分 → 计数 → 高斯阈值加噪 → 写出再通过 dynamic_program.py 的树上动态规划求解 k-median 目标最终输出聚类中心与目标得分。理解本文涉及的参数语义layers、epsilon/delta、seed、min/max_value_entry、两级流水线Beam 构建 DP 求解以及高斯阈值机制与隐私预算的关系即可将该实现迁移到自己的数据集上并依据论文框架进一步扩展实验。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考