基于黑洞算法的k-匿名化方法

沙特国王大学学报KAB：一种新的基于黑洞算法的LyndaKacha，Abdelhailla Zitounia，Mahieddine Djoudiba阿尔及利亚君士坦丁第二大学LIRE实验室b法国普瓦捷大学TechnNE实验室阿提奇莱因福奥文章历史记录：2021年1月21日收到2021年4月21日修订2021年4月27日接受在线预订2021年关键词：隐私匿名化K-匿名聚类黑洞算法A B S T R A C TK-匿名是微数据隐私保护中应用最广泛的一种方法，它主要基于泛化。基于推广的k-匿名方法虽然能够达到隐私保护的目的，但存在信息丢失的问题。基于匿名化的方法已经成功地适用于k-匿名化，因为它们提高了数据质量，然而，找到最佳解决方案的计算复杂性已被证明是NP难的。自然启发的优化算法在寻找复杂问题的解决方案方面是有效的。在本文中，我们提出了一种新的算法的基础上，一个简单的自然启发式的元启发式称为黑洞算法（BHA），以解决这些限制。在真实数据集上的实验表明，与k-匿名、基于BHA的k-匿名和基于聚类的k-匿名方法相比，该方法提高了数据的利用率.版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍隐私保护是发布包含敏感信息的数据时的主要关注点之一。在这种情况下，被称为微观数据的数据由关系表组成，其中每行由根据表的属性描述个人的基本信息组成。因此，在表示个体的表中，我们可以找到四组不同的属性（显式标识符1，准标识符2，敏感属性和非敏感属性）（Ciriani等人，2006年）。众所周知的技术，以隐私保护微数据是匿名化。匿名化是隐藏用户身份以保护其敏感信息的过程。一个简单的做法是删除显式标识符，如名称或地址。然而，这还不够，事实上，数据主 体 仍 然 可 以 重 新 识 别 。 简 单 匿 名 化 的 弱 点 被 L.Sweeney in（Sweeney，2002），并由Y.A. de Montjoye等人在（DeMontjoye等人，2015年）。通过连接两个公共数据源（马萨诸塞州雇员的匿名医疗保险数据集和选民登记列表），L。斯威尼成功指认威廉*通讯作者：LIRE实验室，新信息技术和通信学院电子邮件地址：lyndakacha@yahoo.fr（L. Kacha），Abdelhausi.univ-constantine2.dz（A. Zitouni），mahieddine. univ-poitiers.fr（M. Djoudi）。1可以唯一识别个人的属性2不能单独识别个体但与其他外部数据相结合的属性可以重新识别个体韦尔德，前马萨诸塞州州长 这种攻击称为“链接攻击”，如图所示。1 .一、为了克服这个问题，提出了更复杂的匿名化方法。K-anonymity（Sweeney，2002）就是其中之一。它是文献中提出的第一个模型，并且仍然是微数据隐私保护中最常用的模型。它要求表中的每个记录不能在至少k-1个其他记录中区分。在这种方法中，原始表的记录首先被分成几组，称为等价类。然后，每个组的记录被泛化，以共享相同的准标识符值。因此，很难在群体中识别个体，因为同一群体中的所有个体都是相似的。这个想法与集群非常相似。基于这个定义，k-匿名可以被看作是一个聚类问题，其目标是找到一组k-记录的聚类。每个等价类可以被认为是一个集群和质心作为一种形式的推广的等价类。基于加密的k-匿名方法具有良好的数据效用，因为它们将相似的记录分组在一起。虽然基于k-匿名的聚类的思想在概念上很简单，但找到最佳k-匿名解决方案的计算复杂度是NP-难的（Meyerson 和Williams ，2004）。在这种情况下，已经做出了很大的努力来开发能够支持最佳解决方案的详尽搜索的方法，即，其具有尽可能小的信息损失然而，他们中的大多数失败，并遭受坏的数据质量。使用自然启发式算法来解决NP难问题是众所周知的，并且在许多领域都非常有效https://doi.org/10.1016/j.jksuci.2021.04.0141319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comL. Kacha，A.Zitouni和M.Djoudi Journal of King Saud University2.1. 基于聚类方法的Fig. 1. 链接攻击以重新识别数据（Sweeny，2002）。但其在隐私和匿名领域的应用却很少被探索。自然启发式算法是一种受自然启发的近似优化方法，用于解决精确方法失败或需要不可接受或昂贵的计算时间时的困难问题。它们基于随机机制来探索研究空间，以找到或接近全局最优值（Talbi，2009）。在本文中，我们提出了一种基于简单元启发式的新方法，称为黑洞算法（BHA）（Hatamlou，2013）。我们之所以选择这种元启发式算法，是因为它的简单性和减少的参数数量; BHA具有简单的结构，易于实现。它没有参数设置问题，归结为[0-1]中的随机数。此外，BHA尚未应用于隐私领域，也从未适用于匿名化过程。BHA是受黑洞现象启发的基于种群的算法。黑洞现象是当一颗大质量恒星形成时形成的空间区域。它的引力是如此强大，以至于任何靠近它的物体，包括光，都会永远消失在宇宙中。将BHA应用于k-匿名化问题，用星表示k-匿名解，用黑洞表示最优解。 该算法从随机生成的候选解的初始种群开始。 它的目标是基于这个群体找到最优的k-匿名解决方案，即，其具有最小的信息损失。由于我们的目标是解决基于聚类的k-匿名的局限性，我们认为BHA的初始人口作为一组基于聚类的k-匿名的解决方案生成的聚类算法。为了提高数据质量，聚类算法应该将相似的记录（相对于准标识符）放在同一组中，每组至少包含k个记录。 相似性是基于作为距离和成本度量的信息损失来计算的。 这确保了需要较少的失真来匿名化集群中的记录，从而提高了数据质量。本文的其余部分组织如下。下一节调查有关工作的k-匿名为基础的方法。我们的算法在第3节中介绍，并在第4节中进行实验我们在第5节结束本文。2. 相关工作K-匿名模型在过去的几年里引起了人们的极大兴趣已经提出了许多用于k-匿名化及其变体的方法Ciriani等人实现了对各种k-匿名化方法的调查（Ciriani等人， 2006年）。由于我们的方法是基于自然启发的优化算法和聚类算法的k-匿名方法，因此我们在本节中描述了文献中提出的基于这两个概念的k-匿名方法。表1总结了这些方法。4076Li et al.（2006）提出了一种基于属性层次聚类的K-匿名化（K-Anonymization by Clustering in Attribute Hierarchies，KACA）算法，通过局部记录实现k-匿名。KACA算法的出发点是基于排序数据集创建的一组等价类。该算法首先随机选择一个大小小于k的等价类C。然后，它计算C与所有其他等价类之间的距离，并找到与C距离最小的等价类C最后，对两个等价类C和C这个过程一直持续到每个等价类包含至少k条记录。Chiu和Tsai（Chiu和Tsai，2007）采用加权特征C均值聚类算法进行k-匿名化，并提出了一种称为（WF-C-means）的算法。所提出的算法首先计算等价类的数量（C），使得C =无元组/k值，并选择C个随机记录作为种子。然后，该算法分配给每个准标识符的权重。下一步是等价类的形成，通过将所有记录分配给它们各自最接近的等价类（即，最接近的种子），并更新特征权重以最小化信息损失。此步骤迭代，直到对聚类的记录影响停止变化。最后一步包括合并小等价类（包含少于k个记录）与大等价类，以满足k-匿名的约束。Byun等人（Byun等人，2007）提出了另一种基于k-匿名的聚类，称为k-成员聚类。该算法首先构建一个集群。该算法随机选取一个记录r作为种子，将k-1个最近的记录迭代地添加到该记录上，然后选取一个距离r最远的新记录，重复相同的过程构建下一个簇。如果存在任何未签名的记录，则算法将这些记录单独分配给它们各自最接近的聚类。当所有记录都被分配给集群时，该过程结束。Loukides和Shao（Loukides and Shao，2007）提出了另一种贪婪k-匿名化算法。像k-成员算法（Byun等人，2007），该算法通过随机选择种子开始。然而，他们在建筑群上有所不同在该算法中，通过迭代地将最接近的种子元组添加到聚类中直到达到用户定义的阈值来形成聚类如果簇中的记录数小于k，则删除该簇。Lin和Wei（Lin and Wei，2008）提出了一种两阶段算法，称为一次通过K-means算法（OKA），用于实现基于聚类的k-匿名。OKA首先定义数据库记录上的准识别属性的度量空间，然后将其视为该空间中的点。然后，在第一阶段中，使用k-means算法对点进行分区，但仅用于第一次迭代，在大小>= k的组的集合中。在第二阶段，调整簇的大小，以确保每个簇包含不少于k个记录。通过将记录从具有多于k个记录的聚类移动到具有少于k个记录的聚类来完成调整。Lin等人（Lin等人，2008）提出了一种混合算法，其结合了OKA（Lin和Wei，2008）和k成员算法（Byun等人， 2007年，被称为混合方法。第一步使用OKA算法生成部分信息损失较小的聚类，第二步使用k成员算法生成其余信息损失波动较小的聚类。Aggarwal等人（Aggarwal等人，2010）提出了一种基于聚类的分层属性结构中实现k-匿名的算法。该算法的基本思想是找到一个大小小于k的任意等价类，并将其与最接近的等价类合并，形成一个具有最小失真的更大等价类。这个过程递归地重复，直到每个等价类包含至少k个元组。表1K-匿名方法概述论文该方法比较方法比较的参数比较指标测试数据集仿真结果基于网络的K-Li等人，2006K-聚类分析Incognito（LeFevre等人，（2005年）无QID = 3.. . 8.执行时间成人（UCI）.更好的失真比匿名Chiu和Tsai，2007年基于属性层次的加权特征C均值聚类算法.单链接聚类（Jain等人，一九九九年）. 完全链接聚类（Jain等人，一九九九年）.平均链接聚类（Jain等人，一九九九年）. 失真比k=2.. . 十六岁执行时间. 失真比.分类错误率（CER）.葡萄酒（UCI）.虹膜（UCI）.动物园（UCI）.更差的执行时间.更好的失真比.更好的CER为葡萄酒和动物园数据集。Iris数据集.要好的计算效率Byun等人， 2007年贪婪k成员聚类算法（K-成员CM）. Mondrian（LeFevre等人，（2006年）. k= 2.. . 500. no tuple = 1 k.. . 30K.执行时间.总信息丢失（总IL）.区分度度量（DM）.分类指标（CM）成人（UCI）。 总IL、DM和CM更.更差的执行时间Loukides和Shao，2007年贪婪k-匿名化算法. Mondrian（LeFevre等人，（2006年）. K-成员（Byun等人，（2007年）. k= 10.. . 120. no tuple = 50.. .1k.执行时间. 有用性. 保护.区分度度量（DM）. 成人（UCI）.合成（IBM研究）.更好的保护.对成人数据集的有用性更好-对合成数据集的.执行时间介于两个比较算法. DM比MondrianLin和Wei，2008年，单遍K均值算法（OKA）. K-成员（Byun等人，（2007年）k=50.. . 五百块执行时间.总信息丢失（总IL）成人（UCI）。 更好的总IL.更好的执行时间Lin等人， 2008混合算法（OKA + K-成员）. K-成员（Byun等人，（2007年）. OKA（Lin和Wei，2008）k=50.. . 五百块执行时间.总信息丢失（总IL）成人（UCI）。 更好的总IL.执行时间介于两个比较算法Aggarwal等人（二零一零年）用于匿名化数据记录的方法无实验He等人， 2012年基于分类的推广算法（CB）.非齐次推广（Wong et al.，（2010年）. k= 50.. . 250. 没有元组= 10 k.0.50 k. 无QID = 3.. . 6.执行时间.全球违约金（GCP）. SAL（千磅）.收入（伊普姆斯）.更好的GCP.更差的执行时间Pramanik等人，2016改进的k-匿名算法（KOC）. K-means（Jagannathan和Wright，2005）. k= 20.. . 250.无QID = 3.. . 8.执行时间.失真比成人（UCI）。 更好的GCP.更差的执行时间Aghdam和Sonehara，2016年基于相似性的聚类算法（SBCA）. Mondrian（LeFevre等人，（2006年）.数据飞（Sweeney，1998年）. Incognito（LeFevre等人，（2005年）. k=2.. . 100总标准化违约金（总NCP）. 成人（UCI）.互联网服务提供商（ISP）总NCPBhaladhare和Jinwala，2016年a.方法#1：QI-SA的不平等组合. 方法2：QID-SA的等量组合. K-成员（Byun等人，（2007年）.系统聚类算法（Kabir等人，（2011年）. k=20.. . 一百执行时间.总信息丢失（总IL）成人（UCI）。更好的总IL为两个建议的方法。方法#2的总IL.两种方法Ni等人， 2017基于集群K-匿名（串行GCCG并行GCCG）. KACA（Li等人，（2006年）. Incognito（LeFevre等人，（2005年）. k=3.. . 10个。执行时间. 信息损失成人（UCI）。 更好的IL.串行GCCG的执行时间介于两种算法之间Zheng等人，2018改进的K-匿名性算法（IKA）. Mondrian（LeFevre等人，（2006年）. K-成员（Byun等人，（2007年）. OKA（Lin和Wei，2008）. k = 100.. . 500.无元组= 5 k.0.30 k全球违约金（GCP）成人（UCI）更好的GCP（接下页）L. Kacha，A.Zitouni和M.朱迪沙特国王大学学报4077表1（续）论文该方法比较方法相比比较指标测试数据集仿真结果参数Arava和Lingamgunta，2019年自适应k-Anxiety方法（AKA）. 混合算法（Lin等人，（2008年）. KOC（Pramanik等人，（ 2016年）. k = 100.. . 500.执行时间.总信息丢失（总IL）成人（UCI）.更好的总IL.更好的执行时间Guo等人，2019基于自然等价类的k-匿名. K-成员（Byun等人，（2007年）. OKA（Lin和Wei，2008）. 基于NEC的OKA. 基于NEC的K-成员. k= 2.. . 100. no tuple = 5 k..总.无QID = 1.. . 8.执行时间.全球违约金（GCP）成人（UCI）.基于NEC的K-成员的平均GCP和执行. 更好的GCP和执行时间基于NEC的OKA，而非OKAYan等人，2021加权K元聚类. K-成员（Byun等人，（2007年）. k= 2.. . 50.执行时间成人（UCI）平均. 更好的集群内算法（WKMCA）. OKA（Lin和Wei，2008）. IKA（Zheng等人， 2018年）.总信息丢失（总IL）.平均内部/内部聚类相异性.标准差（SD）K-成员和OKA的差异性、SD和总IL的差异性大于IKA，而与IKA的差异性接近。. 等簇间相异度平均而言，元启发式-Lunacek等人，新的交叉算子.传统交叉遗传算法人口收敛速度成人（UCI）算法.执行时间比k-成员/IKA更好，比OKA更更快的收敛速度，基于k-匿名2006Lin和Wei，2009年基于遗传算法的k-匿名基于遗传算法的杂种.新交叉.混合算法（Lin等人，尺寸= 200.. . 1k. K = 100.. . 500. 总信息损失成人（UCI）求解质量更好的总ILRun等人，2012算法（GA）基于遗传算法的（2008年）. 基于遗传算法的混合算法.基于遗传算法的k-匿名K= 3.. . 15（总IL）.可辨别性度量皮马印第安人更好的ILM和DM，Bhaladhare和算法和禁忌搜索算法（GA-TS）部分结石-细菌. 基于TS的k-匿名. Mondrian（LeFevre等人，. K= 20.. . 100（德国马克）.信息丢失度量（ILM）.执行时间糖尿病. 成人（UCI）情况.更好的总ILJinwala，2016 aWai等人，2017觅食优化（FC-BFO）分层粒子群算法（2006年）.希尔伯特空间填充（Moon等人，（2001年）. K-成员（Byun等人，（2007年）.系统聚类（Kabir等人，2011）. BFO算法（Das等人，2009）/.无迭代= 5.. . 20. K = 5-.总信息丢失（总IL）.执行时间. 大学（UCI）成人（UCI）.执行时间比Hilbert算法差，优于其余比较算法/马丹和相似数据聚类的优化龙粒子群. K-Anxiety（Fung等人，. 没有迭代= 300.. . 10 K. K=2.. . 3. ILoss.总信息丢失（IL）成人（UCI）更好的IL和CAGoswami，2018马丹和优化（Dragon-PSO）重复-发散-差异（2007年）. K-Diversity（EliabethandSarju，2015）.基于遗传算法的k-匿名.基于蜻蜓算法的k-匿名. 基于遗传算法的K-Anxiety.无群集= 2.. . 5. 人口.分类准确度（CA）.总信息丢失成人（UCI）.更好的总ILGoswami，2019年a性能使能龙遗传算法. 基于遗传算法的K分集. 基于遗传算法的k-DDDsize = 4.. . 16.无迭代= 5.. . 20（总IL）.分类准确度（CA）.从更好到相等L. Kacha，A.Zitouni和M.朱迪沙特国王大学学报4078L. Kacha，A.Zitouni和M.朱迪沙特国王大学学报4079He et al.（He et al.，2012）提出了一种基于聚类的k-匿名算法。该算法是一个迭代过程。在每一轮，数据集被划分为两个子集G1和G2的基础上归一化的不确定性惩罚（NCP）作为距离测量。如果一个子集的大小小于k，假设G1<为k，则通过借用K来调整两个子集的大小。|G1|从G2中提取元组，以确保G1的基数大于或等于k。调整继续，直到每个子集包含至少k个元组。Pramanik等人（Pramanik等人，2016）提出了一种聚类方法来实现称为KOC的k-匿名。该算法从计算每个记录的n个最近邻居开始，并按降序对记录进行排序。然后创建p个聚类（p =无元组/k值）并选择排名最高的记录（即，具有最N最近的记录）作为初始质心。剩余的（没有元组-p）记录被分配到它们最接近的质心，使得每个集群都应该满足k-匿名属性。如果创建的最后一个簇包含少于k条记录，则其记录被分散到其他最近的簇。最后，聚类被单独匿名化。Aghdam和Sonehara（Aghdam和Sonehara，2016）提出了一种自下而上的贪婪算法，称为基于相似性的聚类算法（SBCA），通过本地记录泛化实现k-匿名，用于具有数值和分类属性的数据集，而没有分层分类树。SBCA首先对数据集进行排序，并将数值属性与分类属性分开。下一步是根据k值对数据集进行聚类和匿名化。为此，该算法选择排序数据集中的第一个元组，并将k-1个最近的元组添加到该元组中，形成一个聚类，该聚类通过本地记录进行匿名化。然后，属于聚类的元组从排序的数据集中删除。重复该过程，直到排序数据集中的总元组为零或小于k。其余元组被抑制或加入到最接近的等价类。Bhaladhare和Jinwala（Bhaladhare和Jinwala，2016年a）提出了两种基于系统聚类实现k-匿名的方法（方法1和方法2）。这两种方法都使用准标识符（QID）和敏感信息（SA）的组合将原始数据库分解成单独的子数据库，然后匿名化并发布生成的子数据库。两者之间的区别在于，方法#1创建QID和SA的不等组合，而方法#2创建QID和SA的相等组合。这两种方法首先计算簇的数量，其等于（无元组/k值），然后使用QID和SA的组合生成子数据库在方法#1中，创建QID和SA的不相等在方法#2中，创建QID和SA的相等组合从每个生成的子数据库中，创建将所有记录划分为k个组的分区 然后系统聚类算法（Kabir等人， 2011）被应用于生成聚类。为此，从第一组中随机选择一个记录用于创建第一簇。从第一组中选择其他记录并将其添加到最接近的聚类中。类似地，通过从剩余的组中随机选择记录来创建剩余的集群，并且选择其他记录并将其添加到最接近的集群。如果某个簇超过k大小，则应将额外元素添加到相应的最接近簇中。Guo等人 （Guo等人， 2019）提出了一个新的概念，名为纳特-并基于此概念设计了一个k-匿名化算法。算法背后的思想在原始的微观数据中，即包括具有相同准标识符属性的所有记录。这些等价类称为自然等价类。NEC用于在匿名化过程之前执行聚类。该算法首先查找数据集中的所有NEC。它将每个大于k的NEC作为一个表1（续）论文该方法比较的参数. K= 2.. . 5.无群集= 2.. . 5比较方法比较指标测试数据集仿真结果Madan和Goswami，2019. K-Anxiety（Fung等人，（2007年）. K-Diversity（EliabethandSarju，2015）.基于遗传算法的k-匿名. Dragon-PSO. DDDG（Madan和Goswami，2019 a）基于灰狼优化-猫群优化的混合算法（GWO-CSO）.总信息丢失（总IL）.分类准确度（CA）成人（UCI）更好的总IL和CA，除了k = 3，其中Dragon-PSO的IL更好L. Kacha，A.Zitouni和M.朱迪沙特国王大学学报4080独立集群通过应用聚类算法（K-成员（Byun等人，2007）或OKA（Lin等人，2008年））。对于无法聚类的NEC，它们被分配到各自最近的聚类。最后一步是聚类的泛化。将NEC应用于K-成员/OKA，增强了原始方法的实用性和有效性。Ni等人（Ni等人，2017年）提出了一种基于聚类的K-匿名算法，称为GCCG，由四个步骤组成：分级，中心化，聚类和泛化。在分级和居中步骤中，记录根据每个记录的计算得分进行排序，然后选择前X个记录作为质心。第三步是通过将k-1个最近的记录添加到每个质心来形成聚类。在最后一步中，对记录进行归纳。为了提高GCCG算法的性能，提出了一种并行化的GCCG算法.Zheng等人（Zheng等人，2018）提出了一种基于聚类的K-匿名算法，该算法考虑了多维空间中准标识符组的总体分布。该算法首先随机选取一个记录r作为第一个聚类的质心，并将k-1个最近的记录添加到它，以形成第一个聚类。然后，该算法选择具有最大的记录之间的距离，其本身和第一个质心，并设置它的第二个质心。第i个质心是以相同的方式创建的，基于第i个记录与所有现有质心之间的距离。在每个质心创建步骤之后，算法将k-1个最近的记录添加到质心以形成聚类。在此过程结束时，创建的所有集群都包含k条记录。如果有未分组的记录。 该算法迭代剩余的记录并将每个记录插入到最接近的聚类中，即，与其质心的距离最小Arava and Lingamgunta（Arava and Lingamgunta，2019）提出了一种自适应k-匿名算法AKA。 它以科威特石油公司的系统方法为基础（Pramanik等人， 2016年，为寻找最佳的种子价值。AKA从计算聚类数p =无元组/k值开始。对于每个组中的所有记录，它计算与每个其他记录的k-接近度，并按降序对它们进行排序。然后，在每个组中设置具有最小和最大接近度的记录作为初始质心（即，2*p种子）并构建集群。剩余的（np元组-2p）记录被分配到它们最近的簇，这样每个簇应该有k个簇成员。附加记录（即，其大小不同于k）被重新组织并附加到它们最近的簇。对于大于k的簇，该算法生成最少为k条记录的新簇现有的聚类算法将被应用到其余的集群，与大小小于k，分布他们的记录。Yan等人（Yan等人，2021）提出了一种称为（WKMCA）的加权k成员聚类算法。所提出的算法是修改的k成员（Byun等人，2007）以减少离群值对聚类效果的影响。为此，WKMCA增加了一个加权阶段，其中分配了一系列加权指标来评估记录的离群值，以便于过滤出离群值。因此，k-成员是基于这些指标，以实现k-匿名。该算法分为三个阶段：加权阶段，分组阶段和调整阶段。在加权阶段，算法计算所有记录的ARscore （平均排名得分），并选择ARscore排名最高的b（b= 0.05* 无元组）个记录离群值单独存储，并在调整阶段重新插入到发布数据表中分组阶段是基于聚类的k-匿名阶段。它包括应用具有修改的距离和基于权重分数的信息损失的k-成员在这个阶段结束时，所有的集群都包含K条记录。在调整阶段，算法将剩余的记录和离群值插入到它们各自最接近的聚类中。2.2. 基于自然启发优化方法的Lunacek等人（Lunacek等人，2006）提出了一种新的交叉算子，并利用该交叉算子实现了一种基于遗传算法的k-匿名方法，以证明该交叉算子优于传统交叉算子。本文在不同的种群规模下，将新的交叉算子与传统的2点简化代理算子在每种情况下，新的交叉算子都能更快地收敛到更有效的解。Lin 和Wei （Lin and Wei ，2009 ）提出了一种基于遗传算法（GA）的聚类方法来实现k-匿名。在这种方法中，遗传算法的初始种群是基于（Lin和Wei，2008）中提出的混合方法由一个染色体编码的、包含不少于k个基因的种群的候选解，其中每个基因表示原始数据集中一个记录的索引。该算法只使用遗传算法的由于算法使用无法更改的原始记录索引，因此不执行突变Run等人（Run等人，2012）提出了一种基于禁忌搜索（TabuSearch，TS）和遗传算法（Genetic Algorithm，GA）的混合搜索方法来实现k-匿名。在该方法中，TS被嵌入到一个trans-functional GA执行的突变的作用。其目的是通过遗传算法实现多起点局部搜索，克服传统TS单起点“爬山”能力的局限性。所提出的算法从构造表示泛化策略的解空间格（域泛化层次）开始。遗传算法基于格点构造初始种群，通过禁忌搜索来寻找最优泛化策略。Bhaladhare和Jinwala（Bhaladhare和Jinwalab，2016）提出了一种基于分数阶微积分的细菌觅食优化算法，称为FC-BFO，以生成最佳聚类。FC-BFO的目标是提高BFO算法的优化能力和收敛速度（Das等人，2009）通过在其趋化步骤中对其应用FC的概念。由于分数阶导数具有固有的记忆能力，分数阶微积分的观点导致更平滑的变化和更长的记忆效应。有效地，FC-BFO呈现比BFO更好的信息丢失和执行时间。BC-BFO分为两个主要阶段：第一步是基于聚类算法生成初始种群，并评估每个解的目标函数和隐私因子。第二步是对生成的种群应用BFO算法，该算法包括基于分数阶微积分的改进趋化步骤、繁殖步骤和消除扩散步骤三个步骤。这些步骤用于在k-匿名数据库中生成聚类Wai and al.（Wai和al.，2017）提出了一种基于分层粒子群优化（HPSO）的大数据隐私保护方法。所提出的方法构建在MapReduceHadoop基础设施上，以解决大数据的可扩展性问题。它包括两个阶段：第一阶段是HPSO聚类。该算法创建一个MapReduce作业来生成预定义数量的中间聚类，由粒子表示，然后在每个集群上执行HPSO集群的MapReduce作业通过迭代地执行Map和Reduce步骤，直到每个粒子中的数据成员的数量超过k。在第二阶段中，将得到的聚类进行泛化，以转化为它们的匿名形式。映射步骤简单地将每个中间聚类的所有数据成员传递到其各自的Reduce步骤，该Reduce步骤执行HPSO聚类作业以产生k-匿名聚类。Madan和Goswami提出了两种混合优化算法来实现k-匿名，称为Dragon-PSO （ Madan 和 Goswami ， 2018 ） 和 GWO-CSO 方 法（Madan和Goswami，2019 a）。Dragon-PSO算法通过修改传统的粒子群算法，将Dragonfly算法（DA）和粒子群算法（PSO）L. Kacha，A.Zitouni和M.朱迪沙特国王大学学报4081N-我JjDjjDj用粒子群算法对DA的更新过程进行了研究更准确地说，所提出的Dragon-PSO算法的更新- 数字属性将两个原算法的更新GWO-CSO算法结合了灰狼优化算法（GWO）和猫群优化算法（CSO）。在GWO-CSO算法中，D. v;vNCP1/4。vi-vj。ð1Þ通过添加对应于CSO算法的更新的新项，使用修改的GWO更新来执行更新。Madan和Goswami（Madan和Goswami，2019 b）提出了一种基于K-DDD度量的数据发布匿名模型，基于Dragonfly算子的遗传算法，称为Duplicate-Divergence-DifferentpropertiesenabledDragonGenetic（DDDG）算法。第一步是基于所提出的k-DDD度量将原始数据库转换为k-DDD数据库，称为k-DDD匿名化。k-DDD措施通过在数据库的每个集群中创建'k'个重复记录，'k'个敏感属性中的分歧和'k'个不同服务提供者来修改原始数据库。第二步，在k-DDD数据库上应用D-Genetic算法。D-遗传算法是用蜻蜓算法（DA）对遗传算法（GA）进行改进而形成的。提出的D-遗传算法是一个迭代过程，包括六个阶段：（1）选择两个类作为父类，（2）应用交叉算子，（3）应用变异算子，（4）应用哪里|D|是D上所有元组的范围。也就是说，在整个桌子上。- 分类属性dC. vi;vjNCPC尺寸c2其中c是分类树中vi和vj的最接近的共同祖先，并且size（c）是c中的叶节点的数量。|D|是D上不同值的个数。- 记录间距离两个记录r1和r2之间的距离是两个记录中相应的数字和分类准标识符之间的距离之和。 LeQI<$fN1; ··· ;Nm;C1; ··· ;Cng t是数据集T的准标识符，其中Ni<$i<$1; ··· ;mn g t是数值属性，Cj<$j<$1; ··· ;ng t是分类属性。记录r1和r2之间的距离定义为：龙操作符和更新新位置的记录，（5）fit-mnness评价该过程在以下情况下终止：dRr1;r2NC PRXdNr1½Ni];r2½Ni]NXdC。r1½Cj];r2½Cj]迭代满足。一种基于在MapReduce框架下，提出了一种基于MapReduce的数据挖掘方法。1/1第1页基于聚类的方法提高了基于泛化的k-匿名化的数据质量，但是对最优聚类解决方案的穷举搜索可能是指数的。自然启发的优化方法满足这一限制，因为它们更适合探索大的搜索空间。因此，它们的极限在于它们的计算复杂性。在本文中，我们试图通过结合这两种方法来解决这些局限性。3. 该方法本节提出了一种新的基于黑洞算法的k-匿名化方法，称为基于黑洞算法的k-匿名化（简称KAB）。KAB算法从初始的星形种群开始具有最小的信息损失。由于该算法源于黑洞算法，种群向最优解的进化是通过将所有恒星移动到由黑洞表示的最优解来完成的3.1. 聚类算法我们的方法是基于一个聚类算法来创建candidate解决方案。每个解代表一个k-匿名聚类。为了获得良好的数据质量，聚类中的记录应该尽可能相似这确保了需要较少的失真来概括来自同一聚类的记录，从而导致良好的数据质量。为了达到这一目标，我们采用了标准化违约金（NCP）（Xu等人，2006）作为聚类算法的距离和成本度量。NCP是一种有效且易于使用的度量标准，用于衡量匿名化过程导致的信息丢失程度距离函数测量数据点之间的差异，通常由数据类型（数字或分类）确定。设D为一个数值的定义域/成本函数由聚类问题的目标定义。由于我们的目标是最小化信息损失，我们使用eq。（3）作为成本函数。聚类算法的伪代码总结在图中。 二、聚类算法首先计算聚类数N。聚类的数量是一个重要的标准，因为它对聚类的质量有影响。簇的数量越大，由于产生的小NCP值而导致的信息损失越小。这就是为什么我们选择了尽可能多的集群，即，M=k（其中M是数据集中记录的总数，k是k-匿名参数）。在计算N之后，算法运行聚类过程（步骤2-5）。首先，它随机选择一个记录并将其设置为质心。随机性确保所创建的解决方案，即，组成总体的候选解决方案是不同的。然后，迭代地选择具有最小NCP值的k-1个记录与质心形成聚类。该过程迭代，直到处理完所有记录。如果存在未分配的记录，则算法将它们中的每一个影响到其相应的最接近的聚类，即，在其质心和未分配记录之间涉及最小NCP的簇。3.2. 解编码在利用聚类算法创建候选解之后，它们必须被编码以便由优化算法使用，即，BHA。如前所述，种群由一组星组成，这些星对应于聚类算法创建的可行解为了正确地表示解决方案，在我们的方法中，每个星由一维的整数数组编码3，其大小等于数据集中的记录数，其中第i个索引指示第i个记录，第i个元素指示第i个记录所属的集群的ID。例如，假设X是由15个记录组成的候选解决方案，并在6个簇上分区。X= {（1，2），（3，5），（4，6，7），（8，9），（10，1,2，13），（11，14，15）}。X的编码解是X范畴属性任何两个值v之间的距离定义为3编码表示恒星NL. Kacha，A.Zitouni和M.朱迪沙特国王大学学报4082.ðÞ¼XPð Þ ð ÞX'=112323344565566群集ID123456789101112131415记录ID3.3. 适应度评估为了评估恒星的质量并选择黑洞，我们使用了基于隐私和效用参数 的 适 应 度 函 数 （ Madan and Goswami ， 2018 ） （ MadanandGoswami，2019 a）所使用的恒星X的适应度可以用下面的公式计算，算法1. 基于NCP的聚类算法1.计算聚类数等2.随机选择一个记录 来自数据集3.创建等价类 与4.查找最接近的记录基于等式（三）5.通过添加到Ci来形成群集6.重复2-5，直到所有记录都处理完毕7.如果没有受影响的记录，则将每个剩余记录分配给最近的第3集关于EQ （三）图二、基于NCP的聚类算法的伪代码算法2. 基于K-一致性的黑洞算法（KAB）健身X1最小值1/2×2privacy实用程序1.生成恒星的初始种群2.根据等式评估每颗星的适合度。(4)把最好的星星B孔隐私和效用度量表示如下，3.根据等式将所有星星移向b孔（10）并更新他们的健身4.如果一颗星到达了比b洞更好的位置，它就变成了b洞，反之亦然。pri v acy X0;如果X满足k-匿名性1;否则ð5Þ亦然5.如果一颗恒星太靠近b洞，就会产生一颗新的恒星来取代旧的恒星N实用型数控机床NCPai61/1其中ai是X的第i个簇。N是X的簇数。 NCPai是群集ai的NCP。NCPai由等式7计算，其中NCP record是a i中的记录的NCP 而jaij是簇ai的大小。NCPai ¼NC P记录ωjaij7给定，在匿名化过程之后，根据准标识符，集群的所有记录将是相似的，我们计算任何记录的NCP并将其乘以集群中的记录数jaij。NCP记录通过公式8计算，其中NCP属性j是记录中属性j的NCP，d是属性的数量D并对其适应度进行了评价6.如果满足最大迭代次数，则