• 从磁盘读入数据的时间是从内存读入数据 的100000倍。磁盘读入数据的时间大约是 10毫秒。 • 如果需要读取的数据在磁盘上的一个柱面 上，则读入一批数据时不需要转动磁头， 则读入每块数据的时间可以小于10毫秒。
–如果哈希键值随机地从某个合理可能的哈希键 分布中抽样而成，函数h把数目近似相等的哈希 键值映射到相同的桶编号。
• H(x)=x mod B • 如果x是随机的整数值，则x将被均匀分配 到每个桶中，即0到B-1的整数
–如果X只是偶数，且B=10，则答案只有0，2， 4，6，8.答案不够均匀 –如果X只是偶数，且B=11，则答案均匀
• 设有一群坏人会偶尔在酒店聚会策划阴谋 • 想找出那些同一天在同一个酒店至少出现两 次的人群.
• 其他条件同上，但是在文档k中，此w出现 一次，而该文档中出现最多的词的频率是 20.则
• 哈希函数的输入是一个哈希键值(hashkey），输出是一个桶编号(bucket number）。哈希函数将哈希键值随机化
• 假设线 对坏人在同一个酒店出现两 次. • 需要扫描250,010 对候选人才能找出这10对 坏人.
• 寻找某个性质的事件的时候 (如, “两个人在 同一个旅馆出现了两次”), 需要考虑纯随机 性是否会产生多个具有这个性质的事件。
• 数据挖掘已被看成是一个算法问题。数据 模型就是提供复杂查询的答案。 • 除了统计建模，其它大部分建模方法可分 为如下两类
–对数据进行简要汇总 –从数据中抽取最突出的特征来代替数据并将剩 余内容忽略。
• pagerank。谷歌成功的关键算法之一。Web 的复杂结构可以由每个页面的pagerank描 述，反映了一个web上的随机游走者在任意 时刻处于该页面的概率。 • 聚类。数据被看成是多维空间的点。空间 相互邻近的点被认为是相同的类别。每个 类别可以析括表示，如质心或者是到质心 的平均距离。
• 从数据中寻找某个现象的特殊样例，用这 些样例来表示数据。介绍两种方法：
–频繁项集：在很多购物篮/订单里面寻找同时出 现的项集/商品。 –相似项：数据可以描述为一系列的集合。寻找 共同元素较多的集合。亚马逊网站的顾客可以 理解为他购买商品的集合。寻找相似的集合也 就是寻找具有类似兴趣的人，把这些人购买过 的东西推荐给该顾客。也称为协同过滤
• 他告诉这些人他们有超能力，并要求他们 再做一次同样的实验. • 这些人都失去了他们的超能力. • 为什么?
• 这个心理学家总结道：你不能告诉人们他 们具有超能力，否则他们就会失去超能力.
• 理解了Bonferroni’s 原理，能够使你不犯那 个心理学家的错误
• 通常的数据对象是记录。每个记录包括多 个字段。 • 在某个字段上面建立索引。索引一种高效 的数据查找结构。例如，哈希函数就是一 种实现方法。 • 如图1-2所示。
• • • • Web图中的节点度 商品的销量 Web网站的大小 词在文档中的分布
–某网站有较多的输入链接，将导致更多的人找 到他，从而获得更多的输入链接
• 研究可见数据遵从的总体概率分布。如已有一系列 数据，先猜想服从高斯分布，从数据获取模型参 数，验证与数据分布是附合
• 将数据当作某类算法的训练集训练算法。然后再用 这个算法分析未知的数据
• 机器学习的长处。当对要在数据中寻找的目标一无 所知的时候。如不知道是哪些因素影响人们对影片 的喜好。netflix竞赛。 • 如目标能明确描述，机器学习方法并不成功。如在 web上寻找个人简历。机器学习方法.不如关键词或 者短语更准确,
• 2002年，布什政府提出一项对所有数据进 行挖掘的计划，没有被国会通过。目的是 追逐恐怖活动 • 问题：如果能够获得所有的数据，并且想 从中获得恐怖活动的信息。是否会导致误 报很多无辜的行为？
• 随着数据规模的增加，任何数据都会显现 出一些不同寻常的特征，这些特征看上去 非常重要，实际上却并不重要。 • Bonferroni’s Principle。在数据随机性假设 的基础上，计算所寻找的事件的发生的期 望值，如果该期望值大于找到的真实事件 的数目，则所找到的事件是假象。
• Joseph Rhine是1950年代的心理学家，他猜 想某些人有超感知能力. • 他设计了一个实验：要求实验对象猜10张 隐藏的卡片的颜色： – 红 或者 蓝？ • 他发现1000个人里面有1个具有超感知能力 –能猜对所有10张卡片的颜色!
• 1·1 数据挖掘的定义 • 1.2 数据挖掘的统计限制 • 1·3 相关知识
–根据文档的主题对文档进行分类 –主题是通过一些能够表现主题的词语进行刻 画。例如棒球、球、跑等。 –并不是出现频率高的词最重要。如the,and等， 这些常见的词（数百个）应该去掉 –事实上，描述主题的词都比较罕见。
• 假定有N篇文档，fij为词i在文档j中出现的 频率（次数），词项i在文档j中的词项频率 Tfij定义为 • Tfij=fij/maxkfkj • 其实就是fij除以在该文档出现次数最多的词 的频率
• 例1.3 如果有1048576个文档，词w在1024个 文档中出现。对于文档j，w出现了20次， 也是该文档中出现的最高频率。
