火龙果-大数据的存贮和处理

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