大数据存储与处理-概述.ppt

大数据存储与处理-概述
【通用模板】【教育说课】【述职报告】【工作汇报】
数据汇总
pagerank。谷歌成功的关键算法之一。Web的复杂结构可以由每个页面的pagerank描述，反映了一个web上的随机游走者在任意时刻处于该页面大数据存储与处理-概述
【通用模板】【教育说课】【述职报告】【工作汇报】
数据汇总
pagerank。谷歌成功的关键算法之一。Web的复杂结构可以由每个页面的pagerank描述，反映了一个web上的随机游走者在任意时刻处于该页面的概率。
聚类。数据被看成是多维空间的点。空间相互邻近的点被认为是相同的类别。每个类别可以析括表示，如质心或者是到质心的平均距离。
*
*
*
*
特征抽取
从数据中寻找某个现象的特殊样例，用这些样例来表示数据。介绍两种方法：
频繁项集：在很多购物篮/订单里面寻找同时出现的项集/商品。
相似项：数据可以描述为一系列的集合。寻找共同元素较多的集合。亚马逊网站的顾客可以理解为他购买商品的集合。寻找相似的集合也就是寻找具有类似兴趣的人，把这些人购买过的东西推荐给该顾客。也称为协同过滤
*
*
数据挖掘的统计限制
2002年，布什政府提出一项对所有数据进行挖掘的计划，没有被国会通过。目的是追逐恐怖活动
问题：如果能够获得所有的数据，并且想从中获得恐怖活动的信息。是否会导致误报很多无辜的行为？
*
*
Bonferroni’s Principle
随着数据规模的增加，任何数据都会显现出一些不同寻常的特征，这些特征看上去非常重要，实际上却并不重要。
Bonferroni’s Principle。在数据随机性假设的基础上，计算所寻找的事件的发生的期望值，如果该期望值大于找到的真实事件的数目，则所找到的事件是假象。
*
*
关于整体情报预警的故事
设有一群坏人会偶尔在酒店聚会策划阴谋
想找出那些同一天在同一个酒店至少出现两次的人群.
13
假设
109 可疑人.
1000 days.
每个人去酒店的概率 1% (1000天里住10天酒店).
酒店容纳100 人 (有 105 个酒店).
每个人行为都是随机的。数据挖掘能发现可疑行为吗？
14
Calculations – (1)
人员 p 和人员 q 同一天在同一个酒店出现的概率 :
1/100  1/100  10-5 = 10-9.
人员p 和 q 在d1 和 d2 出现在同一个酒店的概率:
10-9  10-9 = 10-18.
1000天任意两天的排列组合:
5105.
p at
some
hotel
q at
some
hotel
Same
hotel
15
Calculations – (2)
人员 p 和 q 在任意两天出现在同一个酒店的概率:
5105  10-18 = 510-13.
可能的人数是10亿，任意两个人的排列组合是:
51017.
平均可疑的人员对的数目:
51017  510-13 = 250,000.
实际上他们是纯随机导致的巧合
16
结论
假设真的有10 对坏人在同一个酒店出现两次.
需要扫描250,010 对候选人才能找出这10对坏人.
这个方法好吗？
17
小结
寻找某个性质的事件的时候 (如, “两个人在同一个旅馆出现了两次”), 需要考虑纯随机性是否会产生多个具有这个性质的事件。
18
Rhine Paradox – (1)
Joseph Rhine是1950年代的心理学家，他猜想某些人有超感知能力.
他设计了一个实验：要求实验对象猜10张隐藏的卡片的颜色： – 红 或者 蓝？
他发现1000个人里面有1个具有超感知能力 –能猜对所有10张卡片的颜色!
19
Rhine Paradox – (2)
他告诉这些人他们有超能力，并要求他们再做一次同样的实验.
这些人都失去了他们的超能力.
为什么?
见下一个幻灯片.
20
Rhine Paradox – (3)
这个心理学家总结道：你不能告诉人们他们具有超能力，否则他们就会失去超能力.
21
Moral
理解了Bonferroni’s 原理，能够使你不犯那个心理学家的错误
22
相关知识
词语在文档中的重要性
根据文档的主题对文档进行分类
主题是通过一些能够表现主题的词语进行刻画。例如棒球、球、跑等。
并不是出现频率高的词最重要。如the,and等，这些常见的词（数百个）应该去掉
事实上，描述主题的词都比较罕见。
*
*

假定有N篇文档，fij为词i在文档j中出现的频率（次数），词项i在文档j中的词项频率Tfij定义为
Tfij=fij/maxkfkj