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

保护隐私的数据挖掘方法研究_教育学/心理学_人文社科_专业资料

570人阅读|32次下载

保护隐私的数据挖掘方法研究_教育学/心理学_人文社科_专业资料。浙江大学 硕士学位论文 保护隐私的数据挖掘方法研究 姓名:温晗 申请学位级别:硕士 专业:计算机应用技术 指导教师:林怀忠 20060301 浙江大学硕士学位论文 摘要 信息时代给我们带来了数据


浙江大学 硕士学位论文 保护隐私的数据挖掘方法研究 姓名:温晗 申请学位级别:硕士 专业:计算机应用技术 指导教师:林怀忠 20060301 浙江大学硕士学位论文 摘要 信息时代给我们带来了数据在数量和复杂性上的爆炸性增长,也催生了富 自挑战性的研究领域——数据挖掘。在很多情况下,数据由不同的组织持有、 分布于不同的地理位置.而且持有者可能出于数据安全性和敏感性等原因不愿 意卣接共享他们的数据。怎样跨越数据挖掘和数据机密性之问的这道鸿沟进行 各种研究和应片j,是当前数据挖掘的~大研究方向,称为保扩隐私的数据挖掘 (Pri racy—Preserving Data Mining,PPDMl。 保护隐私的数据挖掘方法有两大类,随机化方法和基于密码学的方法,本 立关注前者,它有两种模式.基于随机数据扰乱以及基于随机响应的方法。 随机数据扰乱方法及重构技术难以消除由于属性变量本身相关性引起的数 据泄露。本文介绍了一种利用主成分分析进行属性精简的增强随机化方法,降 低了参与数据挖掘的属性数据阅相关性,更好的保护了隐私数据,同时对此方 法实施条件下数据遗失率及隐私保护性能进行了量化研究,得出隐私保护性能 与属性精简程度和随机量数学特征之间的关系。 基于随机响应的隐私保护技术则借鉴了统计学研究中的经典方法,模拟调 查者在尽量不侵犯被访者隐私情况F搜集有意义的统计数据的过程。本文介绍 了随机响应技术与ID3决策树分类算法结合进行数据分类的过程,并将其引入 关联规则挖掘应用环境中,构建了基于随机响应技术保护隐私数据的关联规则 挖掘框架,并讨论了一个具体算例。 关键词:保护隐私的数据挖掘,随机数据扰乱,主成分分析,随机响应,决策 捌分类,关联规则挖掘。 浙江大学硕士学位论文 Abstract Wlth the advance of the have exploded information age.data collention and analysis and both in size complexity.The attempt vast to extract to important patterns and trends from the In many by data sets has 1ed the cha]1 enging fi old data raining across contexts,data are distributed organizations due to different sitee and held to different others who’re reluctant share their data with privacy and cor】fidentiality coocerns Pri racy—Preserving Data Mining(PPDM)has emerged zhe to address tbis issue The research of PP啉{is aimed at mining and data bridging gap between collaborative data confidentiality. Can There are many approaches which have been adopted for PPDM.They be c】assif'5 ed]neetwo major categories:Randomi sation—based approaches and Cryptography—based techniques.We focused two on the former,which has schemes.Random Perturbation(RP)and Randomized Response(RR). RP and data reconstrLlSt inn,as an important technique in PPDM field, can’t 1imit priracy breaches of datasets with high correlated attributes effectively.We brought forward an Component and improvement by Principal Analysis(PCA)to more reduce the attributes involved in data mining of preserve privacy original data We also tried to quantify the relationship between performance of of original RR the algorithin and compression attributes/random were noise. statl techniques developed in the stics community for zn the RR purpose of protecting surveyee’s privacy.We described how use techniques to bui Id decision tree classifier from the disguised data,with ID3 algorithm.We al so conducted privacy—preserving association rules in mining using RR techniques and di seussed the process of the algorithm detail. Ke)Ⅵ'erds:Privacy—Preserving Principal Data Mining . Random Perturbation, Tree Component Analysis,Randomized Response,Deeision Classification,Association Rules Mining. 浙江大学硕士学位论文 第一章绪论 1.1数据挖掘概述 数据挖掘是一门汇集统计学、机器学习、数据库、模式识别、知识获取、专 家系统、数据可视化和商性能计算等多种学科的新兴交叉学科【l,41],这个研究 领域融合了多个不同学科领域的技术与成果,使其方法表现出多种多样的形式。 数据挖掘的研究是以应用驱动的,从一诞生,就带上了强烈的应用色彩[I]。 由于其本身的特点,数据挖掘在金融、保险业、零售业、医学、制造业、运输业、 科学与工程研究等众多领域都有广阔的应用前景。例如在金融行业,数据挖掘可 以用来分析客户的信用状况,可以预测贷款偿还情况等,在生物医学领域,可以 采用数据挖掘对DNA序列进行研究,在生产制造行业,数据挖掘可以应用在机器 故障诊断、库存优化、生产调度等方面。 与数据挖掘紧密联系在一起的概念是数据仓库(Data Warehousing)以及联机 分析处理(OLAP)等。由于传统的数据库是面向事务操作而设计的,其处理方式都 是对指定的数据进行简单的数字处理,不能对这些数据所包含的内在信息进行提 取。企业需要把已经广泛收集到的数据集成到数据仓库中,从事务数据中提取有 用的信息,帮助他们对企业决策中做出即时的正确判断,而OLAP是数据仓库系统 的核心组成部分,是针对特定问题的联机数据访问和分析。 由于数据形式、数据挖掘任务及数据挖掘方法的多样性,数据挖掘领域有 很多挑战性的课题,高效有用的数据挖掘方法、数据挖掘语言的设计、交互集 成的数据挖掘环境的建立等众多的问题,是当前数据挖掘研究开发入员都需要 面对。的数据挖掘领域今后的焦点和发展趋势可能表现在以下几个方面:数据挖 掘语台的标准化、数据挖掘过程中的可视化方法、可伸缩的数据挖掘方法、Web 挖掘、复杂数据类型挖掘的新方法以及数据挖掘中的隐私保护和信息安全。 1.2 PPDM的提出与现状 数据挖掘是从大量数据中提取或“挖掘”知识[1],但是很多情况下,数据 可能分布于不同地点,属于不同组织。传统数据仓库方法要求将分布各处的数 据集中于菜中心点,虽然这么做方便了部署应用,但是许多数据所有者出于保 护隐私或者数据机密性原因,不愿共享他们自己的数据[2,3,4]。保护隐私的 浙江大学硕士学位论文 数据挖掘(Privacy—Preserving Data Mining,PPDM),就是研究解决此类问题 的解决方案,其县标在于建立某种关联,跨越数据挖掘和数据杌密性之问的这 道鸿沟[2,3]。它的研究内容涵盖众多领域,如统计学、计算机科学,甚至社 会科学等方面,其基本思想在于对原始数据或者挖掘方法进行某种改进,在不 向非数据所有者泄露敏感数据取值的同时,发现原始数据的某些统计规律或隐 含的知识和规则[2,3]。 PPDM是未来数据挖掘的一个极其重要而富有挑战性的课题。2000年,文献 [2,6]同时从两个不同的角度提出了两种不同的PPDM问题,并分别采用数据扰 乱(Data Perturbation)技术和安全多方计算(SecHre Multi-party Computation,SMc)协议加以解决,推动了许多相关的研究。 文献(2]提出这样的同题:能否在不访问数据精确值的前提下构建模型?由 此展开了~个新的研究领域,并试图从加入随机量的扰乱数据中重构原始数据 分布,而菲数据库中的具体数值。文献t6]探讨了两个不愿意共享数据的数据持 有者之间,如何进行数据挖掘的应用,而且参与双方理论上除了输出之外,不 能获取任何其他额外的关于对方的知识和具体数据,其中具体讨论了]D3算法 在这种假设下的实现。 此外,文献[5]还提出了利用另一种基于随机化韵方法——随枧确应技术 (Randomized ResDonse),利用这种源于统计学研究中隐私保护的方法,来实现 在不泄露隐私数据的情况下进行一定精度的建模,主要探讨了与ID3决策树算 法结合进行分类的方法。文献[37,39,40]将这种技术与其他数据挖掘算法进 行结合设计了其他算法框架。 文献[9,23,25,26,30,32]研究了对关联规则进行隐藏的问题;文献[9, 23]讨论了保护私有信息的关联规则挖掘的一般方法;文献[25]讨论了一个将利 用不确定性符号进行数据阻塞应用于关联规则挖掘的具体例子,这种情况下支 持度和置信度分别用支持度区间和置信度区间代替;在保护隐私的关联规则挖 掘中,按照用户的相互合作方式可以将共享的数据库分为垂直划分(vertically partitioned)[30]与水平划分(horizontally partitioned)[32]两类,文献(30] 提出一种新的点积协议来求孵垂直划分问题;文献[32]基于安全求并算法求解 水平划分问题。 本文将提出对现有主流PPDM方法的几个不同分类标准并从隐私保护角度具 体探讨已有的各种方法。下一步的工作将集中在对这个领域概念及方法等的标 准化、提出一些对现有方法的效率以及隐私保护性能进行浏试以及评值的方法 等。具体来酷,较有挑战的研究领域有:隐私泄露及评价研究,在安全数据挖 掘中的具体应用实施以及针对分类、聚类、关联规则等挖掘方法中的具体应用 方法的研究和实施。其应用领域可以逐渐扩展到Web挖掘、企业间分布计算以 浙江大学硕士学位论文 及安全(分布式)应用系统等等。 1.3研究内容与章节结构 在上述背景下,本文将先提出几个分类角度/维度,对现有的各种PPDM方 法进行分类综述,并提出衡量算法的几个指标。主要关注随机化方法,包括随 机数据扰乱(Random Perturbation,RP)[2,3.4]和(Randomized Response, RR)[5]两种模式。对于随机扰乱方法,引进对现有基于重构的方法的~种改进, 可以减少属性变量之间相关牲引起的隐私泄露;对于随机响应方法,研究它的 原理,以及在决策树分类和关联规则挖掘中的结合和应用。下面是本文的章节 结构: 第一章绪论 介绍数据挖掘的基本情况,引入保护隐私的数据挖掘,介绍其基本原理及 现状,总括全篇的研究目标和各章内容。 第二章数据挖掘概念与常用方法 介绍数据挖掘相关概念,如数据仓库、联机分析处理等以及数据挖掘的典 型过程常用方法,并对应用趋势做了展望。 第三章PP叫算法分类研究与性能度量 从不同角度提出PPDM方法的分类标准和框架,对各种方法做了简介。同时 提出函个对隐私保护方法性能和质量进行评估的度量指标。 第四章随机数据扰乱PPDM重构的改进 讨论现有基于随机数据扰乱的PPDM方法存在的问题,针对属性间相关度可 能引起的数据隐私泄露和运算性能问题进行研究,提出一种改进方案,并估算 和评价了这种方案中由引入随机量导致的信息遗失率。 第五章随机响应与数据挖掘算法的结合 介绍基于随机响应的PPDM技术,以及在保护隐私的决策树分类中的应用。 将随机响应技术引入分布式关联规则挖掘环境,结合现有关联规则挖掘方法构 建应用,给出了在经过随机响应技术伪装的数据集上进行关联规则挖掘的算法 完整过程。 第六章回顾与展望 总结全文,对提出的方法和框架的不足之处和未来的工作进行概括,并对 下一步的磺究和应用作出展望。 最后:参考文献以及致谢。 浙江大学硕士学位论文 第二章数据挖掘的概念与方法 2.1数据挖掘的概念 数据挖掘(Data Mining)也被译作数据开采、数据采掘等。它是一类深层次 的数据分析方法,可能被用于科学研究或者商业领域,对大量数据进行较为复杂 的分析和建模,发现各种规律和有用的信息,就像从矿石中淘金一样,数据挖掘 也因此而得名。它经常被视为另一个常用术语一一—数据库中的知识发现 (Knowledge 的定义为: D1SeoYery in Database,KDD)的同义词。这种观点中比较有影响力 定义1。数据挖掘是指从数据库中提取模式的过程,这些模式是有效的、新 颖的、潜在可用和容易理解的。模式是指利用一些语言来描述数据的一个子集或 子集的一个可应用的模型[147。 或者可以把数据挖掘看作是知识发现过程的一个基本步骤。文献[15]中对它 的定义是: 定义2.数据挖掘是数据库中的知识发现过程中的一个步骤。这个步骤由应 用数据分析和发现算注组成,在满足一定计算效率的约柬下,从数据中产生一个 特殊的模式。 而企业界构建应用过程中和数据库相关理论研究过程中,通常将数据挖掘和 知识发现作为同一过程进行研究和描述,本文就将采用广义的观点: 定义3数据挖掘是从存放在数据库、数据仓库或其他信怠库中的大量数据 中挖掘知识的过程[1,19]。 2.2数据仓库与联机分析处理 20世纪70年代出现的数据库在收集、存储、处理数据中发挥了重要的作用, 但是,由于传统的数据库是面向事务操作而设计的,无论是查询、统计还是报表, 其处理方式都是对指定的数据进行简单的数字处理,不能对这些数据所包含的内 在信息进行提取。企业需要新的技术来弥补传统数据库的不是,在这样的背景下, 数据仓库作为一种新兴并日益成熟的技术引起了人们的广泛重视。与传统的面向 事务性处理的数据库相比,数据仓库面向复杂的分析型数据,解决了数据集成、 数掘综合、数据不一致等问题,使企业的业务操作环境和信息分析环境分离,同 时内置了各种复杂数据分析处理的系统工具,有效地为企业进行信恩发掘,进而 时内置了各种复杂数据分析处理的系统工具,有效地为企业进行信总发掘,进而 浙江大学硕士学位论文 第二章数据挖掘的概念与方法 2.1数据挖掘的概念 数据挖掘(Data Mining)也被译作数据开采、数据采掘等。它是一类深层次 的数据分析方法,可能被用于科学研究或者商业领域,对大量数据进行较为复杂 的分析和建模,发现各种规律和有用的信息,就像从矿石中淘金一样,数据挖掘 也因此丽得名。它经常被视为另~个常用术语——数据库中的知识发现 (Knowledge Discovery 的定义为: in Database,KDD)的同义词。这种观点中比较有影响力 定义1.数据挖掘是指从数据库中提取模式的过程,这些模式是有效的、新 颖的、潜在可用和容易理解的。模式是指利用一些语言来描述数据的一个子集或 子集的一个可应用的模型[14]。 或者可以把数据挖掘看作是知识发现过程的一个基本步骤。文献[15]中对它 的定义是: 定义2.数据挖掘是数据库中的知识发现过程中的一个步骤。这个步骤由应 用数据分析和发现算法组成,在满足一定计算效率的约束下,从数据中产生一个 特殊的模式。 而企业界构建应用过程中和数据库相关理论研究过程中,通常将数据挖掘和 知识发现作为同一过程进行研究和描述,本文就将采用广义的观点: 定义3.数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据 中挖掘知识的过程[1,19]。 2.2数据仓库与联机分析处理 20世纪70年代出现的数据库在收集、存储、处理数据中发挥了重要的作用, 但是,由于传统的数据库是面向事务操作而设计的,无论是查询、统计还是报表, 其处理方式都是对指定的数据进行简单的数字处理,不能对这些数据所包含的内 在信息进行提取。企业需要新的技术来弥补传统数据库的不足,在这样的背景下, 数据仓库作为一种新兴并日益成熟的技术引起了人们的广泛重视。与传统的面向 事务性处理的数据库相比,数据仓库面向复杂的分析型数据,解决了数据集成、 数据综合、数据不一致等问题,使企业的业务操作环境和信息分析环境分离,同 时内置了各种复杂数据分析处理的系统工具,有效地为企业进彳亍信息发掘,迸雨 浙江大学硕士学位论文 做出决策提供了强大的支持[1,16,17,18]。 2.2.1数据仓库的定义和组织 数据仓库之父frilliam H.Inmon首先系统地论述关于数据仓库的思想、理论。 他把数据仓库的定义为:“数据仓库是一个面向主题的、集成的、时变的、非易 失的数据集合,支持管理部门的决策过程。“[1,16]这个简短而又全面的定义指 出了数据仓库的全部特征,我们进一步分析这些关键的特征[1,17,18]: (1)面向主题(Subject~oriented):传统的数据是面向应用的,数据与应 用紧密相连,而数据仓库则是面向主题的,主题是在一个较高层次上的将数据 归类的标准。基于主题的数据在逻辑上相互不交叉C17]。数据仓库可能围绕这 样一些主题,如顾客、供应商、产品和销售组织,数据仓库关注数据建模与分 析,而非组织机构的日常操作和事务处理,它排除对于主题或决策无用的数据, 提供特定主题的简明视图。 (2)集成(Integrated):集成性和面向主题性紧密相关的,当前很多企业内 的数据是分散的面非集成的。其主要原因是事务处理的分散性、数据的不~致性、 外部数据和非结构化数据。数据仓库中的数据来源于这些现行的业务系统或管理 信息系统,而这些系统是相互独立的,在数据字典、编码规则、命名方式和关键 字之间等各个方面各不相同,甚至相互矛盾。数据仓库则需要根据决策分析的要 求,将各异种数据源,如关系数据库、一般文件和联机事务处理记录等通过抽取、 筛选、清理、综合等工作,解决命名冲突、度量单位的不一致性等闽题后,集成 为统一的形式导入到数据仓库,使得其中的数据具有集成性。 (3)时变(Time—variant):数据仓库的时变性,就是数据应该随着时间的推 移而发生变化。尽管数据仓库中的数据并不像事务数据库那样直接反映事务处理 的目前状况,雨是从历史的角度提供信息,其关键结构都隐式或现实的保护时间 元素[1]。但数据也不能长期不变。数据仓库必须能够不断地捕捉事务系统中的 变化数据,将那些变换的数据追加到数据仓库中去,一般是在数据仓库中不断生 成事务数据库的快照,以满足决策分析的需要。 (4)非易失(Nonvolatile):数据仓库的数据非易失性是指数据仓库中的数 据不经常进行更新处理,因为数据仓库中数据大多表示过去某一时刻的数据。主 要用于查询,而不像事务系统数据库那样,需要经常进行修改、添加。同时,一 般也不需要事务处理、恢复和并发控制机制Ill。 数据仓库中的数据组织形式不同于原有的关系型数据库,其中数据组织的逻 辑结构可分为近期基本数据层、历史数据层和综合数据层(其中综合数据是为决 策服务的)。近期基本数据是最近时期的业务数据,也是数据仓库用户最感兴趣 浙江大学硕士学位论文 的部分:源数据经过综合后,首先就是当前基本数据,并根据具体需要进行进一 步的综合,从而进入轻度综合级乃至高度综合级;老化的数据将被转化为历史数 据,通常被转存在其他介质中。数据仓库中数据的物理存储形式有多维数据库组 织形式和基于关系数据库组织形式两种。前者的数据以空间超立方体形式组织, 后者则由关系型单维表组成,这种高度集中而组织形式不尽相同的数据为各种不 同的信息获取和决策支持需求提供了有用的分析基础。 除此之外,数据仓库中还有一种重要的数据——元数据,整个数据仓库的组 织结构都是由它来组织的,也被称作是“关于数据的数据”[16,17]。元数据在 数据仓库中起着很重要的作用,表现在如下几个方面:定位数据仓库的目录,记 录或转换数据从业务环境向数据仓库环境传送时的目录内容,以及指导从当前基 本到轻度综合、轻度综合到高度综合数据的综合算法的选择。还有一些数据仓库 模型中将元数据按用途的不同分为两类:技术元数据(Technical Metadata)和业务 元数据(Business Metadata)[18j。 ~个数据仓库环境除了包括相关的数据库外,还包括ETL解决方法、联机分 析处理引擎、用户分析工具和其它负责收集和传输数据的模块[17,18]。 2.2.2联机分析处理的概念和特征 联机分析处理[1,17,18](On—Line Analytical Processing,OLAP)的概念 是由E.F.Codd于1993年首先提出的。他同时提出了关于OLAP的12条准则,从此 OLAF作为一类产品同联机事务处理(OLTP)明显区分开来。 在大数据量、高应用复杂度的环境下,用户的决策分析需要对关系数据库进 行大量计算才能得到结果,而传统数据库中的事务性操作不能满足用户深层次分 析的需求。针对这个问题,Codd提出了多维数据库和多维分析的概念,EIJOLAP, “维”(Dimension)是人们观察客观世界的角度,是一种高层次的类型划分,一般 包含着层次关系,这种层次关系有时会相当复杂。OLAP通过把一个实体的多项重 要的属性定义为多个维,使用户能对不同维的数据进行比较,因此也可以说它是 多维数据分析工具的集合。一种较通用的OLAP的定义简单而明确:共享多维信息 的快速分析[1,17,18],这个定义概括了其主要特点: ? 多维性:多维性是OLAP的关键属性。系统必须提供对数据分析的多维视 图和分析,包括对层次维和多重层次维的完全支持。事实上,多维分析是分析企 业数据最有效的方法,是OLAP的灵魂。 ?信息性:OLAF管理大量历史数据,提供汇总和聚集机制,并在不同粒度 级别上存储和管理信息,但不论数据量有多大,存储在何处,OLAF系统应能及时 获得信息,并且管理大容量信息。这里有许多因素需要考虑,如数据的可复制性、 浙江太学碗士学位论空 可利用的磁盘空间、0LAP产品的性能及与数据仓库的结合度等。 ?快速性:用户对0LAI’的快速反应能力有很高的要求。如果终端用户在可 接受时间内得不到系统响应就可能放弃,因而失去分析主线索,影响分析质量。 对于大量的数据分析要达到预期的速度并不容易,需要一些技术的支持,如专门 的数据存储格式、大量的事先运算、特别的硬件设计等。 ?分析性:OLA[1系统应能处理与应用有关的各种逻辑分析和统计分析。尽 管系统需要事先编程,但并不意味着系统已定义好了所有的应用。用户无需编程 就可以定义新的专门计算,将其作为分析的~部分,并以用户理想的方式给出报 告。用户可以在OLAP平台上进行数据分析,也可以连接到其他外部分析工具上, 如时间序列分析工具、成本分配工具、意外报警、数据开采等。 2.3数据挖掘过程与功能 2.3.1过程与步骤 数据挖掘过程【1]如图2.1所示,它不是~个线形的过程,而是包括许多的反 馈回路在内的,这些过程在具体实施中可能需要重复多次,在每一过程中,需要 不问专业人员的参与,包括业务分析人员、数据分析人员和数据管理人员等。 在特定的数据挖掘应用设计和部署之前.需要先确定挖掘对象:确定应用的 范围,了解用户的需求,确定最后的挖掘目标,一般来说,数据挖掘使用的核心 算法可以是关联规则、分类、聚合、回归、相关分析建模等。 数据挖掘的过程大致可咀分为以F4个阶段。 1数据的选择和清理集成 在确定数据挖掘的业务对象后,需要搜索所有与业务对象有关的内部和外部 数摒。从中选出适合于数据挖掘应用的数据。如果是基于数据仓库的情况,由于 数据仓库己经为用户准各好了数据挖掘的基本数据,因此数据选择相对来随比较 简单,否则,需要从各个数掘源中去选择用于挖掘的数据,并进行清理集成、净 化预处理,解决数据中的缺值、冗余、噪声和不一致的数据值和数据定义等问题。 2.数据的变换和压缩 根据任务的目标,查找有用的特性来表示数据,将其变换或统一成适合挖掘 的形式。可以利用空间压缩和变化的方法来减少要考虑的有效变量数目或找到数 据的不变表示。一般通过把数据投影到某个空间上以利于问题的解决。 3数据挖掘 进入数据挖掘的核心步骤.先饕根据KDD过程的目标和确定的数据挖掘对象, 选择相戍的数据挖掘方法。如统计分析的方法.机器学习和人工智能的方法、模 新江大学硕士学位论文 式识别的方法等;其次要选择具体算法,用来查找模式或符合数据的模型的,确 定合适的模型和参数:最后利用这些选定的算法.查找感兴趣的模式,模式通常 表示为一种特殊的形式或一套表达式.如关联规则、分类规则、聚类集或回归函 数等等。 4.评估、表示和巩固挖掘所得知识 先根掘某种兴趣度度量,对于上步数据挖掘的结果进行评估,筛选和评 价有用部分.查找可接受的结果;然后可以利用可视化和知识表示等方法,尽 量直观的向用户展示和提供挖掘所得结果,便于他们理解和使用;最后可能需 要对所得知识进行巩固,一般是把挖掘出的知识结合}q执行系统中,了解这些 知识的作用或证明这些知识,用已知目呵信的知识来检查和验证所挖掘的知汉, 解决可能存在的矛活, 图2.1数据挖掘过程示意 2.3.2功能及模式 数据挖掘的主要功能是确定数据挖掘任务巾要找的模式类型,数据挖掘任 务一般可以分为描述和预测两大类。描述性挖掘任务主要是刻画数据库中数据 的一般特性,预测性挖掘任务是在当前数据上进行推断,以进行预测。 14 新江大学硕士学位论文 数据挖掘功能以及它们可以发现的模式类型主要有[1,41]: 1.类/概念描述 数据可以与类或概念相关联,用汇总的、简洁的、精确的方式描述每个类和 概念是有用的,目的是对数据进行浓缩,给出它的总体的综台描述,实现对原始 数据的总体把握[1]。这种类或概念的描述称为类/概念描述。通过类/概念描述 使得人们能够在复杂数据库中了解数据的意义以及产生数据的过程。这种描述可 以通过}【=总所研究类的数据来获得,这个过程也叫数据特征化,即目标类数据的 一般特征或特性的汇总。基于数据立方体的OLAPJz卷操作来执行指定维的数据汇 总就是一种很有效的数掘特征化的方法,数据特征的输出可以甩多种形式提供, 如饼图、条图、曲线、多维数据立方体和包括交叉表在内的多维表等来形象的表 现出来[1]。 2,关联分析 数据库中的数据之间一般都存在某种关联关系,即变量之间可能存在某种规 律,关联分析(Assoeiation hnalysis)的任务就是发现关联规则,即数据库中哪 些事物或属性共同出现的条件。关联规则广泛用于购物篮或事务数据分析。例如 可以通过关联规则挖掘来发现超级市场哪些商品经常被同时购买,商家可以利用 这些关联信息来确定进货的计划、商品应该如何摆放等,如可以把经常一起购买 的商品摆的近一点,有助于同时购买。关联攫刚挖掘自£给企业带来辍有价值的信 息相知识。最有影响力的关联规则挖掘的算法是Rakesh Agrwal等人提出的 Aprlori算法[】,42],近年来,也出现了很多Apriori的改进算法,如Edith Cohen 等人提出的不需要剪枝的改进算法C43],Mohammed J.Zaki提出的可伸缩的改进 算法[44]等。 3.分类与预测 分类(Classification)就是通过研究己分类的样本集的特征,分析样本集的 属挂,建立一个可以描述并区分数据类或概念的分类模型/函数,通过这个分类 模型,未分类的新数据就可阻分派到不同的类别中.达到分类的目的。分类的方 法有:决策树归纳、贝叶斯网络、入工神经元网络(如BP网络等)、粗糙集、遗传 算法、K最临近分类和支持向量机等方法。分类可以预测对蒙的类标签,当要预 测的数据是数值数据(连续值,,而不是离散的类别标志时,ⅢⅡ称为预测[4 Jj。预 删主要使用回归方法,当然也可以使用人工神经元网络,支持向量机等机器学习 方法。此外分类和预测之前可能需要进行相关分析(Relevance Analysis),以识 别对于分类和预测无用的属性。将它们排除[1]。 4聚类分析 聚类是将对象集合按照相似性归为若二F类别,与分类和预测不同,属于无指 导分类,即分析数据对象而不考虑已知的类标记。属于同一类的对象具有较高的 浙江大学硕士学位论文 某种相似性,而不同类的对象之间的差别较大。对象根据最大化类内相似性、最 小化类间相似性的原则进行聚类或分组,这样形成的每个簇(聚类)都可以看作一 个对象类,由它可以导出规则[1]。 5.孤立点分析 数据库中经常存在这样一些数据对象,它们与数据的一般行为或模型不一 致,这些数据对象我们就称之为孤立点(Outlier)。在一般情况下,数据挖掘方 法会将孤立点视为噪声或异常而丢弃,但是在一些应用中,罕见的事件可能比正 常出现的更为有趣[1]。孤立点数据分析称作孤立点挖掘(Outlier Mining)。 6.演变分析 数据演变分析(Evolution Analysis)用来描述行为随时问变化的对象的规律 或趋势,并对其建模。可能包括时间相关数据的特征化、区分、关联、分类或聚 类等[1]。这类分析的特点在于时间序列数据分析、序列或周期模式匹配和基于 类似性的数据分析。 2.4数据挖掘常用方法 数据挖掘的研究融合了多个不同学科领域的技术与成果,使的目前的数据挖 掘方法表现出多种多样的形式。从统计分析类的角度来说,统计分析技术中使用 的数据挖掘模型有线形分析和非线形分析、回归分析、逻辑回归分析、单变量分 析、多变量分析、时间序列分析、最近序列分析、最近邻算法和聚类分析等方法。 利用这些技术可以检查那些异常形式的数据,然后,利用各种统计模型和数学模 型解释这些数据,解释隐藏在这些数据背后的市场规律和商业机会。知识发现类 数据挖掘技术是一种与统计分析类数据挖掘技术完全不同的挖掘技术。包括人工 神经元网络、支持向量机、决策树、遗传算法、粗糙集、规则发现等。下面列举 一些常见的算法及它们各自的应用领域; 1.Apriori算法 Apriori算法用于数据挖掘中的关联规则,是一种最有影响的挖掘布尔关联 规则频繁项集的算法。算法使用频繁项集性质的先验知识,使用一种称作逐层 搜索的迭代方法,k一项集由于搜索(k+1)一项集,首先找出频繁l一项集的集合厶, 再将三。用于找频繁2-项集的集合上:,厶用于找厶,如此下去,直到不能找到 频繁k一项集为止。然后在频繁项集的基础上计算各规则的支持度和置信度,按 照预定义的条件输出符合的规则。 2.决策树 决策树是建立在信息论基础之上,通过逼近离散值目标函数对数据进行分 浙江大学硕士学位论文 类的一种方法。首先,通过一批已知的训练数据建立一棵决策树。然后,利用 建好的决策树,对数据进行预测。建立决策树的过程,即树的生长过程是不断 的把数据进行划分的过程,每次划分对应一个问题,也对应着一个节点。对每 个划分都要求分成的组之间的“差异”最大C41]。决策树学习通过把实例从根 节点排列到某个叶节点来分类实例,叶节点即为实例所属的分类。树上的每个 结点说明了对实例的某个属性的测试,该结点的每一个后继分支对应于该属性 的一个可能值,分类实例的方法是从这棵树的根结点开始,测试这个结点指定 的属性,然后按照给定实例的该属性值对应的树枝向下移动的过程。 3,K一均值聚类算法 K一均值(K-mean)算法用于数据挖掘中的聚类,它以k为参数,把n个对象分为 k个簇,在同簇内相似度较高,在不同簇之间的相似度较低,每个簇用该簇中对 象的平均值来表示。这个算法尝试找出使方差最小的k个划分,当结果集是密集, 簇与簇之间的区别明显时,效果很好。k-mean算法的特点在于处理大数据集时, 该算法具有可伸缩性和比较高的效率[41]。 4.人工神经元网络 神经元网络系统是由大量简单的处理单元(即神经元)广泛连接丽成的复 杂网络系统。它模拟人脑神经元结构,并做了一定的简化和抽象为解决大复杂 度问题提供了一种相对来说比较有效的简单方法,以lfIP模型和}{ebb学习规则 为基础,建立三大类多种神经元网络,具有非线形映射特性、信息的分布存储、 并行处理和全局集体的作用、高度的自学习、自组织和自适应能力的种种优点。 前馈神经元网络以感知器网络、BP网络等为代表,可以用于分类和预测等方面; 反馈式网络以Hopfield网络为代表,用于联想记忆和优化计算;自组织网络以 ART模型、Kohonon模型为代表,用于聚类。 5.遗传算法 遗传算法(Genetic Algorithm,CA)是一神全局优化算法,它借用了生物遗 传学的观点,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的 提高。具体来说,一般通过变异和重组当前己知的最好假设来生成新的假设。每 一步,通过使用目前适应性最高的假设的后代替代群体的某个部分,来更新当前 群体的一组假设,来实现各个个体的适应性的提高。遗传算法由三个基本过程组 成:繁殖(选择)是从一个JHl十群(父代)选出生命力强的个体,产生新种群(后代) 的过程:交叉【重组)选择两个不同个体【染色体)的部分(基因)进行交换,形成 新个体的过程;变异(突变)是对某些个体的某些基因进行变异的过程。在数据挖 掘中,可以被用作评估其他算法的适合度。 6.糨糙集 粗糙集能够在缺少关于数据先验知识的情况下,只以考察数据的分类能力为 浙江大学硕士学位论文 基础,解决模糊或不确定数据的分析和处理问题。相糙集用于从数据库中发现分 类规则的基本思想是将数据库中的属性分为条件属性和结论属性,对数据库中的 元组根据各属性不同的值分成相应的子集,然后对条件属性划分的子集与结论属 性划分的子集之间上下近似关系生成判定规则。粗糙集理论的最重要优点之一 是:除了所需要分析的数据集外,不需要任何别的先验知识。它可以应用于数据 挖掘中的分类、发现不准确数据或噪声数据内在的结构联系。 7.支持向量机 支持向量机(¥VM)是在统计学习理论的基础上发展出来的一种新的机器学习 方法,它基于结构风险最小化原则上的,尽量提高学习机的泛化能力。具有良好 的推广性能和较好的分类精确性,能有效的解决过学习问题。它的基本思想是在 样本空间或特征空间,构造出最优超平面,使得超平面与不同类样本集之间的距 离最大,从而达到最大的泛化能力。另外,支持向量机算法是~个凸优化问题, 局部最优解一定是全局最优解,这些特点都是包括神经元网络在内的其它算法所 不能及的。支持向量机可以应用于数据挖掘的分类、回归、对未知事物的探索等 方面,也已经在文本分类、手写识别、图像分类、生物信息学等领域中获得了较 好的应用。 2.5数据挖掘应用与发展趋势 数据挖掘的研究是以应用驱动的,从一诞生,就带上了强烈的应用色彩,由 于本身的特点,数据挖掘在金融、保险、零售、医学、制造、运输各行业以及科 学与工程研究等众多领域都有广阔的应用前景。在金融行业,数据挖掘可以用来 分析客户的信用状况,可以预测贷款偿还情况等:在商业领域,数据挖掘所能解 决的典型商业问题包括数据库营销、客户群体划分、背景分析、交叉销售等市场 分析行为:在生物医学领域,可以采用数据挖掘对I)NA序列进行研究:在生产制 造行业,数据挖掘可以应用在机器故障诊断、库存优化、生产调度等方面。 总体来说,当前数据挖掘研究与开发的总体水平相当于数据库技术在70年代 所处的地位,迫切需要类似于关系模式、DBMS系统和SQL查询语言等理论和方法 的指导,才能使其得到普遍推广。由于数据形式、挖掘任务及方法的多样性,数 据挖掘领域有很多富有挑战性的课题,如高效有用的方法、数据挖掘语言的设计、 交互集成的数据挖掘环境的建立等等,是当前数据挖掘研究开发人员都需要面对 的。预计在未来很长一段时间,数据挖掘无论在学术上还是应用上都还是热门研 究领域。数据挖掘领域今后的焦点和发展趋势可能表现在以下几个方面: (1)数据挖掘语言的形式化和标准化:研究专门用于知识发现的数据挖掘 语吉,也许会像sQL语言~样走向形式化和标准化。这将使数据挖掘项目的系统 浙江大学硕士学位论文 化开发提供便利、并有助于各个数据挖掘系统和功能模块之间的互操作,便于在 企业中的培训和使用。 (2)数据挖掘过程中的可视化方法:这个方面的研究可以使知识发现的过程 能够被用户形象的理解,也便于在知识的发现过程中人机交互。 (3)可伸缩的数据挖掘方法:传统数据分析方法大都基于内存,数据挖掘面 对的是大数据量,因此如何有效并交互式的处理大数据量,就成为研究的一个方 向,一个好的数据挖掘算法,其复杂度应该随数据记录数、属性数目里线性增长。 (4)Web挖掘:Internet目前已经成为巨大的、全球性的信息服务中心,Web 上存在有大量的信息,有关Web内容的挖掘、Web日志的挖掘、Web结构的挖掘, 已经成为当前和以后数据挖掘领域最重要的热点之一。 (5)非结构化和复杂数据类型的挖掘:如对文本数据、图形数据、视频图像 数据、声音数据乃至综合多媒体等非结构化数据的挖掘以及地理空间、时序等复 杂数据类型的挖掘已经取得了一些进展,但离实际应用还有很大的距离,因此这 一领域的研究也显得很重要。 (6)数据挖掘中的隐私保护和信息安全:数据挖掘可能带来一些社会问题, 其中最敏感的要属个人隐私问题。从应用领域来说,如在商业领域,各公司都 不愿意向其他公司,特别是竞争对手公开自己的业务记录数据,以防止泄露商 业机密,因此,他们需要有一个安全的方法来解决联合统计分析问题,同时能 保护各自的隐私信息;或在卫生领域,有多家医疗机构,希望合作进行临床研 究,分析某种药品对某类疾病的治疗效果。由于病历涉及到病人及医院的隐私, 显然,任何医疗机构都不愿意向其他机构公开自己的数据。在保护各方隐私的 条件下如何进行科学准确的临床调查也是隐私保护的研究目标。而从数据挖掘 应用本身的数据分布和系统拓扑上来说,在网络环境或者新兴的网格计算环境 下,大量的数据往往广泛分布于网络/网格的各节点上,在跨节点联合数据挖掘 时,无论从网络信息安全角度还是应用数据机密性角度来说,同样存在保护隐 私的问题。本文将主要讨论这个领域的现状,并对一些方法进行研究。 浙江大学硕士学位论文 第三章PPDM算法分类研究与质量度量 PPDM是一个在数据挖掘和统计数据库领域中比较新的研究方向,关注于各 种数据挖掘方法和算法在数据隐私性保护方面所产生的副作用[1 1J。可以由两 方面加以考察:某些敏感的原始数据,如个人证件号、姓名、住址等,可能可 以从原始数据中抽取,从而产生隐私泄露[20,46];某些可以通过数据挖掘应 用得到的敏感的知识(Sensitive Knowledge),它们同样可能产生隐私保护方面 的问题[20]。因而,PPDM的主要研究目标,就是提出一些算法,对原始数据进 行~定的加工处理,使得经过数据挖掘之后,“敏感”数据和知识仍不至泄露。 保密信息被未经授权的用户获耿,这种问题也时常被称为“数据库推理” (Database Inference)问题[46]。本章将提出一些分类标准,并分别在这些标 准的框架之下对现有主流PPDM方法进行分类研究。 我们可以从五个角度,或者说维度(Dimension),或者分类标准,对众多文 献中出现的,较为典型的PPDM方法进行分类研究。 第一种,数据分布(Data Distribution),这个角度主要针对分布式数据挖 掘环境而言,如前文所述,大多数传统数据挖掘方法基于集中式的数据仓库, 而出于数据机密性和隐私保护的考虑,PPDM研究的环境大都为分布式环境[6]。 分布式环境按照数据集的分布情况,可以分为水平划分数据集和垂直划分数据 集两种[11,12,30,32]:水平划分,即相同属性(Attribute)集的不同记录分 布在不同位置;垂直划分,则是指不同属性的值分布于不同位置。 第二种,数据更改(Data godification),改变数据库中可能暴露的数据的 原始值,要与隐私保护的具体需求相结合。主要有几种方法[3,11]:数据扰乱 (Data Perturbation),用其他值替换原始值,如0-1互换,或者给原始数据加 上噪声;数据阻塞(Blocking),直接将某属性值替换为“?”等未定义、预留的 不可识别字符,进行扰乱;数据聚合/归并(Aggregation/Merging),几个数据 值合并为一个较大粒度的值;数据交换(swapping/Interchanging)方法;取样 本(Sampling),只对部分用户(样本)发布数据。 第三种,数据挖掘算法(Data Mining Algori thm),算法接受改变后的数据 并产生用户想要的输出,在特定的应用中,核心挖掘算法也是一定的。本文将 可能提到多种数据挖掘算法,其中最常用也是最重要的包括:决策树分类算法、 关联规则挖掘算法、聚类算法、粗糙集算法以及贝叶斯网络算法等等。 第四种,数据及规则的隐藏,主要指基本的原始数据集成的数据是否隐藏。 想要隐藏以规则形式存在的集成数据,复杂度相当高,正因如此,学者们提出 浙江大学硕士学位论文 了各种推断(Heuristics)算法。公共信息暴露越少,数据挖掘的推断精度就越 低,但同时数据的安全性得到了一定程度的保障。这种过程称为“规则混淆” (Rule Confusion)[11,46]。 第五种,隐私保护(Privacy Preservation)措旋,这是五个数据分类标准 中最重要的,因为它正是隐私保护程度的直接度量。对于原始数据有选择性的 进行改变,是保证数据实用性(Utility)的同时保证隐私不被侵犯的有效手段, 从这个角度可以分为:启发/推导式技术的方法,如自适应的进行数据更改,只 改变部分选中数值而非所有数值[2,5];基于密码学的方法,如安全多方计算 (Secure Multi—party computation,s%),参与计算的各方只能获得自己所提 供的输入数据以及最终结果[6,8,13];基于重构(Reconstruction)技术的方 法,最典型的就是从被加上随机扰乱噪声数据的伪装数据中获取原始数据的分 布规律[2,3,4]。 下文将从隐私保护角度分为三大类,分别讨论。 3.1启发推导式方法 众多正在使用的数据挖掘技术,如分类、关联规则发现和聚集等,都基于 一个前提:数据选择性更改(Selecti ve Data Modi ficati on),或称为数据清洗, 这是一个NP一难问题,因而,需要使用一些启发式(推导)方法,来降低问题的 复杂度。 1.集中式扰乱数据集上的关联规则隐藏 关联规则挖掘中,敏感大数据项集的最优清洗是一个NP一难问题,这一点在 文献[20]中有形式化证明。我们这里提到的问题描述如下: 已知:D为源数据库,R为从JD中可以挖掘出的重要规则,而~为R的一 个子集; 问题:怎样将D转换为D’,并发布D,,使得除了民之外的所有属于旯的规 则,都可以从D’中挖掘而得。更改数据的启发式方法基于数据扰乱(Data Perturbation),具体来说,一般是选定某个数据集,将其中的1值替换为0值, 这样,敏感规则的支持度降低,丽真正发布的数据库中数据实用性(Utility)将 保持在一个最大值。这里的数据实用性是由数据更改后被隐藏的非敏感规则数量 来度量的。 文献[21]将敏感数据集清洗问题,扩展到了敏感规则的清洗,其中提到了 两种方法:第一种是通过可以推导出规则的数据集的隐藏实现,第二种方法则 是将敏感规则的置信度(Confidence of the Sensitive Rules)降低到用户定义 浙江大学硕士学位论文 的某个门限(Threshold)。由这两种方法,催生出三种隐藏敏感规则的策略。然 而,原始数据中二进制的O—l值互换,可能导致~些副作用:非敏感规则被隐 藏,或者非频繁规则(Non—frequent Rules)成为频繁规则(Frequent Rules)一 一这些规则称为“幽灵规则”(Ghost Rules),等等。这些副作用,降低了更改 后的发布数据库的数据实用性。所以,推断方法,应更多关注数据实用性方面, 同时保证安全因素。文献[22]中提供了更进一步的讨论。文献[23]在已有工作 的基础上,致力于通过减少数据清洗阶段的影响,或减少意外隐藏和幽灵规则, 实现在发现尽可能多的知识和保护隐私数据之间找到某种程度的平衡。 2.集中式阻塞数据集上的关联规则隐藏 还有一种用于关联规则隐藏的数据更改方法,称作数据阻塞(Data Blocking)[24]。这种方法的具体实现,是将一些数据集的某些属性值用问号(?) 替换,因为在某些应用(如,医疗方面的应用)中.参与者更希望将真实数据用 未知值(Unknown Value)代替,而非一个“错误值”(False Value)。文献[25] 讨论了一个将数据阻塞应用于关联规则挖掘的具体例子。由于不可知数据值的 引入,支持度和置信度的定义有所不同——最小支持度和最小置信度分别用最 小支持度区间和最小置信度区间代替。因为对于某条敏感规则,其支持度和/ 或置信度落在这个区间范围内,所以数据本身的机密性可以得到保证。同时, 在具体算法设计时,要保证l、0值在一定几率下交叉替换成不可知符号(问号 ~?),否则其所代表的含义就被破解,也就起不到隐藏信息的作用[25,26]。总 的来说,关联规则的隐藏有两种方法:减小产生本规则的数据集的最小支持度 和减小规则的最小置信度。 3.集中式阻塞数据集上的分类规则隐藏 文献[27]给出了一个将分类规则分析(Classification Rule Analysis)和 谨慎(吝啬)降级(parsimonious downgrading)结合起来的框架。在分类规则框 架中,数据持有者一般会尽量将类标签对应数据值阻塞起来,这样数据的接受 者就不能从这种降级后的数据中获取有意义的信息模型。谨慎降级是一个将从 安全环境(高安全环境,用High表示)到公共环境(低安全环境,用Low表示) 信息流动进行形式化的框架,其前提是存在一定的推理渠道。谨慎降级方法中, 对于潜在的、可能无法到达Low的被降级的信息,有一定度量规则。此文献的 目标在于探讨是否有必要为了降级某些信息,而增加High本身的保密程度。 这种降级所使用的技术,需要用到所谓的参数基本集(Parametric Base Set)。在这种方法中,不是用上文提到的未知符号,如问号,来代替要阻塞的 数据,而是置入一个参数口,0≤0≤l,这个参数表示此属性可能去某值的概率, 然后计算初始的整体信息熵和阻塞后的信息熵,它们之间的差再与Low方面用 决策树分析所得的规则置信度的降低作比较。决定这种方式所增加的安全性是 浙江大学硕士学位论文 不是大于从High到Low之I.白J数据实用性降低的幅度,即作出是否值得付出数据 实用性降低代价的判断[27]。 3.2基于密码学的方法 考虑这样一个问题:一组计算的参与者,他们之间互不信任,但是他们希望 安全地计算一个约定的函数,这个函数的输入由这些参与者提供,这里安全地计 算一个约定函数的意思是:即使在有不诚实参与者的情况下,每个参与者都能得 到正确的计算结果,同时每个参与者的输入是保密的,也就是说一个参与者无法 得知另一个参与者的输入(除非某些参与者的输入可以从函数的输出推导而得), 这就是著名的安全多方计算(gecure Multiparty Computation,SMC)问题[6,28, 48]。早在20世纪80年代,文献[13]中就有这个问题的雏形,而文献[6]从数据挖 掘中隐私保护的角度把它较为系统的提出来,成为PPDM~个重要分支。 如果有可信第三方(Trusted Third Party,TTP)的存在,这个问题很容易解 决,参与者只需将自己的输入加密传送给TTP,由TTP计算这个函数然,后将计 算结果广播给各参与者,这样每个参与者都得到了正确的结果,同时自己的输入 也是保密的。但是这时候TTP就成为了整个解决办法的关键同时也是问题解决的 薄弱环节。只要通过不正当手段将其攻破,则整个解决办法崩溃。所以很难找到 这样一个所有参与者都信任的,可以保障各自信息安全同时又可以进行全局计算 的TTP。安全多方计算的研究主要是针对无TTP情况下,如何安全地计算一个约定 函数的问题。它除了可以解决类似经典的百万富翁比富[13]问题外,在电子选举、 电子投票、电子拍卖、秘密分享以及门限签名等场景中有着重要的作用[6,11,28, 48]。可以预见,在当前电子商务兴起的背景下,安全多方计算技术将会越来越 广泛的被应用到各种网络环境和交易系统之中。 安全多方计算一般发生在分布式网络环境下,不同参与者持有不同数据,确 保输入之间的独立性、计算结果的正确性以及参与者之间无法获得对方的隐私信 息成为很大的挑战。 文献[28]对SMC方法和应用作了一个综述,并给出了一个将常规计算问题转 换为SMC问题的框架。还有很多学者探讨了各种数据挖掘问题和应用到sMc问题的 转换过程,其中包括分类、聚集、关联规则挖掘、数据泛化、数据概化以及特征 化等等。文献[47]针对比较基础而简单的情况,安全双方问题(Secure Two—party Computation,STC)提出了一个较为赢效的运算框架和一些工具性质的基{}}:操作 (Bui lding Blocks)。 文献(29]提出了四种基于s∽的低级操作/运算来支持PPDM,其中有:安全和 运算(Secure Sum)、安全并集运算(Secure Set Union)、安全交集大小运算 浙江大学硕士学位论文 (Secure Size of Set Intersection)以及标量乘积运算(Scalar Product)。举 较为简单的安全和运算为例: 设要求的值越=∑“,,已知其值落在【o,n】区间; 准备:其中~个计算节点(Site)指定为主节点,ID为l,其余各节点ID分别 为2…s。 由节点1从[O,n】之间的均匀分布中取出~个随机数R,将它加到本地值地上, 并将值(R+/91)modn发送给节点2,由于R从【O,H】间均匀分布取出,所以 (R+U1)modn同样服从[O,n]间均匀分布,即,节点2得不到%的真实值,从而保 护了节点1数据的隐私:同理。对于剩下的节点Z=2…J一1,算法继续滚动,从而 节点7得到了值y:(R+∑l-I“,)roodn,仍然服从以上分布,节点;得不到任何数 j=l 据值的具体信息。然后节点,计算(R+∑o)modn=@,+V)roodn并将其传给节 点,+1。最后,节点J作同样的操作,并将计算结果发送给节点1。节点l知道月的 具体取值,可以从得到的结果中减去矗,从而获得了所需要的分布在各个节点的 数据的和的真实值。 我们分类讨论在SMC框架下已有的一些计算方法,由于问题本身的特性,参 与计算的数据都是分布在两个或两个以上的节点上的: 1.垂直划分分布式数据集上的关联规则挖掘 对于垂直划分的数据集而言,数据项是分布的,而且每个项集可能被划分 开来,位于不同的节点,从中挖掘敏感规则,可以通过找到数据项集(Itemset) 的支持度计数(Support Count)来实现。如果这个支持度计数可以“安全”计算 而得,我们就可以通过判断它是否大于所设定的门限而决定这个数据项集是否 属频繁项集。而计算支持度计数的最关键之处,在计算表示位于不同节点,或 属于不同所有者的各孑数据项集的向量的标量积[9,21]。即,如果可以“安全” 计算标量积,则可以“安全”的得到支持度计数。文献[30]中提出了一种利用 随机数屏蔽真实值的标量积安全算法,它的“安全性”基于这样的事实:我们 无法通过解k个联立方程,求出数量大于k的未知数——其中多余k个的未知 数的值,用随机选择的值代替,因而保证了数据的安全性,文献[31]也提出了 类似算法,或者使用文献[29]中提出的标量积算法。 浙江大学硕士学位论文 2.水平划分分布式数据集上的关联规则挖掘 对于水平划分的数据集而言,情况比垂直划分要简单许多,因为数据项的 不同记录分布在不同节点,一个项集的总体支持度计数就是在各节点支持度计 数的简单加和。对于一个项集x而言,若总体的支持度计数超过整体数据总数 的s%(门限值),则它就是频繁的,或称整体支持的(Global Supported)。文献 [32]使用前文提到的安全并集运算(Secure Union)和安全和运算(Secure Sum)[29]对文献[33]中提出的分布式环境中关联规则挖掘算法作了改进,使其 适用于SMC环境。 3.垂直划分分布式数据集上的决策树生成 文献[34]研究了垂直分布数据集上的决策树分类器构造,它所提出的方法, 基于安全标量积协议[29,47],并使用了一个第三方的服务器。 4.水平划分分布式数据集上的决策树生成 文献[6]提出一种在sMc框架下解决分类问题的方法——对水平划分数据集 使用所谓的遗忘传输(Oblivious Transfer,OT)协议。它关注决策树方法,并 讨论了最常用的ID3决策树算法,这个算法通过信息增益的计算与比对,每一 步均选择最佳分类预测属性,来提高数据分类的效率和准确度。[63中的ID3计 算过程调用了众多安全计算的子过程。 5.保护隐私的聚类方法 文献[29]提出了一种使用“期望最大化”(Expectation Maximization,EM) 算法[35]进行安全聚类的算法。这个算法利用上文所述的SMC框架下的安全和 操作[293进行迭代计算,最终实现了隐私信息保护聚类。 3.3原始分布重构方法 许多PPDM算法基于原始分布的重构技术,即各数据持有者对涉及隐私的原 始数据进行扰乱,并在数据集成时对源数据的分布进行一定精度的重构,再进 行挖掘处理。下面分类讨论这些方法。 1.数值型数据分布的重构 文献[2]最早提出了这样的问题:在数据各自具体值被经过扰乱处理之后的 数据集上,怎样进行决策树的构造?当然,我们无法从扰乱后的数据中精确恢 复最原始的数据中各记录项的各字段具体值,否则这种扰乱就是失败的,无法 保护数据的隐私性。但是,可以通过~定的方法,较为糟确的重构原始数据的 分布情况。通过这种方式,可以在扰乱后的数据集上构建决策树,其预测精度 堪比原始数据集上构建的决策树。为了对原始数据进行扭曲,文中还提出了~ 种离散化的方法和一种数值扭曲的方法,并利用贝叶斯公式从扰乱后的数据集 浙江大学硕士学位论文 上重构原始数据分布的概率密度函数。为了构建比较精确的决策树,文中还针 对原始数据的不同分布,提出了三种不同的算法。 文献[35]基于贝叶斯方法,提出了对文献[2]中重构过程的一种改进——利 用所谓的“期望最大化”(Expectation Maximization,EM)算法,并证明,在 扰乱后的数据集上,EM算法可以得到原始分布的极大似然估计(Maximum Likelihood Estimate),且当可获取的数据量足够大的时候,EM算法给出了原 始分布的强估计(Robust Estimation)。 2.二进制及已分类数据分布的重构 文献[9]和[36]对在二进制和已分类数据上进行关联规则挖掘的情况进行 了讨论。二者都使用了随机化方法,并且得出类似结论:可以在保持较高数据 可用性条件下维护数据的隐私性。 3.4各种方法的质量度量 为了更好的研究和评估PPDM算法和工具,有一套适当的评估标准,或测试 基准(Benchmarks)是相当重要的。通常情况是,没有任何一种PPDM算法,在任 何方面都胜过其他算法,当然,有些算法在特定方面优于任何其他已有方法, 如在性能(Performance),或数据实用性(DataUtility)等方面。如果有了一些 评定标准,用户就可以根据持有的数据、所需要的挖掘结果以及其他一些情况, 选择合适的技术。我们认为对于PPDM方法,可以从以下几个方面加以度量: 算法性能(Performance):主要考虑时间上的性能,即对此算法,隐藏某~ 特定敏感信息集合所需要的运算时间; 数据实用性(Data Utility):可以由经过PPDM算法后的信息遗失 (Information Loss)来衡量; 不确定性级别(Uncertainty Level):被隐藏的信息在多大程度上可以仍旧 被使用某些方式直接获取; 对非目标挖掘算法的阻力(Resi stance):莳子隐私隐藏方法大都针对一种或 某几种挖掘算法而言,所以,如果末授权数据用户,甚至恶意攻击者可能采取其 他挖掘算法,在这种情况下,能在多大程度上保护信息的隐私性。 1.算法性能 对于各PPDM算法而言,评估其性能最直观的方法当然是通用的方法——估 算其时间复杂度。如一个时问复杂度o(n2)的算法在性能上要由于时间复杂度 为o(e”)的算法。 一种替代的方法是,对一算法,考察其在令某些敏感信息的暴露程度处在 浙江大学硕士学位论文 某个门限值以内的前提下,所需要的平均操作步骤,然后估算出所需的时间。 这种方法并不是一种绝对的度量方法,但可以作为不同算法间相互比较的一种 比较快速的方案。 当然,数据可能分布在不同节点之上,这些协作节点之间进行数据通信所 需的开销也是必须考虑的一个因素,在PPDM框架下应尽量将其控制在最小范围 内。 2.数据实用性 PPDM过程最后阶段,需要考虑数据的实用性,这是一个非常重要的指标, 因为为了隐藏敏感数据。贩始数据被加入了各种混淆性的内容,或者加入了其 他一些非常规字符等(如在阻塞过程中加入“?”号)。当然,在一些PPDM技术 应用过程中,原始数据库中的数据并未发生改变,如数据抽样处理等,但是如 此一来,信息的完整性被破坏了,所以还是一样降低了数据的实用性。明显地, 对原始数据库的改动越多,改动后的数据对原本的兴趣域(Domain of Interest) 的反映程度就越弱[2,I 1,35]。所以,数据实用性一个比较直观的度量方法, 就是经过某PPDM算法处理过程后,所发生的信息遗失量/率。当然,这种信息 遗失的具体度量,依赖于所使用的特定数据挖掘算法以及隐私保护算法。 举例来说,关联规则挖掘中,信息遗失可以通过数据清洗前后,保留下来 的和被排除的规则数目来衡量,或者甚至可以用各规贝lj支持度和置信度的升高 和降低程度来衡量[9,21]。而对于分类方法,也可以采用类似度量规则。而对 于聚类而言,处理前的数据和处理后的数据很大一点不同在于它们各自之间的 距离可能发生了变化,这种距离的变化,是衡量信息遗失的基础。 3.不确定性级别 隐私保护策略,简单来说其实就是对原始信息进行处理,将其暴露程度降 低到一定的门限以下。但是,被隐藏的信息,还是可能在一定的精度,或称不 确定性级剐上被推理,或者恢复出来【35]。所以,这些算法还需要这种不确定 性级别的度量,来反应原始的数据和信息可以在多大程度上,在多大可能范围 内被直接重构出来。 4.对非目标挖掘算法的阻抗 数据/信息隐藏算法的终极目标,就是防止~些未授权的操作破坏信息隐私 性或泄露某些敏感信息,所以,应该防备攻击者们和数据窃取者们利用各神数 据挖掘算法本身来发现和发掘隐私数据和信息。而且,针对某一特定挖掘算法 设计的信息保护和原始数据处理算法,可能不保证对其他挖掘算法也能起到类 似的保护作用。 为了对特定数据处理方法进行全面的评估,我们需要衡量它对所针对的数 据挖掘算法之外的算法的“阻抗”,或称作“横向强度”(Transversal ——一一 塑婆查兰堡主兰堡笙塞 Endurance)。需要获取这个度量参数,我们需要针对许多数据挖掘算法做测试, 为了简化这个过程,可以从所需角度,对已有数据挖掘算法进行一定的分类, 在同一类算法中,只要取出一种典型的进行度量,就可以代表目标数据处理方 法对这一类算法全部的阻抗强度。 -28, 浙江大学硕士学位论文 第四章随机数据扰乱PPDM重构的改进 由第三章讨论的PPDM问题的分类,如果把阻塞方法也算作一种随机化的方 法,PPDM问题的解决方案主要就可以分为两大类:随机化(Randomization)方 法[2,3,4,5]和基于密码学的安全多方计算(Secure Multi-party Computation,SMC)[6,7,28]方法。随机化方法中最具代表性的是随机数据扰 乱(RP)【2,3,4]和随机响应(RR)[5]两种模式,接下来的两章中,我们主要探 讨这两种模式。对于随机数据扰乱方法,我们注意到它在于数据集属性变量之 间存在的相关度较高时潜在的隐私泄露和性能方面的问题,提出一个模型将其 进行一定的改进:而随机响应本身时统计学中使用的方法,我们可以将它与数 据挖掘算法相结合,从而保护用户的隐私信息,主要考察其与决策树分类算法 和与传统关联规则挖掘算法相结合的应用。 4.1随机数据扰乱方法的提出 随机数据扰乱方法,简单的说,就是将某一随机量添加到需要保密的数据 上,如,对要保密的数据值“,,数据所有者将数值“。+,提供给数据挖掘应用, 其中r是符合某种分布的随机噪声,给出其分布则可由扰乱后的数据在一定程 度上重构原数据的分布[2]。基于随机数据扰乱模式的PPDM关注保护原始数据 和对数据挖掘应用的支持两方面。其中数据挖掘应用关注的是模式化、知识化 的信息,而非具体数据值,所以,只要从随机化后的数据中能够在一定精度范 围内建模原数据的统计特征或建立模型,就可以认为是成功的应用,具体的如 在扰乱后的数据上进行决策树建模[2,8]或关联规则的挖掘[9,21,22,23,40] 等。 4.1.1方法的具体步骤 由方法提出的背景和目的可知,此方法分为两个步骤: 第一步,对原始数据进行扰乱以保护隐私数据。设原数据项为钎,,则数据所 有者提供数据“,+r,其中r为从某一特定分布中取出的随机值,通常使用的是 卜口,口】区间的均匀分布(uniform distribution),或者均值∥=0、标准差为口 浙江大学硕士学位论文 的高斯分布(Gaussian distribution)[2,3]。n个原始值“l,“2,.“。NNg见Nnq" 独立同分布的随机变量Ui(扣1,2,.功的具体值,这个同一分布的随机变量记为 U。而为了进行数据扰乱,必须产成n个同分布独立随机数n,r2,¨.厶,其分布对 应随机变量R。这样,数据所有者提供扰乱后的数据序列“,+_,“2+屹,..“。+‘, 以及随机量R的分布函数R(,),为了发现原始数据的分布规律,实现数据挖掘 的目的,我们需要从扰乱的数据中迸行原始分布的重构,即从中获取昂(“)。 第二步,对扰乱后的数据实施计算以获取原始数据的分布规律——计算 鼻,(“)。由第一步的处理看出,已知条件包括两方面:wf=“。+‘,i=1,2…”以及 吩(,)。由贝叶斯公式,若记U+R=∥,随机变量u的后验概率巧@)可以由下 式计算[2,3,4]: 咖):兽坐坐丝 [^(w—z)万(z)出 』!!!二!选塑 ..,;,啊)= (4t1) (4.2) e^(w—z),U(z)出 其中,厶(.)和兵(.)分别表示u和R的概率密度函数,由前文,我们有11 个独立实例,所以可以通过求均值获得后验分布: 椭=1。智争肪fR((w一-u)眦fv(u)函 ‘4?3) 由(4.3)式,如果提供足够大的样本空间,即iq足够大,则』j(“)可以逼迸 石,(“)。但实际应用中,因为正,(“)并不可知,而且它正是我们要得到的目标分 布,所以(4.3)式的中出现的/;,(“)必须用其他可得的值代替[2,3]。如迭代方 法,即将每一步,=1,2…,将前一步所得的后验概率密度函数彤。(“)带入计算, 并利用一致分布密度函数进行初始化,当两次计算结果小于某一闽值时,迭代 停止。为了加快计算速度,可以将数值划分区间,N--N间所有数值皆以近似 值代替,只计算一次,减少了计算次数,节约了时问[2]。 浙江大学硕士学位论文 4.I.2重构存在的问题 原始的随机扰乱方法,让所有属性变量都参与计算,计算结果作为数据挖 掘的输入。这带来了两个问题:计算效率不高,当数据达到一定量级,速度下 降很快;更严重的是,如果原始数据中各属性变量相关性较高的话,即使假如 随机扰乱也难以破坏其相关性。例如对于原数据集中某属性变量4.,若有其他 某些属性变量与其高度相关,则对于4.就有了足够的冗余信息,由此可能对其 取值进行较高精度的估算,即从扰乱后的数据中推算出部分原始数据,这就严 重背离了数据隐私保护的初衷[3,4]。 4.2利用PCA增强随机扰乱方法 4.2.1 PCA方法实施 Component 主成分分析(Principal AnalysiS,PCA)是一种经典的多元统计 分析技术。Pearcon于1901年首次引入主成分分析的概念,Hotelling在30年代对 主成分分析进行了发展[38]。如其他多元统计分析一样,在计算机出现之前,主 成分分析应用面很窄。当计算机出现后,主成分分析得以广泛地应用。 主成分分析的中心目的是将数据降维,以排除众多信息共存中相互重叠的 信怠,它是将原变量进行转换,使少数几个新变量是原变量的线性组合,同时, 这些变量要尽可能多地表征原变量的数据结构特征而不丢失信息。新变量互不 相关,即正交【38]。所以,利用PCA对必要属性变量进行约简后再计算、分析 [3,4,lO],可以在一定程度上解决由于属性间相关性引起的隐私泄露问题。 当然,这种约简可能导致信息遗失(Information Loss),但这种信息遗失的程 度,在可控范围之内。基于PCA的数据重构(Data Reconstruction)可以称作 PCA—DR。 1,PCA及PC的构造 PCA可用于构造一种基于数据相关性来减少数据集维度的方法。如,若一数 据集由m个属性变量组成,每个属性可能有”个值,则可以视作聊个转置的向 量。通过PC&可以将其缩减为Ps胧个属性,这P令属性彼此无关,且按照向 量内部方差大小排列,这些属性及其数据值中就包含了大部分原数据的信息, 称为主成分(Principal Component,PC)[i0]。通过PC,我们可以减少数据维 度,利用Pc计算出所需结果后,再进行原数据的恢复。 浙江大学硕士学位论文 Pc可以如下计算: 第一步。先计算包含聊个属性变量的原数据集D的协方差矩阵C。C的定义 如下: C¨=Cov(d,,d』).1≤f≤肼,l≤i蔓珑; 第二步,通过c,计算D的特征向量k,8:,.P。】及各自对应的特征值 五,五2,.五。,其中A≥五2…≥丸; 第三步,构造m×P维矩阵E=眩,e”。。】,计算D。=DE,则砩为n+P的 矩阵,其中中属性变量个数从m降到了P(P≤愀),构造完毕。 当然,PCA方法实现数据降维的同时,保持了原数据集中的部分信息。从 Pc获取原始数据有两种情况: 第一种,P=m,即无属性变量精简,则E为正交阵,即E~=E7, D=nE一=DnE。: 第二种,P<脚,有属性变量被精简,则只能得到估计值D=见占7。 2.将PCA应用到随机化数据重构中 将PCA应用到保护隐私的数据挖掘领域中时,可能遇到各种问题,因为原 始数据的协方差等统计规律未知,可得数据集都是经过随机增量扰乱后的数据 集[2]。所以,数据重构必须通过一些特殊的方法,而且应发现其重构精度具有 的规律,从而尽量提高它的值。重构过程有两个步骤: 第一步,原始协方差矩阵的估算。 由Pc定义及计算方法,需要知道原数据的协方差矩阵,但是原数据的统计 规律正是我们挖掘的目标,这是不可知量,也是PPDM问题的特点所在。所以, 我们需要通过已知的扰乱后的数据和随机量的分布来获凝这个矩阵c。 假设X.和Ⅳ.分别表示原始数据集中的两个属性变量,则经过扰乱后它们分 别变为x;+R,和x。+R,,其中R、Rj为数学期望为0的随机量(如果其数学 期望不为0,总可以通过每个具体值减去其总体期望,将其调整到0,在结果中 再加上总体期望,回复原值【2,3j),Cov(X。十R,,x,+R,)表示扰乱后数据的 扔方差矩阵的第(f,J)项, 则由协方茬定义: Cov(X;,X,)表示原数据的协方差矩阵的第({,』)项。 浙江大学硕士学位论文 Cov(X:+Ri,X;+R}) =N(x,+R,)(x,+灭J)卜E(Xf+R,)E(x,+RJ) =E(X,Ⅳ,)4-E(置)E(R,) +E(R,)占(x,)+E(R。R,)一F4X,)E(X,) =E(x,x,)4-0+0+E(R,R,)一E(Xi)E(x,) =Cov(X,,名,)+E(R。R,) 而当i≠J时,R。、R1相互独立,E(R。R,)=0;当i=J时,E(月。R,)=盯2, 其中,盯为随机变量R的标准差。由此,可以从已知的协方差矩阵和随机变量 分布,求得原数据协方差矩阵。 (4.4) cDV(Ⅳ。,石,)=lCco鲫v((Xx,,++震R,,,,Xxj,++R兄j『),)--当cr2j,≠当J‘=_, 当然,这种计算方法基于统计规律,得到的只是近似值,但当样本数量足 够大的时候,计算结果将越来越精确。 第二步,实现重构。 由第一步得到的协方差矩阵(近似值),我们可以作如下构造:利用PCA构 造_C=-QAQ7,其中A为特征值组成的对角阵,Q是由特征向量构造的正交阵。 若我们要选择的Pc数为P,则令O为Q的前p列;则原数据重构可以通过下式 进行: 岩:短豆7,其中y为扰乱后的数据,j为最终估算值。 当然,如果P=m,计算结果就是j,本身;如果p<m,则出现信息遗失, 若原数据属性间相关度大,则遗失程度较低,否则遗失程度较高。下文将量化 讨论。 4.2.2重构精度分析 利用4.2.1中提到的方法,可以对原数据进行一定精度的重构,得到 力=垃07,将其展开: 童:(z+R)@@r=短@7+R007(4.5) 可见,叠与原始数据Ⅳ之间的偏离来自两方面:柏盆7引起的和矗垂垂7引 浙江大学硕士学位论文 起的,而前者由原数据属性变量之间的相关性决定[3,4],所以,主要讨论后 者对最终偏离的影响,即考察R@垂7与p、m以及R的分布特征之间的关系, 主要考虑由R垂扩引起的均方差偏离。其中R为仰×m)随机量矩阵,门为数据 集的记录总数,掰为属性变量个数。简单起见,先对于某一m阶方阵A,考察 刚: ∑^熙。 I=】 ∑‘,d。, 』=I 删= ∑‰口fl izl ∑o。。 f=1 则删第一列的均方差:去∑(∑oflil)=去∑∑(∑o‰allakt)。考察括号 “,=I‘=l ,‘i=1 k=l J=1 中的部分 00 胁 % 当 卜= 砸 lI L埘 , @回 ∑o乍q.% 严l Il ,K—、 1一聆l一聆 。∑尉。∑川 f ‰0 胁 以 当 ≠ 媳J 一一 _二 朋 她 刀 当雎足够大时,(4.6)式变为:d2口。2:而5≠f时,由随机量的分布有 £(兄成)=E(R)E(置)=。,即当n足够大时,(4.7)中的丢喜。如2。,可得删 第一列均方差为;仃:羔q.2。同理可得其他列的均方差为:盯2芝鲰2,女=l,.,跏., 所以,可得各列的总体均方差,即脚的均方差为: ∥一m 。∑M 。∑Ⅲ 口 (4.81 下面,将4替换成垂@7,其中 浙江大学硕士学位论文 Pi qp e. . ● , 一 %, ll 圭%% 厶‰ I=1 .Q .Q |f ... ,带入(4,8)得到均方差 ,. 。 L PⅢ P 卵 vo io几 F ● p 一 %p 、 ● 、,● / ∑‰% i=1 ∑‰% 鲁善薯c鼢。2=詈2善p善c善m善m ejie/ae]te灯M.。, 考 察 (4.9) 括 号 中 部 分 , 如 下 ∑∑e,e。e,,e。,= ∑e孟∑%2、一、i=r,s=1…p)=l(‘.‘Q为正交阵) “1 7“ ,代入(4.9),得 ∑e,.e,,∑e。。。,(当{≠f)=oc.’Q为正交阵) 由月垂Q7引发的PCA均方差为:玎2旦。它与随机量足本身的特征有关,还与属 m 性精简程度(旦)相关。 m 4.2.3结论与下一步工作 可见,在进行属性精简之后.由月@垂7,即随机量引起的偏离虽然只是两方 面原因之一,但可以看到,总体偏离与随机量方差盯2和属性精简比例(兰)之间 _l’2 分别存在着线性关系。即,在加入PCA的随机化隐私数据保护环境中,随机量 本身方差仃2以及保留作为Pc的属性数量增大将使结果数据方差增大,即更好 的保护了数据隐私(难以从结果数据恢复原始数据)。 而由宕=(x十置)垂§7:短壹7+碰垂7可见,属性精简度高(即P较小 的情况).则由前半部分引起的偏差大,后半部分引起的偏差小,仃2只影响后 半部分。怎样在原始数据包含信息的遗失与隐私保护两者中间找到合适的平衡, 是下一步的工作的目标。 浙江大学硕士学位论义 第五章随机响应与数据挖掘算法的结合 5.1随机响应方法的提出 随机响应(Randomized Response,RR)技术是在统计学中为了保护被调查者 的隐私而设计的一种数据隐藏技术,首先在文献[38]中提出。基本方法是:为了 解一群人中具有(可能涉及隐私的)属性A的百分比,需要对这些人进行调查, 由于被调查者可能不愿意回答或做出与事实不符的回答。在相关问题模型 (Related Question Model)[5]中,首先对属性A设计两个互为否定的问题,例 如: 问题1:被访者具有敏感属性A? 问题2:被访者不具有敏感属性A? 对每个问题的回答均为是(yes)或否(nO)。调查者首先确定一个实数 0∈fo…1】,被调查者通过随机函数产生一个0到1之间的随机实数r,若r≤0, 则被调查者回答问题1,否则回答问题2,即以概率0回答问题1,以概率l一0回 答问题2。尽管调查者知道被调查者回答的是yes或[tO,但并不知道后者到底 回答的是哪个问题,从而保护了被调查者的隐私[5,40]。 假设分别用P+(一=yes)和P+∽=no)来表示被调查者回答为yes和nO的百 分比。则可以通过下述方程组求出被调查群体中具有属性A和不具有属性A的 百分比的近似值P(A=yes)和P(A=御)[5]: f尸’(爿=yes)=P(A=yes)?口+P(A=”D)?(1一口) iP’(A=no)=P(A;yes)?(1~臼)+P(A=no)?(D f与1、 由这个方程组可以求出P(A=yes)和P(A=月o)。显然,当0≠0.5并且被调 查人数很多时,这两个近似值的误差就足够小。 5.2与决策树分类算法结合 下面我们关注这样一个问题:怎样在前文所述的随机响应技术伪装的数据 集上进行决策树分类器的构造。这个问题可以这样描述: 某数据挖掘搭建者A需要从不同的数据持有者处搜集数据,并构建一个中 浙江大学硕士学位论文 央集中的数据库系统,然后在这个数据库上进行数据挖掘具体应用。A向各数 据持有者发送调查问卷,这些问卷包括了N个问题,A要求所有接收到这份问 卷的用户回答这些问题,并将答案发送回来。但是这些问题包括了一些敏感性 问题,并不是所有接受者都愿意给出他/她们的答案。A要怎样才能在不需要知 道问题接受者过多信息,尽量不让被访者隐私暴露的基础上,得到尽可能多的 信息,同时建立较为精确的决策树分类器? 可以使用随机响应方法,我们分别对建立决策树过程的三个步骤进行讨论: 数据搜集、决策树建立测试和剪枝。 5.2.1数据的搜集 随机响应方法最早提出的时候,只针对一个属性[38],然而,在数据挖掘 条件下,数据集都包括了众多的属性,发现这许多属性之间的关系,也是数据 挖掘的一个主要目标。所以,我们需要扩展随机响应技术,使它在支持多属性, 并且支持多种挖掘计算。早在上世纪80年代初,文献[39]就提出了用包含多个 问题的问卷进行调查的方法,但是,其中的方法只适合于数据维度很低的情况 (一般数据维度为2),无法扩展到如今复杂的、包含众多数据属性的数据挖掘 环境。针对数据挖掘的环境,我们利用多元随机响应(Mu]tivariate Randomized Response,MRR)[5,39]技术,并将其应用到隐私数据集上的决策树分类器构建 上,克服原始随机响应方法太过简单的不足之处。 假设我们要进行挖掘的数据集上有N个属性,E表示这些属性组合的一个逻 辑表达式。P’(E)为扰乱/伪装后的数据集上所有满足E=true的数据记录所占 的比例,而P(E)为原始(未经扰乱和伪装)数据集上使得E=true的数据记录所 占的比例——当然,原始的数据集无法直接得到,就是说,对于我们的挖掘应 用,它是不存在的。P’(五)可以从扰K/伪装后的数据集上直接计算出来,然而 P(E)才’是我们真正感兴趣的东西,却无法直接得到,因为任何一方未能持有整 个未扰乱的数据集,我们必须通过某种方法,由已知的信息来估算P(E)。MRR 就是这样的一种方法,由己知信息,结合P‘(E)来对P(E)进行一定精度的估算, 在保护隐私信息的前提下获取有用的统计概率信息。 为简单起见,且不失一般性,我们假设所有数据都是二进制形式的,我们 以合取式(4.=1)^(爿:=1),、(^=O)为例,假设我们想要得戮 浙江大学硕士学位论文 p(AI=1^A2=l^A3:O),或将P(Al=1AA2=1AA3=0)简记为P(110),将 P(A1=0^A2=0^A3=1)筒记为_P(001),依嫩类推。 由前文所述的关联模式(Related Model),被访者以概率0回答所设定的敏 感问题(或称为说真话,tell 悦谎话,tell the the truth[5]),以概率1—0回答相反的问题(称为 lie[5])。以上一段提到的例子来说,若被访者对于属性 A。、A:、A,的真实值是110,用户端在【O…1]区间产生一个随机数,如果这个随 机数小于0,则他/她发送llO给数据搜集端(说真话),否则,如果这个随机数 大于移,他/她发送001回数据搜集端(对所有闯题,都说谎话)。因为数据搜集 端并不知道被访者这一边到底产生了一个怎样的随机数,所以就不知道所搜集 到的数据到底是真实值的集合还是非真实值的集合,从而无法知道被访者所不 愿意公开的信息,保护了被访者的隐私数据C37.38,39] 由于P+(110)和P+(001)分布都是部分由e(110)来,部分由P(001)来,我们 得到方程组: 』P'(110)=尸(1lo)。口+P(001)‘(1一口’ 【P’(001)=P(001)?0+尸(110)?(1—0) (5.2) 联立而解之,可以求得P(001)和P(110),这是建立决策树所需要的信息。 5.2.2决策树建立 数据分类(Data Classification),是数据分析的有效方法,可以发现模型、 揭示数据的类剽,或者预测将来数据趋势。其核心步骤是在己有数据的基础上 进行学习,得出一个分类函数或构造出一个分类模型,即我们所说的分类器 (Classifier)。这个方法已经被分别从机器学习、专家系统以及统计理论角度 加以研究,作为知识发现的~种解决方案。分类,一般有两个步骤[1]: 第一步,建立一个模型,描述预定的数据类集或概念集,通过分析由属性 描述的数据库元组来构造模型。其中数据元组也称作样本、实例或对象。假定 每个元组属于一个预定义的类,幽~个称作类标签属性(Class Label Attribute) 的属性确定。为建立模型而被分析的数据元组构成训练数据集,其中的单个元 组称作训练样本,由样本群中随机抽取。由于提供了每个训练样本的类标签, 该步骤也称作有指导的学习(即模型的学习在被告知每个训练样本属于那个类 的“指导”下进行)。它不同于无指导的学习——主要指聚类,聚类方法中每个 训练样本的类标签是未知的,要学习的类集合或数量也可能事先不知道。 {j:Ji江大学硕士学位论文 第二步,使用模型进行分类。首先评估模型(分类法)的预测准确率,将一 些已经归好类的样本数据作为输入,测试分类器的分类结果。对每一个样本数 据集,比较已确定的类标签和分类器的预测结果。如果模型的准确率根据训练 数据集评估,评估可能是乐观的,因为学习模型倾向于过度适应(Over-fitting) 的数据[1,2,5],即,它可能并入训练数据中某些特别的异常,这些异常不出 现在总体样本群中,因此,一般使用其他的测试集。如果认为模型的准确率可 以接受,就可以用它对类标签未知的数据元组或对象进行分类。 还需要提到预测和分类的不同之处:预测(Prediction)是构造和使用模型 评估无标签样本类,或评估给定样本可能具有的属性值或值区间。在这种观点 下,分类和回归是两类主要预测问题,其中分类是预测离散或标称值,而回归 则是用于预测连续或有序值。然而,在数据挖掘领域被一般接受的观点是[1, 41]:用预测法预测类标签为分类,用预测法预测连续值(例如使用回归方法) 则称为预测。 决策树就是一种分类方法,它递归的对训练数据集进行划分,直到每个划 分只包含属于一个类的样本数据为止。它是一个类似于流程图的树结构,其中 每个内部节点表示在一个属性上的测试,每个分支代表一个测试输出,而每个 叶节点代表类或类分布。树的最顶层节点是根节点。一棵判断某商场中的顾客 是否购买计算机决策树可能呈现如图5.1的形状: 图5.1指出某商场的顾客是否可能购买计算机的一棵决策树 一个常用的算法是ID3算法[1,5],ID3算法在所有可能的决策树空间中采 用一种自顶向下、贪婪的递归搜索方法。假设S表示训练数据集(Training Samples),AL表示属性列表(Attribute List),则算法可以表示如下: 算法:ID3(S,AL),由给定的训练数据产生一棵决策树 输入:训练样本集S,由离散值属性表示;候选属性列表AL —— 一 塑婆盔兰堡主兰垡堡苎 输出:一棵决策树 1.创建~个节点v 2.If S中所有样本数据属于同一个类c 地为空 //多 then节点V作为叶节点返回,以类C标记 3.If then节点V作为时节点返回,标上s的主类(即S中最普通的类) 数表决 4.从AL中选择信息增益最高的测试属性(Test Attribute,TA) 6.将V标为TA 6.For TA中的所有值a。 //划分样本集S (a)从V上由条件TA=a,生出新的分支 (b)设s。是S中的数据集,s。满足TA-玎, (c)If s,为空 then加上一个标上S主类的叶节点 (d)E1se (递归)加上节点:ID3(J.,AL—TA). 由算法描述可以看出,所有菲畸苇点都有一个“分又点”<S西ittingPoint), 而建立决策树过程中最核心的任务就是基于信息增益(Information Gain)的计 算,为每个分叉点确定其所依据的属性。信息增盏豹计葬可以通过信息熵 (Entropy)来进行,假设整个训练数据集中有111个类,则信息熵Entropy(s)定义 如下: Enf,opy(S)=一∑9 logQ, (5.31 其中,Q,是类J在see出现的相对频度(Relative Frequency),有了信息熵的 计算方法,我们可以计算用来划分S的所有候选属性A的信息增益: G翻@4)=Entropy(s)一∑(斜默ropyiS’))(5.4) 其中,V表示属性A的所有可能取值:}S,{是指s,中包括的元素个数:{Sj 则是S中包括的元素个数。对某一节点而畜,要选择最佳的划分属性,我们必 须对所有候选属性都计算其信息增益,然后取使信息增益最大者为划分属性【1, 浙江大学硕士学位论文 5j。 如果数据没有经过扰乱、伪装,我们可以轻易计算得到所需要的信息增益, 但是,数据已经被施加了随机响应调查方法,信息增益台勺计算就变得不那么直 观易行了。因为我们不知道数据库中的一条记录到底是真实的(true)还是虚假 的(false),即,不知道“被访者”到底回答的是不是原来的问题,还是相关的 反面问题,所以我们也就不知道到底那些数据是属于原本的样本数据库s的, 就无法像原始的ID3算法那样,直接计算得到{S1、is,1、Entropy(S),或 Entropy(S。),我们必须通过一定的手段进行估算。 不失一般性,我们假设数据库中只存储了二进制数据,我们来探讨一下怎 样计算满足4=lAA,=0的节点V上的信息增益,其中,A。、A,为V的祖先节 点用于分支的两个属性。记S为包括属于节点v的样本数据的训练数据集,即 对于S中所有数据都满足A,=1^A,=0,这个中间状态的决策树形态如图5.2: N0d。蠢歹、刍 图5。2中间状态的决策树 设E为属性集上的一个逻辑表达式,户(E)为未经伪装的数据集(当然,现实 中这个数据集并不存在)上满足E=true的所有记录占总数据量的比例。由于数据 已经被伪装过,所以P(E)无法直接从伪装后的数据上计算得到,必须进行估算。 设P‘(E)为伪装后数据集上满足E=true的所有记录所占的比例,则P+(D可以直 接计算而得。 浙江大学硕士学位论文 为了计算1S J,我们令 E=t爿,=1)A L五,=O)?E=(A,=O)人t4,=1), 则在前面提到的相关问题模型的随机响应环境下,我们可以得到: m9邓(竺卯”忸).(1印) iP+(£)=P(E)?O+P(E)?(1一∞ (5.5) 由于P+(E)和JP+(云)都可以从伪装后的数据集上直接计算出来,所以通过解 (5.5),我们可以算出P(E)(当0≠0.5)。此时lSl-P(D?M,其中,n为整个训 练数据集的数据记录总数。 而为了计算Enwopy(S),我们必须先计算鳊和Q1,假设类标签也是二进制 形式,而且也经过了一定的伪装,令: E=(爿,=1)^(爿,=o)A(Class=O),E=(4f=O)A(爿J=1)^(Class=1), 当然,有时候,类标签并不是敏感信息,没有经过伪装,则关于类标签的信 息总是真的,我们就可以将以上定义稍作修改: E=(A,=1)^(A,=0)^(Class=0)r E=(A。=0)A(Aj=1)^(Class=0), 这样,我们可以从整个伪装后的数据榘上直接计算出P‘(E)和P+(君),再解 (5.5)算出P(E),这样一来,Qo=!静,而Q{=l—Qo?西缈卿@)就可以 计算了,需要指出的是,这里算出的ⅨE)与前蕊计算lSl时候的P(E)是不同的。 假设Ak是一个候选属性,我们要计算∞加(s,A。),我们需要值IS血;1f、 I瓯=o卜EnWopy(S4=1)以及Entropy(S4=o),这些值可以通过类似方法同 样求得,如要求1S。=11可以令; E=(爿。=1)i(爿,=0)^(S^二n,E=(爿,=1)^(4,;0)^◇^=0)? 同样解(5.5)可以获得P(E),而JS血;1卢|P(E)+n,『S^=Ol可以同样求得。 总之,这里的算法和原始ID3算法的主要不同之处在于P(E)的计算方法。 ID3算法中,数据未经处理,尸【£)可以计算通过数据库中有多少记录满足 渐江大学硕士学位论文 E2true直接计算而得;而在我们这里所讨论的框架中,这样直接计算只能得到 P+(E),是在伪装后的数据集上计算出来的,P(E)的非真实版本,而随机响应 技术可以帮助我们由P+(E)估算出尸(E),进而构造基于这些值的算法。 5,2.3测试与剪枝 为消除在决策树构造过程中的“过度适应”(Over—fitting)现象,一般做 法是用与训练数据集不同的其他数据集对生成的树进行测试,估算其精确度n, 2,5]。树的剪枝应在测试结果之上进行,即测试这棵决策树有多大程度上的精 确性。若在未经伪装的数据集上进行测试操作是直观可行的,但是,当测试数 据和训练数据一样,经过了伪装操作,测试就没有那么直观易行了。设想我们 从测试数据集中选取~个记录,利用决策树得到预测的类标签,发现这个类标 签和这条记录本身的类标签并不匹配(相同),可以直接得出本次测试,在这条 记录上的测试失败了吗?——如果这条记录中的是真实数据,可以得出这个结 论,但是如果这条记录因为经过随杌化处理不是真实数据,我们就不能得出这 样的结论。那么,怎样才能得到比较精确的决策树评定值昵? 答案是,我们继续使用随机响应方法。考察以下的例子:设属性个数为5, 概论常数0=0.7,为了测试记录01101(即对应第一个属性的值为0,第二个为 I.一依此类推),我们将01 101以及它的补10010作为测试输入,总有一个类标 签的预测结果是正确值,如果对于这两种输入,预测结果都是对的(或都是错 的),我们就可以对测试结果下一个比较糖确的结论。但是,如采01101的结果 是对的而10010的结果是错的,或反之亦然,我们只能作出准确率为O.7这样 的判断。但当测试数据集足够大对候,我啦】可以估算比较精确的精确率评定值, 下面是估算方法: 利用(伪装扰乱过的)测试数据集S,我们可以反转S中的所有数据值(1为 变0,0变为1)来构造另一个数据集夏,即,i中所有记录都是S中对应的记录 的补(Complement),我们将i称作数据集s的补,利用这两个数据集,我们可 以进行测试。同样,我们定义u表示原始的,未经伪装扰乱的测试数据集,盯 为U的补。用P’(correct)表示测试数据集S上正确预测结果所占的比例, F‘(correct)表示在S上正确预测结果所占的比例。P(correct)表示原始未伪 装数据集U上正确预测结果所占比例,P(correct)则为U上对应的比例,则 浙江大学硕士学位论文 P(correct)是我们需要估算的值。 同样的,P+(correct)和F‘(correct)部分由P(correcO,部分由-ff(correct)而 来,我们可以得到如下方程组: {三(c卯旭甜)2璺。。”卵f)?p+芦(∞rr卵f)?(1一口) iP’(correct)=P(correct)?0+P(correct)?(1一目) (5.6) 其中,P‘(correct)和芦’(correct)可以从测试数据集S和i直接求得,带入 (5.6)则可以解出P(correct),即此次测试所得的预潞精度。 5.3与关联规则挖掘结合 5.3.1关联规贝fJ挖掘 i.关联规则的提出和实例 关联规则挖掘目标在于发现大量数据中项集之间有趣的关联或相关联系 n]。随着大量数据不停的搜集和存储,许多业界人士对于从他们的数粥库中挖 掘关联圭见则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系,可以 帮助许多商务决策的制定,如分类设计、交叉购物和拍卖分析等。 关联舰则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其 购物篮中不同商品之间的联系,分析顾客的购买习惯。通过了辩哪些商品频繁 的被顾客同时购买,这种关联的发现可以帮助零售商制定销售策略。通过帮助 零售商有选择的经销和安排货架,这种信息可以引导销售,如爝顾客频繁“趣 绑”购买的物品放近一些,可以进一步刺激顾客的同时购买这些商品[1],另外, 关联规则发现的思路还可以用于序列模式发现,如顾客在购买物品时,除了具 有上述关联规律,还有时间上或序列上的规律,这次买这些东西,下次买同上 次有关的一些东西等等。 如果我们想象全域是商店中可利用的商品集合,则每种商品有一个布尔变 量,表示该商品的有无,每个购物篮可以用~个布尔向量表示,可以分析布尔 向量,得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规 则的形式表示。例如,购买计算机也趋向于同时购买财务软件可以用以下关联 规则表示(1]: computerjfinancial soft,rare[support=2%,confidence=60%](5.7) 规则的支持魔(support)和置信度(confidence)是两个规贝1j的兴趣度度量, 浙江大学硕士学位论文 他们分别反映规则的实用性(Utility)和确定性(Certainty),具体概念我们将 在下文讨论。如假设关联规则(5,7)的支持度为2%,置信度为60%,则意味着全 部事务的2%同时购买了计算机和财务软件,而购买计算机的顾客中有60%的人 购买了财务软件。一条关联规则,若满足最小支持度阈值和最小置信度闷值, 则认为它是“有趣的”,或称作“强规则”,可以作为本次关联规则发掘的结果 而表示、输出给用户,而这些相关阈值则根据用户或领域专家的需求或建议来 设定。 2.关联规则相关概念 设,={i,,i:,..,i。)是项的集合,设任务相关的数据D是数据库事务的集合, 其中每个事务T是项的集合,使得T£,,每个事务有一个标识符,称作TID, 设A是一个项集,事务T包含A当且仅当A∈T。关联规则是形如4号B的蕴 涵式,其中Ac』,Bc,,且AnB=庐。规则爿jB在事务D中成立,具有支 持度s,s是D中事务包含Au曰的百分比,即概率P(Au毋。规则AjB在事 务D中具有置信度C定义如下;如果D中包含A的事务同时也包含B的百分比 是c,即条件概率P(曰1一)。 support(Aj B)=P(AuB) confidence(A=,曰)=P(B l爿) 如上文所述,同时满足最小支持度阈值(min—sup)和最小置信度阈值 (min—conf)的规则称作“强规则”。一般用o%到100%之间的值来计数。 项的集台称为项集(itemset),包含k个项的项集称为k一项集。项集的出现 频率是包含项集的事务数,简称为项集的频率、支持计数,或计数。若项集的 出现频率大等于min—sup与D中事务总和的乘积,则项集满足最小支持度 min—sup,此时称为频繁项集(Frequent Itemset),频繁k一项集的集合通常记 做L。 5.3。2 Apriori算法 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法[1,42]。 它使用一种称作逐层搜索的迭代方法,即k一项集用于搜索k+l项集,最后生成 具备普适性的规则表达式:首先找出频繁卜项集的集合上1,再将上。用于找频繁 浙江大学硕士学位论文 2~项集的集合三2,£:用于找L,,如此下去,直到不能找到频繁k一项集为止, 找到每个£。需要一次数据库扫描(1]。 为提高频繁项集逐层产生的效率,我们用称作Apriori性质的重要性质来 压缩搜索空间: Apriori性质:频繁项集的所有非空子集必须也是频繁的。Apriori性质基 于如下观察:根据定义,如果项集I不满足最小支持度闽值min—sup,则l不 是频繁的,即P(1wA)<rainsup。如果项A添加到I,则结果项集(即八JA) 不可能比I更频繁出现,因此八JA也不是频繁的,即P(iuA)<mJnsup。其 实该性质属于一种特殊的关系,称作反单调(Anti—monotone},意指如果一个集 合不能通过测试,则它的所有超集也都不能通过相同的测试,称为反单调,是 因为在通不过测试的意义下,该性质是单调的。 将Apriori性质用于算法,主要是从三。如何找到厶,这个过程由连接和 剪枝两个步骤组成[1,41,42]: 1.连接步:为寻找‘,通过£。与自己连接产生候选k一项集的集合.记为 C。。设小z:是厶一。中的项集,记号“门是‘的第J项(例如,“七一2】表示‘的 倒数第3项)。为方便计,假设事务或项集中的项按照字典次序排列。执行连接 丘一.p司L。,其中t一。的元素如果前(k一2)项相同-则是可连接的a即上“中的 元素小,:是可连接的,当“Ⅲ=厶[】】)^“[2】=1212])A…^以睥一2】=,2【七一2】)。 条件“£一1]-12冲一1]简单的保证不产生重复。则连接0 f:所产生的结果集是: (,.【l】f:【21).0、坼一11f2砧一11)。 2.剪枝步:q是厶的超集,它的成员可以或不是频繁的。但所有的频繁 k一项集都包含在G中。扫描数据库,确定q中每个候选的计数,从而确定厶(即 根据定义。计数值不小于最小支持度计数的所有候选是频繁的,从而属于‘)。 C。可能很大,涉及的计算量就很大,为压缩C;,可以用以下办法使用AprioTi 性质:任何非频繁的(k-1)一项集都不可能是频繁k一项集的子集。因此,如果一 个候选k一项集的(k—1)一子集不在‘一,中,则该候选也不可能是频繁的,从而可 浙江大学硕士学位论文 以由C。中删除。这种子集测试可以使用所有频繁项集的散列树快速完成[45]。 5.3.2利用RR进行隐私保护 对于我们所关注的,数据属于不同所有者,可能分布在不同节点,数据的 隐私需要保护的情况,即有多个用户参与计算,每个用户有多条记录,此时我们 可以采用前文介绍的随机响应技术来伪装这些记录,达到保护各数据持有者的 数据和信息隐私的目的。此时仍旧可以使用某些针对应用环境改进后的算法在 一定精度范围内挖掘关联规则【53,下面我们进行具体讨论。 为描述方便,我们不妨先假设事务集中的每个事务都是3一项集fA,B,c), A,B,C均为布尔属性,然后将其扩展到更多项集。为挖掘关联规则,首先用 随机响应技术对数据进行伪装,然后在伪装后的数据集上执行挖掘算法[40]。 1,数据的伪装与搜集。在我们研究的诗算环境中,有多个焉户参与计算, 每个用户有多条记录。我们采用类似于第5.1节中介绍的随机响应技术来伪装 这些记录。记(』《,丑,C)变换后为(一7,B,,C“,分别为A、B、c设置一个变换概率 61、0'2、%,即;用户对每条汜录伪装时.先产生三个随机实数,;,如,勺E[0,11, 若‘≤Oi,则A≯A,,否则4=1—4,即o~l互换;若r2≤岛,则研=E,否 则B≯1一Bi;同理若^蔓岛,则C=c,,否则C;=1~q。由于变换后的属性 值是随权的,算法执行中心无法知道每条记录的真实值。假设有3个数据持有者 U1,U2,U3共同参与计算,ul有记录T1、T2,U2有记录T3、T4、T5,U3有 记录T6、T7,如表5.1。不妨选取变换概率分鄹为01=O.4,岛=013、岛=O.7, 表5.1描述了每个用户的记录伪装过程。 原始数据 TID Ul T1 T2 A 0 l 1 随机实数 B O 伪装后数据 r3 O.8 O.6 0.S 0.8 A’ l C 1 0 O 1 l r1 0.5 O.6 O。3 0.2 G,6 O.1 O,5 r2 O.4 O.2 O,5 0.1 G.4 0.4 O.7 B’ 1 e’ O 0 1 1 O 1 O O l l 0 l U2 T3 T4 0 l O e 0 O 0 l T5 U3 T6 T7 O l l 0.5 O.8 0.5 O l 0 0 0 Q 1 O 表5.1数据伪装过程 浙江大学硕士学位论文 若用P来表示各类属性组合值的近似概率,并将P(A=1,B=l,C=1)简记为 P(1 I 1),表示同时具有属性A,B,C--者的近似橛率,其他组合值近似概率依此类 推,且仍按前文提到的表示方法,如P’(011)表示伪装后的数据集中 A 7=O,B’=1,C 7=1的记录所占的百分比,则P’(011)可以直接由表5。1的数据计算 得到:P+(011)=1/7。同时,与前面讨论的随机响应模式相似,我们可以得到下 面的方程组其中,若记数据集中有n个属性,则共有2”个方程式,本例中有23=8 个方程组成方程组: P+(000)=?(ooo)oJ岛岛+p(ooDo.02(1-03)+P(OlO)Ot(1~目2)03+…+P(111)(1—01)(1一吼)(1—03) P’(ooi)=P(OOO)毋1020-o,)+P(001)o、岔20,+P(Oto)01(1—02)(I-0,)+…+_产011XI一侈1)O一02)03 P+(olo)=p(ooo)o】0203+P(oo])01吼(1一00+P(OIO)O,(1一目2)03+…+Jp(111)(1-0I)(1一以)(1—6~) P‘(111)=e(ooo)o-0,)(1-o:)(1一只)+P(001)(1一Oi)(1一o,)03+…+P011)o?岛岛 由于尸+(ooo)…P‘(1l 1)可以从伪装后的数据集上直接计算出来,从丽通过解 上述方程组可以算出P(000)…P(1 1 1)。 2.规则的产生。当数据集越来越大时,通过上面联立的方程组求出的 p(ooo)…P(1 l 11就越来越接近从原始数据集中统计得到的结果,于是,以规则 AjB为例: support(A)=P(A)=P(100)+P001)+P(1 11) support(Aj B)=P(AB)=P(110)+P(111) c。nfidence(爿=,口)=璺塑:鬻=7石石P石i(1;1j0)i+灭再P了(I丽1 同理可以得到其他规则的支持度和置信度。 sup J t)(5?7) 此时,关联规则可以如下产生:第一步,对于每个频繁项集Z,产生z的所有非 空子集;第二步,对于f的每个非空子集s,如果塑班!!!婴≥rainconf。则输 port(J 出规则5≥(,一5),其中,min~conf是最d、置信度阈值。由于规则由频繁项集产 浙j工大学硕士学位论文 生,每个规则都自动满足最小支持度,所以可以将频繁项集连同它们的支持度预 先存放在散列表中作为一种改进,使得它们可以快速访问。 我们可以看一个算例,基于类似表5.1的伪装后的数据集上,按照上面的假 定已有频繁项集,=fA,B,C),同时假定由方程组解得以下结果 要求的概率 P(ooo) P(001) P(010) P(011) P(100) P001) P(110) P(n1) 解方程组所得的概率值 0.1l 0.13 O.06 O,17 0.08 O.10 0 14 D.21 表5.2求解由扰乱数据集得到的方程组得出的概军值(1嵌设值) 1的非空真子集有:{m,{B}:{a,{4,钟,(爿,C},{B,c),可以得出以下关联规 则,每个都可阱由类似5.7的方式得到置信度: ∞嘞删=业嚣学=而丽丽P(而ttl)而翊螂=a毗 AjBAC, Bj AAC, 一 ,n 凹2— rt(B— olo)+V(OlI)+ 1 1)一 删,j^H 出咖。,,:—siu而p o蔽万~2≥A—AC)e:(——————————!—P塑O』』!OI )+_—e(————~:21/58:36% c。撇础=—supp而ort(C扩jAAB)=丽而而e而01]丽)而丽。21/6l=34% c0蛳“”—support—t,A^B) AAC=》B. C=,AAB, M州揪2enfid ㈣M——一ss面而百忑广一PjBAtopu r ( C)0 1)+P(1 1) A^BjC, !!!!堕 2瓦丽汗琢丽一 :21/35:60% 一 AC;B) 型11L:21/31:68% 一 占^C等A, 浙江大学硕士学位论支 ∞nfide脚:—support(B—ixCjA):!凹2:21/38:55% suppo一(B^C)P(011)+P(111) 所以,若取最小置信度阈值为50%,则只有后三者,即关联规则:AAB尊C、 A^Cj B和B^Cj A满足强规则条件,可以作为算法的最后输出。这样, 从分布的数据持有者处搜集数掘.且利用随机响应技术在一定程度上保护了持 有者的敏感数据和信息。然后通过得到的伪装后数据集上计算出的各概率值, 联立方程组,在一定程度上得到这些原始概率值,最后作为关联规则挖掘的计 算依据,我们展示了利用RR技术保护隐私数据的关联规则挖掘整个过程。 浙江大学硕士学位论文 第六章回顾与展望 数据挖掘在众多领域和行业有了成功的应用,但是数据隐私的保护和信息 安全的保障仍是现实应用构建中一个巨大的挑战,是数据挖掘领域重要的研究 方向。 本文从不同角度对现有的各种PPDM算法进行了分类研究,并主要关注随机 化方法。针对原始数据本身各属性变量掇关性可能弓I起的隐私数据泄露闯题, 提出了利用PCA进行属性精简,从而降低属性间相关性,并且在一定精度范围 内重构原始数据分布规律的方法,同时对数据分布的重构精度进行量化分析, 得出隐私保护性能与属性精简度和随机量本身数学特征之问的关系。对于另一 种随机化方法,随机响应方法,介绍了它的原理以及与决策树分类算法穗结合, 保护分布式环境下隐私数据和敏感信息的具体分类算法过程,并将其引入关联 规则挖掘,对分布式环境下原始数据进行伪装,与传统关联规则挖掘方法结合, 在保护数据隐私的前提下获取原始数据的部分规律,对关联规则进行了一定精 度的发掘。 对本文所关注的两种随机化模式,可以深入进行研究的内容有: 1.基于随机扰乱的原始分布重构:利用PCA减少由属性相关性引起的隐私 信息泄露的同时,可能引起信息遗失,对隐私傈护程度和信息遗失程度进行量 化建模,找到一个最佳平衡点将是一项很有意义的研究课题。 2,随机响应技术与数据挖掘算法结合:除了本文提至0的随机响应与决策树 分类、关联规则挖掘等算法的结合,还可以将这项隐私保护技术与其他各种数 据挖掘算法和技术檑结合,构建新的PP晰框架;另外,概率常数口的选取必然 对隐私保护程度和各种数据挖掘方法的精度造成了一定的影响,对其进行量化 研究,以提高算法的性能也是~项有挑战的工作:同时,还可以将关联规则挖 掘从布尔型扩展到其他类型,甚至从单维扩展到多维,或在性能上对现有方法 避行改进。 隐私保护的数据挖掘技术的应用将逐步扩展到Web挖掘、企业间分布协同 计算以及分布式安全应用系统构建等各个领域,在不久的将来,随蓑各企业和 组织对自身数据安全性、保密性意识的不断增强,随着协作型数据挖掘研究和 应用的纵深化,涉及隐私、敏感数据的搜集和在其上进行各种知识发现的挖掘 应用,将需要PPDM领域的各种算法和技术作为一种支撑平台或引擎,其应用前 景十分广阔。 ——一一 一一 塑望奎兰婴主兰垡堡兰 参考文献 [1 J J.Han,M,Kamber.Data Mjning Concepts and Techniques【M].北京:机 械工业出版社,200t. [2]R.Agrawai,R.Srikant.Privacy—preserving Proceedings of ACM SIGMOD SIGMOD;2000.439—450. on data mining[A] USA:ACM Management of Data[C],Dallas,TX [3]H.Kargupta,S.Datta,Q.Wang,et a1.On the privacy—preserving properties of random data perturbation techniques[A】.IEEE Interna七ional Conference 106. on Data Mining[C].Melbourne,Florida USA:IEEE,2003.99— [4j Z.Huang.W,Du and Biao.Chen.Deriving Prirate Information from Randomized Oata CA].SIGMOD 2005[C].Baltimore.Maryland,USA:ACM SIGgOD, 2005.37—48. [5]w.Du and z.Zhan.Using randomized response ngs techniques for pri racy—preserving data mini ng[A].Proceedi on of The 9th ACM SIGKDD International Conference Knowledge Discovery and Data Mining[c]. Washington,0C,USA:ACM SIGMOD,Z003.505—510。 [6]Y.Lindell and B.Pinkas.Privacy preserving data mining[A].Advances in Cryptology—CryDto 2000[c].Santa Barbara,CA:springer—VerIag,2000, 36—54. (?]B,Pinkas.Cryptographic techniques for privacy—preserving data mining[J].SIGKDD Explorations,2002,4(2):12—19. [8]w.Du Workshop and Z,Zhan.Buitdingdecisiontree classifier on prirate Oil data[A]. IEEE City, Privacy,Security,and On Data Mining at The 2002 International Conference Data Mining(ICDM’02)[C],Maehaahi Japan:IEEE,20陇.1—8. (9]A.Evfimevski,R.Srikant,R.Agrawal of association et a1.Privacy preserving mining rules[A].Proceedings of the ACM SIKDD Conference[C], Edmonton,Canada:ACM SIKDD,2002.217—228. [10] Jelliffe. n . I.Principal component analysis[M]. New York: 蹶 E 泓l三J .啦¨ 吼o 螺恼 均m 嗡 盼 }虽 D N 陆m 吡 “ ‰妒 一 恤 啪 .52 浙江大学硕士学位论文 in Privacy Preserving Data Mining[A].In SIGMOD Record(2004)【C].33(1) 50—57. [12]S、R,M.01iveira,0.R.Zaiane,Toward Privacy—Preserving Data Data Mining Standardization in on Mining[A].Proceedings of the 3rd.Workshop Standards[cl,Seattle,USA:2004. for secure on [13]A.C,Yao.Protocals computations[A].Proceedings of the 23rd Annual IEEE Symposium 160 ~ Foundations of Computer Science[C].1982: 164. Tutorial Notes:Data Ming Techniques[A].In: on [14]J.W.Han,Conference Prec the ACM SIGMOD International Conference Management of Data[C], Montreal,Canada,1996. [1 5]U.Fayyad,G.Piatesky—Shapiro,P.Smyth.From Knowledge Discovery in Data Mining to Databases[J].AI~[AGAZINE,1996:37—53. the Data [16]w.H.Inmon.Building &Sons,1996. Warehouse[M].New York:John Wiley (17]Efrem G.Mallaeh.李昭智译.决策支持系统与数据仓库系统[M].北京: 电子工业出版社,2001. [18]Sid Adelman.薛宇译.数据仓库项目管理[M].北京:清华大学出版社, 2003. [19]J.L.Weldon.Data and Mining and Visualization[J].Database Programming Design.1995.9(5)21—24 Bertino,Ahmed K,et a1.Disclosure [20]Mike.J.Atallah,Elisa LiII】itation of Sensitive and Rules[A].In Proceedings of the IEEE Knolwedge Data Engineering Workshop(1999)[C],45—52. a1.Hiding [21]E.D.Vassilios,S.Verykios,Ahmed.K.Elmagarmid,et Association Rules by using Confidence and the 4th Information Hiding Support[A]In Proceedings of Workshop(2001)[C],369—383. [22]V Rule a1.Association S,Verykios,Ahmed K.Elmagarmid,Bertino Elisa,et Hiding[J],IEEE Transactions On Knowledge and Data Engineering (2003). [23]Stanley itemset Securitv R.M.Oliveira,Osmar R.Zaiane.Privacy preserving frequent Proceedings of the IEEE ICDM Workshop on mining[A].In and Data Privacy, Mining(2002)【C],43—54. [24]Li Wu Chang and Ira S.Moskowitz.An integrated framework for database inference and privacy protection[J],Data and Applications .53? ——一堑鋈查兰堕主堂垡堡苎 Security(2000),161—172,K1uwer,IFIP WG Ii,3,The Netherlands. [25]Yucel Saygin,Vassilios S.Verykios,and Ahmed K.Elmagarmid,Privacy preserving association on rule mining[幻,In Proceedings of tbe 12tb International Workshop 15l~158. Research Issues in Data Engineering(2002)[C], [26]Yueel Saygin,VassiIlos Verykios,and Chris C1ifton,Using unknowns to pz’event discovery of association rules[J],SIGMOD Record 30(2c01)。 no.4,45~54. [27]LiWu deeision Chang and Ira S.Moskowitz.Parsimonious to downgrading 8nd trees applled the inference problem[A],In Proceedings of the 1998.New Security Paradigms Workshop(1998)[C],82—89. [28]Wenliang Du and Mikhail J.Attalah.Secure multi-problem computation problems and their applications:A review and open problems[R],Tech. Report CERIAS Tech Report 200i~51,Center for Education and Research in Information Assurance and Security and Department of Computer Sciences, Purdue Universi ty,West Lafayette 2001. [29]Chris C1ifton,Murat Kantarcioglou,Xiadong Lin,et a1.Tools privacy preserving for distributed data mining[J],SIGKDD Explorations 4(2002),no.2. [30]Jaideep rule mining Vaidya in and Chris Clifton.Privacy preserving association verticolly on partitioned data[A]。In the 8th ACMSIGKDD International Conference 639—644. Knowledge Discoverg and DataMining(2002)tcj. [31]Ioannis protocol for Ioannidis,Ananth Grams,and computing dot products of in gikhail clustered Atallah。A and secure distributed on environments¨],In Proceedings the International Conference Parallel Procesging(2002)[C]. [32]Murat Kantarcioglou of and Chris rules C1ifton,Privacy-preserving on distributed mining aSSOCiation hurlzontally pattitioned in data[A],In Proceedings of the ACM SIGMOD Workshop on Research Isuues Data Mining and Knowledge Discovery(2002)[C],24—31. 933]David W.Cheung,Jiawei Han,Vincent T.Ng.et a1.A fast distributed algorithm for mining association rules[A],In International Conference on Proceedings of the 1996 Distributed Information Parallel and Systems(1996)[C]. .54 浙江大学硕士学位论文 [34]Wenliang Du and Zhijun Zhan,Building decision Proceedings of the IEEE tree classifier on on private data[A],In Security and Data ICDM Workshop Privacy. Mining(2002)[e]. and Charu C. [35]Dakshi Agrawal of Aggarwal. data On the design and quantification privacy preserving Oll mining algorithms[A],In Database Systems Proceedings of the 20th ACMSymposium Principles of (2001)[C],247—255. [36]Shariq J.Rizvi association rule Conference on and Jayant R.Haritsa.Maintaing Proceedings of data privacy in mining[A],In Large the 28th International Very Databases(2002)[C]. Du.Privacy—Preserving Data [37]Zhijun Zhan,Wenliang Mining Using Multi—Group Randomized Response Techniques[R].Technical Report,June 2003. 【38]S.L.Warner.Randomized evasive answer response:h survey technique for eliminating American bias[J].The Statistical Association,1965, 60(309):63—69. [39]A.C.Tamhane.Randomized attributes(J],The December 1981. response techniques for multiple sensitive American Statistieal Association,76(376):916—923, [40]罗永龙,黄刘生,荆巍巍等.一个保护私有信息的布尔关联规则挖掘算法 [J].电子学报,2005.5(33):900—903. [41]David Hand。Heikki Mannila,Padhraic Smyth.数据挖掘原理[M].机械 工业出版社,2003. [42]Rakesh Rules Agrawal,Tomasz Imielinski and Arun Swami.Mining Association between Sets of Items in Large Databases[A].in Proc.ACM SIGMOD Conference,Washington(1993)[C]:207—216. [43]Cohen without E,Datar M,Fujiwara S.et a1.Finding interesting associations support pruning[J].IEEE Transactions on Knowledge and Data Engineering(2001).13(1),64—78. [44]Mohammed J.Zaki,Scalable IEEE Transactions on Algorithms for Association Mining[J], Knowledge and Data Engineering(2000).12(3):372—390 [45]R.Agrawal rules[A]In and R.Srikant.Fast algorithms for mining association Proc.1994 Int.Conf.Very Large Databases(VLDB 7 94)[C]. Privacy [46]A.Evfimievski,J.E.Gehrke,and Breaches in Privacy Preserving Data R,Srikant.Limiting Mining[Aj.In Proceedings of the 22nd .55? 浙江大学硕士学位论文 ACM SIGACT—SIGMOD—SIGART Symposium on Principles of Database Systems (PODS 2003)[C].San [47]Wenliang Di ego,CA.June 2003, Study of Du.A Several Specific Secure Two—party Lafayette, Computation Problems.PhD thesis,Purdue University,West Indiana.2001. [48]黄征.安全多方计算协议及典型应用研究.PhD thesis,上海交通大学, 2003. -56? 浙江大学硕士学位论文 致谢 两年多的硕士研究生学习生活就要结束,这是我人生中又一段宝贵的经历。 一路走来,伴着众多良师、益友给我的鼓励和帮助,我才能够不断克服困难, 提高自己。 首先感谢我的导师林怀忠副教授,他严谨的治学态度、对研究领域学术前 沿敏锐而准确的把握、扎实的理论和实践基础以及随和谦逊的为人作风都让我 钦佩不已且受益良多。他在学术领域对我悉心指导,引领我登堂入室,在此谨 表达我诚挚的谢意。 感谢陈纯教授和h佳俊副教授,他们对工作认真负责的态度,在学术上孜 孜不倦的追求精神,都潜移默化影响着我,他们也为我提供了良好科研与学习 环境,在此表示深深的谢意。 此外,我还要感谢两年多来在课堂上和其他场台向我传授知识、为我指点迷 津的老师们,他们的治学态度将继续鼓舞我学而不辍。 我要感谢同实验室的同学们,王荣、马隆、赵仕峰,以及师弟师妹们:王晓 伟、蒋维和周晓群,每次与他们探讨,我都受益匪浅。同时感谢计算机学院2003 级硕士同学们,他们在学习、工作和生活中陪伴着我,为我提供各种无私的帮助, 让我分享着友情和快乐。 我要深深感谢我的家人,他们让我时刻体会到亲情的温暖。并支持着我顺利 完成我的学业。 最后,感谢为我审稿和出席我论文答辩的诸位老师、专家,谢谢你们的辛勤 劳动。 温晗 2006年3月于求是园

文档贡献者

zr13555

贡献于2012-04-11

喜欢此文档的还喜欢