您的浏览器Javascript被禁用,需开启后体验完整功能, 请单击此处查询如何开启
网页 资讯 视频 图片 知道 贴吧 采购 地图 文库 |

数据挖掘的隐私保护研究_IT/计算机_专业资料

1956人阅读|134次下载

数据挖掘的隐私保护研究_IT/计算机_专业资料。数据挖掘领域的隐私保护策略,讲解还算清晰。


2010 年第 10 期 (总第 134 期) 大 众 科 技 DA ZHONG KE JI No.10, 2010 (Cumulatively No.134) 王滟方 谢文阁 (辽宁工业大学,辽宁 锦州 121001) 【摘 要】随着数据量的增大,数据挖掘技术应用不断扩大,如何在挖掘过程中不泄露私有信息或敏感知识,同时能得到 比较准确的挖掘效果,已经成为数据挖掘研究中的一个热点课题。文章从数据分布的角度结合挖掘算法对目前几种关键的隐私 保护方法进行了介绍、分析,给出算法的评估,最后分析总结了数据挖掘隐私保护未来的研究方向。 【关键词】数据挖掘;隐私保护 【中图分类号】TP311 【文献标识码】A 【文章编号】1008-1151(2010)10-0020-02 随着计算机和网络信息技术的发展,人们产生和搜集的 数据大大增加,各行各业的历史数据量猛增。怎样从这些数 据中获得有用的知识、信息,对数据分析提出了新的要求。 数据挖掘刚好可以解决此问题,可以利用这些数据,得到有 用的数据信息或结果,从而帮助决策者制定更好的决策,但 是与此同时产生了一个重要问题那就是信息的泄露。各行业, 各企业单位既想获得数据挖掘的有用结果,又不想将自己拥 有的某些数据信息泄露给他方或他人。因此,如何在有效的 数据挖掘中保护隐私数据已经成为一个重要问题。 户提供所挖掘的知识) 2 数据挖掘中的隐私 不同的环境下对隐私的定义不同。数据挖掘中涉及的隐 私主要有: (1)个人隐私,一般指的是用户的一些能够识别 用户身份的标识,如姓名、年龄、家庭住址、电话号码等, 或者是用户某些行为产生的信息,例如购物信息,医疗信息 等; (2)公共隐私,两个或多个机构,企业为了共同的利益, 他们合作进行挖掘,在挖掘过程中都不愿意将自己的某些信 息泄露给他方。 隐私保护的主要目标是使用某种方法对原始数据进行处 理,使得私有数据和知识在挖掘之后仍然是私有的。不但要 在开始时对某些信息进行保护,而且对挖掘过程中产生的敏 感规则也要进行保护,还要考虑挖掘产生的结果是否会包含 某些重要的隐私信息。 (一)基本概念 1 数据挖掘 数据挖掘的定义很多,表达方式各不相同。从技术角度 看,数据挖掘是从大量的、不完全、有噪声的、模糊的、随 机的实际数据中,提取隐含在其中的、人们不知道的、但又 是潜在有用的信息和知识的过程;从商业角度看,数据挖掘 是一种崭新的商业信息处理技术。其主要特点是对商业数据 库中的大量业务数据进行抽取、转化、分析和模式化处理, 从中提取辅助商业决策的关键知识,即从一个数据库中自动 发现相关商业模式。 数据挖掘是从数据库中知识发现中的一部分,而知识发 现是将原始数据转化为有用知识的整个过程。当数据挖掘成 为普及的涵盖面更广的术语时,数据挖掘与知识发现之间的 界限就不是那么明确了。事实上,在现如今大多数场合中, 这两个术语的使用是不加以区别的,本文也不区分。知识发 现是一个多步骤的过程,典型的知识发现过程包括以下几个 步骤: (1)数据抽取与集成(抽取各个数据源的所需数据,进 行合并处理) (2)数据预处理与清洗(对数据再加工,消除噪声等) (3)数据选择与变换(选择相关数据,统一成适合挖掘 的形式) (4)数据挖掘(用智能的方法提取数据模式) (5)模型评估(根据需要,识别表示知识的真正有趣的 模式) (6)知识表示(使用可视化等各种知识表示技术,向用 (二)数据挖掘的隐私保护分类 1999 年,Rakesh Agrawal 在 KDD99 中提出将数据挖掘的 隐私保护将作为未来的研究重点之一,此后,数据挖掘的隐 私保护得到了发展,许多方法不断的涌现。从不同的角度对 数据挖掘的隐私保护方法的分类也不同。 2004 年, Vassilions S. Verykios 和 Elisa Bertino 等人从数据分布、数据修改、 数据挖掘算法、数据及规则的隐藏及隐私保护技术五个角度 对现有的较为典型的隐私保护数据挖掘算法进行了分类。 1.数据的分布方式 根据数据的分布情况,可以分为集中式数据和分布式数 据的隐私保护技术,其中分布式数据的隐私保护技术又分为 水平分割和垂直分割的隐私保护技术。水平分割主要是指数 据按记录分布于多个机构或组织,垂直分割主要指数据按属 性分布于多个机构或组织。 2.数据修改 为了确保原始数据中的隐私信息不被泄露,原始数据在 被公开之前要进行一定的修改、伪装,数据修改方案需要和 隐私保护策略相结合。常用的数据修改方法主要有一下几种: (1)值替代方法:即将原始数据的属性值替换为一个新 的值,或者用一个符号替代一个已存在的值,以此来保护敏 感的数据和规则; 【收稿日期】2010-07-15 【基金项目】辽宁省教育厅研究项目(2008314) 【作者简介】王滟方(1985-) ,女,辽宁工业大学电子与信息工程学院在读硕士研究生,研究方向为数据仓库、数据挖掘; 谢文阁(1966-) ,男(满族) ,辽宁锦州人,辽宁工业大学电子与信息工程学院副教授,硕士生导师,研究方向为数据仓库、 数据挖掘。 - 20 - (2)聚集的方法:将多个详细的数据进行合并或者抽象 为更高层次的数据; (3)取样方法:即抽样,在数据集中抽取样本数据; (4)交换方法:记录值之间的交换; 3.数据挖掘算法 目前数据隐藏技术都是在不同的挖掘算法中进行考虑 的,不同的挖掘算法应用的隐私保护技术不同,例如:决策 树算法、关联规则算法、聚类分析等挖掘算法。 4.隐私保护的对象 这主要是指对原始数据的隐藏还是对隐含规则的隐藏。 通常隐藏规则比伪装原始数据要复杂很多,有时通过保护敏 感的隐含规则,往往能同时起到保护重要原始数据的目的。 5.隐私保护技术 指修改数据所采用的技术。主要有以下几种: (1)基于启发式的隐私保护技术:仅修改一些特定值, 而非所有数值,以减少挖掘效果的偏离; (2)基于密码学的隐私保护技术:利用密码学方法来对 数据进行加密,典型的是多方安全计算(SMC)方法,参与计 算的各方只能获得自己所提供的输入数据以及最终结果,对 其他参与者的数据一无所知; (3)基于重构技术的方法:将数据进行变换后,再对原 始分布进行重构。 (三)数据的分布方式 1.集中式数据分布 (1) 聚类的隐私保护 该算法主要采用对原始数据进行几何变换,例如平移、 缩放和旋转等方法以实现对数据的保护。 Stanley R.M. Oliveira 先后提出通过几何变换和旋转变 换(RBT)来变换数据的方法。后一种方法解决了前一种方法 对维数的限制。 RBT 算法首先要将数据视为 m 行 n 列的矩阵 D,行数据为 数据记录,列数据表示属性,并定义一个变换矩阵: R= ? sinθ cosθ,随后进行数据规范化,数据匿名化,数据变 换。其中数据变换主要是以下三步:1、将数据集 D 的属性任 意两两配对,设 Sij= Ai 为任意一对属性对,其中 Ai 和 Aj 分 Aj cosθ sinθ 别表示 D 的第 i 列和第 j 列数据的转置所组成行矩阵。属性 n +1 n 个数 n 为偶数时,组成 2 对,n 为奇数时,组成 2 对属性 降级后的数据值的熵进行计算,是二者的差值同数据库变化 前后置信度的降低程度比较,从而得出这种对数据库的修改 是否是可以接受的,也即是否对数据库的影响是最小的。 (3) 重构技术 重构技术主要分为数值型数据的重构技术以及二进制数 据与分类数据的重构技术。对于数值型数据的重构典型的方 法是 Rakesh Agrawal 的数据离散化方法与值变形方法,通过 添加随机偏移量来修改原始数据,然后用重构原始数据的分 布;对于二进制数据与分类数据的重构技术,Alexandre Evfimievski 利用了统一随机化技术对部分数据进行修改的 关联规则算法。即将一个交易发送给服务器前,客户端取走 每一个项时将以概率 p 替换为原先在交易中没有的新项, S.J.Riziv 等人利用贝努力概率模型提出了一种成为 MASK 的 算法。其使用的数据库是固定长度的 0,1 序列组成的,算法 对所有原始数据按照贝努力概型进行变换,即设原始数据为 X={Xi}, Xi=0 或 1, 使用变换函数 Y=distort (X) 其中 Yi=Xi , Xor r i ,ri 是服从贝努力分布的一个随机变量,即取 1 的概 率为 p,取 0 的概率为 1-p。但是此算法对数据变换耗费的时 间和空间较大。 2.分布式数据分布 (1)数据垂直分布 垂直分布数据,数据是按属性分布在各个站点,在此条 件下可以通过发现项集的支持计数来进行数据挖掘。因此, 如果数据的某个项集的支持计数可以被安全地计算,则通过 检查计数和预先设定的阈值比较,就可以知道该项集是否是 频繁项集。Jaideep Vaidya 提出了一种不向对方公布向量的 计算标量积的方法。其依据是一个 n 元线性方程组,方程组 的个数小于 n, 那么结果是不确定的。 通过这样的方法可以达 到保护隐私的目的,还能保证各方只能得到全局的频繁项集 和关联规则。对各站点将其拥有的属性构成一个 n 维系数矩 阵,通过产生随机的 n 个数 R1,R2,…,Rn,使之与其拥有 的属性线性组合,通过交换计算结果得到规则。 (2)数据水平分布 数据水平分布是数据按着记录分布在各个站点,对其进 行隐私保护,就是要各个站点在不必知道其他站点的具体记 录信息的情况下就可以计算出全局的关联规则。针对各参与 方既想联合进行数据挖掘又不愿意泄漏各自的信息,由此产 生了半可信第三方,即遵守事先约定的协议,合作的多方只 向第三方发送和接收数据,第三方对这些数据进行计算,并 将最终结果传给合作的各方。 (四)算法的评估 目前还没有一个能针对各种数据集,各种挖掘算法的有 效的隐私保护策略,当前算法都是针对特定的数据集,特定 的挖掘算法研究设计的,对于在什么情况下用什么样的算法 应该从以下几点考虑: 1.保密性 方法研究的是对数据挖掘的隐私保护,首要考虑的是对 隐私数据保密的程度。目前的算法中不能保证做到完全保密, 每个算法的保密性都是有限的,根据不同的保密需要选择不 同的隐私保护方法; 2.挖掘效果 指对隐私数据进行处理后,数据挖掘的结果是否可用。 若经过处理后,得到的数据挖掘的结果是错误的,或者不能 反映真实的情况,那么原来的数据失去了价值,挖掘做了无 用功,相应的隐私保护处理也就失去了意义。因此在考虑保 密性的同时,数据挖掘的结果还要相对准确; 3.算法复杂度 算法复杂度是衡量所有算法的一个标准,当然对于隐私 保护也不例外。在考虑算法的有用性的基础上也要考虑算法 的可行性,应使算法的复杂度尽可能的低,这是在设计方法 时的一个重要目标。 (下转第 28 页) 对。令 Sij′=R·Sij= Ai' Aj' ,其中 Ai' 和 Aj' 分别表示数据 D ' 第 i 列和第 j 列数据的转置所组成的行矩阵;2、预先给定两个 均大于 0 的阈值α1 和α2,求解θ的范围θ1≦θ≦θ2,使得 θ满足 D(Ai- Ai' )≧α1,D(Aj- Aj' )≧α2;3、θ随机取 [θ1,θ2]中的一个值,重新计算 Sij′=R·Sij。依次计算每一 对属性值对,最终得到变换后的数据D′。 此算法是基于旋转变换的等距变换,因此在变换前后挖 掘结果相同。但是因为旋转角度θ旋转范围是根据要求的最 低的隐私保护度来确定的,所以当对隐私保护的要求较高时, 算法有可能无法取得合适的旋转角度。 (2) 分类的隐私保护 Chang Li Wu,Moskowitz I S.提出了吝啬降级法。其中 降级是指从敏感级或隐私级降低到可以公布级即低级别。算 法通过产生一个称之为参变量基础集的方法来实现数据的降 级。用参数θ∈[0,1]来取代敏感数据。同时对于降级前和 - 21 - 对应的列出所需的 WBS 方法造价控制分析表输入 Excel 表格。列出各个层级(其工序名称、计划造价、预计、实际造 价), 输入出核算单元、 各控制单元的造价投资额, 并用 Excel 表格进行计算,通过对表进行分析,可以方便的看出各项施 工内容或各层级的造价的变化情况。在进行造价控制时可以 与主体工程的投标工程清单中分部分项工程作为控制单元, 也可以与项目中各个单体作为控制单元进行原预算造价与实 际发行造价对比,下一级控制单元的变化必然会引起上一级 控制单元的变更,掌握控制单元造价在施工过程中变化情况, 从而对造价进行合理控制。 3.在施工过程造价管理中结合 Excel 表格使用 WBS 分析 方法,应注意如下问题: (1)WBS 分解前应认真研究招标文件和合同,了解施工 项目的工程范围和任务; (2)应根据施工方案的要求进行项目分解,特别是施工 布置和施工流程; (3)分解中应要结合责任体系和任务的落实,应把握各 责任人的管理深度; (4)各控制单位的描述要详细、准确; (5)编码要容易识别,尽量用字母,少用数字。编码在 整个计划和控制中极为重要,大量的数据汇集、统计、信息 查询都是通过编码实现。在项目开始初应专门进行编码设计; (6)在输入计算软件 Excel 表格时每个细项按照合同清 单价格确定造价值要准确,要与 WBS 分解的控制单元相对应, 不可以漏项。对于简略的项目可以合并到相应的细项中,但 造价值也必须合计到该项中。 (四)结合计算机软件的 WBS 造价分析方法优越性 1.使各细目、工序、项目 价变化 的造 更为直 观 列出各个层级(其工序名称、计划造价、实际造价),每 个细项按照合同清单价格确定造价值,细化到每个工作包都 输入有造价值,输入 Excel 表格后得出各核算、控制单元的 造价投资,并用 Excel 表格进行计算,通过对表内数据进行 分析,可以知道原投资与预计投资或实际投资发生的变化, 能方便的、直观的看出各项施工内容细目、工序、控制单元 或各层级的实际或预计的造价变化情况。 2.更方便的实施动态管理 利用 WBS 结合现代先进的计算机技术实现项目造价控制, 各控制单元或细化的工作包的造价能随着施工过程中发生的 造价变化而变化,并及时记录下来,有利于让项目管理者对 造价实施动态管理。 3.分析更加快捷有效 将施工阶段的投资变化输入对应的细目、控制单元的造 价单元格中,借助按 WBS 方法建立的计算机电子表格对进行 造价分析,各控制单元的造价投资变化立即可以从表格中对 应单元格数据中反应出来,使建设项目造价管理分析变的更 加快捷有效。 4.分析选择更加灵活 在输入计算软件 Excel 表格时对于简略的项目可以合并 到相应的细项中,并将造价值合计到该项中。也可以将核算 单元尽可能的细化后分析。各核算单元也可能视做控制单元 进行投资变化分析。造价管理人员能非常灵活的选择做控制 单元或核算单元的工作包,按自身工作的要求灵活的进行造 价分析。 5.更利于信息的集中存储、处理 借助计算机电子表格对 WBS 进行造价分析,将大量的数 据信息进行分类、整理,方便历史数据和信息的收集、存储, 但易于施工过程中的数据提取处理,也方便为将来的类似工 程提供详实的信息、资料。 但是要注意不管是任何方法都不是万能的,受 WBS 编码 的扩展性、计算机录入水平、管理人员知识能力限制、执行 能力等诸多环节的影响,在 WBS 建立、编写计算机录入程序 过程中业主也要进行不断改进,不断对已执行的 WBS 架构和 计算机分析程序进行调整,以适应项目动态发展的需要。 使用借助计算机平台的 WBS 造价管理方法虽不能直接对 造价进行控制,但其利用现代先进的计算机技术建立起一个 广泛的信息平台,使项目实施过程能得到直观有效的量化分 析,实行更细化的动态管理,分析可以选择在事前也可以在 事后,即发现某一方面的预计将要出现造价偏差,则应将该 部分造价偏差问题单独提出,及时将发现的造价变化情况反 馈给各相关部门,及时针对投资变化的原因研究控制的对策, 做进一步分析,对造价采取措施进行控制。或对已发生的造 价控制问题进行分清责任,汲取宝贵经验,即分析不是目的, 分析的目的只是为了方便进行下一步的控制。 【参考文献】 [1] 江萍,成虎.施工项目结构 WBS 分解方法及准则研究[J].东 南大学学报,2000(4):32. (上接第 21 页) (五)结束语 本文从数据分布的角度介绍、分析了数据挖掘隐私保护 的几种算法,每类隐私保护技术都有不同的特点,在不同的 需求下各个技术的应用范围不同,但是没有一个可以通用的 算法,算法的可扩展性不强,各个算法的各项性能也不是都 很好,所以接下来寻找通用的算法,和改进算法的各方面性 能是需要进一步研究的。 【参考文献】 [1] 刘颖.数据挖掘领域的信息安全问题_隐私保护技术浅析[J]. 计算机安全.2007,7. [2] 陈晓明,李军怀,等.隐私保护数据挖掘算法综述[J].计算机 科学.2007,Vol.34 No.6. [3] 陈芸,张伟.隐私保护数据挖掘方法的研究[J].微计算机信 息,2006,Vol.22 No.73. [4] Vassilios S.Verykios,Elisa Bertino,Igor Nai Fovino,Loredana Parasiliti Provenza,Yucel Saygin,Yannis Theodoridis.State of the art in Privacy Presserving Data Mining[A].ACM SIGMO Record[C],March 2004,Vol.33,No.1. [5] Chang Li Wu,Moskowitz I S..Parsimonious downgrading and decisions trees applied to the inference problem. In:Proceedings of the 1998 New Security Paradigms Workshop,1998.82-89. - 28 -

文档贡献者

wangxuhong2026

贡献于2011-01-25

喜欢此文档的还喜欢