基于KD树最优投影划分的k匿名算法

• 作者: 吴文莉 江叶峰 汪小寒 罗永龙 赵传信 郭良敏
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 数据发布 隐私保护 k匿名 KD树 划分
• 年，卷（期）: 2016,（6）
• 所属期刊栏目: 城市大气污染专栏
• 页码范围: 1050-1064
• 页数: 15页
• 分类号: TP391
• 字数: 9175字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2016.06.008

摘要

针对现有数据发布隐私保护保护算法中的“局部最优”划分问题，提出了一种基于KD树最优投影划分的k匿名算法。首先，在全局范围内对每一个属性维度进行遍历，根据投影距离方差值衡量每个维度的离散度，并确定最优维度；然后，在最优属性维度上，计算其划分系数值，并确定最优划分点。进一步引入一种改进的 KD 树结构，与传统的KD树结点是一个数据点不同，新设计的KD树中的每个结点均是一个集合。用经过划分点并垂直于最优维度的超平面将一个结点分成两部分，分别作为其左、右孩子结点。最后通过理论分析证明了本文算法的正确性，用实验比较和验证了算法的性能，实验结果显示所提算法平均概化范围减小10%~22%，能够实现更优的划分和更好的数据集可用性。