张岐山，郭 昆

（1.福州大学 管理学院，福建 福州 350108； 2.福州大学 数学与计算机科学学院 福建 福州 350108）

0 引言

在数据挖掘工具日益强大的同时，在挖掘过程中可能导致隐私泄漏的问题也日益引起人们关注.因此，在挖掘有效信息的同时保护用户隐私已经成为数据挖掘领域的重要研究课题[1］.在发布数据前，对其中敏感属性（或字段）进行匿名处理是保护隐私的重要方法.目前，在静态数据隐私保护方面已经有相关研究成果[2-9］，k匿名[10］、l多样性[11］、t接近度[12］、ε-微分隐私[13］等设计准则被广泛使用.泛化（Generalization）和抑制（Suppression）是2种常见的数据匿名化技术.

在现实生活中，大量数据实际上是不断变化更新的数据流，如企业销售记录、医疗机构就诊信息、社交网络亲友信息等.在提交数据流用于数据挖掘时，需要考虑隐私保护问题.与静态数据的隐私保护相比，在发布数据流时保护用户隐私面临更大挑战.由于数据流具有潜在无限、流动迅速、变化频繁等特点[11］，要求算法具有更低的时间和空间复杂度.

LiFF等提出一系列基于扰动的数据流匿名算法[14］，通过向原始数据添加随机噪声数据，使攻击者无法从扰动后的数据中提取原始数据包含的信息.CASTLE算法[15］将数据流的匿名化看做一个连续聚类过程.当元组的到达时间超过一个时延阈值时，它们将以连续的方式被发布.B-CASTLE算法[16］通过设置簇大小上限解决CASTLE算法生成不平衡簇的问题.

笔者提出一种基于灰关联分析的数据流匿名算法（DSAoGRA），采用灰色关联度描述元组间的相似度并结合聚类思想，将元组划分成k匿名簇，得到满足k匿名准则的隐私保护数据流.通过在真实数据集上与CASTLE算法的对比实验，表明新算法能够实现数据流的快速匿名化，并保证匿名后数据的高可用性.

1 数据流匿名

数据流匿名是将原始数据流S中的数据项进行泛化或抑制处理后，输出满足匿名要求的数据流S′，并保证S′中元组的输出时延不超过δ.

定义1 k匿名数据流.设数据流S的属性序列为AS＝（pid，a1，a2，…，am，q1，q2，…，qn，ts），其中pid为用户身份标识，q1，q2，…，qn为准标识符属性（quasi-identifier（QI），指能够联合额外获得的信息唯一确认用户身份的属性[10］），a1，a2，…，am为其他属性，ts为元组到达时刻，S′为由S 生成的匿名数据流，其中属性id和ts被隐去，映射f：S→S′，若S′满足：

定义2 时延约束.设有数据流k匿名方法F，若F输出的k匿名数据流S′满足∀t′∈S′，t′.ts-t.ts＜δ，t为原数据流S中与t′对应的元组，δ为给定正整数，则称F满足时延约束δ.

（1）当qi为数值型属性时，

（2）当qi为分类型属性时，为与qi对应的域泛化结构（Domain Generalization Hierarchy（DGH））中vqi的上层结点.

定义4 k匿名簇.若簇C中的元组具有至少k个独立的pid值，则称簇C为满足k匿名要求的簇.

首先，计算元组在每个QI上的信息损失：当QI为数值型属性时，信息损失为元组在该QI上泛化后区间[rli，rui］的长度与该QI的值域[Rli，Rui］的比值；当QI为分类型属性时，信息损失为元组在该QI上泛化后对应的结点Hi所覆盖的叶子结点数｜Hi｜与该QI的DGH的所有叶子结点数｜DGHi｜的比值，结点Hi所覆盖的叶子结点指DGH中以Hi为根的子树的叶子结点.然后，再求所有QI信息损失的均值作为元组泛化后的信息损失.

定义6 簇泛化信息损失.簇C泛化为gc（g1，g2，…，gn）后的信息损失为

定义7 数据流泛化平均信息损失.设gi为元组ti的泛化，则数据流S在时刻tp的平均信息损失为

定义8 灰关联度.设X 为灰关联因子集，X＝｛Xi｜Xi＝（xi（1），xi（2），…，xi（n）），i∈N｝，N＝｛0，1，…，m｝，m≥2，K＝｛1，2，…，n｝，n≥3，X0∈X 为参考序列，Xi∈X 为比较序列.若存在一个非负实数γ（x0（k），xi（k））为X 上一定环境下的比较测度，且令非负实数

则当其满足规范性、偶对称性、整体性、接近性时，称γ（x0（k），xi（k））为Xi对X0在第k点的灰关联系数，为

2 灰关联分析

称γ（X0，Xi）为Xi对X0的灰关联度[19］.

定义9 灰关联密度.设γi＝（γ（x0（k），xi（k）））为第i个比较序列的灰关联系数序列，C 为灰关联系数序列集，C＝｛γi｜i∈N｝，则称映射

为灰关联系数分布映射，映射值v（x0（k），xi（k））为第i个比较序列在第k点的灰关联密度值.此比较序列灰关联密度值的全体构成灰关联密度序列，记为vi.

定义10 灰关联熵.设V＝｛vi｜i∈N｝，V为灰关联密度序列集，则称函数

当然，腊味饭中最有年味的做法，当属腊味八宝饭。八宝饭多是甜味糯米饭，所谓八宝指的是杏仁、梅子、葡萄干之类的甜食。然而，咸味的腊味八宝饭，更能勾人食欲。八宝并不一定是八种食材，只是取其丰盛吉祥之意。腊味八宝饭主要采用干货杂粮，寓意是五谷丰登，团圆富贵。

为第i个比较序列的灰关联熵.

定义11 熵关联度.设I（vi）为第i个比较序列的灰关联熵，Im为灰关联系数序列的最大关联熵，则称

为第i个比较序列的熵关联度.

定义12 均衡接近度.设γ（X0，Xi）和E（X0，Xi）分别为第i个比较序列的灰关联度和熵关联度，则称

为第i个比较序列的均衡接近度.

由于均衡接近度既考虑灰关联因子序列间点的距离接近性，又考虑整体的无差异性接近，因此可以克服点关联强倾向问题.

3 数据流匿名算法

数据流匿名化的核心是将数据流中的元组划分成k匿名簇，同一k匿名簇元组采用相同的泛化形式输出.因此，选择合适的描述元组相似度的测度对生成的k匿名簇质量有重要影响.利用灰关联分析中的均衡接近度能够从宏观上描述元组间的无差异性接近的特点，可以得到具有较高内聚的k匿名簇，从而使匿名后的数据具有较高的可用性.

3.1 算法思想

模拟数据聚类过程，通过不断从数据流中提取相似元组生成k匿名簇，并在δ时间内输出簇实现数据流的匿名化.已输出的k匿名簇存储于k匿名簇集.后续元组输出时可以选择直接采用k匿名簇集中的元组泛化输出，以减小信息损失.

为了实现数据流的匿名化，从时间上考虑，需要约束k匿名簇集大小不超过限值Cs，使查找覆盖待发布元组t的k匿名簇的时间从O（｜S｜）减小为O（Cs），使算法具有线性时间复杂度.设计Cs的表达式为Cs与δ成正比，δ值越大需要及时发布的元组越多，从而需要较大的k匿名簇集.k值越大新生成的k匿名簇越少，从而可以减小k匿名簇集的大小.c0≥1.0，为倍率系数，用于调整二者之间的比例.从空间上考虑，由于k匿名簇集的大小不超过O（Cs），算法用于存储k匿名簇簇的空间大小也不超过O（Cs），因此算法具有常量空间复杂度.

数据流匿名在实现匿名要求的同时还需要保持较小的信息损失.采用基于差异信息的均衡接近度描述元组间的相似度，一方面可以克服部分属性值对相似度占绝对影响的问题；另一方面也符合从信息量角度描述元组相似度以减小信息损失的要求.因此，算法中元组相似度采用均衡接近度描述.将这种算法称为基于灰关联的数据流匿名算法，记为DSAoGRA（Data Stream Anony mization based on Grey Relational Analysis）.

3.2 算法实现

数据流匿名算法DSAo GRA的实现过程：

在到达发布时限时，DSAoGRA算法先调用函数greedy Condense（）将Settp中的元组划分成簇，再调用过程output With Work Cluster Or Condensation（）决定如何输出新创建的簇中的元组.函数greedy Condense（）的实现过程：

函数greedy Condense（）首先从Settp中随机选择一个元组t，找出其k-1个pid值不同的近邻.然后将元组t与其k-1个近邻聚合成新簇Cnew，并将Cnew加入簇集Setc.这个过程不断迭代进行，直至Settp中的剩余元组少于k个为止.剩余元组依次分配到加入该元组后信息损失增量最小的簇.步骤（4）中的距离采用基于差异信息理论的均衡接近度计算.最后返回Setc.过程output With Work Cluster Or Condensation（）的实现过程：

对Setc中的每个元组ti，过程output With Work Cluster Or Condensation（）先在Setwc中查找所有覆盖ti且簇信息损失增量最小的簇.如果存在这样的簇，则继续将其信息损失与ti所属簇Ci的信息损失作比较，从中选择信息损失较小的簇，用其泛化输出ti，否则用Ci的泛化输出ti.若ti使用Setwc中簇的泛化输出，则将其从Ci中删除，不再参加后续判断.因此，当内层foreach循环结束时，由函数greedy Condense（）创建的簇内的元组可能减少.这是步骤（15）需要判断｜Ci｜≥k的原因.在过程output With Work Cluster Or-Condensation（）中，每个元组在输出前不但查找k匿名簇集，还查找元组自身划分生成的簇，扩大选择的范围，因此能够得到更低的信息损失.由于过程output With Work Cluster Or Condensation（）包含双重循环，运行时间将增加.

4 实验结果分析

通过实验对DSAoGRA算法的性能进行分析，并将其与CASTLE算法进行比较.实验采用的数据集是在隐私保护文献中广泛使用的UCI的Adult数据集[20］.在删除信息不完整的元组后，实际用于实验的数据集包含3.016 2×104个元组.实验采用的QI集合从属性集合｛age，final-weight，education-number，capital-gain，capital-loss，hours-per-week，education，marital-status，occupation，nation｝中选取.前6个为数值型属性，后4个为分类型属性.对分类型属性采用与文献[5］相同的DGH.所有算法采用Java语言实现.实验的硬件配置为Intel Core2Duo 1.66GHz CPU，2 048MB RAM，软件配置为Microsoft Windows XP SP2，JDK 6.0.

比较算法在数据量变化和参数变化条件下的平均信息损失和运行时间.信息损失根据信息损失相关公式计算.各个算法的参数见表1，c0取为1.0.

表1 实验算法参数

4.1 平均信息损失

CASTLE和DSAoGRA算法的平均信息损失见图1.由图1可以看出，在所有实验结果中DSAoGRA算法的平均信息损失均低于CASTLE算法的.CASTLE算法的分割操作虽然通过为元组重新分配距离最近的簇（距离基于信息损失计算），但是这种分配只发生在单个簇中.DSAoGRA算法是在整个k匿名簇集（Setwc）范围内为元组选择最接近的簇，从而能够获得更低的信息损失.此外，DSAoGRA算法采用均衡接近度计算元组相似性，也使得其能够进一步降低泛化信息损失.

图1（a）表明，随着数据量的增加，平均信息损失总体呈逐渐减小趋势，但变化较缓慢.

图1（b）表明，k值对算法的平均信息损失有显著影响.较大的k值要求一个k匿名簇需要包含较多的元组，才能满足匿名要求.因此，随着k值的增大，算法的平均信息损失增加较快.

图1（c）表明，时延约束δ对算法性能也有较大影响.δ值越大，平均信息损失越小.随着δ值的增大，算法能够从更多的元组中产生簇，从而有更大的概率得到相对紧凑的簇.

图1（d）表明，算法的平均信息损失随QI数量的增加而增大，因为QI越多，由QI泛化导致的平均信息损失也越大.

图1 CASTLE和DSAoGRA算法的平均信息损失

4.2 运行时间

CASTLE和DSAoGRA算法的运行时间见图2.由图2可以看出，在所有实验结果中DSAoGRA算法的运行时间显著少于CASTLE算法的.CASTLE算法的时间复杂度实际与数据流大小的平方成正比，并且其采用的合并和分割操作较耗时.DSAoGRA算法对k匿名簇集大小设置上限，使其时间复杂度下降为与数据流大小的线性函数.此外，为了加快匿名处理速度，DSAoGRA算法舍弃合并和分割操作.使DSAoGRA算法具有更快的运行速度，且随着数据量的增加，其差别也越来越明显.

图2（a）表明，算法的运行时间随数据量的增大而增加.随着元组的不断到达，k匿名簇集不断扩大，为新元组选择泛化信息损失最小的k匿名簇所需要的时间也同步增加.

图2（b）表明，参数k对算法运行时间的影响不大.虽然各个算法的时间复杂度与数据流大小和k有关，但是k值要远小于数据流大小，因此相对于数据流大小的变化，算法的运行时间受k值变化影响较小.CASTLE算法的运行时间随k值的增大而增加，时间复杂度不仅与数据流大小有关，还与其采用的分割操作的执行时间有关.k值越大，算法生成的簇越大，分割操作也就越频繁.

图2（c）表明，运行时间随参数δ的增大而增加.δ值越大，元组缓冲区中需要一次性处理的元组也就越多，从而增加算法的运行时间.

图2（d）表明，算法运行时间与QI数量成正比，但CASTLE算法的运行时间增加较显著，DSAoGRA算法的运行时间对QI数量较不敏感.

图2 CASTLE和DSAoGRA算法的运行时间

5 结论

针对数据流环境下的隐私保护问题，首先定义数据流匿名和灰关联分析的基本概念；然后讨论基于聚类的数据流匿名方法的设计思想，并给出一种基于灰关联分析的数据流匿名算法（DSAoGRA）；最后通过在真实数据集上的对比实验，验证DSAoGRA算法能够在快速实现数据流匿名的同时保持数据的高可用性.未来可在提供更强的隐私保护水平及提高算法性能等方面开展研究.

[1]Nergiz M E，Clifton C.Thoughts on k-anonymization[C］.Data ＆ Knowledge Engineering，2007，63（3）：622-645.

[2]LeFevre K，DeWitt D J，Ramarkrishnan R.Incognito：efficient full-domain k-anonymity[C］.Proceedings of the 2005ACM SIGMOD International Conference on Management of Data（SIGMOD＇05）.Baltimore：ACM，2005：49-60.

[3]LeFevre K，DeWitt D J，Rama krishnan R.Mondrian multidimensional k-anonymity[C］.Proceedings of the 22nd International Conference on Data Engineering（ICDE＇06）.Hong Kong：IEEE Computer Society，2006：25-25.

[4]Bayardo R J，Agrawal R.Data privacy through optimal k-anonymization[C］.Proceedings of the 21st International Conference on Data Engineering（ICDE＇05）.Houston：IEEE Computer Society，2005：217-228.

[5]Fung B C M，Wang K，Yu P S.Top-Down specialization for information and privacy preservation[C］.Proceedings of the 21st International Conference on Data Engineering（ICDE＇05）.Tokyo：IEEE Computer Society，2005：205-216.

[6]Xiao X，Tao Y.Anatomy：simple and effective privacy preservation[C］.Proceedings of the 32nd International Conference on Very Large Database（VLDB＇06）.Seoul：VLDB Endowment，2006：139-150.

[7]Iyengar V S.Transforming data to satisfy privacy constraints[C］.Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining（KDD＇02）.Edmonton：ACM，2002：279-279.

[8]Li T，Li N.Towards optimal k-anony mization[J］.Data ＆ Knowledge Engineering，2008，65（1）：22-39.

[9]Fung B C M，Wang K，Wang L，et al.Privacy-preserving data publishing for cluster analysis[C］.Data ＆ Knowledge Engineering，2009，68（6）：552-575.

[10]Sweeney L.k-anonymity：a model for protecting privacy[C］.International Journal on Uncertainty，Fuzziness and Knowledge-based Systems，2002，10（5）：557-570.

[11]Machanavajjhala A，Kifer D，Gehrke J，et al.l-diversity：privacy beyond k-anonymity[J］.ACM Transactions on Knowledge Discovery from Data，2007，1（1）：1-52.

[12]Li N，Li T，Venkatasubramanian S.t-closeness：privacy beyond k-anonymity and l-diversity[C］.Proceedings of the 23rd International Conference on Data Engineering，2007（ICDE＇07）.Istanbul：IEEE Computer Society，2007：106-115.

[13]Dwork C，Lei J.Differential privacy[C］.Proceedings of the 33rd International Colloquium on Automata，Languages and Programming，part II（ICALP＇06）.Venice：Springer-Verlag，2006：1-12.

[14]Li F F，Sun J，Papadimitriou S，et al.Hiding in the crowd：privacy preservation on evolving streams through correlation tracking[C］.Proceedings of the 23rd International Conference on Data Engineering（ICDE＇07）.Istanbul：IEEE Computer Society，2007：686-695.

[15]Cao J，Caminati B，Ferrari E，et al.CASTLE：continuously anonymizing data streams[C］.IEEE Transactions on Dependable and Secure Computing，2011，8（3）：337-352.

[16]Wang P，Lu J，Zhao L，et al.B-CASTLE：an efficient publishing algorithm for k-anonymizing data streams[C］.Proceedings of the 2010 2nd WRI Global Congress on Intelligent Systems.Wuhan：IEEE Computer Society，2010.132-136.

[17]邓聚龙.灰理论基础[M］.武汉：华中科技大学出版社，2002.

[18]张岐山.灰朦胧集的差异信息理论[M］.北京：石油工业出版社，2002.

[19]刘思峰，谢乃明.灰色系统理论及其应用[M］.北京：科学出版社，2008.

[20]Frank A，Asuncion A.UCI machine learning repository[EB／OL］.http：／／archive.ics.uci.edu／ml，2010.