第4卷第2期 智能系统学报 Vol 4 Ng 2 2009年4月 CAA I Transactions on Intelligent Systems Apr 2009 一种分布式隐私保护的密度聚类算法 吉根林，姚瑶 (南京师范大学数学与计算机科学学院，江苏南京210097) 摘要：对基于密度的分布式聚类算法DBDC进行改进，提出了一种基于密度的分布式隐私保护聚类算法DBPPDC 在由局部模型确定全局模型时，通过相关安全协议有效地保护了局部模型，同时不影响全局聚类在利用全局模型 更新局部模型时，通过改进算法、应用安全协议保护隐私信息最终使各站点分布的数据能够安全聚类.理论分析和 实验结果表明，DBPPDC算法是有效的. 关键词：隐私保护：分布式聚类：DBDC,DBPPDC 中图分类号：TP3111文献标识码：A文章编号：1673-4785(2009)02-0137-05 Density-ba sed privacy preserving distr ibuted clustering a lgor ithm JI Gen-lin,YAO Yao (School ofMathematics and Computer Science,Nanjing Nomal University,Nanjing 210097,China Abstract:A density-based privacy preserving distributed clustering algorithm (DBPPDC)was proposed follwing the mprovements to the density-based distributed clustering DBDC algorithm.When a glbal model is detem ined from a bcal model,(DBPPDC)effectively protects the bcal model without obstructing global clustering On the contrary,when the bcal model is updated with the glbalmodel,DBPPDC makes all the data in local sites cluster safely by mproving the previous algorithm and appling a secure protocol Expermental results showed that DBPP- DC is effective and efficient Keywords:privacy preserving distributed clustering DBDC;DBPPDC 分布式聚类算法1在聚类过程中将本站点有 划分的分布式数据库环境下，对基于密度的分布式 关真实数据传送给其他站点，从而导致信息泄露.在 聚类算法I(density based distributed clustering,DB- 实际分布式聚类应用中，有时候需要保护本站点的 DC)进行改进，提出了一种基于密度的分布式隐私 真实信息不被传送给其他站点，即需要进行隐私保 保护聚类算法(density based privacy preserving dis- 护，为此，需要研究基于隐私保护的分布式聚类算 tributed clustering,DBPPDC).在由局部模型确定全 法.聚类过程中的隐私保护方法可大致分为数据扰 局模型时，通过相关安全协议有效地保护局部模型， 乱和安全多方计算2种.基于数据扰乱的隐私保护 同时不影响全局聚类.在利用全局模型更新局部模 聚类思想是通过转换数据使得真实的敏感数据不为 型时，通过改进算法、应用安全协议保护隐私信息， 人知，然后再进行聚类分析.而基于安全多方计算的 最终使各站点分布的数据能够安全聚类， 隐私保护聚类主要通过构造安全多方协议，使得一 组站点在仅仅拥有自己私有信息的情况下能最终获 1问题描述 知全局聚类信息.后者主要应用于分布式聚类分析. 11相关定义 针对水平划分的分布式数据库，文献[56提出 定义1全局数据集.分布式系统中有m个站 基于隐私保护的分布式聚类算法，本文同样在水平 点，各站点相应的d维局部数据集分别为DB, DB2,DBm,各局部数据集的大小分别为N, 收稿日期：2008-12-16 基金项目：国家自然科学基金资助项目(40771163). 通信作者：姚瑶.Emai让cindy yaoyao@homail oom N2,,Nm,DB=UDB称为全局数据集 1a1 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net第 4卷第 2期 智 能 系 统 学 报 Vol. 4 №. 2 2009年 4月 CAA I Transactions on Intelligent System s Ap r. 2009 一种分布式隐私保护的密度聚类算法 吉根林 ,姚 瑶 (南京师范大学 数学与计算机科学学院 ,江苏 南京 210097) 摘 要 :对基于密度的分布式聚类算法 DBDC进行改进 ,提出了一种基于密度的分布式隐私保护聚类算法 DBPPDC. 在由局部模型确定全局模型时 ,通过相关安全协议有效地保护了局部模型 ,同时不影响全局聚类. 在利用全局模型 更新局部模型时 ,通过改进算法、应用安全协议保护隐私信息 ,最终使各站点分布的数据能够安全聚类. 理论分析和 实验结果表明 ,DBPPDC算法是有效的. 关键词 :隐私保护 ;分布式聚类 ; DBDC; DBPPDC 中图分类号 : TP311. 1 文献标识码 : A 文章编号 : 167324785 (2009) 0220137205 Density2based pr ivacy preserving distr ibuted cluster ing algor ithm J I Gen2lin, YAO Yao ( School ofMathematics and Computer Science, Nanjing Normal University, Nanjing 210097, China ) Abstract:A density2based p rivacy p reserving distributed clustering algorithm (DBPPDC) was p roposed following the imp rovements to the density2based distributed clustering DBDC algorithm. W hen a global model is determ ined from a local model, (DBPPDC) effectively p rotects the local model without obstructing global clustering. On the contrary, when the local model is updated with the globalmodel, DBPPDC makes all the data in local sites cluster safely by imp roving the p revious algorithm and app ling a secure p rotocol. Experimental results showed that DBPP2 DC is effective and efficient. Keywords: p rivacy p reserving; distributed clustering; DBDC; DBPPDC 收稿日期 : 2008212216. 基金项目 :国家自然科学基金资助项目 (40771163). 通信作者 :姚 瑶. E2mail: cindy_yaoyao@hotmail. com. 分布式聚类算法 [ 124 ]在聚类过程中将本站点有 关真实数据传送给其他站点 ,从而导致信息泄露. 在 实际分布式聚类应用中 ,有时候需要保护本站点的 真实信息不被传送给其他站点 ,即需要进行隐私保 护 ,为此 ,需要研究基于隐私保护的分布式聚类算 法. 聚类过程中的隐私保护方法可大致分为数据扰 乱和安全多方计算 2种. 基于数据扰乱的隐私保护 聚类思想是通过转换数据使得真实的敏感数据不为 人知 ,然后再进行聚类分析. 而基于安全多方计算的 隐私保护聚类主要通过构造安全多方协议 ,使得一 组站点在仅仅拥有自己私有信息的情况下能最终获 知全局聚类信息. 后者主要应用于分布式聚类分析. 针对水平划分的分布式数据库 ,文献 [ 526 ]提出 基于隐私保护的分布式聚类算法 ,本文同样在水平 划分的分布式数据库环境下 ,对基于密度的分布式 聚类算法 [ 7 ] ( density based distributed clustering, DB2 DC)进行改进 ,提出了一种基于密度的分布式隐私 保护聚类算法 ( density based p rivacy p reserving dis2 tributed clustering, DBPPDC). 在由局部模型确定全 局模型时 ,通过相关安全协议有效地保护局部模型 , 同时不影响全局聚类. 在利用全局模型更新局部模 型时 ,通过改进算法、应用安全协议保护隐私信息 , 最终使各站点分布的数据能够安全聚类. 1 问题描述 1. 1 相关定义 定义 1 全局数据集. 分布式系统中有 m 个站 点 ,各站点相应的 d 维局部数据集分别为 { DB1 , DB2 , …, DBm }, 各局部数据集的大小分别为 N1 , N2 , …, Nm , DB = ∪ m i = 1 DBi称为全局数据集