丁永红



基于聚类分析的数据流隐私保护算法

丁永红

（淮南联合大学，安徽淮南 232001）

由于数据流具有无限、流动迅速、变化频繁的特点，因此，在进行对其隐私保护时存在很大的困难．针对数据流的隐私保护，文章首先分析了数据流匿名隐私保护的特点，然后进行算法的实施，及实验结果和分析．

聚类；数据流；隐私；保护算法；匿名

1 数据流的匿名隐私保护

社会经济快速发展导致数据存储的爆炸式增长，时常会造成隐私泄露，甚至更严重后果[1]．为了防止信息被泄露而将一些敏感信息匿名隐藏起来，从而形成新的数据流，但是要确保数据的不变性和可用性，就不能单单地对敏感数据进行隐藏和删除，只能进行一定意义和一定程度上的修改．对于数据匿名流的定义有许多种，大致分为以下几个：（设原始数据为，输出的新的数据流为，且新数据流中元组的输出时延不超过δ）

定义1：匿名数据流，设数据流的属性序列为(pid,a,a,…,a,q,q,…,q,ts)，其中pid为用户身份标识，q,q,…,q为准标识符属性，a,a,…,a为其他属性，为元组到达时刻，为由生成的匿名数据流，其中属性id和被隐去，映射,若满足：

1）对任意t∈,存在与对应；

2）对任意，|DP(EQ)|≥,EP=·q·q,i=1,…,n},DP(EQ)为EQ（t'）中元组对应的pid属性不同的用户组成的集合，则称为匿名数据流．

定义2：时延约束，设有数据流匿名方法，若输出的匿名数据流，满足任意为原数据流中与对应的元组，为给定正整数，则称满足时延约束．

定义3：元组泛化．设元组t(pid,u,u,…,u,u,u,…u,ts的泛化为g,g,…,g)=(f(u),f(u),…,f(u)),则：

1）当q为数值型属性时，f(u)=[r,r],u∈[r,r]；

2）当q为分类型属性是，f(u)=H,H为与q对应的域泛化结构中u的上层节点．

定义4：簇泛化．设g(g,g,…,g)为簇的泛化，则：

1）q为数值性属性时，g=[r,r]r和r，分别为簇中所有元组在属性q上的最小值和最大值．

2）q为分类型属性时，g=H,H为簇中所有元组在属性q的DGH上节点的共同最低父节点．

定义5：匿名簇．若簇满足：

1）|DP(C)|≥,DP(C)为簇中元组对应的pid属性值不同的用户组成的集合；

2）任意=g,t'为匿名后数据流中与对应的元组，g为簇的泛化．则称簇为匿名簇

定义6：元组泛化信息损失．元组t(pid,u,u,…,u,u,u,…u,ts)泛化为g,g,…,g后的信息损失为：，．

当属性为数值型属性时，信息的损失为元组在该属性上泛化后区间[r,r]的长度与该属性值域[R,R]的比值；当属性值为分类型属性时，信息损失为元组在该属性上泛化后对应的节点．

定义7：簇泛化信息损失．簇泛化为g(g,g,…,g后的信息损失为：

定义8：数据流泛化平均信息损失．设g为元组t的泛化，则数据流在时刻t的平均信息损失为：

定义9：簇信息损失增量．簇在加入元组后产生的信息损失增量为：Enlargement(C,t)=Infoloss(C',gc')-Infoloss(C,gc)，其中：为增加元组之后的簇，表示为泛化后的簇．

2 基于聚类的数据流匿名算法

2.1 基本思想

数据流的匿名算法是一种很特殊的算法，而为了满足这种特殊的要求，提出了三个基本原则：其一，无限和快速到达是数据流的两个特点，而数据流的算法在进行计算时只对数据流扫描一遍，并且所需的时间要在一定范围内[2]；其二，由于数据流有无限的特点，算法空间复杂度以一个常数为上界，而与反应时间无关；其三，对于已发布的新的数据流要重复利用，降低因对信息匿名而产生的损失．

2.2 算法实现

根据FCADS对数据流匿名计算，在满足算法基本框架的基础上，能够对数据流进行匿名计算．首先输入数据流、属性集、匿名参数和发布时延以及信息损失下限；输出结果为满足匿名参数匿名要求的新数据流．

Set为待发布元组集，初始化为空集

Set为已发布匿名簇集，初始化为空集

While≠ do

从中读取一个元组加入Set

If |Set|≥then

Set=greedy Condense ( )

Output With Work Cluster Or Condensation

end

end while

if |Set|≥k then

Set=greedy Condense ( )

Output With Work Cluster Or Condensation (Set)

else

将Set中的所有元组抑制后输出，并从中删除已输出元组

end if

对于greedy Condense ( )函数则有下列程序

Set

While |Set|≥do

从Set中随机选择一个元组

计算剩余|Set|-1个元组与的距离，并按照距离从小到大排序，选出前-1个和的pid值不同的元组，与组成新簇

将C加入Set

从Set中删除C包含的元组

end while

if |Set|≥0 then

for each ti∈Setdo

在Set中查找加入t后信息损失的增量最小的簇

将t加入C

从Set中删除t

end foreach

end if

返回Set

对于output With Work Cluster Or Condensation ()的程序如下

Output With Work Cluster Or Condensation (Set)

for eachC∈Setdo

for eachtCdo

Set

在Set中查找所有覆盖t且簇信息损失增量最小的簇

将找到的簇添加到Set

ifSet≠then

从Set中随机选择一个簇C

If Infoloss(C)C) then

用C的泛化输出t

从C中删除t，并重新计算C的泛化

end if

end if

从Set中删除t

end foreach

If |C|≥k then

用C的泛化输出t

In Infoloss (C)

If |Set|≥cs/kthen

删除Set中最早生成的簇

end if

将C加入Set

end if

else

用C的泛化输出C中所有元组

end if

end for each

3 实验及结果分析

对于本文所用的算法的性能，可通过实验进行分析,并参与CASTLE算法的比较．在进行实验时，所采用的数据集是被隐私文献广受欢迎的UCI的Adult数据集．实验所选用的属性集合为中的一部分，且这些属性集合中的前6个和后4个分别为数值型属性和分类型属性．

当数据量和参数变化时，实验要记录变化所带来的平均信息损失和运行时间，对于平均信息损失，可以运用以下公式来计算：

为了弥补FAANST只能进行数值型数据的处理，而不能对算法的性能进行充分的测试，特设计两组实验：第一组实验用于对新算法和CASTLE算法的测试；第二组实验用于对新算法、CASTLE和FAANST算法的测试[3]．两组实验的属性都从以上给出的十个属性中选取，而第二组实验所用的属性值均为数值型属性．

首先进行第一组实验，其中各算法的参数如表1所示，c0取1.

表1 第一组实验的算法参数表

进行第一组实验，并将实验关于平均信息损失的结果以图表的形式表现出来，如图1所示．

（a）随数据流大小变化 （b）随值变化 （c）随δ值变化 （d）随属性数量变化

图1 CASTLE和FCADS在第一组实验中的平均信息损失

从图1中我们可知：当数据流的大小、值、δ值和属性的数量发生变化时，CASTLE算法的平均信息损失都普遍高于FCADS算法．由图1中（a）图可知，数据流大小对两种算法的平均信息损失的影响都很小，且数据流越大两种算法对平均信息损失的影响越趋于平缓．由图1中（b）图可知，值的变化对两种算法对平均信息损失的影响较大，且值越大，即元组越多，两种算法对平均信息损失的影响也就越大[4]．由图1中（c）图可知，δ值越大，两种算法对平均信息损失产生的影响越小，且最后趋于平缓，但前期的影响较大．由图1中（d）图可知，两种算法对平均信息损失量随属性的数量增多而增多．总的来说，从图1中可以知道，对于CASTLE和FCADS这两种算法对平均信息损失，值和值的影响很大．

对于第一组实验，关于运行时间的结果如图2所示：

（a）随数据流大小变化 （b）随值变化 （c）随δ值变化 （d）随属性数量变化

图2 CASTLE和FCADS在第一组实验的运行时间

由图2可知，当数据流大小、值、δ值和属性的数量发生变化时，CATLE的运行时间总比FCADS的运行时间长．由图2中（a）图可知，随着数据流的增长，CASTLE和FCADS的运行时间成正比例增长，且CASTLE受数据流影响较大．由图2中（b）图可知，当值较小时，值对CASTLE算法关于时间的影响较大，且成递增趋势，当值越大时，其变化越小，但总体是递增的；对于FCADS算法对运行时间来说，值是有上限的．由图2中（c）图可以看出δ值的变化对CASTLE的影响较大，且CASTLE算法的反应时间随δ值的增大而增大，FCADS几乎不受δ的影响．由图2中（d）所示，属性的数量几乎不影响FCADS算法的运行时间，但是对CASTLE算法的运行时间的影响比较大，且随着属性数量的增加，CASTLE算法的运行时间也在不断的增加．

进行第二组实验时，对FAANST和FCADS两种算法的参数取：=100，属性数量为6，δ=10 000，τ=0.5，c取1.则关于第二组实验中，两种算法对平均信息损失的影响如图3所示：

（a）随数据流大小变化 （b）随值变化 （c）随δ值变化 （d）随属性数量变化

图3 FAANST和FCADS在第二组实验中的平均信息损失

由图3可知：在数据流大小、值、值和属性的数量影响因素下，FAANST和FCADS两种算法的平均信息损失的影响相差较小，且平均信息损失随数据流的增加以及的增加而减少，随值的增加和属性数量的增加而增加．经两种算法的比较，FCADS算法对平均信息的损失影响相对FAANST算法而言要小．

通过图1与图3比较可得：在只有数值型的数据流中数据流的大小和值的变化对平局信息损失的影响与含有多种属性数据流的变化是相同的，在数据流大小和值方面，分类型数据比数值型数据更敏感．

在第二组实验中，关于FAANST和FCADS两种算法在运行时间上的影响如图4所示：

（a）随数据流大小变化 （b）随值变化 （c）随δ值变化 （d）随属性数量变化

图4 FAANSTA和FCADS在第二组实验中的运行时间

由图4可知：FAANSTA算法的运行时间普遍大于FCADS算法的运行时间，即FCADS算法的运行速度快于FAANSTA算法的运行速度，且数据流量越大，两种算法运行的速度差越大．FAANSTA和FCADS两种算法的运行时间随数据流、值和属性数量的值增大都增大，随值的增大都减小．通过图4和2比较可知：在只有数值型和混合型的数据流中，数据流大小和值对算法运行时间的影响是一致的．

做好隐私保护就要不断加强对数据流的保护．随着经济与科技的发展，隐私的泄露还存在着很大的隐患，因此要不断加强隐私的安全保护．

[1] 翟国富，陈金豹，邢通.基于聚类分析的航天继电器多余物检测方法研究[J].振动与冲击，2013（2）.

[2] 李征.基于动态膜计算的聚类算法[D].郑州：河南大学，2013.

[3] 彭显刚，赖家文，陈奕.基于聚类分析的客户用电模式智能识别方法[J].电力系统保护与控制，2014（19）.

[4] 罗养霞，房鼎益.基于聚类分析的软件胎记特征选择[J].电子学报，2013（12）.

（责任编辑：涂正文）

Data Stream Privacy Protection Algorithm Based on Clustering Analysis

DING Yonghong

with the development of economy and technology, privacy leakage has become a hidden danger which is badly in need of an effective protection. Because of the characteristics of data stream, such as limitlessness, rapid flow, and frequent changes, it is very difficult to prevent the leakage of privacy. This paper first analyzes the characteristics of anonymity privacy protection of the data stream, and then carries out the implementation of the algorithm, following with the experimental results and analysis.

clustering; data stream; privacy; protection algorithm; anonymity

TP311

A

1009-8135（2016）03-0033-05

2016-02-20

丁永红（1975-），男，安徽安庆人，安徽淮南联合大学计算机系讲师，主要研究计算机网络技术．

中国民航信息技术科研基地开放基金课题：基于函数依赖的民航大数据共享与隐私保护研究（编号：CAAC-ITRB-201404）阶段性成果