1、第7课 数据挖掘的高级主题 徐从富，副教授 浙江大学人工智能研究所浙江大学本科生数据挖掘导论课件内容提纲nWeb挖掘n隐私保护数据挖掘一Web 挖掘KnowledgeWWWI.Web 挖掘简介II.Web日志挖掘I.Web Mining简介1.产生原因2.应用3.分类4.过程1.产生原因n网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。n传统数据挖掘和文本挖掘技术的不断完善和应用。2.应用n查询相关信息n从Web数据发现潜在的未知信息n了解用户的兴趣爱好n信息个性化3.Web 挖掘分类Web MiningWeb Content MiningWeb Usage Minin
2、gWeb Structure Mining Web内容挖掘nWeb内容挖掘是从文档内容或其描述中抽取知识的过程。nWeb内容挖掘策略直接挖掘文档的内容在其它工具搜索的基础上进行改进Web内容挖掘（续）n提取文字、图片或者其他组成网页内容成分的信息，即通过有效的内容挖掘能告诉我们哪些页面是德文或者法文的？哪些站点卖我们喜欢的东西？哪些页面介绍了我们感兴趣的知识？搜索引擎、智能代理和一些推荐引擎都使用内容挖掘来帮助客户在浩瀚的网络空间中寻找所需的内容。Web结构挖掘nWeb结构挖掘研究的是Web文档的链接结构，揭示蕴含在这些文档结构中的有用模式，处理的数据是Web结构数据。是从WWW的组织结构和链
3、接关系中推导知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。Web结构挖掘（续）n提取网络的拓扑信息网页之间的链接信息，即通过有效的结构挖掘能告诉我们哪些页面被其他页面所链接？哪些页面指向了其他页面？哪些页面的集合构成了一个独立的整体？Web日志挖掘nWeb日志挖掘的主要目标则是从Web的访问记录中（Web服务器log日志）抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。Web日
4、志挖掘（续）n一般的访问模式跟踪通过分析日志数据来了解用户的访问模式和倾向，以改进站点的组织结构n个性化的使用记录跟踪倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。Web日志挖掘（续）n提取关于客户如何运用浏览器浏览和使用这些链接的信息，即通过有效的日志挖掘能告诉我们那些客户访问了哪些页面？在每一页上待了多长时间？下一步单击了什么？在站点中是按照怎样的访问路线通向检查计数器，又是通过怎样的路线直接退出的？Web内容挖掘Web结构挖掘Web日志挖掘处理数据类型IR方法：无结构数据、半结构数据数据库方法：半结构化数据Web结构数据用户访问Web数据主要数据自由
5、化文本、HTML标记的超文本HTML标记的超文本Web文档内及文档间的超链Serverlog,Proxy serverlog,Client log表示方法词集、段落、概念、IR的三种经典模型对象关系模型图关系表、图处理方法统计、机器学习、自然语言理解数据库技术机器学习、专有算法统计、机器学习、关联规则主要应用分类、聚类、模式发现模式发现、数据向导、多层数据库、站点创建与维护页面权重分类聚类模式发现Web站点重建，商业决策4.Web挖掘过程n资源发现：在线或离线检索Web的过程，例如用爬虫（crawler）或（spider）在线收集Web页面n信息选择与预处理：对检索到的Web资源的任何变换都属
6、于此过程。词干提取高低频词的过滤汉语词的切分n综合过程：自动发现Web站点的共有模式n分析过程：对挖掘到的模式进行验证和可视化处理II.Web日志挖掘1.Web日志挖掘数据类型2.Web日志挖掘应用3.Web日志挖掘过程服务器日志数据类型nClient IP:128.101.228.20nAuthenticated User ID:-nTime/Date:10/Nov/1999:10:16:39-0600nRequest:GET/HTTP/1.0nStatus:200nBytes:-nReferrer:“-”nAgent:Mozilla/4.61 en(WinNT;I)2.Web 日志挖掘应用
7、nApplications电子商务中发现潜在客户增强终端用户信息获取的质量提高Web服务器的性能合理放置广告提高站点设计欺诈和入侵检测预测用户行为3.Web日志挖掘过程Web日志挖掘过程预处理数据挖掘模式分析 数据预处理n数据清理n用户对话识别n页面视图识别n路径完整数据清理n根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（status code）进行检查。清理后的Sample LogIP AddressTime/DateMethod/URIReferrerAgent202.120
8、.224.4 15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:37:09/2-Jan-01 GET E.htmhttp:/ex.
9、edu/C.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.phpMozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:
10、35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htmMozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)用户对话识别n1.IP Address&Agentn2.Embedded Session IDn3.Registration(User Profile)n4.Cookien5.Software Agent(Applet&Scrtipt)n6.Modified Browser用户对话识别（续）方法说明隐私性保护优点缺
11、点IP地址/代理服务器假定每个独立IP地址/代理服务器组是独立用户低通常可用，无需附加技术。无法保证唯一性，在随机或者轮换IP情况下失效嵌入式对话ID通过动态形成页面将ID加入每个链接低/中等通常可用，不需依赖于IP地址无法了解重复访问，需要完全动态站点。注册用户确切地登陆站点中等可以跟踪单个用户，而不仅仅是浏览器不是全部用户都愿意注册Cookie在客户端机器上保留标识符中等/高可以跟踪重复访问能被禁止。不为大众接收软件代理服务器程序载入浏览器从而将日志数据返回高可以得到单个Web站点的确切日志数据很可能被拒绝。不为大众接收改进型浏览器浏览器记录日志数据非常高可以得到关于整个Web的日志数据用
12、户必须确切地得到软件用户对话识别15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.php15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htm15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htm15:30:01/2-Jan-01 GET 1.htmhttp:/ex.ed
13、u/index.htm15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htm15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:页面视图识别1-Ahttp:/ok.edu/res.phpBA.htm1-Ahttp:/ok.edu/link.htmEC.htm1-CA.h
14、tmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:路径补全n解决由于Cache带来的问题路径不全的问题数据挖掘n统计分析n频繁项集和关联规则n聚类分析和分类n序列模式统计分析统计分析主要用于改进系统的性能、设计等包括：1)最频繁访问的页面2)每个页面的平均访问时间3)通过一个站点的平均时间频繁项集和关联规则频繁项集和关联规则可以寻找出经常频繁访问的page组，可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。包括两方面的应用：*user 用于Market segmentat
15、ion(市场分割)和个人内容定制*page(content)后者主要用于IR和冲浪辅助聚类和分类聚类和分类序列模式序列模式可用于用户的 visit pattern.包括：1.趋势分析2.拐点检测模式分析n目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。Visualization二隐私保护数据挖掘n隐私保护数据挖掘简介n隐私保护数据挖掘n面向企业信用评估的分布式隐私保护数据挖掘研究一、隐私保护数据挖掘简介nWhatnWhynWhonGoalnHownAn Example什么是数据挖掘n数据挖掘是从大量数据中提取或“挖掘”知识的过程。n数据挖掘以客观、有效的数据源
16、为物质基础。n数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。什么是隐私n针对不同的应用环境，隐私定义不同。n在信息时代，隐私指用户隐藏个人信息的权利和控制自己的信息给其他人的能力。什么是隐私保护数据挖掘n“getting valid data mining results without learning the underlying data values”n噪声背景的数据挖掘n受限制的数据挖掘数据挖掘可能会违反用户的隐私n数据挖掘以准确的数据为数据源，进行数据归纳分析。n个体隐私记录级和属性级上的隐私n组织隐私结果级上的隐私，统计分析后的结果什么人需要隐私保护数据挖掘？n政府和
17、公用事业部门疾病控制中心保险公司n工商业组织n跨国公司每个国家的法律是不同的n军事情报分析n犯罪行为分析n反恐分析隐私的限制不会阻止数据挖掘n数据挖掘的目标是结果的总结关联规则分类聚类n结果本身不会违反隐私不包含个人身份信息反映的是整个数据的归纳统计结果，而不是针对每个单位The problem is computing the results without access to the data!隐私保护数据挖掘的目标nPPDM encompasses the dual goal of meeting privacy requirements and providing valid data
18、 mining results.n保护隐私和满足安全性要求（安全性）n产生正确的数据挖掘归纳结果（准确性）n提供高效的数据挖掘算法（高效性）AccuracyEfficiencyPrivacy如何进行隐私保护数据挖掘计算频繁项集：ABC 5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC:R+count-freq.*DBSizeR=17ABC:17+5-.05*100ABC:17ABC:17+9-.05*200ABC:12ABC:12+18-.05*300ABC:19ABC:19 R?ABC:YES!计算频繁项集：ABC 5%?2ABC
19、=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC:R+count-freq.*DBSizeR=17ABC:17+9-.05*200ABC:12+18-.05*300ABC:19 R?ABC:YES!二、隐私保护数据挖掘n隐私保护数据挖掘分类保护个体用户隐私个体用户隐私保护组织用户隐私组织用户隐私n研究方法数据隐藏安全多方计算保护个体用户隐私个体用户隐私n这是一种记录和属性级上的隐私保护。在原始数据库中，类似于标识符、姓名、地址和喜好等用户数据作为用户的隐私应该被保护。保护敏感的原始数据的隐私保护数据挖掘方法应该能够使得用户的敏感的原始数据被修改，
20、以便数据的使用者不能对用户的原始数据进行直接存储，不能查看用户的隐私，以此保护用户的私有数据。个体隐私:保护记录n每个项都不允许泄漏n记录的一部分是可以泄漏的个人身份信息个人身份信息n删除标识符n但是我们无法保证身份不能被推断候选码一些个体特有的属性Data Mining enables such tracing!保护组织用户隐私组织用户隐私n这是一种结果级上的隐私保护，这里的目标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。在数据挖掘的统计模型中，有很多挖掘出的知识也会泄漏用
21、户的隐私。保护敏感的挖掘知识的隐私保护数据挖掘方法能够保护用户的敏感知识，以便不会被泄漏用作其他的目的，造成用户重要信息的泄密。组织隐私n保护个体隐私是不够的n保护从组织中获得的敏感知识策略模式数据挖掘的结果n目标：身份信息不能泄漏数据挖掘之后的模式和知识同样不能泄漏Database用户数据挖掘挖掘得到的知识变换后数据库隐藏敏感的知识P3Pn发布的隐私策略n协同达成的一致策略隐私保护数据挖掘架构nB2B的架构中，具体的事务分布在几个不同的站点。每个站点拥有一个包含大量事务的私有数据库。这里用到的主要计算技术是安全多方计算（Secured multiparty computation）及其变种。
22、nB2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。在线调查表是这种B2C架构的一个典型的例子。其中包含一个调查表收集器和分析器以及众多的数据提供者。解决方法分类n数据隐藏(Data Obfuscation)对数据进行挖掘时，不能看到真实的数据n安全多方计算仅仅可信的结点可以看到数据数据隐藏n目标:隐藏被保护信息私有数据可用噪声较大真实值不能确定得到主要技术匿名技术 随机的数据转换(random data perturbation)阻塞技术(blocking)聚集或融合技术(aggregation or merging)交换技术(swapping)采样技术(sampling)基于
23、阻塞的技术(blocking)BlockingAlgorithm主要用于组织隐私的保护随机的数据转换(random data perturbation)ABCD11101011000111101011ABCD111010100011110101DistortionAlgorithm随机的数据转换n目标统计属性可以较精确得到个体数据不能得到n离散型变量转换布尔型变量分类型(Category)变量n连续型变量转换布尔型变量转换分类型变量转换连续型变量转换布尔型变量转换n购物篮问题n数据位以概率p 被翻转n对经过变化的数据进行挖掘1TDCM C101,1CppMCCp p分类型变量转换nSelect
24、-a-size RandomizationnCut and Paste RandomizationSelect-a-size Randomizationn给定大小为t的事务,构造t:选择j 属于0 到m Pj被选择的概率=pmj把事务加入t的 j个项加入事务t;其它不在事务t的属性以概率pm 加入事务 tn参数pmj和pm的选择基于需要的隐私度Cut and Paste Randomizationn给定大小为t的事务,构造t:在0到Km间选择 j把事务t 的j个项加入t;事务t的其它项以概率pm加入 tn参数Km和pm的选择基于所需要的隐私度连续型变量隐私保护挖掘方法nAgrawal and
25、Srikant,SIGMOD00Bayes rulen改进by Agrawal and Aggarwal,SIGMOD01Expectation Maximization(EM)Bayes rulenAgrawal and Srikant(2000)Decision TreesnPerturb Data with Value Distortion用户提供 xi+r 代替 xir 是一个随机变量，服从分布n平均分布-a,an高斯分布(u,)Bayes rulenx1,x2,xn 是n个独立同分布的随机变量ny1,y2,yn 是n个独立同分布的随机变量nW=X+Yn给定FY和W，估计FX安全多方计算nMotivation:分布式隐私保护数据挖掘n目标：结果公布每个用户只知道自己的数据比较数据隐藏安全多方计算复杂性一般高计算、通信安全性较高高主要问题安全性和准确性的折衷效率适用领域较广Web,Corporate小规模分布式Corporate分布式隐私保护数据挖掘的目标n安全性分析知道自己的数据和最终的结果不清楚其它用户的数据n避免相互勾结n通信分析分布式隐私保护数据挖掘方法nSemi-Honest ModelnMalicious分类n水平分布型数据(Horizontal Partitioning)n垂直分布型数据(Vertical Partitioning)水平型分布数据垂直分布型数据
