第课数据挖掘的高级主题优秀文档.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,课 数据挖掘的高级主题,徐从富，,副教授,浙江大学人工智能研究所,浙江大学本科生,数据挖掘导论,课件,内容提纲,Web,挖掘,隐私保护数据挖掘,Web,挖掘,Knowledge,WWW,Web,挖掘简介,Web,日志挖掘,Web Mining,简介,产生原因,应用,分类,过程,产生原因,网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。,传统数据挖掘和文本挖掘技术的不断完善和应用。,应用,查询相关信息,从,Web,数据发现潜在的未知信息,了解用户的兴趣爱好,信息个性化,主要用于组织隐私的保护,什么人需要隐私保护数据挖掘？,分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。,主要用于组织隐私的保护,Web站点重建，商业决策,15:37:09/2-Jan-01,数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。,Semi-Honest Model,提高Web服务器的性能,数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。,阻塞技术(blocking),保护隐私和满足安全性要求（安全性）,Web日志挖掘数据类型,一般地，我们需要对日志中的状态码（status code）进行检查。,*page(content),不是全部用户都愿意注册,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,结构挖掘,Web,日志挖掘,处理数据,类型,IR,方法：无结构数据、半结构数据,数据库方法：半结构化数据,Web,结构数据,用户访问,Web,数据,主要数据,自由化文本、,HTML,标记的超文本,HTML,标记的超文本,Web,文档内及文档间的超链,Serverlog,Proxy serverlog,Client log,表示方法,词集、段落、概念、,IR,的三种经典模型,对象关系模型,图,关系表、图,处理方法,统计、机器学习、自然语言理解,数据库技术,机器学习、专有算法,统计、机器学习、关联规则,主要应用,分类、聚类、模式发现,模式发现、数据向导、多层数据库、站点创建与维护,页面权重,分类聚类,模式发现,Web,站点重建，商业决策,Web,挖掘过程,资源发现：在线或离线检索,Web,的过程，例如用爬虫（,crawler,）或（,spider,）在线收集,Web,页面,信息选择与预处理：对检索到的,Web,资源的任何变换都属于此过程。,词干提取,高低频词的过滤,汉语词的切分,综合过程：自动发现,Web,站点的共有模式,分析过程：对挖掘到的模式进行验证和可视化处理,Web,日志挖掘,Web,日志挖掘数据类型,Web,日志挖掘应用,Web,日志挖掘过程,服务器日志,数据类型,Client IP:,Authenticated User ID:,-,Time/Date:,10/Nov/1999:10:16:39-0600,Request:,GET/HTTP/1.0,Status:,200,Bytes:,-,Referrer:,“-”,Agent:,Mozilla/4.61 en(WinNT;I),Web,日志挖掘应用,Applications,电子商务中发现潜在客户,增强终端用户信息获取的质量,提高,Web,服务器的性能,合理放置广告,提高站点设计,欺诈和入侵检测,预测用户行为,Web,日志挖掘过程,Web,日志挖掘过程,预处理,数据挖掘,模式分析,数据预处理,数据清理,用户对话识别,页面视图识别,路径完整,数据清理,根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（,status code,）进行检查。,清理后的,Sample Log,IP Address,Time/Date,Method/URI,Referrer,Agent,202.120.224.4,15:30:01/2-Jan-01,GET Index.htm,ok.edu/link.htm,Mozilla/4.0(IE5.0W98),202.120.224.4,15:30:01/2-Jan-01,GET 1.htm,ex.edu/index.htm,Mozilla/4.0(IE5.0W98),202.120.224.4,15:30:01/2-Jan-01,GET A.htm,ex.edu/index.htm,Mozilla/4.0(IE5.0W98),202.120.224.4,15:37:09/2-Jan-01,GET E.htm,ex.edu/C.htm,Mozilla/4.0(IE5.0W98),202.120.224.4,15:33:04/2-Jan-01,GET Index.htm,ok.edu/res.php,Mozilla/4.0(IE4.0NT),202.120.224.4,15:33:04/2-Jan-01,GET 1.htm,ex.edu/index.htm,Mozilla/4.0(IE4.0NT),202.120.224.4,15:33:04/2-Jan-01,GET A.htm,ex.edu/index.htm,Mozilla/4.0(IE4.0NT),202.120.224.4,15:35:11/2-Jan-01,GET B.htm,ex.edu/A.htm,Mozilla/4.0(IE4.0NT),202.120.224.4,15:35:11/2-Jan-01,GET C.htm,ok.edu/A.htm,Mozilla/4.0(IE5.0W98),用户对话识别,1.IP Address&Agent,2.Embedded Session ID,3.Registration(User Profile),5.Software Agent(Applet&Scrtipt),6.Modified Browser,用户对话识别（续）,方法,说明,隐私性保护,优点,缺点,IP,地址,/,代理服务器,假定每个独立,IP,地址,/,代理服务器组是独立用户,低,通常可用，无需附加技术。,无法保证唯一性，在随机或者轮换,IP,情况下失效,嵌入式对话,ID,通过动态形成页面将,ID,加入每个链接低,/,中等,通常可用，不需依赖于,IP,地址,无法了解重复访问，需要完全动态站点。,注册,用户确切地登陆站点,中等,可以跟踪单个用户，而不仅仅是浏览器,不是全部用户都愿意注册,Cookie,在客户端机器上保留标识符,中等,/,高,可以跟踪重复访问,能被禁止。不为大众接收,软件代理服务器,程序载入浏览器从而将日志数据返回,高,可以得到单个,Web,站点的确切日志数据,很可能被拒绝。不为大众接收,改进型浏览器,浏览器记录日志数据,非常高,可以得到关于整个,Web,的日志数据,用户必须确切地得到软件,New Database,B2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。,提供高效的数据挖掘算法（高效性）,其它不在事务t的属性以概率pm 加入事务 t,阻塞技术(blocking),数据挖掘之后的模式和知识同样不能泄漏,x1,x2,xn 是n个独立同分布的随机变量,数据隐藏(Data Obfuscation),15:37:09/2-Jan-01,这是一种结果级上的隐私保护，这里的目标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。,选择j 属于0 到m,x1,x2,xn 是n个独立同分布的随机变量,Web Mining简介,15:30:01/2-Jan-01,Bayes rule,x1,x2,xn 是n个独立同分布的随机变量,Time/Date:10/Nov/1999:10:16:39-0600,用户对话识别,15:33:04/2-Jan-01,GET Index.htm,ok.edu/res.php,15:33:04/2-Jan-01,GET 1.htm,ex.edu/index.htm,15:33:04/2-Jan-01,GET A.htm,ex.edu/index.htm,15:35:11/2-Jan-01,GET B.htm,ex.edu/A.htm,15:30:01/2-Jan-01,GET Index.htm,ok.edu/link.htm,15:30:01/2-Jan-01,GET 1.htm,ex.edu/index.htm,15:30:01/2-Jan-01,GET A.htm,ex.edu/index.htm,15:37:09/2-Jan-01,GET E.htm,ex.edu/C.htm,15:35:11/2-Jan-01,GET C.htm,ok.edu/A.htm,Mozilla/4.0(IE5.0W98),202.120.224.4,User1:,202.120.224.4,Mozilla/4.0(IE4.0NT),User2:,页面视图识别,1-A,ok.edu/res.php,B,A.htm,1-AE,1-C,Mozilla/4.0(IE5.0W98),202.120.224.4,User1:,202.120.224.4,Mozilla/4.0(IE4.0NT),User2:,路径补全,解决由于,Cache,带来的问题路径不全的问题,数据挖掘,统计分析,频繁项集和关联规则,聚类分析和分类,序列模式,统计分析,主要用于改进系统的性能、设计等,包括：,1),最频繁访问的页面,2),每个页面的平均访问时间,3),通过一个站点的平均时间,频繁项集和关联规则,可以寻找出经常频繁访问的,page,组，,可用于修改,Web,站点的设计或提前缓冲页面，改进系统的性能。,包括两方面的应用：,*,user用于,Market segmentation(,市场分割,),和个人内容定制,*,page(content),后者主要用于,IR,和冲浪辅助,聚类和分类,序列模式,可用于用户的,visit pattern.,包括：,1.,趋势分析,2.,拐点检测,模式分析,目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。,Visualization,隐私保护数据挖掘,隐私保护数据挖掘简介,隐私保护数据挖掘,面向企业信用评估的分布式隐私保护数据挖掘研究,一、隐私保护数据挖掘简介,What,Why,Who,Goal,How,An 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,.,保护隐私和满足安全性要求（,安全性,）,产生正确的数据挖掘归纳结果（,准确性,）,提供高效的数据挖掘算法（,高效性,）,Accuracy,Efficiency,Privacy,15:33:04/2-Jan-01,New Database,Modified Browser,B2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。,交换技术(swapping),Web内容挖掘是从文档内容或其描述中抽取知识的过程。,一般地，我们需要对日志中的状态码（status code）进行检查。,ABC:12+18-.,数据位以概率p 被翻转,什么人需要隐私保护数据挖掘？,浙江大学本科生数据挖掘导论课件,提高Web服务器的性能,15:30:01/2-Jan-01,如何进行隐私保护数据挖掘,计算频繁项集：,ABC,5%?,2,ABC=9,DBSize=200,1,ABC=18,DBSize=300,3,ABC=5,DBSize=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%?,2,ABC=9,DBSize=200,1,ABC=18,DBSize=300,3,ABC=5,DBSize=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),A,B,C,D,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,1,0,1,1,A,B,C,D,1,1,1,0,1,0,?,1,?,0,0,1,1,1,1,0,1,0,1,1,Blocking,Algorithm,Initial Database,New Database,主要用于组织隐私的保护,随机的数据转换,(random data perturbation),A,B,C,D,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,1,0,1,1,Sample Database,A,B,C,D,1,1,1,0,1,0,0,1,0,0,0,1,1,1,1,0,1,0,0,1,Distorted Database,Distortion,Algorithm,随机的数据转换,目标,统计属性可以较精确得到,个体数据不能得到,离散型变量转换,布尔型变量,分类型,(,Category,),变量,连续型变量转换,布尔型变量,转换,分类型变量,转换,连续型变量,转换,布尔型变量转换,购物篮问题,数据位以概率,p,被翻转,对经过变化的数据进行挖掘,分类型变量转换,Select-a-size Randomization,Cut and Paste Randomization,Select-a-size Randomization,给定大小为,t,的事务,构造,t,:,选择,j,属于,0,到,m,P,j,被选择的概率,=,p,m,j,把事务加入,t,的,j,个项加入事务,t,;,其它不在事务,t,的属性以概率,p,m,加入事务,t,参数,p,m,j,和,p,m,的选择基于需要的隐私度,Cut and Paste Randomization,给定大小为,t,的事务,构造,t,:,在,0,到,K,m,间选择,j,把事务,t,的,j,个项加入,t,;,事务,t,的其它项以概率p,m,加入,t,参数,K,m,和,p,m,的选择基于所需要的隐私度,连续型变量隐私保护挖掘方法,Agrawal and Srikant,SIGMOD00,Bayes rule,改进,by Agrawal and Aggarwal,SIGMOD01,Expectation Maximization(EM),Bayes rule,Agrawal and Srikant(2000)Decision Trees,Perturb Data with Value Distortion,用户提供,x,i,+r,代替,x,i,r,是一个随机变量，服从分布,平均分布,-a,a,高斯分布,(u,),Bayes rule,x,1,x,2,x,n,是,n,个独立同分布的随机变量,y,1,y,2,y,n,是,n,个独立同分布的随机变量,W=X+Y,给定,F,Y,和,W,，估计,F,X,安全多方计算,Motivation:,分布式隐私保护数据挖掘,目标：,结果公布,每个用户只知道自己的数据,比较,数据隐藏,安全多方计算,复杂性,一般,高,计算、通信,安全性,较高,高,主要问题,安全性和准确性的折衷,效率,适用领域,较广,Web,Corporate,小规模分布式,Corporate,分布式隐私保护数据挖掘的目标,安全性分析,知道自己的数据和最终的结果,不清楚其它用户的数据,避免相互勾结,通信分析,分布式隐私保护数据挖掘方法,Semi-Honest Model,Malicious,分类,水平分布型数据,(Horizontal Partitioning),垂直分布型数据,(Vertical Partitioning),水平型分布数据,垂直分布型数据,