K匿名的隐私保护算法的初步学习.doc

K匿名的隐私保护算法的初步学习LBS先看看什么是LBS。LBS是基于位置的服务，它是通过电信移动运营商的无线电通讯网络（如GSM网、CDMA网）或外部定位方式(如GPS)获取移动终端用户的位置信息（地理坐标，或大地坐标），在地理信息系统（外语缩写：GIS、外语全称：GeographicInformationSystem）平台的支持下，为用户提供相应服务的一种增值业务。（百度百科）LBS的作用是根据无线信号或有线网络对用户位置进行确定，并提供相应服务。可以举几个例子：例如我在秦皇岛和太原因为上学和放假的原因而变换了上网环境，上网的IP(不管是静态动态IP还是拨号)，网上的天气预报会改变预报的城市，百度推送的广告（有关位置的）会相应改变，qq登陆会显示异地登陆等等。打开手机地图类的APP，能够得到“我的位置”的信息，如果GPS是开着的，一般定位比较准确，否则可能有偏差，例如你在街道上，显示你的位置在附近一个建筑物里，通常是你连接了这栋楼的基站得到的反馈。问题在于位置信息在LBS下容易泄露，对个人的隐私造成危害。所以要对地址信息进行加密，最好的方法就是使用虚拟位置信息，但是虚拟位置信息的生成有一些问题，例如用于生产虚拟位置的服务器被控制，或者生成虚拟位置的规则不合适，生成的位置在山脉，湖泊，河流等等不符合逻辑的位置，可以被简单的规则过滤掉等。K-匿名2.1数据挖掘带来的挑战随着Internet技术、大容量存储技术和数据处理技术的迅猛发展以及数据共享范围的逐步扩大，数据的自动收集和发布越来越方便。然而，在数据发布过程中隐私泄露问题也日益突出，因此实施隐私保护就显得尤为重要。数据发布中隐私保护对象主要是用户敏感数据与个体身份之间的对应关系。通常使用删除标识符的方式发布数据是无法真正阻止隐私泄露的，攻击者可以通过链接攻击获取个体的隐私数据。我曾经学习了部分机器学习的算法，例如SVM，可以根据挖掘到一个人的信息，将每一个信息作为一个维度，在大量数据的情况下，可以学习出分割函数，建立超平面，从而进行分类，将其归入某一类人里。同时在有丰富的个人信息（多维度）和大量数据作为全局信息，可以用CRF进行行为预测。如果是针对性的，可能通过链式攻击来获取个人的敏感信息。链式攻击：攻击者通过对发布的数据和其他渠道获取的外部数据进行链接操作，以推理出隐私数据，从而造成隐私泄露，相当于一种个人信息维度的扩充。最简单的例子就是数据库里两张表通过主键关联，得到更多的信息。2.2k-匿名的引入为解决链接攻击所导致的隐私泄露问题，引入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,…,em}：其中，e表示簇e的大小，p(l,i)表示簇e1中的第i个数据点（将记录视为数据点），D(x,y)表示数据点x和y之间的距离。2.距离和代价度量聚类问题的核心是定义距离函数用以度量数据点间的相似性，定义代价函数以使聚类问题代价最小化。距离函数通常由数据点的数据类型（如数值型或分类型）决定,而代价函数则由聚类问题的具体目标来定义。由于k-匿名问题所涉及的数据中可能既包含数值型属性,又包含有分类型属性,因此,需要定义∈能够处理不同类型数据的距离函数。以下描述适用于k-匿名问题的距离和代价函数。定义2（数值型数据间的距离）令D为有限数值域，任意数值vi,vj∈D间的标准距离定义为：其中|D|表示域D的最大值与最小值之间的差值定义3（分类型数据间的距离）令D为分类域，TD为D上的分类树，任意分类值vi,vj∈D间的标准距离定义为：其中，Λ(x,y)代表分类树中以x和y的最小公共祖先为根的子树，H(T)表示分类树T的高度。