一种基于MapReduce的差分可辨性k原型聚类方法

摘要

本发明公开一种基于MapReduce的差分可辨性k原型聚类方法，包含以下步骤：步骤1：对输入数据集D进行预处理；步骤2：MapReduce框架的任务设置；步骤3：确定每个Map任务中的局部中心点集合Q；步骤4：根据局部中心点集合Q确定聚类个数k；步骤5：设置差分可辨性实现机制的参数；步骤6：划分数据集D1的每条数据记录至相应聚类；步骤7：计算新一轮聚类中心点；步骤8：比较两轮聚类中心点；步骤9：根据最终聚类中心点划分数据集D1。本发明方法为大数据挖掘的从业者提供了一种简单的参数化方法；提高数据处理效率，同时可保证数据的安全性和效用。

权利要求

1.一种基于MapReduce的差分可辨性k原型聚类方法，其特征在于：该方法包含以下步骤：

步骤1：对输入数据集D进行预处理；包括数据集D中数值型数据的归一化以及对数值型和分类型属性的调整，预处理后形成新数据集D1；

步骤2：MapReduce框架的任务设置；设置主任务Driver，先后调用基于MapReduce框架的两个子任务：一个是确定初始中心点和聚类个数，即第一个子任务；另一个是实现差分可辨性k原型聚类，即第二个子任务；两个子任务通过执行Map任务和Reduce任务实现；

步骤3：确定每个Map任务中的局部中心点集合Q；

步骤4：根据局部中心点集合Q确定聚类个数k；

步骤5：设置差分可辨性实现机制的参数；对于数值型数据和分类型数据，分别采用Laplace机制和指数机制实现差分可辨性；

步骤6：划分数据集D1的每条数据记录至相应聚类；

步骤7：计算新一轮聚类中心点；

步骤8：比较两轮聚类中心点；主任务Driver读取接收新一轮生成的聚类中心点集合和上轮的k个初始中心点集合，计算两轮聚类中心点集合间的距离Dis；若这两轮中心点集合的距离Dis小于指定阈值Threshold或者迭代次数已经到达迭代总数值T，则迭代终止，输出最终的聚类中心点集合U'；若不满足要求，继续重复步骤6～步骤8；

步骤9：根据最终聚类中心点划分数据集D1；主任务Driver再次调用MapReduce中的Mapper类，设置map函数按照最终生成的聚类中心点集合对数据集D1进行聚类，将每条记录xi'划分至相应的聚类，数据记录的各维属性值作为键值对的key1，聚类标号作为键值对的value1，map函数输出(key,value)键值对，即最终的聚类结果；

所述步骤5的具体过程为：Laplace机制对数值型数据添加一个服从Laplace分布的随机噪声 指数机制以正比于 的概

率从分类型数据中选择并输出属性值；其中，f为查询函数，Δf为f的总敏感度；对于归一化r c

的数值型数据，全局敏感度Δf＝dr，对于分类型数据，全局敏感度Δf＝1，数据集D1总敏感度为Δf＝dr+1；m为可能数据集数，mr和mc分别为数值型和分类型可能数据集数的最小值；ρ为差分可辨性的隐私参数，迭代次数T未知时，第n(1≤n≤T)轮迭代数值型和分类型数据的隐私参数分别为

2.根据权利要求1所述的一种基于MapReduce的差分可辨性k原型聚类方法，其特征在于：所述步骤1的具体过程为：输入数据集D共有N条数据记录，每个数据记录表示为xi(1≤i≤N)；数据集D维数为d，其中数值型数据维数为dr，分类型数据维数为dc，即数据集D中某一数据记录表示为xi＝(xi1,xi2,…,xid)；对数据集D每维属性进行调整，使前dr维为数值型数据，后dc维为分类型数据；读取数据集D每条记录xi的前dr维属性，设置第一条记录x1前dr维属性值分别为初始最大值 和最小值

将其余N‑1条记录的前dr维属性值分别与max和min比较大小，得到前dr维各维属性的最大值 和最小值通过归一化公式 将xi的前dr维属性归一化处理至空间 中，形成新数据集D1。

3.根据权利要求1所述的一种基于MapReduce的差分可辨性k原型聚类方法，其特征在于：所述步骤3的具体过程为：主任务Driver调用MapReduce中第一个子任务，确定初始中心点和最优聚类个数；所述第一个子任务执行Mapper类，map函数中设置集合Q＝null，设置迭代次数 L为每个map函数读取数据的记录数；在迭代次数 内，当集合Q为空时，计算数据集D1中数据点xi与坐标原点距离的最小值，将数据点xi保存至集合Q；当集合Q不为空时，计算数据集D1中数据点xi与集合Q中局部中心点的距离，得出最小距离中的最大者，将最小距离中的最大者保存至集合Q。

4.根据权利要求1所述的一种基于MapReduce的差分可辨性k原型聚类方法，其特征在于：所述步骤4的具体过程为：第一子任务继续执行Reducer类，reduce函数接收集合Q＝{Q1,…,Qj，…}，计算P＝Count(Q)，P为集合Q的数据总量，设置迭代次数为 和集合Q'＝null；在迭代次数 内，当集合Q'为空时，计算集合Q中局部中心点与坐标原点距离的最小值，将局部中心点保存至集合Q'；当集合Q'不为空时，计算集合Q中局部中心点q与Q'的中心点之间的距离，得出最小距离中的最大者，将最小距离中的最大者保存至集合Q'；计算集合Q'的数据总量K，设置迭代次数为 在迭代次数 内，计算集合Q'中指标Depth(i)的最大值，将集合Q'中前i个点赋值至空集合U中，U为聚类的初始中心点集合，最优聚类个数k＝i，输出初始中心点集合U。

5.根据权利要求1所述的一种基于MapReduce的差分可辨性k原型聚类方法，其特征在于：所述步骤6的具体过程如下：主任务Driver调用MapReduce中第二个子任务，进行差分可辨性k原型聚类；子任务执行Mapper类，设置Mapper类的setup函数读取集合U中k个初始中心点u1,...,uk，读入事先定义的集合clustercenters中；map函数读取接收到的每条数据记录xi，分别计算xi与k个初始中心点的距离Distance，得到与xi'距离值最小的聚类中心us(1≤s≤k)，将记录xi划分到此聚类；将聚类标号s作为键值对的key值，数据记录的各维属性值作为value，map函数输出(key,value)键值对。

6.根据权利要求1所述的一种基于MapReduce的差分可辨性k原型聚类方法，其特征在于：所述步骤7的具体过程为：第二个子任务继续执行MapReduce中的Reducer类，接收键值对(key,value)，合并属于同一个key值的聚类；设置reduce函数，对于前dr维的数值型数据，计算同一个聚类中数据数目之和numl和各维属性值之和suml，对其添加Laplace噪声可得到suml'，计算suml'/numl得到数值型数据的聚类中心 对于后dc维分类型数据，计算每维属性的分类值出现次数，根据出现次数，使用指数机制选择并输出每维属性的分类值，即为分类型数据的聚类中心 将 和 合并即可得到新一轮聚类中心点集合ul'。

说明书

一种基于MapReduce的差分可辨性k原型聚类方法

技术领域

[0001] 本发明涉及一种基于MapReduce的差分可辨性k原型聚类方法，属于网络空间安全技术领域。

背景技术

[0002] 数据挖掘是大数据背景下一种高效的、深层次的数据分析技术，吸纳了机器学习、数据库、统计学等许多应用领域的大量技术，迅速成为各行各业的研究热点。聚类分析作为
数据挖掘的重要方向，被广泛应用于各种场景。聚类针对数据集的特点和具体分析任务的
不同可设计不同的算法，按照处理对象的类型可以将聚类算法分为三类：数值型数据聚类
算法、分类型数据聚类算法和混合型数据聚类算法。数据挖掘中大部分聚类算法只能处理
数值型或者分类型的数据。实际上，生成的数据多为混合型，使用单一类型属性数据的聚类
算法对混合型数据聚类，会造成信息丢失，数据效用降低。因此，对混合型数据的聚类算法
的研究具有十分重大的意义。

[0003] 数据挖掘在分析大数据的同时，在某种程度上加剧了隐私泄露的可能性。隐私保护问题最早在20世纪70年代末被提出，此后众多学者陆续研发出许多隐私保护的模型。传
统的隐私保护模型中，传统隐私保护方法以k‑anonymity及相同理论基础上的扩展方法最
具代表性。但上述隐私保护方法存在两个问题：(1)具有背景相关依赖性，即假定了某一攻
击模型或者攻击者具有的背景知识；(2)缺少较为严格的理论基础，证明隐私保护水平程度
十分困难。Dwork提出的差分隐私(Differential Privacy，DP)解决了这两个问题。2012年，
Lee和Clifton认为差分隐私定义存在缺陷。隐私参数ε是差分隐私中评价隐私保护水平的
指标，但是ε只限制相邻两个数据集的概率差异，即限制单个个体对输出的影响程度，而不
是个体信息泄露的程度，这不符合相关法律对隐私的定义。因此，提出差分可辨性
(Differential Identifiability，DI)，与差分隐私提供相同的隐私保证，差分可辨性参数
ρ限制个体被重新识别的概率，可为从业者提供了更简便的参数化方法。

[0004] 传统的单机处理模型已经不能满足大量数据计算和存储的需要，使用并行模式处理大数据是目前最优的解决方案。Hadoop大数据平台上提供了一个开源的可扩展性和高可
靠性的分布式计算环境，利用集群存储大量数据。MapReduce框架是Hadoop平台的重要组成
部分，采用Master/Slave(M/S)架构，构建在分布式文件系统之上。MapReduce应用于大规模
数据集的并行编程接口，基于“分而治之”的思想实现，归纳了经典的顺序式处理大数据的
流程和特点，并借助函数式设计语言Lisp的基本思想，将map函数和reduce函数设计为两个
高级的并行编程接口和抽象模型，用户只需编写这两个函数，即可完成简单的并行程序的
设计，是目前提高大数据处理效率的最佳框架。

[0005] 综上，在大数据分析时，混合型数据聚类方法易造成隐私泄露，并且传统数据处理模型不能满足大数据计算的需要。因此，本发明将给出大数据中的差分可辨性方法，确定差
分可辨性的实现机制和组合性质，基于MapReduce框架实现混合型聚类算法k原型(k‑
prototypes)，确保大数据平台上聚类结果的安全性和效用。

发明内容

[0006] 本发明的技术解决问题：针对Hadoop平台现有安全技术的不足，提供一种基于MapReduce的差分可辨性k原型聚类方法，解决混合型聚类分析过程中隐私泄露问题的同
时，实现算法并行化。

[0007] 本发明采取的技术方案是：一种基于MapReduce的差分可辨性k原型聚类方法，它包含以下步骤：

[0008] 步骤1：对输入数据集D进行预处理。数据集D的预处理包括D中数值型数据的归一化以及对数值型和分类型属性的调整,预处理后形成新数据集D1。

[0009] 具体过程如下：

[0010] 输入数据集D共有N条数据记录，每个数据记录表示为xi(1≤i≤N)。数据集D维数为d，其中数值型数据维数为dr，分类型数据维数为dc，即数据集D中某一数据记录表示为xi
＝(xi1,xi2,...,xid)。对数据集D每维属性进行调整，使前dr维为数值型数据，后dc维为分类
型数据。读取数据集D每条记录xi的前dr维属性，设置第一条记录x1前dr维属性值分别为初
始最大值 和最小值 将其余N‑1条
记录的前dr维属性值分别与max和min比较大小，得到前dr维各维属性的最大值
和最小值 通过归一化公式
将xi的前dr维属性归一化处理至空间 中，形成新数据集D1。

[0011] 步骤2：MapReduce框架的任务设置。设置主任务Driver，先后调用基于MapReduce框架的两个子任务：一个是确定初始中心点和聚类个数，即第一个子任务；另一个是实现差
分可辨性k原型聚类，即第二个子任务。两个子任务通过执行Map任务和Reduce任务实现。

[0012] 步骤3：确定每个Map任务中的局部中心点集合Q。主任务Driver调用MapReduce中第一个子任务，确定初始中心点和最优聚类个数。所述第一子任务执行Mapper类，map函数
中设置集合Q＝null，设置迭代次数 L为每个map函数读取数据的记录数。在迭代次数
内，当集合Q为空时，计算数据集D1中数据点xi与坐标原点距离的最小值，将数据点xi保
存至集合Q；当集合Q不为空时，计算数据集D1中数据点xi与集合Q中局部中心点的距离，得出
最小距离中的最大者，将最小距离中的最大者保存至集合Q。

[0013] 步骤4：根据局部中心点集合Q确定聚类个数k。第一子任务继续执行Reducer类，reduce函数接收集合Q＝{Q1,…,Qi,…}，计算P＝Count(Q)，P为集合Q的数据总量，设置迭代
次数为 和集合Q'＝null。在迭代次数 内，当集合Q'为空时，计算集合Q中局部中心
点与坐标原点距离的最小值，将局部中心点保存至集合Q'；当集合Q'不为空时，计算集合Q
中局部中心点q与Q'的中心点之间的距离，得出最小距离中的最大者，将最小距离中的最大
者保存至集合Q'。计算集合Q'的数据总量K，设置迭代次数为 在迭代次数 内，
计算集合Q'中指标Depth(i)的最大值，将集合Q'中前i个点赋值至空集合U中，U为聚类的初
始中心点集合，最优聚类个数k＝i，输出初始中心点集合U。

[0014] 步骤5：设置差分可辨性实现机制的参数。对于数值型数据和分类型数据，分别采用Laplace机制和指数机制实现差分可辨性。Laplace机制对数值型数据添加一个服从
Laplace分布的随机噪声 指数机制以正比于
的概率从分类型数据中选择并输出属性值。其中，f为查询函数，Δf为
r
f的全局敏感度。对于归一化的数值型数据，全局敏感度Δf＝dr，对于分类型数据，全局敏
c
感度Δf＝1，数据集D1总敏感度为Δf＝dr+1。m为可能数据集数，mr和mc分别为数值型和分
类型可能数据集数的最小值。ρ为差分可辨性的隐私参数，迭代次数T未知时，第i(1≤i≤T)
轮迭代数值型和分类型数据的隐私参数分别为

[0015] 步骤6：划分数据集D1的每条数据记录至相应聚类。主任务Driver调用MapReduce中第二个子任务，进行差分可辨性k原型聚类。子任务执行Mapper类，设置Mapper类的setup
函数读取集合U中k个初始中心点u1,...,uk，读入事先定义的集合clustercenters中。map函
数读取接收到的每条数据记录xi，分别计算xi与k个初始中心点的距离Distance，得到与xi
距离值最小的聚类中心ui(1≤i≤k)，将记录xi划分到此聚类。将聚类标号i作为键值对的
key值，数据记录的各维属性值作为value，map函数输出(key,value)键值对。

[0016] 步骤7：计算新一轮聚类中心点。第二个子任务继续执行MapReduce中的Reducer类，接收键值对(key,value)，合并属于同一个key值的聚类。设置reduce函数，对于前dr维
的数值型数据，计算同一个聚类中数据数目之和numi和各维属性值之和sumi，对其添加
Laplace噪声可得到sumi'，计算sumi'/numi得到数值型数据的聚类中心 对于后dc维分类
型数据，计算每维属性的分类值出现次数，根据出现次数，使用指数机制选择并输出每维属
性的分类值，即为分类型数据的聚类中心 将 和 合并即可得到新一轮聚类中心点
集合ui'。

[0017] 步骤8：比较两轮聚类中心点。主任务Driver读取接收新一轮生成(所述步骤7)的聚类中心点集合和上轮(所述步骤6)的k个初始中心点集合，计算两轮聚类中心点集合间的
距离Dis。若这两轮中心点集合的距离Dis小于指定阈值Threshold或者迭代次数已经到达
迭代总数值T，则迭代终止，输出最终的聚类中心点集合U'。若不满足要求，继续重复步骤6
～步骤8。

[0018] 步骤9：根据最终聚类中心点划分数据集D1。主任务Driver再次调用MapReduce中的Mapper类，设置map函数按照最终生成的聚类中心点集合对数据集D1进行聚类，将每条记
录xi划分至相应的聚类，数据记录的各维属性值作为键值对的key1，聚类标号作为键值对
的value1，map函数输出(key1,value1)键值对，即最终的聚类结果。

[0019] 本发明与现有技术相比的优点在于：

[0020] (1)本发明提出的差分可辨性k原型聚类方法为大数据挖掘的从业者提供了一种简单的参数化方法，可以在挖掘中通过设置隐私参数ρ实现个体可识别性的隐私概念，并且
为差分隐私的隐私预算ε提供了一个取值上界。

[0021] (2)本发明将差分可辨性技术与经典的混合型聚类方法相结合，基于Hadoop中的MapReduce并行框架上实行操作，提高数据处理效率，同时也可保证数据的安全性和效用。

附图说明

[0022] 图1为本发明的MapReduce框架组成示意图；

[0023] 图2为本发明选取初始中心点示意图；

[0024] 图3为本发明的差分可辨性k原型聚类流程图。

[0025] 图中符号说明如下：

[0026] X1，X2，X3，X4表示选取的初始中心点；

[0027] D1表示输入数据集D归一化后的数据集；

[0028] Q表示局部中心点集合；

[0029] Depth(i)表示选择最佳聚类个数的指标，i表示第i个中心点；

[0030] k表示聚类个数；

[0031] key表示聚类标识，key1表示数据记录各维属性值；

[0032] value表示数据记录各维属性值，value1表示聚类标识。

具体实施方式

[0033] 本发明所提出的一种基于MapReduce的差分可辨性k原型聚类方法，需解决以下两个问题：第一、如何将差分可辨性应用于大数据聚类实现数据的隐私保护；第二、如何部署
差分可辨性k原型聚类方法到大数据平台上。

[0034] 下面分两个部分阐述本发明的具体实施方法：

[0035] 1.MapReduce框架

[0036] Hadoop大数据平台上的MapReduce框架是开源实现的，采用Master/Slave(M/S)架构，构建在分布式文件系统之上。MapReduce框架计算工作具有以下特点：工作任务可以被
划分为多项子任务，而且这些子任务相对独立，彼此之间无牵制，可以并行计算完成，子任
务完成后，该项工作内容也随之完成。MapReduce将map函数和reduce函数设计为两个高级
的并行编程接口和抽象模型，通过编写这两个函数完成分布式程序的设计。

[0037] MapReduce框架主要由以下几个组件组成，如图1所示：

[0038] 1)Client

[0039] 用户编写的MapReduce程序通过Client提高到JobTracker端，用户可以通过Client提供的接口查看作业的运行状态。Hadoop内部使用作业(Job)表示MapReduce程序，
一个MapReduce程序可以对应若干个作业，每个作业会被分解成若干个Map任务和Reduce任
务(Task)。

[0040] 2)JobTracker

[0041] JobTracker主要负责资源监控和作业调度。JobTracker监控所有TaskTracker与作业的健康状况，一旦发现失败的情况，则将相应的任务转到其他节点；同时，JobTracker
会跟踪任务的执行进度蒙自源使用量等信息，并将这些信息告知任务调度器，任务调度器
会在资源出现空闲时，选择合适的任务使用这些资源。任务调度器是一个可插拔的模块，用
户可以根据自己的需要设计相应的调度器。

[0042] 3)TaskTracker

[0043] TaskTracker周期性地通过Heartbeat将本节点上资源的使用情况和任务的运行进度汇报给JobTracker，同时接收JobTracker发送的命令并执行相应的操作。TaskTracker
使用“slot”等量划分本节点上的资源量。“slot”代表计算资源(CPU、内存等)，一个任务获
取到一个slot后才有机会运行，Hadoop的调度器的作用就是将TaskTracker上的空闲slot
分配给各个任务使用。slot分为Map slot和Reduce slot两种，分别供Map任务和Reduce任
务使用。

[0044] 4)Task

[0045] Task分为Map任务和Reduce任务两种，均有TaskTraker启动。对于MapReduce框架，处理数据的单位是split。split是一个逻辑概念，只包含一些元数据信息，比如数据起始位
置、数据长度、数据所在节点等，划分方法由用户决定，每个split各自交由一个Map任务处
理，split的多少决定了Map任务的数目。

[0046] Map任务将对应的split迭代解析成一个个(key,value)键值对，依次调用Mapper类中自定义的map函数进行相应计算，输出处理后的(key1,value1)键值对，(key1,value1)
键值对为中间结果。

[0047] Reduce任务的数量由用户自定义的Partitioner类决定，默认只有一个Reduce任务。根据定义的Reduce任务数量，Map任务输出的中间数据被分为相应的分区(partition)，
每个分区将被一个Reduce任务处理。Reduce任务从远程节点上读取Map任务的中间结果，按
照key值对(key1,value1)键值对进行排序并依次读取，调用用户自定义Reduce类中reduce
函数进行处理，将最终结果存储至HDFS中。

[0048] 在MapReduce框架的Map和Reduce任务的处理过程中，还有一个可供优化的步骤。由于集群上的可用带宽限制了MapReduce作业的数量，应该尽量避免Map任务和Reduce任务
之间的数据传输。因此，Hadoop允许用户针对Map任务的输出指定一个combiner函数，其输
出作为reduce函数的输入。combiner作为Map任务的一部分，执行完map函数后紧接着执行
combiner，其过程与reduce过程类似，都是对具有相同key值的数据进行合并。Hadoop平台
设计是为了降低工作执行过程中开销比较高的部分，一般情况下是磁盘和网络部分，但是
Map任务的输出往往是巨大的，可能是原始输入数据的许多倍，直接传输给Reduce节点的
话，将造成巨大的网络传输开销，采用combiner优化可减少网络传输的数据量。由于
combine属于优化方案，Hadoop无法确定要对Map任务输出记录调用多少次combiner，换句
话说，不管调用combiner多少次，Reduce任务的输出结果是一样的。combiner函数没有属于
自己的编程接口，但是combiner计算处理数据与Reduce任务有同样的特性，继承的也是
Reducer类。

[0049] 2.基于MapReduce的差分可辨性k原型聚类方法

[0050] 为了解决实际应用中混合型大数据聚类分析存在的个体隐私保护问题，设计了差分可辨性k原型聚类方法，并部署在MapReduce框架中进行并行化处理以提高数据处理效
率。

[0051] 本发明的基本思想可分为两个部分：第一部分，借鉴Canopy算法的思想，计算初始中心点和最优聚类个数。为避免中心点陷入局部最优，需要使任意两个中心点之间的距离
尽可能远，因此假设已知前q个中心点，那么第q+1个中心点应是待选取数据点中与前q个中
心点之间最小距离中最大者。对于大数据集，可先求取局部中心点，在此基础上计算全局中
心点，这种方法计算的数据也可以利用MapReduce并行框架，即将输入的数据集分为若干个
数据块，分配到同等数量的Map任务中，Map任务计算分配到的数据块输出局部中心点，以此
为基础利用Reduce任务计算全局中心点，得到初始中心点和最优聚类个数。第二部分，差分
可辨性k原型聚类方法利用初始中心点对数据集迭代聚类，其重点集中于聚类中心点和数
据点之间的相似性的度量，得到可防止隐私泄露的聚类中心点。该方法利用MapReduce框架
实现，以并行方式处理数据，MapReduce框架将输入的数据集分为若干个数据块，分配到同
等数量的Map任务中，Map任务分别计算分配到的数据块并输出中间结果，Reduce任务接收
中间结果进行计算，更新聚类中心点后迭代进行上述过程，直到聚类中心点的变化小于阈
值或者迭代次数达到上限，输出最终聚类结果。

[0052] 本发明的方法首先借鉴Canopy计算聚类个数k和初始中心点，其次使用差分可辨性k原型聚类得到满足差分可辨性的聚类中心点。本发明的方法包括两部分：1)在
MapReduce中确定初始中心点和最优聚类个数；2)在MapReduce中实现差分可辨性k原型聚
类得到最终结果。

[0053] 一种基于MapReduce的差分可辨性k原型聚类方法具体过程如下：

[0054] 步骤1：对输入数据集D进行预处理。输入数据集D共有N条数据记录，每个数据记录表示为xi(1≤i≤N)。数据集D维数为d，其中数值型数据维数为dr，分类型数据维数为dc，即
数据集D中某一数据记录表示为xi＝(xi1,xi2,...,xid)。对数据集D每维属性进行调整，使前
dr维为数值型数据，后dc维为分类型数据。读取数据集D每条记录xi的前dr维属性，设置第一
条记录x1前dr维属性值分别为初始最大值 和最小值
将其余N‑1条记录的前dr维属性值分别与max和min比较大小，
得到前dr维各维属性的最大值 和最小值
通过归一化公式 将xi的前dr维属性归一化处理至
空间 中，形成新数据集D1。

[0055] 在数据处理中，不同评价指标多数具有不同的量纲和量纲单位，会影响数据分析的结果。为了消除量纲的影响，需要对数据进行标准化处理，最典型的就是数据的归一化，
归一化的作用是使得预处理的数据被限定在一定范围内。

[0056] 步骤2：MapReduce框架的任务设置。设置主任务Driver，先后调用基于MapReduce框架的两个子任务：一个是确定初始中心点和聚类个数，即第一个子任务，另一个是实现差
分可辨性k原型聚类，即第二个子任务。两个MapReduce子任务均可通过执行Map任务和
Reduce任务实现。

[0057] 本发明实施方案若要实现并行化，主要是实现确定初始中心点和差分可辨性k原型聚类算法的并行化。根据图1的MapReduce框架，将方案的数据处理任务分为两部分：Map
任务和Reduce任务，其中分别定义了Mapper类、Reducer类的实现。

[0058] 从步骤3到步骤4，主要用于在MapReduce框架中第一个子任务，确定初始中心点和最优聚类个数k。

[0059] 步骤3：确定每个Map任务中的局部中心点集合Q。主任务Driver调用MapReduce中第一个子任务，确定初始中心点和最优聚类个数。所述第一子任务执行Mapper类，map函数
中设置集合Q＝null，设置迭代次数 L为每个map函数读取数据的记录数。在迭代次数
内，当集合Q为空时，计算数据集D1中数据点xi与坐标原点距离的最小值，将数据点xi保
存至集合Q；当集合Q不为空时，计算数据集D1中数据点xi与集合Q中局部中心点的距离，得出
最小距离中的最大者，将最小距离中的最大者保存至集合Q。

[0060] 关于聚类个数k和初始中心点的设置问题，在大多数情况下，两者是随机或根据多次实验选取，两者选取的不同会影响到聚类效果，因此，采用Canopy确定聚类个数k和初始
中心点。

[0061] 已有研究已经证明，通过Canopy算法确定的k值和初始中心点可以得到较好的聚类效果。但是，从原理上可以看出传统的Canopy算法易受区域半径T1和T2的影响。当T1过大
时，将会使某一点属于多个Canopy内；当T2过大时，将减小聚类个数k。因此，本发明借鉴
Canopy算法的思想，采用“最大最小原则”提高聚类个数和初始中心点的准确性。

[0062] Canopy算法的基本思想是将输入数据集分为若干个Canopy，本发明为避免聚类的结果出现局部最优的情况，最初任意两个中心点的距离应该尽可能远。假设已知前q个中心
点，那么第q+1中心点应是待选取数据点中与前q个中心点之间最小距离中最大者，公式如
下：

[0063]

[0064] L表示当前任务中数据集的数据总量，DisCollect(q+1)表示待确定的第q+1个中心点与前q个中心点间距中的最小值，Distmin表示第q+1个中心点应是最小距离中的最大
值。这样就避免了区域半径T2的设置。

[0065] 由于上述公式计算得到的中心点并非最终聚类中心点，在计算时只需要保证各个中心点之间的距离值最大，不必在全局范围内求解，所以可采用以下方式：首先，使用距离
坐标原点最近或者最远的数据点代替整个数据集中初始距离最远的数据点；其次，对于大
数据集，先利用Map任务求取局部中心点，以此为基础利用Reduce任务求取全局中心点；最
后，生成局部中心点时，为降低迭代次数，可选择迭代次数为 此处L为局部数据集大小，
一般情况下聚类个数

[0066] 步骤4：根据局部中心点集合Q确定聚类个数k。第一子任务继续执行Reducer类，reduce函数接收集合Q＝{Q1,…,Qi,…}，计算P＝Count(Q)，P为集合Q的数据总量，设置迭代
次数为 和集合Q'＝null。在迭代次数 内，当集合Q'为空时，计算集合Q中局部中心
点与坐标原点距离的最小值，将局部中心点保存至集合Q'；当集合Q'不为空时，计算集合Q
中局部中心点q与Q'的中心点之间的距离，得出最小距离中的最大者，将最小距离中的最大
者保存至集合Q'。计算集合Q'的数据总量K，设置迭代次数为 在迭代次数 内，
计算集合Q'中指标Depth(i)的最大值，将集合中前i个点赋值至空集合U中，U为聚类的初始
中心点集合，最优聚类个数k＝i，输出初始中心点集合U。

[0067] 在实际应用时，计算公式Distmin有如下规律：当已有的中心点个数低于或者超过真实的类别个数时，Distmin的变化幅度较小；当已有的中心点个数接近或达到真实类别数
时，Distmin有较大变化。因此，为了确定最优的聚类个数，引入指标Depth(i)表示Distmin变
化幅度，公式如下：

[0068] Depth(i)＝|Distmin(i)‑Distmin(i‑1)|+|Distmin(i+1)‑Distmin(i)|

[0069] 当聚类个数达到最优时，Depth(i)有最大值，最优聚类个数k＝i，前i个数据点即为初始中心点。

[0070] 步骤5：设置差分可辨性实现机制的参数。对于数值型数据和分类型数据，分别采用Laplace机制和指数机制实现差分可辨性。Laplace机制对数值型数据添加一个服从
Laplace分布的随机噪声 指数机制以正比于
的概率从分类型数据中选择并输出属性值。其中，f为查询函数，Δf为
r
f的全局敏感度。对于归一化的数值型数据，全局敏感度Δf＝dr，对于分类型数据，全局敏
c
感度Δf＝1，数据集D1总敏感度为Δf＝dr+1。m为可能数据集数，mr和mc分别为数值型和分
类型可能数据集数的最小值。ρ为差分可辨性的隐私参数，迭代次数T未知时，第i(1≤i≤T)
轮迭代数值型和分类型数据的隐私参数分别为

[0071] ρ‑差分可辨性假设攻击者的背景知识为 其中U为全集， 是D的相邻数据集，即|D′|＝|D|‑1，I(t)表示与U中的实体t对应的个体身份，
表示属于数据集D'的个体集合。在给定攻击者的背景知识 时，将会存在一个可能数据集
的集合Ψ，每个可能数据集D′和U中的某个实体组成，表示为
集合Ψ中只有一个数据集产生输出结果的正确数据集，其中每个可能数据集ω∈Ψ为数据
集D的概率是相等的，即推断未知个体属于数据集的先验概率为1/m，m＝|Ψ|＝|U|‑|D′|。

[0072] 给定查询函数f的敏感度Δf时，差分隐私的Laplace机制可用于实现差分可辨性，通过为输出结果添加随机噪声Y实现ρ‑差分可辨性，Y是服从Laplace分布的随机变量，Y～
Lap(λ)， 差分隐私的Laplace机制仅适用于数值型数据。对于非数值型
数据，需要差分可辨性的指数机制。

[0073] 指数机制中查询函数f为U×Range中每个(D,r)对生成一个实值分数。指数机制M以正比于 的概率从输出范围Range中选择并输出实体r，可实现差分可
辨性。假设每个可能数据集等概率，当差分隐私的隐私预算 时，ε‑差分隐私的
指数机制也可用于实现ρ‑差分可辨性。

[0074] 为了实现差分可辨性，全局敏感度Δf，可能数据集数m和隐私参数ρ是实现两个机制的重要参数。设有查询函数f，对于任意两个邻近数据集D和D'，下列公式成立

[0075]

[0076] 则称Δf为函数的全局敏感度。

[0077] 根据差分可辨性的并行组合性，输入数据集D可看作由两个互不相交的子集：数值型子集Dr和分类型子集Dc组成。对于数值型子集Dr，每维属性被归一化至 求和函数
r
fsum的全局敏感度Δf至多为dr。差分可辨性假设攻击者已知数据集D的邻近数据集，仅不确
定某个个体，即攻击者已知数据集的总记录数；对于分类型子集Dc，函数fcount对每维属性的
c
分类值进行计数，其全局敏感度Δf至多为1。

[0078] 根据差分可辨性的序列组合性，n个机制M1,...,Mn序列构成的组合提供 ‑差分可辨性。随着迭代次数的增加，每轮的隐
私参数ρi将逐渐接近攻击者随机猜测正确的概率。对于具有多维属性的输入数据集D，每一
维属性均会产生可能数据集集合Ψ，导致整个数据集D的可能数据集个数m很大，即攻击者
的先验概率很小。实际中攻击者可能以很高的自信推断个体t是否在数据集D中，因此，对于
数值型子集Dr，设算法中使用的可能数据集数mr为Dr中各维属性可能数据集|Ψr|的最小
值；对于分类型子集Dc，设算法中使用的可能数据集数mc为Dc中各维属性可能数据集|Ψc|
的最小值。此时，等价于假设攻击者仅不确定个体t某一维属性的具体值。

[0079] 与差分隐私不同，差分可辨性算法不能直接设置每轮迭代的ρi。根据差分可辨性的并行组合性，已知可能数据集数m，迭代总数为T时，算法满足 ‑差分可辨性。无
论迭代总数T是否确定，每轮迭代的ρi值需要根据可能数据集数m，隐私参数ρ和
计算得到，其中iter表示第iter轮迭代。计算迭代过程的ρi值，关键是确定ρ1的值。大多数聚
类算法以往的经验证明，前期迭代对聚类的影响大于后期的迭代。对于差分隐私，Dwork提
出每轮迭代消耗剩余隐私预算一半的隐私参数分配策略，则第i轮迭代的隐私预算为εi＝
i
ε/2 。在假设可能数据集之间等概率的情况下，差分隐私和差分可辨性之间存在一个映射
关系。当可能数据集m和ρ确定时，k原型算法也满足 ‑差分隐私。因此，第一轮的ρ1
可以通过 计算。对于后期迭代过程，为确保ρi>1/m，ρi将减小为保证
为实现ρ‑差分可辨性，后期迭代ρi的取值应为
因此，对于数值型子集Dr，每轮迭代的
对于分类型子集Dc，数值型和分类型数据的隐私
参数分别为 根据差分可辨性的并行组合性，n个
机制M1,...,Mn对于互不相交且独立的子集，提供(minρi)‑差分可辨性。当迭代总数为T时，
整个k原型算法满足的隐私保护水平为 满足ρ‑差分可辨
性。

[0080] 在差分可辨性k原型聚类算法中，迭代过程需要对数据点进行不断地调整聚类，会进行很多次聚类中心点的计算。对于混合型大数据集，聚类算法的处理效果并不理想，聚类
过程的时间复杂度很大，处理的效率也会降低。为改善混合型大数据聚类的效率，本发明实
施方案从并行计算角度出发，将k原型聚类算法在MapReduce并行计算框架中实现。

[0081] 从步骤6到步骤9，主要用于在MapReduce框架中实现差分可辨性k原型聚类算法得到最终结果。

[0082] 步骤6：划分数据集D1的每条数据记录至相应聚类。主任务Driver调用MapReduce中第二个子任务，进行差分可辨性k原型聚类。子任务执行Mapper类，设置Mapper类的setup
函数读取集合U中k个初始中心点u1,...,uk，读入事先定义的集合clustercenters中。map函
数读取接收到的每条数据记录xi，分别计算xi与k个初始中心点的距离Distance，得到与xi
距离值最小的聚类中心ui(1≤i≤k)，将记录xi划分到此聚类。将聚类标号i作为键值对的
key值，数据记录的各维属性值作为value，map函数输出(key,value)键值对。

[0083] 步骤7：计算新一轮聚类中心点。第二个子任务继续执行MapReduce中的Reducer类，接收键值对(key,value)，合并属于同一个key值的聚类。设置reduce函数，对于前dr维
的数值型数据，计算同一个聚类中数据数目之和numi和各维属性值之和sumi，对其添加
Laplace噪声可得到sumi'，计算sumi'/numi得到数值型数据的聚类中心 对于后dc维分类
型数据，计算每维属性的分类值出现次数，根据出现次数，使用指数机制选择并输出每维属
性的分类值，即为分类型数据的聚类中心 将 和 合并即可得到新一轮聚类中心点
集合ui'。

[0084] 步骤8：比较两轮聚类中心点。主任务Driver读取接收所述步骤7生成的聚类中心点集合和上轮(步骤6)的k个初始中心点集合，计算两轮聚类中心点集合间的距离Dis。若这
两轮中心点集合的距离Dis小于指定阈值Threshold或者迭代次数已经到达迭代总数值T，
则迭代终止，输出最终的聚类中心点集合U'。若不满足要求，继续重复步骤6～步骤8。

[0085] 步骤9：根据最终聚类中心点划分数据集D1。主任务Driver再次调用MapReduce中的Mapper类，设置map函数按照最终生成的聚类中心点集合对数据集D1进行聚类，将每条记
录xi划分至相应的聚类，数据记录的各维属性值作为键值对的key1，聚类标号作为键值对
的value1，map函数输出(key1,value1)键值对，即最终的聚类结果。

[0086] k原型聚类算法计算数据记录与中心点的距离时，采用的相异性度量是k原型距离，通过权重γ把平方欧氏距离和简单匹配距离结合在一起得到一个新的距离计算方式。
假设数据集D包含n个数据记录x1,x2,...xn，每条数据记录均有d维属性xi＝{xi1,xi2,...,
xid}，其中1≤i≤n。两个数据记录xi和xj之间的k原型距离的公式为：

[0087]

[0088] 其中， 表示数值型数据之间的相异性度量，dr为数值型数据的维数，采用平方欧氏距离进行计算。 表示分类型数据之间的相异性度量，dc为分类型数
据的维数，采用简单匹配距离计算，简单匹配距离δ(xil,xjl)为：

[0089] 权重γ的引入是为了避免相异性度量中过于偏向数值型数据或者分类型数据，从而导致聚类的效用降低。γ进行聚类前是未知的，可以通过多次实验确定最佳的权重γ。

[0090] 从上述步骤中可以看出MapReduce并行框架下实施本发明实施方案的聚类过程时，在每次迭代的reduce函数中对数值型数据添加服从Laplace分布的随机噪声计算数值
型的中心点，对分类型数据，使用指数机制选择分类型的中心点，从而满足保护个人隐私信
息的需求。聚类进行迭代时，每个Reduce任务并行地处理数据，计算满足差分可辨性的聚类
中心点，结果相当于差分可辨性的并行组合。根据并行组合性质，若第i轮迭代各个Reduce
任务计算中心点使用的隐私参数均为ρi，则第i轮迭代满足ρi‑差分可辨性。

[0091] 本发明说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。

[0092] 以上所述仅是本发明一种基于MapReduce的差分可辨性k原型聚类方法优选的实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明一种基于
MapReduce的差分可辨性k原型聚类方法原理的前提下，还可以做出若干改进和润饰，这些
改进和润饰也应视为本发明一种基于MapReduce的差分可辨性k原型聚类方法的保护范围。