第7课 数据挖掘的高级 主题 徐从富，副教授 浙江大学人工智能研究所浙江大学本科生数据挖掘导论课件内容提纲nWeb挖掘n隐私保护数据挖掘1Web 挖掘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 MiningWeb Structure Mining Web内容挖掘nWeb内容挖掘是从文档内容或其描述中抽 取知识的过程。nWeb内容挖掘策略直接挖掘文档的内容在其它工具搜索的基础上进行改进Web内容挖掘（续）n提取文字、图片或者其他组成网页内容成 分的信息，即通过有效的内容挖掘能告诉 我们哪些页面是德文或者法文的？哪些站 点卖我们喜欢的东西？哪些页面介绍了我 们感兴趣的知识？搜索引擎、智能代理和 一些推荐引擎都使用内容挖掘来帮助客户 在浩瀚的网络空间中寻找所需的内容。 Web结构挖掘nWeb结构挖掘研究的是Web文档的链接结 构，揭示蕴含在这些文档结构中的有用模 式，处理的数据是Web结构数据。是从 WWW的组织结构和链接关系中推导知识。 由于文档之间的互连，WWW能够提供除文 档内容之外的有用信息。利用这些信息， 可以对页面进行排序，发现重要的页面。Web结构挖掘（续）n提取网络的拓扑信息网页之间的链接 信息，即通过有效的结构挖掘能告诉我们 哪些页面被其他页面所链接？哪些页面指 向了其他页面？哪些页面的集合构成了一 个独立的整体？ Web日志挖掘nWeb日志挖掘的主要目标则是从Web的访 问记录中（Web服务器log日志）抽取感兴 趣的模式。WWW中的每个服务器都保留了 访问日志（Web access log），记录了用 户访问和交互的信息。分析这些数据可以 帮助理解用户的行为，从而改进站点的结 构，或为用户提供个性化的服务。Web日志挖掘（续）n一般的访问模式跟踪通过分析日志数据来了解用户的访问模式和倾 向，以改进站点的组织结构n个性化的使用记录跟踪倾向于分析单个用户的偏好，其目的是根据不 同用户的访问模式，为每个用户提供定制的站 点。Web日志挖掘（续）n提取关于客户如何运用浏览器浏览和使用 这些链接的信息，即通过有效的日志挖掘 能告诉我们那些客户访问了哪些页面？在 每一页上待了多长时间？下一步单击了什 么？在站点中是按照怎样的访问路线通向 检查计数器，又是通过怎样的路线直接退 出的？ Web内容挖掘Web结构挖 掘Web日志挖 掘处理数据 类型IR方法：无结构 数据、半结构数 据数据库方法：半 结构化数据Web结构数据用户访问Web数 据主要数据自由化文本、 HTML标记的超 文本HTML标记的超 文本Web文档内及文 档间的超链Serverlog, Proxy serverlog, Client log表示方法词集、段落、概 念、IR的三种经 典模型对象关系模型图关系表、图处理方法统计、机器学习 、自然语言理解数据库技术机器学习、专有 算法统计、机器学习 、关联规则主要应用分类、聚类、模 式发现模式发现、数据 向导、多层数据 库、站点创建与 维护页面权重 分类聚类 模式发现Web站点重建， 商业决策4. Web挖掘过程n资源发现：在线或离线检索Web的过程，例如用 爬虫（crawler）或（spider）在线收集Web页面n信息选择与预处理：对检索到的Web资源的任何 变换都属于此过程。词干提取高低频词的过滤汉语词的切分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.0“nStatus: 200nBytes: -nReferrer: “-”nAgent: “Mozilla/4.61 en (WinNT; I)“2. Web 日志挖掘应用nApplications电子商务中发现潜在客户增强终端用户信息获取的质量提高Web服务器的性能合理放置广告提高站点设计欺诈和入侵检测预测用户行为3. Web日志挖掘过程Web日志挖掘过程预处理数据挖掘模式分析 数据预处理n数据清理n用户对话识别n页面视图识别n路径完整数据清理n根据一组原始的日志项，完成一系列基本 任务，如归并日志、解析日志等。对于一 些网站，需要过滤掉图象文件，这可以通 过检查文件后缀实现。一般地，我们需要 对日志中的状态码（status code）进行检 查。清理后的Sample LogIP AddressTime/DateMethod/URIReferrerAgent 202.120.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.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: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 其它不在事务t的属性以概率pm 加入事务 tn参数pmj和pm的选择基于需要的隐私度Cut and Paste Randomizationn给定大小为t的事务, 构造t:在0到Km间选择 j把事务t 的j个项加入t;事务t的其它项以概率pm加入 tn参数Km和pm的选择基于所需要的隐私度连续型变量隐私保护挖掘方法nAgrawal and 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)水平型分布数据垂直分布型数据