第7课数据挖掘的高级主题.ppt
第7课 数据挖掘的高级主题,徐从富，副教授 浙江大学人工智能研究所,浙江大学本科生数据挖掘导论课件,内容提纲,Web挖掘隐私保护数据挖掘,Web 挖掘,Knowledge,WWW,Web 挖掘简介Web日志挖掘,Web Mining简介,产生原因应用分类过程,产生原因,网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。传统数据挖掘和文本挖掘技术的不断完善和应用。,应用,查询相关信息从Web数据发现潜在的未知信息了解用户的兴趣爱好信息个性化,Web 挖掘分类,Web Mining,Web Content Mining,Web Usage Mining,Web Structure Mining,Web内容挖掘,Web内容挖掘是从文档内容或其描述中抽取知识的过程。Web内容挖掘策略直接挖掘文档的内容在其它工具搜索的基础上进行改进,Web内容挖掘（续）,提取文字、图片或者其他组成网页内容成分的信息，即通过有效的内容挖掘能告诉我们哪些页面是德文或者法文的？哪些站点卖我们喜欢的东西？哪些页面介绍了我们感兴趣的知识？搜索引擎、智能代理和一些推荐引擎都使用内容挖掘来帮助客户在浩瀚的网络空间中寻找所需的内容。,Web结构挖掘,Web结构挖掘研究的是Web文档的链接结构，揭示蕴含在这些文档结构中的有用模式，处理的数据是Web结构数据。是从WWW的组织结构和链接关系中推导知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。,Web结构挖掘（续）,提取网络的拓扑信息网页之间的链接信息，即通过有效的结构挖掘能告诉我们哪些页面被其他页面所链接？哪些页面指向了其他页面？哪些页面的集合构成了一个独立的整体？,Web日志挖掘,Web日志挖掘的主要目标则是从Web的访问记录中（Web服务器log日志）抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。,Web日志挖掘（续）,一般的访问模式跟踪通过分析日志数据来了解用户的访问模式和倾向，以改进站点的组织结构个性化的使用记录跟踪倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。,Web日志挖掘（续）,提取关于客户如何运用浏览器浏览和使用这些链接的信息，即通过有效的日志挖掘能告诉我们那些客户访问了哪些页面？在每一页上待了多长时间？下一步单击了什么？在站点中是按照怎样的访问路线通向检查计数器，又是通过怎样的路线直接退出的？,Web挖掘过程,资源发现：在线或离线检索Web的过程，例如用爬虫（crawler）或（spider）在线收集Web页面信息选择与预处理：对检索到的Web资源的任何变换都属于此过程。词干提取高低频词的过滤汉语词的切分综合过程：自动发现Web站点的共有模式分析过程：对挖掘到的模式进行验证和可视化处理,Web日志挖掘,Web日志挖掘数据类型Web日志挖掘应用Web日志挖掘过程,服务器日志,数据类型,Client IP:128.101.228.20Authenticated User ID:-Time/Date:10/Nov/1999:10:16:39-0600Request:GET/HTTP/1.0Status:200Bytes:-Referrer:“-”Agent:Mozilla/4.61 en(WinNT;I),Web 日志挖掘应用,Applications电子商务中发现潜在客户增强终端用户信息获取的质量提高Web服务器的性能合理放置广告提高站点设计欺诈和入侵检测预测用户行为,Web日志挖掘过程,Web日志挖掘过程,预处理数据挖掘模式分析,数据预处理,数据清理用户对话识别页面视图识别路径完整,数据清理,根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（status code）进行检查。,清理后的Sample Log,用户对话识别,1.IP Address&Agent2.Embedded Session ID3.Registration(User Profile)4.Cookie5.Software Agent(Applet&Scrtipt)6.Modified Browser,用户对话识别（续）,用户对话识别,页面视图识别,1-A,http:/ok.edu/link.htm,E,C.htm,1-C,A.htm,路径补全,解决由于Cache带来的问题路径不全的问题,数据挖掘,统计分析频繁项集和关联规则聚类分析和分类序列模式,统计分析,主要用于改进系统的性能、设计等包括：1)最频繁访问的页面2)每个页面的平均访问时间3)通过一个站点的平均时间,频繁项集和关联规则,可以寻找出经常频繁访问的page组，可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。,包括两方面的应用：*user 用于Market segmentation(市场分割)和个人内容定制*page(content)后者主要用于IR和冲浪辅助,聚类和分类,序列模式,可用于用户的 visit pattern.包括：1.趋势分析2.拐点检测,模式分析,目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。Visualization,隐私保护数据挖掘,隐私保护数据挖掘简介隐私保护数据挖掘面向企业信用评估的分布式隐私保护数据挖掘研究,一、隐私保护数据挖掘简介,WhatWhyWhoGoalHowAn Example,什么是数据挖掘,数据挖掘是从大量数据中提取或“挖掘”知识的过程。数据挖掘以客观、有效的数据源为物质基础。数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。,什么是隐私,针对不同的应用环境，隐私定义不同。在信息时代，隐私指用户隐藏个人信息的权利和控制自己的信息给其他人的能力。,什么是隐私保护数据挖掘,“getting valid data mining results without learning the underlying data values”噪声背景的数据挖掘受限制的数据挖掘,数据挖掘可能会违反用户的隐私,数据挖掘以准确的数据为数据源，进行数据归纳分析。个体隐私记录级和属性级上的隐私组织隐私结果级上的隐私，统计分析后的结果,什么人需要隐私保护数据挖掘？,政府和公用事业部门疾病控制中心保险公司工商业组织跨国公司每个国家的法律是不同的军事情报分析犯罪行为分析反恐分析,隐私的限制不会阻止数据挖掘,数据挖掘的目标是结果的总结关联规则分类聚类结果本身不会违反隐私不包含个人身份信息反映的是整个数据的归纳统计结果，而不是针对每个单位The problem is computing the results without access to the data!,隐私保护数据挖掘的目标,PPDM encompasses the dual goal of meeting privacy requirements and providing valid data mining results.保护隐私和满足安全性要求（安全性）产生正确的数据挖掘归纳结果（准确性）提供高效的数据挖掘算法（高效性）,如何进行隐私保护数据挖掘,计算频繁项集：ABC 5%?,2ABC=9DBSize=200,1ABC=18DBSize=300,3ABC=5DBSize=100,ABC:R+count-freq.*DBSize,R=17,ABC:17+5-.05*100,ABC:17,ABC:17+9-.05*200,ABC:12,ABC:12+18-.05*300,ABC:19,ABC:19 R?,ABC:YES!,计算频繁项集：ABC 5%?,2ABC=9DBSize=200,1ABC=18DBSize=300,3ABC=5DBSize=100,ABC:R+count-freq.*DBSize,R=17,ABC:17+9-.05*200,ABC:12+18-.05*300,ABC:19 R?,ABC:YES!,二、隐私保护数据挖掘,隐私保护数据挖掘分类保护个体用户隐私保护组织用户隐私研究方法数据隐藏安全多方计算,保护个体用户隐私,这是一种记录和属性级上的隐私保护。在原始数据库中，类似于标识符、姓名、地址和喜好等用户数据作为用户的隐私应该被保护。保护敏感的原始数据的隐私保护数据挖掘方法应该能够使得用户的敏感的原始数据被修改，以便数据的使用者不能对用户的原始数据进行直接存储，不能查看用户的隐私，以此保护用户的私有数据。,个体隐私:保护记录,每个项都不允许泄漏记录的一部分是可以泄漏的个人身份信息,个人身份信息,删除标识符但是我们无法保证身份不能被推断候选码一些个体特有的属性Data Mining enables such tracing!,保护组织用户隐私,这是一种结果级上的隐私保护，这里的目标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。在数据挖掘的统计模型中，有很多挖掘出的知识也会泄漏用户的隐私。保护敏感的挖掘知识的隐私保护数据挖掘方法能够保护用户的敏感知识，以便不会被泄漏用作其他的目的，造成用户重要信息的泄密。,组织隐私,保护个体隐私是不够的保护从组织中获得的敏感知识策略模式数据挖掘的结果目标：身份信息不能泄漏数据挖掘之后的模式和知识同样不能泄漏,Database,用户,变换后数据库,P3P,发布的隐私策略协同达成的一致策略,隐私保护数据挖掘架构,B2B的架构中，具体的事务分布在几个不同的站点。每个站点拥有一个包含大量事务的私有数据库。这里用到的主要计算技术是安全多方计算（Secured multiparty computation）及其变种。B2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。在线调查表是这种B2C架构的一个典型的例子。其中包含一个调查表收集器和分析器以及众多的数据提供者。,解决方法分类,数据隐藏(Data Obfuscation)对数据进行挖掘时，不能看到真实的数据安全多方计算仅仅可信的结点可以看到数据,数据隐藏,目标:隐藏被保护信息私有数据可用噪声较大真实值不能确定得到,主要技术,匿名技术 随机的数据转换(random data perturbation)阻塞技术(blocking)聚集或融合技术(aggregation or merging)交换技术(swapping)采样技术(sampling),基于阻塞的技术(blocking),Initial Database,New Database,主要用于组织隐私的保护,随机的数据转换(random data perturbation),Sample Database,Distorted Database,随机的数据转换,目标统计属性可以较精确得到个体数据不能得到离散型变量转换布尔型变量分类型(Category)变量连续型变量转换,布尔型变量转换,分类型变量转换,连续型变量转换,布尔型变量转换,购物篮问题数据位以概率p 被翻转对经过变化的数据进行挖掘,分类型变量转换,Select-a-size RandomizationCut and Paste Randomization,Select-a-size Randomization,给定大小为t的事务,构造t:选择j 属于0 到m Pj被选择的概率=pmj把事务加入t的 j个项加入事务t;其它不在事务t的属性以概率pm 加入事务 t参数pmj和pm的选择基于需要的隐私度,Cut and Paste Randomization,给定大小为t的事务,构造t:在0到Km间选择 j把事务t 的j个项加入t;事务t的其它项以概率pm加入 t参数Km和pm的选择基于所需要的隐私度,连续型变量隐私保护挖掘方法,Agrawal and Srikant,SIGMOD00Bayes rule改进by Agrawal and Aggarwal,SIGMOD01Expectation Maximization(EM),Bayes rule,Agrawal and Srikant(2000)Decision TreesPerturb Data with Value Distortion用户提供 xi+r 代替 xir 是一个随机变量，服从分布平均分布-a,a高斯分布(u,),Bayes rule,x1,x2,xn 是n个独立同分布的随机变量y1,y2,yn 是n个独立同分布的随机变量W=X+Y给定FY和W，估计FX,安全多方计算,Motivation:分布式隐私保护数据挖掘目标：结果公布每个用户只知道自己的数据,分布式隐私保护数据挖掘的目标,安全性分析知道自己的数据和最终的结果不清楚其它用户的数据避免相互勾结通信分析,分布式隐私保护数据挖掘方法,Semi-Honest ModelMalicious,分类,水平分布型数据(Horizontal Partitioning)垂直分布型数据(Vertical Partitioning),水平型分布数据,垂直分布型数据,
