下载文档原格式
K-匿名技术在无线传感器网络隐私保护中的应用丁媛媛【摘要】无线传感器网络是一种大规模的分布式网络,由于其部署环境的原因和传统的网络相比,其通讯安全存在较大的隐患,尤其是隐私保护问题.本文首先对全局K-匿名算法存在的问题进行了分析,在此基础上,提出了二次k-匿名算法,并进行描述,最后通过实验证明算法的有效性.%Wireless Sensor Network is a large-scale distributed network,because of its deployment environment,there is a big security risk of the communication,compare with the traditional networks,especially the privacy issues.In this paper,analysis the problem of global K-anonymity,on this basis,proposed a second k-anonymity algorithm,and described,and finally proved the effectiveness of the algorithm by experiments.【期刊名称】《内蒙古民族大学学报（自然科学版）》【年(卷),期】2011(026)006【总页数】3页(P650-652)【关键词】k-匿名;无线传感器网络【作者】丁媛媛【作者单位】烟台职业学院电教实验中心,山东烟台264000【正文语种】中文【中图分类】TP309.21 引言无线传感器网络（Wireless Sensor Network,WSN）〔1〕是作为一类规模宏大的分布式网络,通常部署在条件及其恶劣且无人看守的环境之中,在通常情况下，传感节点的使用均为一次性,这就要求传感节点是资源极度受限且价格低廉的无线通信设备.这使得无线传感器网络的安全受到了极为严峻的威胁.因此，为无线传感器网络打造一个较为安全的工作环境,是关系其“生死存亡”的重要问题.此外，在无线传感器网络中,对安全概念的理解也发生了变化,其中一个重要的组成成分是通信安全,因此隐私保护更显重要.2 K-匿名模型与算法描述2.1 全局K-匿名存在的问题全域泛化算法〔2〕就是在整个属性列上而进行的泛化.必须预先对准标识符的每个属性的泛化规则进行定义域泛化等级，整个域在每一步中所对应的域都必须给出全部泛化序列集，通过这个泛化序列集寻找对应值的泛化序列等级.K-匿名算法早期基本都是全域泛化算法，而全域泛化方法存在很大局限性.第一，全域泛化整个属性列操作是针对基本表的，泛化层次结构需要预定义，否则无法统一匿名数据，而对泛化等级的构造常常依赖用户对域知识的掌握情况，并且结果的有用性很难保证.第二，泛化等级会导致很高的信息损失，从而产生许多泛化的不必要，使得信息存在较大失真度.2.2 这个问题的解决方法通常可以采取这种方法解决上面的问题，也就是分块数据，分离一些容量比较大的簇和孤立簇，这两部分数据被分离开来，结果可以得到两部分数据，得到全局K-匿名的这两部分在所有泛化情况下是最优的.将这种方法叫被做二次K-匿名.2.3 衡量算法的性能这是对第一次K-匿名进行改进，度优先算法和OLA都是全局最优的.无论使用哪种算法，信息损失量都是相等的.而衡量算法的时候，要先对比二次匿名和一次匿名的信息损失量，然后分别在时间上对基于度优先和OLA生成的二次匿名算法进行比较.在对衡量信息损失量时，前面所提及的三种度量标准将被采用，也就是prec、基于熵和DM的度量信息损失的标准.2.4 选取算法中两个参数必须对算法中两个参数进行选择，一个是必须指定非孤立数据和孤立数据的分界值，另一个是抑制率.（1）抑制率〔3〕.必须使总抑制率在进行两次K-匿名后满足要求，即指定抑制率不小于两次匿名过程中对数据元组数目进行抑制处理后的总和比上总的数据元组数目.一个总抑制率给定后，第一次匿名需要指定一个抑制率，再根据总抑制率的源数据元组的总条数，可以求出第二次匿名的抑制率，求出抑制率后按照其进行第二次匿名，这样使得数据的总抑制率符合要求.第二个抑制率求法如下：Secondratio=（allratio-firstratio）/（1-firstsize/allsize）.其中，firstratio为第一次匿名的抑制率，allratio为总抑制率，allsize为数据总容量，firstsize孤立数据在第一次匿名后分离出来的数据容量〔4〕.（2）非孤立数据和孤立数据的分界值.在第一次匿名过后，将容量比较小但满足匿名的簇单独分离出来并作为孤立数据，所以，这里需要为非孤立数据和孤立数据的分界值指定一个参数，使用K的倍数来作为这个分界值的标准，例如：指定分界值为30，那么孤立数据就是所有容量小于30K的簇，进行二次K-匿名的簇都是容量大于30*K.2.5 二次K-匿名算法描述整个算法分为三个阶段，第一阶段在数据集上，运行度优先算法进行第一次K-匿名算法，在这一阶段中要保存必要的信息，第二阶段为分割数据，分别保存二次匿名数据和孤立数据；第三阶段对二次匿名数据进行第二次匿名算法.表1是算法所用到的函数列表.首先对整个数据集进行度优先算法，获取最小K-匿名节点的集合，将其保存在kmin中，然后对kmin中的每个节点（每个节点代表一种泛化情况）遍历，针对最小泛化各种情况，将数据依据参数threshold分割成两块，分别保存在seconddata和firstdata中，若判断seconddata中的数据容量为0，可跳过下面的程序而直接对下个节点进行计算.否则，就以当前节点和Lattice的最低结点建立参数的Lattice，同时对孤立数据进行信息损失量计算.再将计算出二次匿名的抑制率，运用第二次K-匿名算法对数据集seconddata上进行计算，获取最小K-匿名节点的集合，从而可以得到的K-匿名节点信息损失量最小并对第二次K-匿名的信息损失量进行计算.然后将两次信息损失量的结果相加后，与临时变量smallinfo相比，保存比smallinfo小的信息损失量.最后得到最小的信息损失量.因为此算法遍历了第一次K-匿名，最后获得全部最小K-匿名的节点，在第二次匿名又运用了最优K-匿名算法，得到全局最优的结果，所以，二次匿名算法可以算得上是最优算法.表1 二次K-匿名算法中用到的函数Table 1 The function used in Secondary K-anonymity algorithm函数的名称get_node(i)get_Info_Of(latticenode)get_cluster(j)add(ClusterInfo.get(j))Latti ce(Bnode,latticenode)info_loss(lattticenode,firstdata)Second_Ratio()Kmin(la ttice,secondratio,seconddata)Get_small_Lattice_node(latticenode.kmin)函数的功能描述取出最小K匿名节点集合中的第i个节点计算latticenode节点的簇信息，包括代表每个簇的节点信息和对应的容量取出第j簇的信息添加簇的信息建立新的lattice在数据集firstdata上计算节点latticenode的信息损失量计算二次K-匿名的抑制率在数据集seconddata上进行抑制率为secondratio的K-匿名计算（度优先算法）将最小K-匿名节点集合中信息损失量最小的节点找出来3 实验与分析比较在三个数据集上运用一次K-匿名和此算法分别得到的不同最优信息损失量，并且根据前面涉及的度量信息损失三种不同的标准.以下为实验结果：（分界值为15，总抑制率0.05，第一次匿名的抑制率为0.04，纵坐标为信息损失量，横坐标为K值，下同）需要指出的是，节点的信息损失量在计算过程中，三种度量机制均有不同实现的方法.在对信息损失量运用Prec度量机制计算时，可以一边对信息损失量进行计算，一边对编码后的源数据进行读取.因为计算的信息损失量只记录一个属性值的时候，只需要了解需要泛化这个属性高度和其所属于的泛化策略的总步数，而在进行节点信息损失量计算时，这两个值是已知的；而在运用DM*机制度量时，需要先统计簇的信息，然后必须将源数据读取完，才能够计算出结果，因为在运用DM*度量机制时，每簇数据的容量都需要被知道，然后求出平方和的结果；最后，在运用熵度量机制时，则需要额外的计算步骤.在未被泛化时候，需要对每个属性的频繁集进行统计.在泛化后，仍需要统计每个属性的全部频繁集，可以一边计算簇一边统计这两部分信息，在簇信息被统计完之后，运用两个频繁集计算log值方法获取熵值.图1 在adult数据集上度量信息损失量Figure 1 The metric information loss in the adult data set（1）使用Prec机制度量信息损失量（2）使用DM⋆机制度量信息损失量图2 在cup数据集上度量信息损失量Figure 2 The metric information loss in the cup data set（1）使用熵机制度量信息损失量（2）使用Prec机制量信息损失量图3 在cup数据集上度量信息损失量Figure 3 The metric information loss in the cup data set（1）使用DM⋆机制度量信息损失量（2）使用熵机制度量信息损失量4 结论经过K-匿名算法处理后，所得到的数据有比较大信息损失量，这是因为存在孤立数据，因此，提出了先将数据分块，再对数据进行二次匿名的方法.运用这种方法可以得到两块全局匿名的所有数据.从实验结果来看，这种方法使得信息损失量得到了改善.参考文献【相关文献】〔1〕李金才,吕艳丽,赵威,等.基于多维桶的K-匿名表增量更新算法〔J〕.燕山山大学学报,2009,（05）：23-27.〔2〕李金才,刘国华,郗君甫,等.一种满足最大隐私泄漏率要求的匿名方法〔J〕.燕山大学学报,2010,（03）：11-14.〔3〕宋金玲,刘国华,黄立明,等.k-匿名方法中相关视图集和准标识符的求解算法〔J〕.计算机研究与发展,2009,（01）：33-35.〔4〕杨高明,杨静,张健沛.隐私保护的数据发布研究〔J〕.计算机科学,2011,（09）：21-24.。
K匿名的隐私保护算法的初步学习一、L BS先看看什么是LBS。
LBS是基于位置的服务，它是通过电信移动运营商的无线电通讯网络（如GSM 网、CDMA网）或外部定位方式(如GPS)获取移动终端用户的位置信息（地理坐标，或大地坐标），在地理信息系统（外语缩写：GIS、外语全称：Geographic Information System）平台的支持下，为用户提供相应服务的一种增值业务。
（百度百科）LBS的作用是根据无线信号或有线网络对用户位置进行确定，并提供相应服务。
可以举几个例子：1.例如我在秦皇岛和太原因为上学和放假的原因而变换了上网环境，上网的IP(不管是静态动态IP还是拨号)，网上的天气预报会改变预报的城市，百度推送的广告（有关位置的）会相应改变，qq登陆会显示异地登陆等等。
2.打开手机地图类的APP，能够得到“我的位置”的信息，如果GPS是开着的，一般定位比较准确，否则可能有偏差，例如你在街道上，显示你的位置在附近一个建筑物里，通常是你连接了这栋楼的基站得到的反馈。
问题在于位置信息在LBS下容易泄露，对个人的隐私造成危害。
所以要对地址信息进行加密，最好的方法就是使用虚拟位置信息，但是虚拟位置信息的生成有一些问题，例如用于生产虚拟位置的服务器被控制，或者生成虚拟位置的规则不合适，生成的位置在山脉，湖泊，河流等等不符合逻辑的位置，可以被简单的规则过滤掉等。
二、K-匿名2.1 数据挖掘带来的挑战随着Internet技术、大容量存储技术和数据处理技术的迅猛发展以及数据共享范围的逐步扩大，数据的自动收集和发布越来越方便。
然而，在数据发布过程中隐私泄露问题也日益突出，因此实施隐私保护就显得尤为重要。
数据发布中隐私保护对象主要是用户敏感数据与个体身份之间的对应关系。
通常使用删除标识符的方式发布数据是无法真正阻止隐私泄露的，攻击者可以通过链接攻击获取个体的隐私数据。
我曾经学习了部分机器学习的算法，例如SVM，可以根据挖掘到一个人的信息，将每一个信息作为一个维度，在大量数据的情况下，可以学习出分割函数，建立超平面，从而进行分类，将其归入某一类人里。
基于K-匿名的隐私保护算法研究的开题报告一、研究背景和研究意义在数字化和信息化的时代，隐私保护成为了一个非常重要的问题。
人们对于个人隐私的保护需求越来越迫切，而在数据挖掘中，个体隐私泄露也成为了一个较大的问题。
因此，研究一种有效的隐私保护算法是非常必要的。
K-匿名算法是隐私保护的一种重要方法，它可以通过将有相同特征的数据聚合在一起，从而达到保护个体隐私的效果。
K-匿名算法的核心就是要使得同一个组内至少有k个不同的记录，从而保证数据隐私性。
因此，本研究将以K-匿名算法为研究重点，探索一种更加有效的隐私保护方法。
本研究的意义在于：一方面，对于隐私保护算法的研究具有重要的实际意义，可以为实际应用提供指导；另一方面，对于k匿名算法的研究也有一定的学术意义，可以为数据挖掘领域提供新思路。
二、研究内容及方法1.研究内容本文将主要研究基于K-匿名算法的隐私保护方法，具体包括以下方面：（1）K-匿名算法的原理和特点；（2）基于K-匿名的隐私保护算法设计，包括分类算法、聚类算法和数据扰动算法等；（3）算法性能分析，包括隐私保护效果、时间复杂度和空间复杂度等。
2.研究方法本研究将采用以下方法：（1）文献查阅法：对国内外关于隐私保护和K-匿名算法的相关研究进行综述和分析；（2）实验仿真法：通过在真实数据集上使用K-匿名方法进行隐私保护，并分析其效果和性能；（3）评估分析法：基于实验数据和分析结果，对算法性能和隐私保护效果进行评估分析。
三、研究预期目标本研究的预期目标如下：（1）深刻理解K-匿名算法的原理和特点；（2）设计一种更加有效的基于K-匿名算法的隐私保护方法；（3）在真实数据集上进行实验仿真，验证所提出方法的有效性和可行性。
四、研究进度安排本研究的进度安排如下：第一阶段：文献综述和分析（1个月）1）查阅国内外相关文献，对K-匿名算法和隐私保护算法进行综述和分析；2）总结已有相关研究存在的问题和不足，并提出研究问题。
K-匿名隐私保护相关技术的研究【摘要】在数据发布领域，k-匿名技术是一种简单有效的隐私数据保护技术。
因此国内外专家学者们对匿名化技术开展了广泛深入的研究工作以寻求防止或减少隐私泄露的有效方法。
本文根据已有的一些研究结论，阐述了匿名化技术的一般概念、匿名化原则、匿名化方法和匿名化度量等方面，并且介绍了两种经典的匿名化算法。
【关键词】数据发布；匿名化技术；k-匿名1.引言计算机处理能力、存储技术及网络技术的快速发展，信息技术在组织中发挥的作用日益增加，一方面，使得信息共享较之以前来得更为容易和方便，以数据库为基础的应用系统成为经济、金融、医疗等领域的信息基础设施，大大地提高了组织的信息化程度；但是另一方面，这也使得数据库系统面对更多的安全威胁，随之产生的隐私信息泄露现象屡见不鲜，越来越多的因故意或疏忽造成的数据泄露的例子，使人们对数据库中的隐私保护问题日益重视。
信息化过程中如何在实现有效的信息共享的同时，有效地保护私有敏感信息不被泄漏，已成为信息安全领域一个活跃的研究方向。
Cox在1980年最先提出使用匿名的方法实现隐私保护，1986年Dalenius在针对人口普查记录集的隐私保护应用了匿名技术。
自从匿名化概念提出以来，很多国内外的学者对匿名化技术开展了广泛的研究。
例如L.Sweeney提出了一种用来保护私有信息的k-匿名模型[1]。
Ji-Won Byun，Ashish Kamra，Elisa Bertino，and Ninghui Li在2007年提出了基于聚类的高效k-匿名话算法[2]。
在这篇文章中提出，k-匿名问题不需要有簇的数量的限制，但是每个簇中至少含有k条记录，所以，提出可以把k-匿名问题当作聚类问题，被称为k-member clustering problem。
现在生活中，人们都很注重隐私保护，尤其像是在医院和银行这种场合，大多数人可能并不愿意让别人知道自己的具体情况，所以怎样既可以做到不泄漏个人的隐私，又可以利用医院和银行中的个人信息做科学研究，这种问题正是我们研究匿名发布信息的重要意义所在。
摘要：随着移动计算技术和无线设备的蓬勃发展，位置服务中的隐私保护成为了研究热点。
传统的k-匿名方法存在查询结果不精确的缺点，尤其是在用户稀少的场景下，将产生较大的匿名区域，从而增大通信开销。
为了平衡服务质量和隐私保护之间的矛盾，依据将匿名区域分裂成几个分散的子匿名区域，提出一种新的划分子匿名区域的方法，该方法将不产生连续的匿名区域而是直接划分出n个子匿名区域，并随机选择一个子匿名区域代替真实用户的位置向lbs服务器发起查询。
实验结果表明，该方法能更加有效地保护用户的隐私，并且能够提高服务质量，减少通信开支。
关键词：位置服务；隐私保护；k-匿名；服务质量；匿名区域1 引言随着无线技术和移动位置技术的不断发展开拓了新的研究领域基于位置的服务（location based services， lbs），如查询基于当前位置的感兴趣点，此类服务是基于k 近邻（k nearest neighbors， knn）查询，即查询距离用户最近的k个可能目标。
例如查询离我最近的工商银行、距离我25米内最近的饭店/加油站等，相应的，用户在提出此类查询的时候将不得不把自己的精确位置包含在查询中发送给服务提供商，换句话说，就是用户用隐私来换取服务。
恶意攻击者通过获取用户的位置信息再结合已有的背景知识，推测出用户的身份信息、健康状况、宗教、爱好等，从而造成隐私泄露。
实际上，享受服务与隐私保护是一对矛盾体，近年来许多研究者致力于在高效的位置服务和位置隐私保护之间寻求一个平衡点，即在最少暴露用户位置的前提下，获得最好的位置服务，让暴露的位置处于可控状态。
k-匿名是隐私保护方法中最常规的一种，其基本的做法是牺牲服务质量来换取隐私保护。
但是k-匿名也存在一些问题，例如在用户稀少的场景下，为了满足k值，可能会出现很大的匿名区域，这时候服务的准确率会急剧下降。
针对上面提出的问题，本文采用将整个匿名区域划分为n个子匿名区域，并且提出了一种新的划分子匿名区域的方案，该方案可以更好地保护用户的位置隐私，并且能够提高服务的准确率。
大数据背景下的K—匿名隐私保护机制研究作者：张毅荣来源：《农村经济与科技》2017年第04期[摘要]面对大数据时代的来临，大数据分析所带来的隐私泄露问题日益严重，而在数据采集隐私保护，数据分析隐私保护，数据可信销毁等方面中，数据发布的隐私泄露问题最为直观和突出。
而伴随着大数据时代的到来，传统意义上的隐私保护难以起到应有的作用，大数据发布的隐私保护也就应运而生。
本文针对K-匿名隐私保护机制展开，从K-匿名模型和各种算法模型出发，研究其可行性与优缺点，并对该机制的发展方向进行阐述。
[关键词]K-匿名；隐私保护；大数据[中图分类号]TP309 [文献标识码]A当下，我们处在一个数据爆炸的时代，每年的可采集数据以几何形式递增。
在2011年全球的数据储量就达到了1.8ZB，如果让每个美国人每分钟写3条Twitter信息，我们将需要写2.6976万年，才能达到这一数据。
在2015年，这个数字增长到了8.61ZB，并在今后十年中，用于存储数据的全球服务器总量还将增长十倍之多。
其中政府，媒体，医疗机构，游戏公司，社交软件，个人等都会产生和发布大量的数据，经过大数据分析和挖掘，不经意中就会有隐私泄露，引发严重问题，隐私的保护技术也就显得尤为重要了，Samarati和L.Sweeney提出的K-匿名模型作为经典的大数据发布时的保护技术。
1 K-匿名模型和方式1.1 K-匿名模型思想K-匿名模型主旨是使用一定的方法切断数据集中的标识属性和敏感属性之间一对一，或者一对多的联系，预防链接攻击，以取得保护数据隐私不被窃取的技术手段。
该模型要求发布者对于发布信息中的每一条数据至少有K条与其拥有相同的标识属性，满足这一条件的数据集则称为K-匿名模型表1中学号属性可以独一无二地对应出某位同学，因此为标识属性。
表1中的联系方式和病情当事人往往不愿让他人得知，故为敏感属性。
虽然校医室在发布时故意隐去了学生的姓名，但如果有人在同时大数据采集得到了该学校发布的学生花名册表2，就很容易通过属性{学号，性别}上的链接，知道具体同学的联系方式与病情，该操作即为链接攻击。
K匿名的隐私保护算法的初步学习
一、L BS
先看看什么是LBS。
LBS是基于位置的服务，它是通过电信移动运营商的无线电通讯网络（如GSM 网、CDMA网）或外部定位方式(如GPS)获取移动终端用户的位置信息（地理坐标，或大地坐标），在地理信息系统（外语缩写：GIS、外语全称：Geographic Information System）平台的支持下，为用户提供相应服务的一种增值业务。
（百度百科）
LBS的作用是根据无线信号或有线网络对用户位置进行确定，并提供相应服务。
可以举几个例子：
1.例如我在秦皇岛和太原因为上学和放假的原因而变换了上网环境，上网的
IP(不管是静态动态IP还是拨号)，网上的天气预报会改变预报的城市，百度推送的广告（有关位置的）会相应改变，qq登陆会显示异地登陆等等。
2.打开手机地图类的APP，能够得到“我的位置”的信息，如果GPS是开着
的，一般定位比较准确，否则可能有偏差，例如你在街道上，显示你的位置在附近一个建筑物里，通常是你连接了这栋楼的基站得到的反馈。
问题在于位置信息在LBS下容易泄露，对个人的隐私造成危害。
所以要对地址信息进行加密，最好的方法就是使用虚拟位置信息，但是虚拟位置信息的生成有一些问题，例如用于生产虚拟位置的服务器被控制，或者生成虚拟位置的规则不合适，生成的位置在山脉，湖泊，河流等等不符合逻辑的位置，可以被简单的规则过滤掉等。
二、K-匿名
2.1 数据挖掘带来的挑战
随着Internet技术、大容量存储技术和数据处理技术的迅猛发展以及数据共享范围的逐步扩大，数据的自动收集和发布越来越方便。
然而，在数据发布过程中隐私泄露问题也日益突出，因此实施隐私保护就显得尤为重要。
数据发布中隐私保护对象主要是用户敏感数据与个体身份之间的对应关系。
通常使用删除标识符的方式发布数据是无法真正阻止隐私泄露的，攻击者可以通过链接攻击获取个体的隐私数据。
我曾经学习了部分机器学习的算法，例如SVM，可以根据挖掘到一个人的信息，将每一个信息作为一个维度，在大量数据的情况下，可以学习出分割函数，建立超平面，从而进行分类，将其归入某一类人里。
同时在有丰富的个人信息（多维度）和大量数据作为全局信息，可以用CRF进行行为预测。
如果是针对性的，可能通过链式攻击来获取个人的敏感信息。
链式攻击：攻击者通过对发布的数据和其他渠道获取的外部数据进行链接操作，以推理出隐私数据，从而造成隐私泄露，相当于一种个人信息维度的扩充。
最简单的例子就是数据库里两张表通过主键关联，得到更多的信息。
2.2 k -匿名的引入
为解决链接攻击所导致的隐私泄露问题，引入k -匿名(k-anonymity) 方法。
k -匿名通过概括和隐匿技术，发布精度较低的数据，使得每条记录至少与数据表中其他k－1 条记录具有完全相同的准标识符属性值，从而减少链接
攻击所导致的隐私泄露。
攻击所导致的隐私泄露。
我从网上找了一张k匿名化的截图：
可以看到名字被隐藏，生日和zip也并非匿名化。
匿名分为抑制和泛化。
抑制，即彻底隐藏信息，如上图姓名。
泛化，如将中国人，韩国人统一为亚洲人，上面的生日和zip也是泛化。
2.3 聚类k -匿名算法
算法的基本思想是将k -匿名问题视为聚类问题，将数据对象分成若干类或簇，使同一簇中的对象之间关于已定义的相似性标准具有很高的相似度，而不同簇中的对象之间高度相异。
1.k 成员聚类问题
传统的聚类过程要求指定具体的簇数目，然而，k -匿名问题并不限制簇的数目，而是要求每个簇至少包含k条记录。
因此，可以将k -匿名问题视为聚类问题，通常称为k 成员聚类问题。
定义1（k成员聚类问题）k成员聚类问题是将包含n条记录的集合划分成一系列簇，使得每个簇至少包含k条记录，并且要求簇内间距总和最小。
形式地，令S为包含n条记录的集合，k为具体的匿名化参数，则k成员聚类问题的最优解是产生满足以下条件的簇的集合E={e1，e2,… ,e m}：
其中，|e|表示簇e的大小，p(l,i)表示簇e1中的第i 个数据点（将记录视为数据点），D(x,y) 表示数据点x和y之间的距离。
2.距离和代价度量
聚类问题的核心是定义距离函数用以度量数据点间的相似性，定义代价函数以使聚类问题代价最小化。
距离函数通常由数据点的数据类型（如数值型或分类型）决定,而代价函数则由聚类问题的具体目标来定义。
由于k -匿名问题所涉及的数据中可能既包含数值型属性,又包含有分类型属性,因此,需要定义∈能够处理不同类型数据的距离函数。
以下描述适用于k -匿名问题的距离和代价函数。
定义2（数值型数据间的距离）令D为有限数值域，任意
数值v i,v j∈D间的标准距离定义为：
其中| D |表示域 D 的最大值与最小值之间的差值
定义3（分类型数据间的距离）令D为分类域，T D为D上的分类树，任意分类值v i,v j∈D间的标准距离定义为：
其中，Λ(x,y) 代表分类树中以x和y的最小公共祖先为根的子树，H(T) 表示分类树T的高度。
结合数值域和分类域上的距离函数，来定义两记录间的距离如下。
定义4（记录间的距离）令Q T={N1,N2,…,N m,C1,C2,…,C n}为数据表T的准标识符,其中N i(i=1,2, ... ,m)为数值型属性，C j(j=1,2,…,n)为分类型属性，则任意记录r1,r2∈T间的距离定义为：
其中r i[A] 表示记录r i的属性A的值。
既然k成员聚类问题的最终目标是实现发布数据的k-匿名，构造代价函数来表示泛化处理所产生的数据扭曲程度。
由于每个簇中的记录被泛化成相同的准标识符值，假定数值型数据泛化成区间[最小值，最大值]，分类型数据泛化成不同属性值的集合。
定义5（信息损失）令e={r1,r2,…,r k} 是一个簇（等价类），其准标识符包含数值型属性N1,N2,…,N m和分类型属性C1,C2,…,C n, T C为分类型属性C i域的分
类树,MIN N
i 和MAX N
i
分别为簇e中数值型属性N i的最小值和最大值，C i表示簇 e
中分类型属性C i不同属性值的集合，对簇e进行泛化处理所产生的信息损失IL(e) 定义为：
其中| e | 表示簇e中的记录数，| N i |表示数值域N i 的最大值与最小值之差，Λ(C i)表示分类树中以C i内所有值的最小公共祖先为根的子树，H(T)表示分类树T的高度。
基于上述定义，匿名化数据表的总信息损失定义如下。
定义6（总计信息损失）令E为匿名表AT 的等价类的集合，则AT的总信息损失定义为：
Total-IL(AT)=∑IL(e)
e∈E
由于k成员聚类问题的代价函数是所有簇内距离总和，其中簇内距离定义为簇内最远数据点间的距离，于是，对簇内记录进行泛化处理时，最小化信息损失就等同于k 成员聚类问题中最小化代价函数，因此，聚类处理时需最小化的代价函数即为Total-IL 。
3.k成员聚类算法
输入数据集S和匿名参数k
输出簇的集合result，其中每个簇至少包含k条记录
1.如果数据集中记录个数小于k,则返回；
2.令簇集result= ϕ ；
3.从数据集S中随机选取一条记录r；
4.当数据集S的记录个数不小于k时，循环执行：
（1）从数据集S中随机选取一条记录r；
（2）S=S－{r}；
（3）c={r}；
（4）当簇c中记录个数小于k时，循环执行：
a. 从数据集S中选取记录r，使其加入簇c产生的信息损失最小；
b. S=S－{r}；
c. c=c{r}；
（5）result=result{c}；
5.当数据集S中有剩余记录时,循环执行：
（1）从数据集S中随机选取一条记录r；
（2）S=S－{r}；
（3）从簇集result中选取簇c,使r加入其中后产生的信息损失最小；
（4）c=c{r}；
6.返回簇集result
三、总结
我这次学习的是通过将k-匿名问题转化为k成员聚类问题的k-匿名算法，相对与简单的贪心策略时间开销增大，但是信息损失减小。
结合我以前的聚类的学习，对k匿名有了一个初步了解。
至于根据熵来决定匿名策略的还有在学习，而且侧重于位置信息，学习完后再发。
