浙江大学本科生《数据挖掘导论》课件 第7课 数据挖掘的高级主题 徐从富，副教授 浙江大学人工智能研究所.

Presentation on theme: "浙江大学本科生《数据挖掘导论》课件 第7课 数据挖掘的高级主题 徐从富，副教授 浙江大学人工智能研究所."— Presentation transcript:

1 浙江大学本科生《数据挖掘导论》课件 第7课 数据挖掘的高级主题 徐从富，副教授 浙江大学人工智能研究所

2 内容提纲 Web挖掘 隐私保护数据挖掘

3 Web 挖掘 WWW Knowledge

4 Web 挖掘简介 Web日志挖掘

5 Web Mining简介 产生原因 应用 分类 过程

6 产生原因 网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。 传统数据挖掘和文本挖掘技术的不断完善和应用。

7 应用 查询相关信息 从Web数据发现潜在的未知信息 了解用户的兴趣爱好 信息个性化

8 Web 挖掘分类 Web Mining Web Content Mining Web Structure Mining
Web Usage Mining

9 Web内容挖掘 Web内容挖掘是从文档内容或其描述中抽取知识的过程。 Web内容挖掘策略 直接挖掘文档的内容 在其它工具搜索的基础上进行改进

10 Web内容挖掘（续） 提取文字、图片或者其他组成网页内容成分的信息，即通过有效的内容挖掘能告诉我们哪些页面是德文或者法文的？哪些站点卖我们喜欢的东西？哪些页面介绍了我们感兴趣的知识？搜索引擎、智能代理和一些推荐引擎都使用内容挖掘来帮助客户在浩瀚的网络空间中寻找所需的内容。

11 Web结构挖掘 Web结构挖掘研究的是Web文档的链接结构，揭示蕴含在这些文档结构中的有用模式，处理的数据是Web结构数据。是从WWW的组织结构和链接关系中推导知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。

12 Web结构挖掘（续） 提取网络的拓扑信息――网页之间的链接信息，即通过有效的结构挖掘能告诉我们哪些页面被其他页面所链接？哪些页面指向了其他页面？哪些页面的集合构成了一个独立的整体？

13 Web日志挖掘 Web日志挖掘的主要目标则是从Web的访问记录中（Web服务器log日志）抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。

14 Web日志挖掘（续） 一般的访问模式跟踪 个性化的使用记录跟踪 通过分析日志数据来了解用户的访问模式和倾向，以改进站点的组织结构
倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。

15 Web日志挖掘（续） 提取关于客户如何运用浏览器浏览和使用这些链接的信息，即通过有效的日志挖掘能告诉我们那些客户访问了哪些页面？在每一页上待了多长时间？下一步单击了什么？在站点中是按照怎样的访问路线通向检查计数器，又是通过怎样的路线直接退出的？

16 Web内容挖掘 Web结构挖掘 Web日志挖掘 处理数据 类型 主要数据 表示方法 处理方法 主要应用 IR方法：无结构数据、半结构数据
数据库方法：半结构化数据 Web结构数据 用户访问Web数据 主要数据 自由化文本、HTML标记的超文本 HTML标记的超文本 Web文档内及文档间的超链 Serverlog, Proxy serverlog, Client log 表示方法 词集、段落、概念、IR的三种经典模型 对象关系模型 图 关系表、图 处理方法 统计、机器学习、自然语言理解 数据库技术 机器学习、专有算法 统计、机器学习、关联规则 主要应用 分类、聚类、模式发现 模式发现、数据向导、多层数据库、站点创建与维护 页面权重 分类聚类 模式发现 Web站点重建，商业决策

17 Web挖掘过程 资源发现：在线或离线检索Web的过程，例如用爬虫（crawler）或（spider）在线收集Web页面
词干提取 高低频词的过滤 汉语词的切分 综合过程：自动发现Web站点的共有模式 分析过程：对挖掘到的模式进行验证和可视化处理

18 Web日志挖掘 Web日志挖掘数据类型 Web日志挖掘应用 Web日志挖掘过程

19 服务器日志

20 数据类型 Client IP: 128.101.228.20 Authenticated User ID: - -
Time/Date: [10/Nov/1999:10:16: ] Request: "GET / HTTP/1.0" Status: 200 Bytes: - Referrer: “-” Agent: "Mozilla/4.61 [en] (WinNT; I)"

21 Web 日志挖掘应用 Applications 电子商务中发现潜在客户 增强终端用户信息获取的质量 提高Web服务器的性能 合理放置广告
提高站点设计 欺诈和入侵检测 预测用户行为

22 Web日志挖掘过程

23

24

25 Web日志挖掘过程 预处理 数据挖掘 模式分析

26 数据预处理 数据清理 用户对话识别 页面视图识别 路径完整

27

28 数据清理 根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（status code）进行检查。

29 清理后的Sample Log IP Address Time/Date Method/URI Referrer Agent
15:30:01/2-Jan-01 GET Index.htm Mozilla/4.0(IE5.0W98) GET 1.htm GET A.htm 15:37:09/2-Jan-01 GET E.htm 15:33:04/2-Jan-01 Mozilla/4.0(IE4.0NT) 15:35:11/2-Jan-01 GET B.htm GET C.htm

30 用户对话识别 1.IP Address & Agent 2.Embedded Session ID
3.Registration(User Profile) 4.Cookie 5.Software Agent (Applet&Scrtipt) 6.Modified Browser

31 用户对话识别（续） 方法 说明 隐私性保护 优点 缺点 IP地址/代理服务器 假定每个独立IP地址/代理服务器组是独立用户 低
通常可用，无需附加技术。 无法保证唯一性，在随机或者轮换IP情况下失效 嵌入式对话ID 通过动态形成页面将ID加入每个链接 低/中等 通常可用，不需依赖于IP地址 无法了解重复访问，需要完全动态站点。 注册 用户确切地登陆站点 中等 可以跟踪单个用户，而不仅仅是浏览器 不是全部用户都愿意注册 Cookie 在客户端机器上保留标识符 中等/高 可以跟踪重复访问 能被禁止。不为大众接收 软件代理服务器 程序载入浏览器从而将日志数据返回 高 可以得到单个Web站点的确切日志数据 很可能被拒绝。不为大众接收 改进型浏览器 浏览器记录日志数据 非常高 可以得到关于整个Web的日志数据 用户必须确切地得到软件

32 用户对话识别 User1: User2: Mozilla/4.0(IE5.0W98) 202.120.224.4
15:30:01/2-Jan-01 GET Index.htm GET 1.htm GET A.htm 15:37:09/2-Jan-01 GET E.htm 15:35:11/2-Jan-01 GET C.htm Mozilla/4.0(IE4.0NT) User2: 15:33:04/2-Jan-01 GET Index.htm GET 1.htm GET A.htm 15:35:11/2-Jan-01 GET B.htm

33 页面视图识别 User1: User2: Mozilla/4.0(IE5.0W98) 202.120.224.4 1-A
1-C A.htm E C.htm Mozilla/4.0(IE4.0NT) User2: 1-A B A.htm

34 路径补全 解决由于Cache带来的问题路径不全的问题

35 数据挖掘 统计分析 频繁项集和关联规则 聚类分析和分类 序列模式

36 统计分析 主要用于改进系统的性能、设计等 包括： 1) 最频繁访问的页面 2) 每个页面的平均访问时间 3) 通过一个站点的平均时间

37 频繁项集和关联规则 可以寻找出经常频繁访问的page组， 可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。

38 聚类和分类 包括两方面的应用： *user 用于Market segmentation(市场分割)和个人内容定制
*page(content) 后者主要用于IR和冲浪辅助

39 序列模式 可用于用户的 visit pattern.包括： 1.趋势分析 2.拐点检测

40 模式分析 目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。 Visualization

41 隐私保护数据挖掘 隐私保护数据挖掘简介 隐私保护数据挖掘 面向企业信用评估的分布式隐私保护数据挖掘研究

42 一、隐私保护数据挖掘简介 What Why Who Goal How An Example

43 什么是数据挖掘 数据挖掘是从大量数据中提取或“挖掘”知识的过程。 数据挖掘以客观、有效的数据源为物质基础。
数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。

44 什么是隐私 针对不同的应用环境，隐私定义不同。 在信息时代，隐私指用户隐藏个人信息的权利和控制自己的信息给其他人的能力。

45 什么是隐私保护数据挖掘 “getting valid data mining results without learning the underlying data values” 噪声背景的数据挖掘 受限制的数据挖掘

46 数据挖掘可能会违反用户的隐私 数据挖掘以准确的数据为数据源，进行数据归纳分析。 个体隐私 组织隐私 记录级和属性级上的隐私
结果级上的隐私，统计分析后的结果

47 什么人需要隐私保护数据挖掘？ 政府和公用事业部门 工商业组织 跨国公司 军事情报分析 犯罪行为分析 反恐分析 疾病控制中心 保险公司
每个国家的法律是不同的 军事情报分析 犯罪行为分析 反恐分析

48 The problem is computing the results without access to the data!
隐私的限制不会阻止数据挖掘 数据挖掘的目标是结果的总结 关联规则 分类 聚类 结果本身不会违反隐私 不包含个人身份信息 反映的是整个数据的归纳统计结果，而不是针对每个单位 The problem is computing the results without access to the data!

49 隐私保护数据挖掘的目标 PPDM encompasses the dual goal of meeting privacy requirements and providing valid data mining results. 保护隐私和满足安全性要求（安全性） 产生正确的数据挖掘归纳结果（准确性） 提供高效的数据挖掘算法（高效性） Accuracy Efficiency Privacy

50 如何进行隐私保护数据挖掘

51 计算频繁项集：ABC ≥ 5%? 1 ABC=18 DBSize=300 ABC: 19 ABC: 12+18-.05*300
ABC: 19 ≥ R? ABC: YES! 2 ABC=9 DBSize=200 3 ABC=5 DBSize=100 R=17 ABC: *200 ABC: 12 ABC: *100 ABC: R+count-freq.*DBSize ABC: 17

52 二、隐私保护数据挖掘 隐私保护数据挖掘分类 保护个体用户隐私 保护组织用户隐私 研究方法 数据隐藏 安全多方计算

53 保护个体用户隐私 这是一种记录和属性级上的隐私保护。在原始数据库中，类似于标识符、姓名、地址和喜好等用户数据作为用户的隐私应该被保护。保护敏感的原始数据的隐私保护数据挖掘方法应该能够使得用户的敏感的原始数据被修改，以便数据的使用者不能对用户的原始数据进行直接存储，不能查看用户的隐私，以此保护用户的私有数据。

54 个体隐私: 保护记录 每个项都不允许泄漏 记录的一部分是可以泄漏的 个人身份信息

55 Data Mining enables such tracing!
个人身份信息 删除标识符 但是我们无法保证身份不能被推断 候选码 一些个体特有的属性 Data Mining enables such tracing!

56 保护组织用户隐私 这是一种结果级上的隐私保护，这里的目标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。在数据挖掘的统计模型中，有很多挖掘出的知识也会泄漏用户的隐私。保护敏感的挖掘知识的隐私保护数据挖掘方法能够保护用户的敏感知识，以便不会被泄漏用作其他的目的，造成用户重要信息的泄密。

57 组织隐私 保护个体隐私是不够的 保护从组织中获得的敏感知识 目标： 策略模式 数据挖掘的结果 身份信息不能泄漏
数据挖掘之后的模式和知识同样不能泄漏

58 数据挖掘 用户 挖掘得到的知识 Database 变换后 数据库 隐藏敏感的知识

59 P3P 发布的隐私策略 协同达成的一致策略

60 隐私保护数据挖掘架构 B2B的架构中，具体的事务分布在几个不同的站点。每个站点拥有一个包含大量事务的私有数据库。这里用到的主要计算技术是安全多方计算（Secured multiparty computation）及其变种。 B2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。在线调查表是这种B2C架构的一个典型的例子。其中包含一个调查表收集器和分析器以及众多的数据提供者。

61 解决方法分类 数据隐藏 (Data Obfuscation) 对数据进行挖掘时，不能看到真实的数据 安全多方计算 仅仅可信的结点可以看到数据

62 数据隐藏 目标: 隐藏被保护信息 私有数据可用 噪声较大 真实值不能确定得到

63 主要技术 匿名技术 随机的数据转换(random data perturbation) 阻塞技术(blocking)
聚集或融合技术(aggregation or merging) 交换技术 (swapping) 采样技术 (sampling)

64 基于阻塞的技术(blocking) 主要用于组织隐私的保护 Initial Database New Database A B C D 1
A B C D 1 ? Blocking Algorithm Na parousiasoume ti kanei kai meta ta differences

65 随机的数据转换(random data perturbation)
Sample Database Distorted Database A B C D 1 A B C D 1 Distortion Algorithm

66 随机的数据转换 目标 离散型变量转换 连续型变量转换 布尔型变量 转换 分类型变量 转换 连续型变量 转换 统计属性可以较精确得到
个体数据不能得到 离散型变量转换 布尔型变量 分类型 (Category) 变量 连续型变量转换 布尔型变量 转换 分类型变量 转换 连续型变量 转换

67 布尔型变量转换 购物篮问题 数据位以概率p 被翻转 对经过变化的数据进行挖掘

68 分类型变量转换 Select-a-size Randomization Cut and Paste Randomization

69 Select-a-size Randomization
给定大小为t的事务, 构造t’: 选择j 属于0 到m P[j被选择的概率]= pm[j] 把事务加入t的 j个项加入事务·t’; 其它不在事务t的属性以概率pm 加入事务 t’ 参数pm[j]和pm的选择基于需要的隐私度

70

71 Cut and Paste Randomization
给定大小为t的事务, 构造t’: 在0到Km间选择 j 把事务t 的j个项加入t’; 事务t的其它项以概率pm加入 t’ 参数Km和pm的选择基于所需要的隐私度

72 连续型变量隐私保护挖掘方法 Agrawal and Srikant, SIGMOD’00
Bayes’ rule 改进by Agrawal and Aggarwal, SIGMOD’01 Expectation Maximization (EM)

73 Bayes’ rule Agrawal and Srikant (2000) Decision Trees
Perturb Data with Value Distortion 用户提供 xi+r 代替 xi r 是一个随机变量，服从分布 平均分布 [-a, a] 高斯分布 (u, σ)

74 Bayes’ rule x1,x2,…,xn 是n个独立同分布的随机变量 y1,y2,…,yn 是n个独立同分布的随机变量 W=X+Y
给定FY和W，估计FX

75

76 安全多方计算 Motivation: 分布式隐私保护数据挖掘 目标： 结果公布 每个用户只知道自己的数据

77

78 比较 数据隐藏 安全多方计算 复杂性 一般 高 计算、通信 安全性 较高 主要问题 安全性和准确性的折衷 效率 适用领域 较广 Web, Corporate 小规模分布式 Corporate

79

80 分布式隐私保护数据挖掘的目标 安全性分析 知道自己的数据和最终的结果 不清楚其它用户的数据 避免相互勾结 通信分析

81 分布式隐私保护数据挖掘方法 Semi-Honest Model Malicious

82 分类 水平分布型数据(Horizontal Partitioning) 垂直分布型数据(Vertical Partitioning)

83 水平型分布数据

84 垂直分布型数据