数据科学导论

第1章 大数据概述

大数据是人们获得新的认知，创造新的价值的源泉；大数据还是改变市场、组织机构，以及政府与公民关系的方法。作者认为，大数据的核心就是预测。这个核心代表着我们分析信息时的三个转变：第1个转变就是，在大数据时代，我们可以分析更多的数据，有时候甚至可以处理和某个特别现象相关的所有数据，而不再依赖于随机采样。第2个改变就是，研究数据如此之多，以至于我们不再热衷于追求精确度。第3个转变，因前两个转变而促成，即我们不再热衷于寻找因果关系

大数据从哪里来？

1Byte = 8 Bit

1KB = 1,024 Bytes

1MB = 1,024 KB = 1,048,576 Bytes

1GB = 1,024 MB = 1,048,576 KB = 1,073,741,824 Bytes

1TB = 1,024 GB = 1,048,576 MB = 1,099,511,627,776 Bytes

1PB = 1,024 TB = 1,048,576 GB =1,125,899,906,842,624 Bytes

1EB = 1,024 PB = 1,048,576 TB = 1,152,921,504,606,846,976 Bytes

1ZB = 1,024 EB = 1,180,591,620,717,411,303,424 Bytes

1YB = 1,024 ZB = 1,208,925,819,614,629,174,706,176 Bytes

1TB 1块1TB硬盘 20万张照片
1PB 两个数据中心机柜 16个Blackblaze pod 存储单元
1EB 2000个机柜 占据一个街区的4层数据中心
1ZB 1000个数据中心 重庆高新区的4/5区域
1YB 100万个数据中心 两个重庆市主城九区

大数据的发展历程

信息化浪潮 发生时间 标志 解决问题 代表企业
第一次浪潮 1980年前后 个人计算机 信息处理 Intel、AMD、IBM、苹果、微软、联想、戴尔、惠普等
第二次浪潮 1995年前后 互联网 信息传输 雅虎、谷歌、阿里巴巴、百度、腾讯等
第三次浪潮 2010年前后 物联网、云计算和大数据 信息爆炸 将涌现出一批新的市场标杆企业

数据科学是什么？

简单来讲：数据科学是一门将数据变得有用的学科

什么是大数据？

维基百科：或称巨量数据、海量数据，指的是所涉及的数据量规模巨大到无法通过人工，在合理时间内达到截取、管理、处理、并整理成为人类所能解读的信息。

Gartner：“大数据”是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

IDC定义：为了更为经济的从高频率获取的、大容量的、不同结构和类型的数据中获取价值，而设计的新一代架构和技术。

麦肯锡：一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合，具有海量的数据规模、快速的数据流转、多样的数据类型和价值密度低四大特征。

大数据的特征

大数据的技术支撑

存储设备容量不断增加

CPU处理能力大幅提升

网络带宽不断增加

数据产生方式的改变

大数据的影响

大数据对科学研究的影响

大数据对思维模式的影响

第2章 大数据相关工程技术与应用

大数据无处不在，包括金融、汽车、零售、餐饮、电信、能源、政务、医疗、体育、娱乐等在内的社会各行各业都已经融入了大数据的印迹

典型的大数据应用实例

2009年，美国谷歌公司在《自然》上发表了关于流感预测的论文，成为大数据在医疗卫生应用的典范。

利用5000****万条美国人最频繁检索的词条和美国疾病预防控制中心（CDC）流感传播时期的数据进行了比较，判断是否流感暴发。

结果显示，数据不仅可以预测流感的暴发情况，而且可以具体到特定地区和州。

从谷歌流感趋势看大数据的应用价值 “谷歌流感趋势”，通过跟踪搜索词相关数据来判断全美地区的流感情况

麻省理工学院、密歇根大学和一家医院创建了一个数据模型，利用心脏病患者的心电图数据，预测在未来一年内患者心脏病发作的几率。

在过去，缺乏对已有数据的比较分析，使得70%的心脏病患者再度发病缺乏预判。

现在通过机器学习和数据挖掘，该模型可以通过累积的数据进行分析，发现高风险指标。

10多年前，康奈尔大学的Sherman教授通过一些小规模食谱的分析，认为气候是影响我们选择调味品最重要的因素

气候本身限制了调味食材的生长（例如八角主要生长在阴湿、土壤疏松的山地，东北就不易培植）

气候条件影响我们对调味食材的需求（例如成都湿度大，大家普遍爱吃花椒，因为它散寒除湿）。

通过大数据，印第安纳大学的Ahn教授分析了多个国家和地区56498份菜谱，他*发现西方和东方一些国家气候相近但饮食天差地别。

西方食材：牛奶、黄油、香草、鸡蛋、蔗糖浆和小麦

东方食材：酱油、葱、香油、米、大豆和姜。

从美食圈国内知名网站“美食街”上下载了我国20个菜系共计8498份菜谱，包含2911种食材。

地理上的相近性对于食材使用的影响远远大于气候的相近性。

结果暗示，如果没有交流，即便气候条件相近，产生的文化结果也会大不一样。

大数据的行业应用——交通领域

大数据技术可以构建城市智慧交通。车辆、行人、道路基础设施、公共服务场所都被整合在智慧交通网络中。洛杉矶利用磁性道路传感器和交通摄像头的数据来控制交通灯信号，从而优化城市的交通流量。通过控制了全市的4500个交通灯，将交通拥堵状况减少了约16%。

大数据的行业应用——通讯领域

利用大数据的采集和分析技术进行实时追踪，例如中国移动的天盾系统能通过大数据有效识别欺诈电话，识别准确率达95%,月均诈骗电话识别总量9200个,月均识别受害人4300个,平均每月挽回客户损失800万。

大数据的行业应用——医疗领域

大数据分析应用的计算能力可以更好的去理解和预测疾病、可以帮助病人对于病情进行更好的治疗。例如，智慧养老及慢性病管理、医药研发、基因工程等

大数据的行业应用——金融领域

大数据在金融领域主要是应用在金融交易方面。高频交易（HFT）是大数据应用比较多的领域。其中大数据分析和挖掘算法可用于交易决策、风险控制、精准营销等。

大数据的行业应用——制造领域

利用工业大数据提升制造业水平，包括产品故障诊断与预测、分析工艺流程、改进生产工艺、优化生产过程能耗、工业供应链分析与优化、生产计划与排程。

大数据的行业应用——生活领域

借助大数据技术更好的了解客户以及他们的爱好和行为。通过搜集浏览器的日志和传感器数据，建立数据模型并预测。

第3章 大数据采集和预处理

大数据采集

（1）数据采集的概念

​ 数据采集（Data Acquisition，DAQ），是指从传感器和其他待测设备等模拟和数字被测单元中自动采集非电量或者电量信号，送到上位机中进行分析，处理。

（2）数据采集的目

​ 是为了测量电压、电流、温度、压力或声音等物理现象。基于PC的数据采集，通过模块化硬件、应用软件和计算机的结合进行测量。

3）数据采集系统

​ 数据釆集系统由硬件和软件两部分组成。从硬件方向来看，目前数据采集系统的结构形式主要有两种：

1）微型计算机数据采集系统。由传感器、模拟多路开关、程控放大器、采样保持器、A／D转换器、计算机及外设等部分组成。

2）集散型数据采集系统。由若干个数据采集站和一台上位机及通信线路组成。

数据抽取转换加载技术

ETL概述

数据抽取转换加载（ETL），是英文 Extract-Transform-Load的缩写，用来描述将数据从来源端经过抽取（extract）、转换（transform）、加载（load）至目的端的过程。

ETL是构建数据仓库的重要一环，用户从数据源抽取出所需的数据，经过数据清洗，最终按照预先定义好的数据模型，将数据加载。

ETL是用来实现异构多数据源的数据集成的工具

其主要的功能包括：

数据的抽取

将数据从不同的网络、不同的操作平台、不同的数据库及数据格式、不同的应用中抽取出来。

数据的转换

数据转换（数据的合并、汇总、过滤、转换等）、重新格式化和计算数据、重新构建关键数据以及总结与定位数据。

数据的装载

将数据跨网络、操作平台装载到目标数据库中。

ETL的实现有多种方法，常用的有三种：

（1）借助ETL工具(如Oracle的OWB、SQL Server 2000的DTS、SQL Server2005的SSIS服务、Informatic等)实现

（2）利用SQL方式实现

（3）通过ETL工具和SQL相结合。

优缺点比较：

借助ETL工具可以快速的建立起ETL工程，屏蔽了复杂的编码任务，提高了速度，降低了难度，但是缺少灵活性。SQL的方法优点是灵活，提高ETL运行效率，但是编码复杂，对技术要求比较高。第三种是综合了前面二种的优点，会极大地提高ETL的开发速度和效率。

数据抽取**——**数据抽取的概念

​ 数据抽取就是一个从数据源中抽取数据的过程。具体来说，就是搜索整个数据源，使用某些标准选择合乎要求的数据，并把这些数据传送到目标文件中。

Ø对于数据仓库来说，必须根据增量装载工作和初始完成装载的变化来抽取数据。

Ø对于操作型系统来说，则需要一次性抽取和数据转换，这两个因素增加了数据抽取工作的复杂性。

数据爬虫技术

爬虫是一种获取数据的工具，通过URL（统一资源定位符，互联网资源存放位置的标准地址）对互联网进行尽可能广泛的遍历。在网络爬虫的系统框架中，主过程由控制器，解析器，资源库三部分组成。

Ø控制器：主要工作是负责给多线程中的各个爬虫线程分配工作任务。

Ø解析器：主要工作是下载网页，进行页面的处理，主要是将一些JS脚本标签、CSS代码内容、空格字符、HTML标签等内容处理掉，爬虫的基本工作是由解析器完成。

Ø资源库：用来存放下载到的网页资源，一般都采用大型的数据库存储，如Oracle数据库，并对其建立索引。

基本流程

1．发起请求

​ 通过HTTP库向目标站点发起请求，即发送一个Request，请求可以包含额外的headers等信息，等待服务器响应。爬虫从已经初始化好的网页链接队列中取出种子链接（如http://www.csdn.net等），通过这些种子链接不断地从互联网中获得新的网页数据。

2．获取响应内容

​ 如果服务器能正常响应，会得到一个Response，Response的内容便是所要获取的页面内容，类型可能有HTML，Json字符串，二进制数据（如图片视频）等类型。通过网页链接下载相应网页数据，通过分析网页数据提取新的链接存储到链接的后续队列中，且将访问过的网页链接进行已访问标记。

3．解析内容

​ 依次不间断地从队列中获取链接并逐一访问，理论上链接集合中的所有链接均被访问后，爬虫将停止工作。得到的内容可能是HTML，可以用正则表达式、网页解析库进行解析。可能是Json，可以直接转为Json对象解析，可能是二进制数据，可以做保存或者进一步的处理。

4．保存数据

​ 保存形式多样，可以存为文本，也可以保存至数据库，或者保存特定格式的文件。

不同种类的爬虫

通用爬虫

（1）从互联网中选出一部分网站页面，将这些页面的URL地址作为URL种子集，将URL种子集中的URL链接依次加入到URL爬取队列中

（2）爬虫工作从爬取队列中读出页面的URL地址

（3）将网页的URL链接地址进行DNS域名解析，变为网站服务器IP地址

（4）网页下载器根据IP地址复制下载页面内容。

（5）从互联网进行网页下载

（6）这些页面内容被存储到页面库中，等待对其建立索引。

（7）为了避免抓取到相同的页面，会有一个存放已经抓取过的网页URL信息的队列。

（8）从被下载的页面中解析出其包含的URL链接，根据上文提到的已抓取URL队列，判断这些URL链接是否爬取过。

（9）如果还没有被爬取，则在URL爬取队列末尾加入该链接，等待后续爬虫任务抓取该网页内容。

（10）直至URL爬取队列为空，爬虫过程停止。

一个通用爬虫的整体工作流程，从宏观的角度来看动态爬取网页的过程，考虑到爬虫工作和互联网所有网页之间的关系，大致可以将这些网页划分为以下五类：

1）已下载网页集合：是指爬虫系统已经从互联网下载到本地等待进行索引工作的网页集合。

2）已过期网页集合：是指考虑到爬虫过程持续时间过长而网页在这个过程中发生了改变，特别是指同一个URL链接代表的已经被爬取下载到本地的网页，和实际该URL链接在互联网中链向的网页内容不一致的情况。

3）待下载网页集合：是指处于URL待爬取队列中的URL地址指向的网页，爬虫系统网页下载器即将下载这些网页。

4）可知网页集合：是指那些没有出现在URL待爬取队列中、也没有被爬虫系统下载的网页，但是通过已被爬取下载的网页或者在URL待爬取队列中的网页的链接关系，可以发现这些可知网页，稍后会被爬虫系统抓取并建立索引。

5）不可知网页集合：是指爬虫无法爬取到的一些网页。不可知网页在实际情况中占据了很高的比例。

主题爬虫

主题爬虫目的是抓取与事先规定的某个主题范围相关的网页，在主题爬虫过程中，建立初始URL集合，集合中的URL链接必须紧扣要爬取的主题

与通用网络爬虫不同之处，主题爬虫对要爬取的页面使用某些算法进行主题判断，将主题无关的网页排除，在系统不断爬取网页的过程中，将与主题相关的网页URL链接加入URL待抓取队列中，然后根据指定的搜索策略选择抓取待抓取队列中网页，如此循环，直到满足爬虫停止条件。

主题爬虫需要尽可能多地识别并爬取相关主题的网页，避免下载主题无关的网页。

分布式爬虫

在面对海量数据时，商业搜索引擎为了在较短的时间内抓取到尽可能多的网页数据，其后台爬虫模式离不开分布式的网络爬虫架构。分布式网路爬虫架构体系使用多层级模式，保证了爬取网页的及时性与覆盖面。

一个大型分布式爬虫分为3个层级：分布式数据中心、分布式抓取服务器及分布式爬虫程序，多个爬虫程序运行在一台抓取服务器上，多个抓取服务器构成抓取集群，也就是分布式数据中心。

常见的分布式爬虫系统架构，根据不同机器之间分工协同方式的差异可以分为两种：主从式分布爬虫和对等式分布爬虫。两者各有优势，也各有缺陷。

主从式分布爬虫

对于主从式来讲，不同的机器分工明确，有一台Master机器是控制节点负责将URL任务分发到其他Slave机器、维护URL待爬取队列和管理各个Slave机器的负载均衡，Slave机器执行下载网页的工作，Slave机器与Slave机器不能直接通信。主从式分布爬虫模式下，Master机器容易成为爬虫系统的瓶颈导致整个爬虫性能的下降。

Master往往容易成为系统瓶颈

对等分布式爬虫

​ 对于对等式来讲，所有的抓取机器在分工上没有不同，每台机器可以独立完成网页爬取任务。每台抓取器之间的分工有一定的运算逻辑(如哈希取模，hash[域名]%m，m为抓取机器数量)，将运算值发送到对应编号相同机器上，由运算的结果来决定由哪台服务器做抓取网页的工作。

这种方式的扩展性不佳，当有一台服务器死机或者添加新的服务器，那么所有URL的哈希求余的结果就都要变化。

大数据爬虫的相关技术

（1）爬虫协议

​ 爬虫协议即Robots协议，其全称为“网络爬虫排除协议”，网站通过Robots协议告诉我们网站中哪些数据可以被爬取，哪些数据不可以被爬取。当我们使用爬虫时也应当尊重网站的意愿并帮助其保护隐私。若网站没有设置爬虫协议，那么我们就默认允许各种爬虫操作。

​ 爬虫协议的内容为一个robots.txt，我们在浏览器上输入“https://www.csdn.net/robots.txt”，即可查看CSDN论坛的爬虫协议了。如右图所示。

（2）链接提取

​ 链接提取我们可以采用正则表达式的方式。对于一个链接例如“大数据”需要提取两部分内容，一个是“a”标签中链接描述的信息，以及“href”中对应的链接。

（3）链接去重

爬虫每次进行页面分析都会获取新的链接，在这些链接集合中难免会有重复，通过链接去重可以提升数据采集的准确率，提高效率。

（4）非网页数据获取

所谓的非网页数据，主要包括Excel、txt、Word、PDF、PPT以及RSS等，除txt文件可以直接进行数据读取之外，其他非网页数据必须要借助相应的读取引擎进行内容获取。PDF的读取引擎是Apache PDFBox或者是xpdf，Word、Excel、ppt的读取引擎为Apache POI。

（5）网页去重

对于网页相似一般有三种情况。完全相似、内容相似和局部相似。

n第一种完全相似，指不仅仅内容上一致，在网页布局格式上也一致，此类完全重复一般发生在同一个站点的多个域名下。

第二种内容相似，指文档内容相同，页面布局格式不同，这种情况一般发生于转载。

第三种局部相似，指对于网页的内容有部分相似，这类情况大多发生于文章段落的引用。

针对这种情况，google采用了一种Simhash算法，利用赋予文档指纹的概念，来解决大数据爬虫网页去重这个问题，即指纹相似度越高，重复率越高。

（具体介绍可以参考Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling》）

（6）广告识别

​ 网页中存在大量噪声，包括头部导航栏、侧边栏和广告信息等。导航栏和侧边栏可以通过正文提取时，根据文字分布情况过滤，但是广告信息复杂多变，其存在不光对我们信息的读取造成影响而且占用不必要的内存空间。如何有效过滤广告也是我们应该了解的技术。

在实际应用中，我们可以借鉴Adblock plus的思想。Adblock plus是著名的广告过滤插件，其对于浏览器在对广告鉴别方式有比较好的借鉴作用：判定页面的元素是不是广告，并不需要通过分析网页结构、机器学习的方式，而是如果大家都浏览过这些页面，而且判定这些页面中某些元素是广告，那么Adblock plus则认定这就是广告。

数据预处理

实际的数据库极易受噪声、缺失值和不一致数据的侵扰，因为数据库太大，并且多半来自多个异种数据源。低质量的数据将会导致低质量的挖掘结果。因此我们需要使用数据预处理技术：
（1）数据清理
可以用来清除数据中的噪声
（2）数据集成
将数据由多个数据源合并成一个一致的数据存储，如数据仓库或数据立方体
（3）数据变换
例如，规范化可以改进涉及距离度量的挖掘算法的精度和有效性，如0.0到1.0。
（4）数据归约
可以通过如聚集、删除冗余特征或聚类等方法来降低数据的规模。

数据清理

现实世界的数据一般是不完整的、有噪声的和不一致的。数据清理例程试图填充缺失的值、光滑噪声并识别离群点、纠正数据中的不一致。

缺失值

噪声数据

噪声(noise)是被测量的变量的随机误差或方差。我们可以使用基本的数据统计描述技术(例如，盒图或者散点图)和数据可视化方法来识别可能代表噪声的离群点。

数据集成

数据分析任务多半要涉及到数据集成。数据集成将多个数据源中的数据结合起来存放在一个一致的数据存储中。这些数据源可能包括多个数据库、数据立方体或一般文件。

将多个数据源中的数据集成起来，能够减少或避免结果数据集中数据的冗余和不一致性。这有助于提高其后挖掘的精度和速度。

数据变换

数据变换就是将数据转换成适合于挖掘的形式。数据变换可能涉及到如下内容：

数据规约

在数据清理、集成与变换后，我们能够得到整合了多数据源同时数据质量完好的数据集。但是，集成与清洗无法改变数据集的规模。我们依然需通过技术手段降低数据规模，这就是数据归约（Data Reduction）。

用一句话来说，数据归约就是缩小数据挖掘所需的数据集规模，具体方式有维度规约与数量规约。

第四章 分布式平台Hadoop

Hadoop简介

Hadoop最初是由Apache Lucene项目的创始人Doug Cutting开发的文本搜索库。Hadoop源自始于2002年的Apache Nutch项目——一个开源的网络搜索引擎并且也是Lucene项目的一部分

在2004年，Nutch项目也模仿GFS开发了自己的分布式文件系统NDFS（Nutch Distributed File System），也就是HDFS的前身

2004年，谷歌公司又发表了另一篇具有深远影响的论文，阐述了MapReduce分布式编程思想

2005年，Nutch开源实现了谷歌的MapReduce

2006年2月，Nutch中的NDFS和MapReduce开始独立出来，成为Lucene项目的一个子项目，称为Hadoop，同时，Doug Cutting加盟雅虎

2008年1月，Hadoop正式成为Apache顶级项目，Hadoop也逐渐开始被雅虎之外的其他公司使用

2008年4月，Hadoop打破世界纪录，成为最快排序1TB数据的系统，它采用一个由910个节点构成的集群进行运算，排序时间只用了209秒

在2009年5月，Hadoop更是把1TB数据排序时间缩短到62秒。Hadoop从此名声大震，迅速发展成为大数据时代最具影响力的开源分布式开发平台，并成为事实上的大数据处理标准。

Hadoop的特性

Hadoop是一个能够对大量数据进行分布式处理的软件框架，并且是以一种可靠、高效、可伸缩的方式进行处理的，它具有以下几个方面的特性：
（1）高可靠性
Hadoop成立之初就是假设计算和存储会失败，它维护多个工作数据副本，确保能够针对失败的节点重新分布处理。
（2）高扩展性
Hadoop是在可用的计算机集群间分配数据并完成计算任务的，这些集群可以方便地扩展到数以千计的节点中。
（3）高效性
Hadoop能够在节点之间动态地移动数据，并保证各个节点的动态负载平衡，因此处理速度非常快。

（4）高容错性
Hadoop能够自动将数据保存为多个副本，并且能够自动将失败的任务重新分配。
（5）低成本
与一体机、商用数据仓库以及QlikView、SpotView等数据集市相比，Hadoop是开源的，项目的软件成本因此大大降低。

•Hadoop被视为事实上的大数据处理标准，本章介绍了Hadoop的发展历程，并阐述了Hadoop的高可靠性、高效性、高可扩展性、高容错性、成本低、运行在Linux平台上、支持多种编程语言等特性

•Hadoop目前已经在各个领域得到了广泛的应用，雅虎、Facebook、百度、淘宝、网易等公司都建立了自己的Hadoop集群

•经过多年发展，Hadoop项目已经变得非常成熟和完善，包括Common、Avro、Zookeeper、HDFS、MapReduce、HBase、Hive、Chukwa、Pig等子项目，其中，HDFS和MapReduce是Hadoop的两大核心组件。

第5章 分布式文件系统HDFS

分布式文件系统把文件分布存储到多个计算机节点上，成千上万的计算机节点构成计算机集群

与之前使用多个处理器和专用高级硬件的并行化处理装置不同的是，目前的分布式文件系统所采用的计算机集群，都是由普通硬件构成的，这就大大降低了硬件上的开销

分布式文件系统在物理结构上是由计算机集群中的多个节点构成的，这些节点分为两类，一类叫“主节点”(Master Node)或者也被称为“名称结点”(NameNode)，另一类叫“从节点”（Slave Node）或者也被称为“数据节点”(DataNode)

总体而言，HDFS要实现以下目标：

•兼容廉价的硬件设备

•流数据读写

•大数据集

•简单的文件模型

•强大的跨平台兼容性

HDFS特殊的设计，在实现上述优良特性的同时，也使得自身具有一些应用局限性，主要包括以下几个方面：

•不适合低延迟数据访问

•无法高效存储大量小文件

•不支持多用户写入及任意修改文件

•分布式文件系统是大数据时代解决大规模数据存储问题的有效解决方案，HDFS开源实现了GFS，可以利用由廉价硬件构成的计算机集群实现海量数据的分布式存储

•HDFS具有兼容廉价的硬件设备、流数据读写、大数据集、简单的文件模型、强大的跨平台兼容性等特点。但是，也要注意到，HDFS也有自身的局限性，比如不适合低延迟数据访问、无法高效存储大量小文件和不支持多用户写入及任意修改文件等

•块是HDFS核心的概念，一个大的文件会被拆分成很多个块。HDFS采用抽象的块概念，具有支持大规模文件存储、简化系统设计、适合数据备份等优点

•HDFS采用了主从（Master/Slave）结构模型，一个HDFS集群包括一个名称节点和若干个数据节点。名称节点负责管理分布式文件系统的命名空间；数据节点是分布式文件系统HDFS的工作节点，负责数据的存储和读取

•HDFS采用了冗余数据存储，增强了数据可靠性，加快了数据传输速度。HDFS还采用了相应的数据存放、数据读取和数据复制策略，来提升系统整体读写响应性能。HDFS把硬件出错看作一种常态，设计了错误恢复机制

第6章 MapReduce基础

在MapReduce出现之前，已经有HPC(High Performance Computing)这样非常成熟的并行计算框架了，那么为什么Google还需要MapReduce？MapReduce相较于传统的并行计算框架有什么优势？

传统并行计算框架 MapReduce
集群架构/容错性 共享式(共享内存/共享存储)，容错性差 非共享式，容错性好
硬件/价格/扩展性 刀片服务器、高速网、SAN，价格贵，扩展性差 普通PC机，便宜，扩展性好
编程/学习难度 what-how，难 what，简单
适用场景 实时、计算密集型 非实时、数据密集型

高性能计算(High Performance Computing)机群，简称HPC机群。构建高性能计算系统的主要目的就是提高运算速度，要达到每秒万亿次级的计算速度，对系统的处理器、内存带宽、运算方式、系统I/O、存储等方面的要求都十分高，这其中的每一个环节都将直接影响到系统的运算速度。

MapReduce模型简介

MapReduce将复杂的、运行于大规模集群上的并行计算过程高度地抽象到了两个函数：Map和Reduce

编程容易，不需要掌握分布式并行编程细节，也可以很容易把自己的程序运行在分布式系统上，完成海量数据的计算

MapReduce采用“分而治之”策略，一个存储在分布式文件系统中的大规模数据集，会被切分成许多独立的分片（split），这些分片可以被多个Map任务并行处理

MapReduce设计的一个理念就是“计算向数据靠拢”，而不是“数据向计算靠拢”，因为，移动数据需要大量的网络传输开销

MapReduce框架采用了Master/Slave架构，包括一个Master和若干个Slave。Master上运行JobTracker，Slave上运行TaskTracker

Hadoop框架是用Java实现的，但是，MapReduce应用程序则不一定要用Java来写

函数 输入 输出 说明
Map <k1,v1> 如： <行号,”a b c”> List(<k2,v2>) 如： <“a”,1> <“b”,1> <“c”,1> 1.将小数据集进一步解析成一批<key,value>对，输入Map函数中进行处理 2.每一个输入的<k1,v1>会输出一批<k2,v2>。<k2,v2>是计算的中间结果
Reduce <k2,List(v2)> 如：<“a”,<1,1,1>> <k3,v3> <“a”,3> 输入的中间结果<k2,List(v2)>中的List(v2)表示是一批属于同一个k2的value

MapReduce体系结构主要由四个部分组成，分别是：Client、JobTracker、TaskTracker以及Task

MapReduce主要有以下4个部分组成：

1）Client

  • 用户编写的MapReduce程序通过Client提交到JobTracker端
  • 用户可通过Client提供的一些接口查看作业运行状态

2）JobTracker

JobTracker负责资源监控和作业调度

JobTracker 监控所有TaskTracker与Job的健康状况，一旦发现失败，就将相应的任务转移到其他节点

JobTracker 会跟踪任务的执行进度、资源使用量等信息，并将这些信息告诉任务调度器（TaskScheduler），而调度器会在资源出现空闲时，选择合适的任务去使用这些资源

3）TaskTracker

TaskTracker 会周期性地通过**“心跳”**将本节点上资源的使用情况和任务的运行进度汇报给JobTracker，同时接收JobTracker 发送过来的命令并执行相应的操作（如启动新任务、杀死任务等）

TaskTracker 使用slot等量划分本节点上的资源量（CPU、内存等）。一个Task 获取到一个slot 后才有机会运行，而Hadoop调度器的作用就是将各个TaskTracker上的空闲slot分配给Task使用。slot 分为Map slot 和Reduce slot 两种，分别供MapTask 和Reduce Task 使用

4）Task

Task 分为Map Task 和Reduce Task 两种，均由TaskTracker 启动

MapReduce工作流程

不同的Map任务之间不会进行通信

不同的Reduce任务之间也不会发生任何信息交换

用户不能显式地从一台机器向另一台机器发送消息

所有的数据交换都是通过MapReduce框架自身去实现的

关于Split（分片）

HDFS 以固定大小的block 为基本单位存储数据，而对于MapReduce 而言，其处理单位是split。split 是一个逻辑概念，它只包含一些元数据信息，比如数据起始位置、数据长度、数据所在节点等。它的划分方法完全由用户自己决定，每片的默认最大值和每块的默认值128M相同。

Map任务的数量

Map任务的数量

•Hadoop为每个split创建一个Map任务，split 的多少决定了Map任务的数目。大多数情况下，理想的分片大小是一个HDFS块

Reduce任务的数量

•最优的Reduce任务个数取决于集群中可用的reduce任务槽(slot)的数目

•通常设置比reduce任务槽数目稍微小一些的Reduce任务个数（这样可以预留一些系统资源处理可能发生的错误）

Shuffle

  • 此阶段，将map的输出经过“整理”后给到reduce，也称为“混洗”。分为map端操作和reduce端操作。
  • 在map端，map的输出先写入缓存，当每次缓存快满时，由缓存“溢写”至磁盘，每次溢写都先进行“分区”，并对每个分区的数据进行“排序”和“合并”（可选）。一般会产生多个溢写的文件，这些文件会在map端先被“归并”为一个大的磁盘文件，通知reduce任务来领取自己的分区。
  • 在reduce端，每个reduce任务会从多个map任务领取文件，然后将这些文件进行“归并”，交给reduce任务。

Map端的Shuffle过程

•每个Map任务分配一个缓存

•MapReduce默认100MB缓存

•设置溢写比例0.8

•分区默认采用哈希函数

•排序是默认的操作

•排序后可以合并（Combine）

•合并不能改变最终结果

•在Map任务全部结束之前进行归并

•归并得到一个大的文件，放在本地磁盘

•文件归并时，如果溢写文件数量大于预定值（默认是3）则可以再次启动Combiner，少于3不需要

•JobTracker会一直监测Map任务的执行，并通知Reduce任务来领取数据

合并（Combine）和归并（Merge）的区别：

两个键值对<“a”,1>和<“a”,1>，如果合并，会得到<“a”,2>，如果归并，会得到<“a”,<1,1>>

Reduce端的Shuffle过程

•Reduce任务通过RPC向JobTracker询问Map任务是否已经完成，若完成，则领取数据

•Reduce领取数据先放入缓存，来自不同Map机器，先归并，再合并，写入磁盘

•多个溢写文件归并成一个或多个大文件，文件中的键值对是排序的

•当数据很少时，不需要溢写到磁盘，直接在缓存中归并，然后输出给Reduce

MapReduce应用程序执行过程

  1. 用户编写Map和Reduce程序，选择一个节点作为Master来运行JobTracker；选择其他若干节点作为TaskTracker运行Map或Reduce程序
  2. 把Map和Reduce程序任务分发到各个Map或Reduce节点中
  3. RR从HDFS读取InputFormat产生的分片所对应的文件数据，转换为键值对
  4. Map任务处理RR产生的键值对，Map输出结果经过Shuffle(分区、排序、合并)后把分区好的数据写入Map任务所在节点的本地硬盘中(不是HDFS中，中间结果只需临时存储，不需要分布式存储)
  5. Map任务执行完毕后通知JobTracker，JobTracker通知Reduce任务读取Map输出的已分区的键值对文件中属于本Reduce任务处理的分区数据；对读取的数据归并后，执行Reduce处理
  6. Reduce输出的键值对进行归并和合并后，由OutputFormat检查并写入HDFS中

MapReduce的具体应用

MapReduce可以很好地应用于各种计算问题

•关系代数运算（选择、投影、并、交、差、连接）

•分组与聚合运算

•矩阵-向量乘法

•矩阵乘法

用MapReduce实现关系的自然连接

假设有关系R(A，B)和S(B,C)，对二者进行自然连接操作

使用Map过程，把来自R的每个元组<a,b>转换成一个键值对<b, <R,a>>，其中的键就是属性B的值。把关系R包含到值中，这样做使得我们可以在Reduce阶段，只把那些来自R的元组和来自S的元组进行匹配。类似地，使用Map过程，把来自S的每个元组<b,c>，转换成一个键值对<b,<S,c>>

所有具有相同B值的元组被发送到同一个Reduce进程中，Reduce进程的任务是，把来自关系R和S的、具有相同属性B值的元组进行合并

Reduce进程的输出则是连接后的元组<a,b,c>，输出被写到一个单独的输出文件中

小结

•MapReduce执行的全过程包括以下几个主要阶段：从分布式文件系统读入数据、执行Map任务输出中间结果、通过 Shuffle阶段把中间结果分区排序整理后发送给Reduce任务、执行Reduce任务得到最终结果并写入分布式文件系统。在这几个阶段中，Shuffle阶段非常关键，必须深刻理解这个阶段的详细执行过程

•MapReduce具有广泛的应用，比如关系代数运算、分组与聚合运算、矩阵-向量乘法、矩阵乘法等

第7章 大数据存储技术

云计算是云数据库兴起的基础

云计算概念

•通过整合、管理、调配分布在网络各处的计算资源，通过互联网以统一界面，同时向大量的用户提供服务

云计算特点

超大规模计算、虚拟化、高可靠性和安全性、通用性、动态扩展性、按需服务、降低成本

云计算应用场景

  • Google个人云服务
  • 华为云开发环境
  • 各类云盘

云计算八大优势

  1. 按需服务
  2. 随时服务
  3. 通用性
  4. 高可靠性
  5. 极其廉价
  6. 超大规模
  7. 虚拟化
  8. 高扩展性

云数据库概念

云数据库是部署和虚拟化在云计算环境中的数据库。云数据库是在云计算的大背景下发展起来的一种新兴的共享基础架构的方法，它极大地增强了数据库的存储能力，消除了人员、硬件、软件的重复配置，让软、硬件升级变得更加容易。云数据库具有高可扩展性、高可用性、采用多租形式和支持资源有效分发等特点。

云数据库与云存储有什么区别？

从对应的层面来讲

  1. 云存储：是在资源层，即云的IaaS层，提供的是存储资源能力。
  2. 云数据库：是在平台层，即云的PaaS层，提供的是中间件服务能力。本地的数据库迁移到云端对应云数据库，而本地的硬盘迁移到云端只能对应云存储。

从提供的服务来说

  1. 云存储：提供存储能力，更多面对的场景是非结构化类数据，如文件，图片，视频等。
  2. 云数据库：提供基础的数据库和数据对象管理能力，既包括oracle, mysql,sql server等关系型数据库，也可以包括类似mongodb，hbase等半结构化数据库。

从两者的关系来说

  • 对于云存储当前基本都基于类似hdfs分布式文件系统进行封装，提供存储服务能力接口。也可以基于hdfs上面再架构一层，形成一个数据库，再将数据库能力暴露出去，形成云数据库，类似HBase。但是对于常见的关系型数据库，也可以做为云数据库，但是他们底层可以不依赖的云存储能力。

云数据库具有以下特性：

  1. 动态可扩展
  2. 高可用性
  3. 较低的使用代价
  4. 易用性
  5. 高性能
  6. 免维护
  7. 安全

云数据库是个性化数据存储需求的理想选择

企业类型不同，对于存储的需求也千差万别，而云数据库可以很好地满足不同企业的个性化存储需求：

•首先，云数据库可以满足大企业的海量数据存储需求

•其次，云数据库可以满足中小企业的低成本数据存储需求

•另外，云数据库可以满足企业动态变化的数据存储需求

到底选择自建数据库还是选择云数据库，取决于企业自身的具体需求

•对于一些大型企业，目前通常采用自建数据库

•对于一些财力有限的中小企业而言，IT预算比较有限，云数据库这种前期零投入、后期免维护的数据库服务，可以很好满足它们的需求

•从数据模型的角度来说，云数据库并非一种全新的数据库技术，而只是以服务的方式提供数据库功能

云数据库并没有专属于自己的数据模型，云数据库所采用的数据模型可以是关系数据库所使用的关系模型（微软的SQL Azure云数据库、阿里云RDS都采用了关系模型），也可以是NoSQL数据库所使用的非关系模型（Amazon Dynamo云数据库采用的是“键/值”存储）

•同一个公司也可能提供采用不同数据模型的多种云数据库服务

•许多公司在开发云数据库时，后端数据库都是直接使用现有的各种关系数据库或NoSQL数据库产品

云数据库厂商

企业 产品
Amazon Dynamo、SimpleDB、RDS
Google Google Cloud SQL
Microsoft Microsoft SQL Azure
Oracle Oracle Cloud
Yahoo! PNUTS
Vertica Analytic Database v3.0 for the Cloud
EnerpriseDB Postgres Plus in the Cloud
阿里 阿里云RDS
百度 百度云数据库
腾讯 腾讯云数据库

Amazon是云数据库市场的先行者。Amazon除了提供著名的S3存储服务和EC2计算服务以外，还提供基于云的数据库服务：

•Amazon RDS：云中的关系数据库

•Amazon SimpleDB：云中的键值数据库

•Amazon DynamoDB：云中的NoSQL数据库

•Amazon Redshift：云中的数据仓库

•Amazon ElastiCache：云中的分布式内存缓存

HBase分布式数据库

BigTable是一个分布式存储系统

BigTable起初用于解决典型的互联网搜索问题

•建立互联网索引

1 爬虫持续不断地抓取新页面，这些页面每页一行地存储到BigTable里

2 MapReduce计算作业运行在整张表上，生成索引，为网络搜索应用做准备

•搜索互联网

3 用户发起网络搜索请求

4 网络搜索应用查询建立好的索引，从BigTable得到网页

5 搜索结果提交给用户

Bigtable是一个稀疏、分布式、持久化存储的多维有序映射表，表的索引是行关键字、列关键字和时间戳 。Bigtable中存储的表项都是未经解析的字节数组

数据模型

行关键字可以是任意字符串，最大支持64KB。Bigtable按照行关键字的字典序组织数据，利用这个特性可以通过选择合适的行关键字，使数据访问具有良好的局部性。如Webtable中，通过将反转的URL作为行关键字，可以将同一个域名下的网页聚集在一起。

​ 表的行区间可以动态划分，每个行区间称为一个子表。子表是Bigtable数据分布和负载均衡的基本单位，不同的子表可以有不同的大小。为了限制子表的移动和恢复成本，每个子表默认的最大尺寸为200MB。

列族

列关键字一般都表示一种数据类型，列关键字的集合称作列族，列族是访问控制的基本单位 。存储在同一列族下的数据属于同一种类型，列族下的数据被压缩在一起保存。数据在被存储之前必须先创建列族，并且表中的列族不宜过多，通常几百个，但表中可以有无限多个列 。在Bigtable中列关键字的命名语法为：“列族：限定词”，列族名称必须是可打印的字符串，限定词则可以是任意字符串。如Webtable中名为anchor的列族，该列族的每一个列关键字代表一个锚链接；anchor列族的限定词是引用网页的站点名，每列的数据项是链接文本 。

时间戳

​ Bigtable中的表项可以包含同一数据的不同版本，采用时间戳进行索引。时间戳是64位整型，既可以由系统赋值也可由用户指定。表项的不同版本按照时间戳倒序排列，即最新的数据排在最前面。

体系结构

Bigtable集群包括三个主要部分：

供客户端使用的库，客户端需要读写数据时，直接与片服务器联系。因为客户端并不需要从主服务器获取片的位置信息，所以大多数客户端从来不需要访问主服务器，主服务器的负载一般很轻。

主服务器（master server），主服务器负责将片分配给片服务器，监控片服务器的添加和删除，平衡片服务器的负载，处理表和列族的创建等。注意，主服务器不存储任何片，不提供任何数据服务，也不提供片的定位信息。

片服务器（tablet server），每个片服务器负责一定量的片，处理对片的读写请求，以及片的分裂或合并。每个片实际由若干SSTable文件和memtable组成，而且这些SSTable和memtable都是已排序的。片服务器可以根据负载随时添加和删除。这里片服务器并不真实存储数据，而相当于一个连接Bigtable和GFS的代理，客户端的一些数据操作都通过片服务器代理间接访问GFS。

Bigtable的实现依托于Google的几个基础组件：

Google File System（GFS），一个分布式文件系统，用于存储日志和文件；

Google Sorted Strings Table（SSTable），一个不可修改的有序键值映射表，提供查询、遍历的功能；

Chubby，一个高可靠用于分布式的锁服务，其目的是解决分布式一致性的问题，通过Paxos算法实现。Chubby用于片定位，片服务器的状态监控，访问控制列表存储等任务。

HBase是一个高可靠、高性能、面向列、可伸缩的分布式数据库，是谷歌BigTable的开源实现，主要用来存储非结构化和半结构化的松散数据。HBase的目标是处理非常庞大的表，可以通过水平扩展的方式，利用廉价计算机集群处理由超过10亿行数据和数百万列元素组成的数据表

HBase和BigTable的底层技术对应关系

BigTable HBase
文件存储系统 GFS HDFS
海量数据处理 MapReduce Hadoop MapReduce
协同服务管理 Chubby Zookeeper

为什么需要HBase?

•HBase数据库是BigTable的开源实现，和BigTable一样，支持大规模海量数据，分布式并发数据处理效率极高，易于扩展且支持动态伸缩，适用于廉价设备。

•Hadoop可以很好地解决大规模数据的离线批量处理问题，但是，受限于Hadoop MapReduce编程框架的高延迟数据处理机制，使得Hadoop无法满足大规模数据实时处理应用的需求

•HDFS面向批量访问模式，不是随机访问模式

•传统的通用关系型数据库无法应对在数据规模剧增时导致的系统扩展性和性能问题（分库分表也不能很好解决）

•传统关系数据库在数据结构变化时一般需要停机维护，空列浪费存储空间

•因此，业界出现了一类面向半结构化数据存储和处理的高可扩展、低写入/查询延迟的系统，例如，键值数据库、文档数据库和列族数据库（如BigTable和HBase等）

•HBase已经成功应用于互联网服务领域和传统行业的众多在线式数据分析处理系统中。

HBase与传统的关系数据库的区别主要体现在以下几个方面：

（1）数据类型：关系数据库采用关系模型，具有丰富的数据类型和存储方式，HBase则采用了更加简单的数据模型，它把数据存储为未经解释的字符串

（2）数据操作：关系数据库中包含了丰富的操作，其中会涉及复杂的多表连接。HBase操作则不存在复杂的表与表之间的关系，只有简单的插入、查询、删除、清空等，因为HBase在设计上就避免了复杂的表和表之间的关系

（3）存储模式：关系数据库是基于行模式存储的。HBase是基于列存储的，每个列族都由几个文件保存，不同列族的文件是分离的

（4）数据索引：关系数据库通常可以针对不同列构建复杂的多个索引，以提高数据访问性能。HBase通过行键建立索引，通过巧妙的设计，HBase中的所有访问方法，或者通过行键访问，或者通过行键扫描，从而使得整个系统不会慢下来。

（5）数据维护：在关系数据库中，更新操作会用最新的当前值去替换记录中原来的旧值，旧值被覆盖后就不会存在。而在HBase中执行更新操作时，并不会删除数据旧的版本，而是生成一个新的版本，旧有的版本仍然保留

（6）可伸缩性：关系数据库很难实现横向扩展，纵向扩展的空间也比较有限。相反，HBase和BigTable这些分布式数据库就是为了实现灵活的水平扩展而开发的，能够轻易地通过在集群中增加或者减少硬件数量来实现性能的伸缩。

HBase访问接口

类型 特点 场合
Native Java API 最常规和高效的访问方式 适合Hadoop MapReduce作业并行批处理HBase表数据
HBase Shell HBase的命令行工具，最简单的接口 适合HBase管理使用
Thrift Gateway 利用Thrift序列化技术，支持C++、PHP、Python等多种语言 适合其他异构系统在线访问HBase表数据
REST Gateway 解除了语言限制 支持REST风格的Http API访问HBase
Pig 使用Pig Latin流式编程语言来处理HBase中的数据 适合做数据统计
Hive 简单 当需要以类似SQL语言方式来访问HBase的时候

HBase数据模型

•HBase是一个稀疏、多维度、排序的映射表，这张表的索引是行键、列族、列限定符和时间戳

•每个值是一个未经解释的字符串，没有数据类型

•用户在表中存储数据，每一行都有一个可排序的行键和任意多的列

•表在水平方向由一个或者多个列族组成，一个列族中可以包含任意多个列，同一个列族里面的数据存储在一起

•列族支持动态扩展，可以很轻松地添加一个列族或列，无需预先定义列的数量以及类型，所有列均以字符串形式存储，用户需要自行进行数据类型转换

•HBase中执行更新操作时，并不会删除数据旧的版本，而是生成一个新的版本，旧有的版本仍然保留（这是和HDFS只允许追加不允许修改的特性相关的）

•表：HBase采用表来组织数据，表由行和列组成，列划分为若干个列族

•行：每个HBase表都由若干行组成，每个行由行键（row key）来标识。

•列族：一个HBase表被分组成许多“列族”（Column Family）的集合，它是基本的访问控制单元

•列限定符：列族里的数据通过列限定符（或列）来定位

•单元格：在HBase表中，通过行、列族和列限定符确定一个“单元格”（cell），单元格中存储的数据没有数据类型，总被视为字节数组byte

•时间戳：每个单元格都保存着同一份数据的多个版本，这些版本采用时间戳进行索引

•HBase中需要根据行键、列族、列限定符和时间戳来确定一个单元格，因此，可以视为一个“四维坐标”，即[行键, 列族, 列限定符, 时间戳]

NoSQL 数据库

NoSQL，指的是非关系型的数据库，也称作Not Only SQL。

NoSQL产生的原因

① 关系数据库无法满足海量数据的管理需求；

②关系数据库无法满足高并发的需求；

③关系数据库无法满足高扩展性和高可用性需求。

纵向扩展

横向扩展：采用集群的方式，但部署、管理、配置很复杂，没有办法自动化实现。

CAP定理：

又称作布鲁尔定理（Brewer‘s theorem），对于一个分布式计算系统来说，不可能同时满足以下三点，最多只能同时较好的满足两点。

  • 一致性(Consistency) (所有节点在同一时间具有相同的数据)

  • 可用性(Availability) (保证每个请求不管成功或者失败都有响应)

  • 分区容忍(Partition tolerance) (系统一部分节点信息的丢失或失败不会影响系统的继续运行)

根据 CAP 原理将 NoSQL 数据库分成了满足 CA 原则、满足 CP 原则和满足 AP 原则三 大类：

  1. CA - 单点集群，满足一致性，可用性的系统，通常在可扩展性上不太强大。
  2. CP - 满足一致性，分区容忍性的系统，通常性能不是特别高。
  3. AP - 满足可用性，分区容忍性的系统，通常可能对一致性要求低一些。

BASE

BASE是NoSQL数据库通常对可用性及一致性的弱要求原则，核心思想是，在保证可用性的基础上，即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。它是AP（可用性+分区容忍性）的优化方案，能满足绝大部分业务需求。

BASE：Basically Available, Soft-state, Eventually Consistency。 由 Eric Brewer 定义。

Basically Available：分布式系统在出现故障时，允许损失部分可用性，即保证核心可用。

Soft-state 软状态：允许系统存在中间状态（数据不一致），不会影响系统整体可用性。

Eventually Consistency 最终一致性：系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。

关系数据库与NoSQL比较

关系型数据库的优势：

1.保持数据的一致性（事务处理）[关系型数据库的最大优势]

2.由于以标准化为前提，数据更新的开销很小（相同的字段基本上都只有一处）

3.可以进行Join等复杂查询(不同服务器之间不能进行Join处理)

4.存在很多实际成果和专业技术信息（成熟的技术）

5.把所有的数据都通过行和列的二元表现形式表示出来，让人容易理解

关系型数据库不擅长的处理：

  1. 大量数据的写入处理

  2. 为有数据更新的表做索引或表结构（schema）变更

  3. 字段不固定时应用

  4. 对简单查询需要快速返回结果的处理

关系库无法满足海量数据的管理需求，无法满足高并发的需求，无法满足高扩展性和高可用性需求

NoSQL数据库的优势：

1.关系型数据库有类似Join这样的多表查询机制的限制导致扩展很艰难，NoSQL数据库不支持Join处理，各个数据都是独立设计的，很容易把数据分散在多个服务器上。

2.NoSQL的存储格式是键值存储形式、面向文档形式、面向列形式等，所以可以存储基础类型以及对象或者是集合等各种格式，而关系数据库则只支持基础类型

3.大量数据的写入处理

4.对数据进行缓存(Cache)处理

5.对数组类型的数据进行高速处理

6.对数据进行全部保存处理

NoSQL数据库的不足：

1.不提供关系型数据库对事务的处理

2.属于新的技术维护的工具和资料有限、将产生一定用户的学习和使用成本

键值数据库

数据模型

键/值对

键是一个字符串对象

值可以是任意类型的数据，比如整型、字符型、数组、列表、集合等

通过键查询，不能通过值来查询。

优点：扩展性好，灵活性好，大量写操作时性能高

缺点：无法存储结构化信息，条件查询效率较低，不能存储数据之间的关系

相关产品：Redis、Riak、SimpleDB、Chordless、Scalaris、Memcached

典型应用：涉及频繁读写、拥有简单数据模型的应用；内容缓存，比如会话、配置文件、参数、购物车等；存储配置和用户数据信息的移动应用

Redis被人们称为“强化版的Memcached”，开源的使用 ANSI C 语言编写、遵守 BSD 协议、支持网络、可基于内存、分布式、可选持久性，提供多种语言的 API，数据恢复、更多数据类型。

Redis内部使用一个redisObject对象来表示所有的key和value。redisObject主要的信息包括数据类型（type）、编码方式(encoding)、数据指针（ptr）、虚拟内存（vm）等。type代表一个value对象具体是何种数据类型，encoding是不同数据类型在redis内部式。

与Memcached仅支持简单的key-value结构的数据记录不同，Redis支持的数据类型要丰富得多，常用的数据类型主要有五种：String、List、Hash、Set和Sorted Set。

  1. 字符串（String）是Redis值的最基础的类型。Redis中使用的字符串是通过包装的，基于c语言字符数组实现的简单动态字符串(simple dynamic string, SDS)一个抽象数据结构。下图为C语言字符串内存结构示意图

  1. Hash是一个String类型的field和value之间的映射表，即redis的Hash数据类型的key（hash表名称）对应的value实际的内部存储结构为一个HashMap，因此Hash特别适合存储对象。相对于把一个对象的每个属性存储为String类型，将整个对象存储在Hash类型中会占用更少内存。适用于一个对象来存储用户信息，商品信息，订单信息等等。
  1. List类型其实就是每一个元素都是String类型的双向链表。我们可以从链表的头部和尾部添加或者删除元素。这样的List既可以作为栈，也可以作为队列使用。适用于如好友列表，粉丝列表，消息队列，最新消息排行等。
  2. Redis 集合（Set类型）是一个无序的String类型数据的集合，类似List的一个列表，与List不同的是Set不能有重复的数据。实际上，Set的内部是用HashMap实现的，Set只用了HashMap的key列来存储对象。集合有取交集、并集、差集等操作，因此可以求共同好友、共同兴趣、分类标签等。
  3. SortSet顾名思义，是一个排好序的Set，它在Set的基础上增加了一个顺序属性score，这个属性在添加修改元素时可以指定，每次指定后，SortSet会自动重新按新的值排序。SortSet的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的是所有的成员，排序依据是HashMap里存的score。适合需要有序且唯一的业务或操作，例：网易云音乐的排行榜功能
分值 2.0 3.2 4.0 7.0 8.2 9.1
元素 歌曲1 歌曲2 歌曲3 歌曲4 歌曲5 歌曲6

列族数据库

典型应用：分布式数据存储与管理；可以容忍副本中存在短期不一致情况的应用程序；拥有动态字段的应用程序：拥有潜在大量数据的应用程序，大到几百TB的数据

优点：查找速度快，可扩展性强，容易进行分布式扩展，复杂性低

缺点：功能较少，大都不支持强事务一致性

相关产品 BigTable、HBase、Cassandra、HadoopDB、GreenPlum、PNUTS
使用者 Ebay（Cassandra）、Instagram（Cassandra）、NASA（Cassandra）、Twitter（Cassandra and HBase）、Facebook（HBase）、Yahoo!（HBase）

文档数据库

文档数据库可看作特殊的键值数据库，值是文档。

“文档”其实是一个数据记录，这个记录能够对包含的数据类型和内容进行自我描述。比如XML文档、HTML文档和JSON 文档。

典型应用 存储、索引并管理面向文档的数据或者类似的半结构化数据 比如，用于后台具有大量读写操作的网站、使用JSON数据结构的应用、使用嵌套结构等非规范化数据的应用程序
优点 性能好（高并发），灵活性高，复杂性低，数据结构灵活 提供嵌入式文档功能，将经常查询的数据存储在同一个文档中；既可以根据键来构建索引，也可以根据内容构建索引
缺点 缺乏统一的查询语法，不支持文档间事务
相关产品 MongoDB、CouchDB、Terrastore、ThruDB、RavenDB、SisoDB、RaptorDB、CloudKit、Perservere、Jackrabbit
使用者 百度云数据库（MongoDB）、SAP （MongoDB）、Codecademy （MongoDB）、Foursquare （MongoDB）、NBC News （RavenDB）

MongoDB 将数据存储为一个文档，数据结构由键值(key=>value)对组成。MongoDB 文档类似于 JSON 对象。字段值可以包含其他文档，数组及文档数组。

设计基于MongoDB的应用程序的数据模型时的关键就是选择合适的文档结构以及确定应用程序如何描述数据之间的关系。有两种方式可以用来描述这些关系： 内嵌和引用

1.Embedded Data Models 内嵌数据模型

内嵌方式指的是把相关联的数据保存在同一个文档结构之内。MongoDB的文档结构允许一个字段或者一个数组内的值为一个嵌套的文档。这种冗余的数据模型可以让应用程序在一个数据库操作内完成对相关数据的读取或修改。这样一来，应用程序就可以发送较少的请求给MongoDB数据库来完成常用的查询及更新请求。

内嵌数据模型的适用情况

一般来说，下述情况建议使用内嵌数据：

数据对象之间有contains(包含)关系。

数据对象之间有一对多的关系。 这些情况下 “多个”或者子文档会经常和父文档一起被显示和查看。请参见 一对多关系建模： 内嵌文档模型。

通常情况下，内嵌数据会对读操作有比较好的性能提高，也可以使应用程序在一个单个操作就可以完成对数据的读取。 同时，内嵌数据也对更新相关数据提供了一个原子性写操作。

2. Normalized Data Models 规范化数据模型

规范化数据模型指的是通过使用引用来表达对象之间的关系。

一般来说，在下述情况下可以使用规范化模型：

当内嵌数据会导致很多数据的重复，并且读性能的优势又不足于盖过数据重复的弊端时候。

需要表达比较复杂的多对多关系的时候。

大型多层次结构数据集。

引用比内嵌要更加灵活一些。 但客户端应用必须使用二次查询来解析文档内包含的引用。换句话说，对同样的操作来说，规范化模式会导致更多的网络请求发送到数据库服务器端。

MongoDB特性与数据模型

1. 原子性

在MongoDB中，即使操作修改单个文档中的多个嵌入文档，写操作在单个文档的级别上也是原子操作。当单个写操作修改多个文档（例如db.collection.updateMany()）时，每个文档的修改都是原子的，但整个操作不是原子操作。

把相关数据定义到同一个文档里面的内嵌方式有利于这种原子性操作。对于那些使用引用来关联相关数据的数据模型，应用程序必须再用额外的读和写的操作去取回和修改相关的数据。

内嵌数据模型

嵌入式数据模型将所有相关数据组合在单个文档中，而不是跨多个文档和集合进行规范化。该数据模型有助于原子操作。

多文档事务

对于存储相关数据片段之间的引用的数据模型，应用程序必须发出单独的读取和写入操作以检索和修改这些相关的数据片段。从版本4.0开始，对于需要原子性来更新多个文档或读取多个文档之间的一致性的情况，MongoDB为副本集提供了多文档事务。

2. 分片

MongoDB 使用 **sharding （分片）**来实现水平扩展。使用分片的集群可以支持海量的数据和高并发读写。用户可以使用分片技术把一个数据库内的某一个集合的数据进行分区，从而达到把数据分布到多个 mongod 实例（或分片上）的目的。

Mongodb 依据分片键分发数据和应用程序的事务请求。选择一个合适的分片键会对性能有很大的影响，也会促进或者阻碍MongoDB的定向分片查询和增强的写性能。所以在选择分片键时候要仔细考量分片键所用的字段。

3. 索引

对常用操作可以使用索引来提高性能。对查询条件中常见的字段，以及需要排序的字段创建索引。MongoDB会对 _id 字段自动创建唯一索引。

创建索引时，需要考虑索引的下述特征：

每个索引至少需要8kB的数据空间。

添加索引会对写入操作产生一些负面的性能影响。 对于具有高写入读取比率的集合，索引的代价很大，因为每个插入也必须更新任何索引。

具有高读写比的集合通常受益于其他索引。 索引不会影响未设置索引的读取操作。

每个索引都会占一定的硬盘空间和内存（对于活跃的索引）。索引有可能会用到很多这样的资源，因此对这些资源要进行管理和规划，特别是在计算热点数据大小的时候

图数据库

数据模型 图结构
典型应用 专门用于处理具有高度相互关联关系的数据，比较适合于社交网络、模式识别、依赖分析、推荐系统以及路径寻找等问题
优点 灵活性高，支持复杂的图形算法，可用于构建复杂的关系图谱
缺点 复杂性高，只能支持一定的数据规模
相关产品 Neo4J、OrientDB、InfoGrid、Infinite Graph、GraphDB
使用者 Adobe（Neo4J）、Cisco（Neo4J）、T-Mobile（Neo4J）

图由两个元素组成：节点和关系。

每个节点代表一个实体（人，地，事物，类别或其他数据），每个关系代表两个节点的关联方式。

Neo4J是由Java实现的开源图数据库，支持ACID，集群、备份和故障转移。Neo4J版本分为社区版和企业版，社区版只支持单机部署，功能受限。企业版支持主从复制和读写分离，包含可视化管理工具。

Neo4J的特点

它很容易表示连接的数据

检索/遍历/导航更多的连接数据是非常容易和快速的

它非常容易地表示半结构化数据

Neo4j CQL查询语言命令是人性化的可读格式，非常容易学习

使用简单而强大的数据模型

它不需要复杂的连接来检索连接的/相关的数据，因为它很容易检索它的相邻节点或关系细节没有连接或索引。

Neo4J的使用实例

例如一部电影有若干演员和导演，那么建立图数据库后，可以容易地表示电影、演员、导演之间的关系，而且在查询时也会变得很方便。

例如一个购物网站。购物网站的业务需求大概具有这样的流程：首先商家上架了商品，然后顾客浏览或查找商品，顾客找到自己需要的商品之后，确定购买，接着使用他的账户支付款项，商家收到货款后，将商品快递给顾客，从而完成一笔交易。根据这个业务流程，也可以使用Neon4J建立数据模型。

不同类型数据库比较分析

MySQL功能稳定，满足多样需求

MongoDB提供更灵活的数据模型，支持较多功能。

Hbase 依赖Hadoop的生态环境，有很好的扩展性。

Redis是键值存储的代表，功能最简单，提供随机数据存储，伸缩性特别好

第8章 大数据处理技术

基于内存的分布式计算框架Spark

AMP实验室于2009年开发，是基于内存计算的大数据并行计算框架，可用于构建大型的、低延迟的数据分析应用程序。

特点

  • 运行速度快：使用DAG执行引擎以支持循环数据流与内存计算。

  • 容易使用：支持使用Scala、Java、Python和R语言进行编程，可以通过Spark Shell进行交互式编程 。

  • 通用性：Spark提供了完整而强大的技术栈，包括SQL查询、流式计算、机器学习和图算法组件。

  • 运行模式多样：可运行于独立的集群模式中，可运行于Hadoop中，也可运行于Amazon EC2等云环境中，并且可以访问HDFS、Cassandra、HBase、Hive等多种数据源

Scala简介

Scala （Scalable Language）是一门多范式编程语言，运行于Java平台（JVM，Java 虚拟机），兼容现有的Java程序

Scala的特性：

具备强大的并发性，支持函数式编程，可以更好地支持分布式系统；

语法简洁，能提供API，自带了很多的算子，比如集合算子；

兼容Java，运行速度快，能融合到Hadoop生态圈中 ；

Scala是Spark的主要编程语言

Scala的优势是提供了REPL（Read-Eval-Print Loop，交互式解释器），提高程序开发效率。

Scala解释器读到一个表达式，对它进行求值，将它打印出来，接着再继续读下一个表达式。这个过程被称做读取–求值–打印–循环，即：REPL。

Hadoop缺点：

表达能力有限

磁盘IO开销大

延迟高

任务之间的衔接涉及IO开销

在前一个任务执行完成之前，其他任务就无法开始，难以胜任复杂、多阶段的计算任务

Spark优点：

Spark的计算模式也属于MapReduce，但不局限于Map和Reduce操作，还提供了多种数据集操作类型，编程模型比Hadoop MapReduce更灵活

Spark提供了内存计算，可将中间结果放到内存中，对于迭代运算效率更高

Spark基于DAG的任务调度执行机制，要优于Hadoop MapReduce的迭代执行机制

表达能力有限。Hadoop把复杂的分布式编程高度抽象到两个函数Map和Reduce上，在降低使用难度的同时，但也带来了表达能有限的问题，实际操作的时候有些问题并不能单单靠这两个函数来解决问题。

执行迭代操作效率低。对于一些大型的机器学习，数据挖掘任务，往往需要更多轮次迭代才能得到结果。采用MapReduce实现这些算法的时候，每次迭代都是执行一次Map，Reduce任务的过程，这个过程的数据来源于分布式文件系统HDFS中，本此的迭代处理的结果也放在HDFS中，继续用于下一次的迭代。反复读写HDFS中的数据，大大降低了迭代操作的效率。

资源浪费。在MapReduce的框架设计中，Reduce任务必须等待所有的Map任务执行完毕后再开始执行，造成不必要资源的浪费。

实时性差。只是适用于离线批数据处理，无法支持交互式数据处理，实时数据的处理。

使用Hadoop进行迭代计算非常耗资源

Spark将数据载入内存后，之后的迭代计算都可以直接使用内存中的中间结果作运算，避免了从磁盘中频繁读取数据

大数据处理包括三个类型：

  • 复杂的批量数据处理：通常时间跨度在数十分钟到数小时之间

  • 基于历史数据的交互式查询：通常时间跨度在数十秒到数分钟之间

  • 基于实时数据流的数据处理：通常时间跨度在数百毫秒到数秒之间

    当同时存在以上三种场景时，就需要同时部署三种不同的软件。比如: MapReduce / Impala / Storm

问题：

  • 不同场景之间输入输出数据无法做到无缝共享，通常需要进行数据格式的转换

  • 不同的软件需要不同的开发和维护团队，带来了较高的使用成本

  • 难以对同一个集群中的各个系统进行统一的资源协调和分配

Spark的设计遵循“一个软件栈满足不同应用场景”的理念，逐渐形成了一套完整的生态系统

既能够提供内存计算框架，也可以支持SQL即时查询、实时流式计算、机器学习和图计算等

Spark可以部署在资源管理器YARN之上，提供一站式的大数据解决方案

Spark所提供的生态系统足以应对上述三种场景，即同时支持批处理、交互式查询和流数据处理

BDAS架构

Spark生态系统组件的应用场景

应用场景 时间跨度 其他框架 Spark生态系统中的组件
复杂的批量数据处理 小时级 MapReduce、Hive Spark Core
基于历史数据的交互式查询 分钟级、秒级 Impala、Dremel、Drill Spark SQL
基于实时数据流的数据处理 毫秒、秒级 Storm、S4 Spark Streaming
基于历史数据的数据挖掘 - Mahout MLlib
图结构数据的处理 - Pregel、Hama GraphX

Spark运行架构

①基本概念

②架构设计

③Spark运行基本流程

RDD

（Resillient Distributed Dataset，弹性分布式数据集），是Spark中最基本的数据抽象，代表一个不可变（只读）、可分区、分布式对象集合。

只读：不能修改，只能通过转换操作生成新的 RDD。

弹性：计算过程中内存不够时它会和磁盘进行数据交换。

分区：不同分区可以保存到集群中不同的节点上，从而可以进行并行计算。

RDD支持两种操作:

转换（Transformation）：返回一个新的 RDD的操作。

行动（Action）：是向驱动器程序返回结果或把结果写入外部系统的操作。

转换操作

RDD转换 含义
map(func) 将一个RDD中的每个数据项，通过函数func映射变为一个新的元素
filter(func) 通过函数func选择过滤数据集中的成员
flatMap(func) 和map转换类似，但函数func可以把单个成员转换为多个成员。
union(other) 返回当前集合与otherDataset集合的union操作
distinct 去掉集合中重复成员，使新的集合中成员各不相同
groupByKey 对键-值（key-value）对集合按照键（key）进行groupBy操作
sortByKey 对键-值（key-value）对集合进行排序
join(other) 对两个键-值（key-value）对集合：（K,V），（K,W）进行连接操作，形成新的键-值对集合：（K，（V,W））

行动操作

Action 含义
collect 返回RDD中的所有元素
count 返回RDD中元素的数量
countByKey 计算键-值对RDD每个键（key）对应的元素个数
first 返回RDD中第一个元素
take(n) 返回RDD中前n个元素
reduce(func) 通过函数func对RDD进行聚合操作
saveAsTextFile(path) 把RDD保存为一个文本文件，可以选择保存在本地文件系统、HDFS等。文件中的一行为RDD中的一个元素
foreach(func) 通过函数func对RDD中的每个元素进行计算，通常在更新累加器或者使用外部存储系统时用到

RDD典型的执行过程：

RDD读入外部数据源进行创建

RDD经过一系列的转换（Transformation）操作，每一次都会产生不同的RDD，供给下一个转换操作使用

最后一个RDD经过“动作”操作进行转换，并输出到外部数据源

RDD 的最重要的特性之一就是血缘关系（Lineage )，它描述了一个 RDD 是如何从父 RDD 计算得来的。如果某个 RDD 丢失了，则可以根据血缘关系，从父 RDD 计算得来。 图 2 给出了一个 RDD 执行过程的实例。系统从输入中逻辑上生成了 A 和 C 两个 RDD， 经过一系列转换操作，逻辑上生成了 F 这个 RDD。 Spark 记录了 RDD 之间的生成和依赖关系。当 F 进行行动操作时，Spark 才会根据 RDD 的依赖关系生成 DAG，并从起点开始真正的计算。

DAG（Directed Acyclic Graph，有向无环图）:RDD的每次转换都会生成一个新的RDD，RDD之间就会形成类似于流水线一样的前后依赖关系。DAG描述了整个流式计算的流程。

在部分分区数据丢失时，Spark可以通过DAG重新计算丢失的分区数据，而不是对RDD的所有分区进行重新计算。

RDD之间的依赖关系

窄依赖

宽依赖

窄依赖表现为一个父RDD的分区对应于一个子RDD的分区或多个父RDD的分区对应于一个子RDD的分区

宽依赖则表现为存在一个父RDD的一个分区对应一个子RDD的多个分区，宽依赖存在Shuffle操作

Application：用户编写的Spark应用程序

Job：一个Job包含多个RDD及作用于相应RDD上的各种操作

Stage：是Job的基本调度单位，一个Job会分为多个Stage，或者称为TaskSet，代表了一组关联的、相互之间没有Shuffle依赖关系的任务组成的任务集。

Task：是运行在Executor上的工作单元 ，1个Stage包含一组Task

Spark 根据DAG 图中的RDD 依赖关系，把一个作业分成多个阶段。

阶段划分的依据是窄依赖和宽依赖。窄依赖对于作业的优化很有利，宽依赖包含Shuffle过程，无法实现流水线方式处理。

阶段划分方法：

①在DAG中进行反向解析，遇到宽依赖就断开

②遇到窄依赖就把当前的RDD加入到Stage中

③将窄依赖尽量划分在同一个Stage中，可以实现流水线计算

Spark运行架构包括集群资源管理器（Cluster Manager）、运行任务的工作节点（Worker Node）、每个应用的任务控制节点（Driver）和每个工作节点上负责具体任务Task的执行进程（Executor）

资源管理器可以自带或Mesos或YARN

Executor优点：

一是利用多线程来执行具体的任务，减少任务的启动开销

二是Executor中有一个BlockManager存储模块，会将内存和磁盘共同作为存储设备，有效减少IO开销

一个Application由一个Driver和若干个Job构成，一个Job由多个Stage构成，一个Stage由多个Task组成

当执行一个Application时，Driver会向集群管理器申请资源，启动Executor，并向Executor发送应用程序代码和文件，然后在Executor上执行Task，运行结束后，执行结果会返回给Driver，或者写到HDFS或者其他数据库中

Spark运行基本流程图

（1）由Driver创建一个SparkContext，为应用构建起基本的运行环境，进行资源的申请、任务的分配和监控

（2）资源管理器为Executor分配资源，并启动Executor进程

（3）SparkContext根据RDD的依赖关系构建DAG图，DAG图提交给DAGScheduler解析成Stage，然后把一个个TaskSet提交给底层调度器TaskScheduler处理；Executor向SparkContext申请Task，Task Scheduler将Task发放给Executor运行，并提供应用程序代码

（4）Task在Executor上运行，执行结果反馈给TaskScheduler，然后反馈给DAGScheduler，运行完毕后写入数据并释放所有资源

Spark架构优点：

实现一键式安装和配置、线程级别的任务监控和告警

降低硬件集群、软件维护、任务监控和应用开发的难度

便于做成统一的硬件、计算平台资源池

说明：Spark Streaming是将流数据分解成一系列短小的批处理作业，无法实现毫秒级的流计算，因此，对于需要毫秒级实时响应的企业应用而言，仍然需要采用流计算框架（如Storm）

由于Hadoop生态系统中的一些组件所实现的功能，目前还是无法由Spark取代的，比如，Storm

现有的Hadoop组件开发的应用，完全转移到Spark上需要一定的成本

不同的计算框架统一运行在YARN中，可以带来如下好处：

计算资源按需伸缩

不用负载应用混搭，集群利用率高

共享底层存储，避免数据跨集群迁移

流计算框架Storm

静态数据：支持决策分析而构建的数据仓库系统存放的大量历史数据就是静态数据。

流数据：数据以大量、快速、时变的流形式持续到达，比如：Web应用的电子商务网站用户点击流，网络监控的数据流、传感监测的PM2.5检测等。

流数据特征：

数据快速持续到达，潜在大小也许是无穷无尽的

数据来源众多，格式复杂

数据量大，但是不十分关注存储，一旦经过处理，要么被丢弃，要么被归档存储

注重数据的整体价值，不过分关注个别数据

数据顺序颠倒，或者不完整，系统无法控制将要处理的新到达的数据元素的顺序

对静态数据和流数据的处理，对应着两种截然不同的计算模式：批量计算和实时计算

批量计算：处理静态数据，如Hadoop

流数据必须采用实时计算，响应时间为秒级

大数据时代，数据格式复杂、来源众多、数据量巨大，对实时计算提出了很大的挑战。因此，针对流数据的实时计算——流计算，应运而生

流计算：

实时获取来自不同数据源的海量数据，经过实时分析处理，获得有价值的信息

了及时处理流数据，就需要一个低延迟、可扩展、高可靠的处理引擎

①目前有三类常见的流计算框架和平台：

②商业级：IBM InfoSphere Streams和IBM StreamBase

③开源流计算框架，代表如下：

a)Twitter Storm：免费、开源的分布式实时计算系统，可简单、高效、可靠地处理大量的流数据

b)Yahoo! S4（Simple Scalable Streaming System）：开源流计算平台，是通用的、分布式的、可扩展的、分区容错的流式系统

④公司为支持自身业务开发的流计算框架：

a)Facebook Puma

b)Dstream（百度）

c)银河流数据处理平台（淘宝）

流计算的处理流程一般包含三个阶段：数据实时采集、数据实时计算、实时查询服务

目前有许多互联网公司发布的开源分布式日志采集系统均可满足每秒数百MB的数据采集和传输需求，如：

Facebook的Scribe

LinkedIn的Kafka

基于Hadoop的Chukwa和Flume

流计算应用场景

实时个性化内容推荐：如百度、淘宝等大型网站中，每天都会产生大量流数据，包括用户的搜索内容、用户的浏览记录等数据。采用流计算进行实时数据分析，可以了解每个时刻的流量变化情况，可以分析用户的实时浏览轨迹，从而进行实时个性化内容推荐

实时交通：借助流计算的实时特性，可以根据交通情况制定路线，而且在行驶过程中，也可以根据交通情况的变化实时更新路线，为用户提供最佳的行驶路线

机器翻译

广告投放

自然语言处理

气候模拟预测等

Storm特点：

整合性：Storm可方便地与队列系统和数据库系统进行整合

简易的API：Storm的API使用简单又方便

可扩展性：Storm的并行特性使其可以运行在分布式集群中

容错性：Storm可自动进行故障节点的重启、任务的重新分配

可靠的消息处理：Storm保证每个消息都能完整处理

支持各种编程语言：Storm支持各种编程语言定义任务

快速部署：Storm可以快速进行部署和使用

免费、开源：Storm是一款开源框架，可以免费使用

Storm主要术语

Streams：Storm将流数据Stream描述成一个无限的Tuple (元组)序列，这些Tuple序列会以分布式的方式并行地创建和处理

每个tuple是一堆值，即Value List（值列表），每个值有一个名字，并且每个值可以是任何类型

Spouts：Storm认为每个Stream都有一个源头，并把这个源头抽象为Spout（出水口）

通常Spout会从外部数据源（队列、数据库等）读取数据，然后封装成Tuple形式，发送到Stream中。

Spout是一个主动的角色，在接口内部有个nextTuple函数，Storm框架会不停的调用该函数

Bolts：Storm将Streams的状态转换过程抽象为Bolt（门闩）。Bolt可以处理Tuple，也可以将处理后的Tuple作为新的Streams发送给其他Bolt

Bolt可以执行过滤、聚合、查询等操作

Topology：**Storm将Spouts和Bolts组成的网络抽象成Topology（拓扑结构），可以被提交到Storm集群执行。**Topology为流转换图，图中节点是一个Spout或Bolt，边表示Bolt订阅了哪个Stream。当Spout或者Bolt发送元组时，它会把元组发送到每个订阅了该Stream的Bolt上进行处理

Topology的每个处理组件（Spout或Bolt）都包含处理逻辑，都是并行运行的， 而组件之间的连接则表示数据流动的方向。

Topology指定每个组件的并行度， Storm会在集群分配那么多的线程同时计算

Stream Groupings：用于告知Topology如何在两个组件间（如Spout和Bolt之间，或者不同的Bolt之间）进行Tuple的传送。

每一个Spout和Bolt都可以有多个分布式任务，一个任务在什么时候、以什么方式发送Tuple就是由Stream Groupings来决定的

Storm中的Stream Groupings有如下几种方式：

(1)ShuffleGrouping：随机分组，随机分发Stream中的Tuple，保证每个Bolt的Task接收Tuple数量大致一致

(2)FieldsGrouping：按照字段分组，保证相同字段的Tuple分配到同一个Task中

(3)AllGrouping：广播发送，每一个Task都会收到所有的Tuple

(4)GlobalGrouping：全局分组，所有的Tuple都发送到同一个Task中

(5)NonGrouping：不分组，和ShuffleGrouping类似，当前Task的执行会和它的被订阅者在同一个线程中执行

(6)DirectGrouping：直接分组，直接指定由某个Task来执行Tuple的处理

Storm框架设计

Storm运行任务的方式与Hadoop类似：Hadoop运行的是MapReduce作业，而Storm运行的是“Topology”

不同：MapReduce作业最终会完成计算并结束运行，而Topology将持续处理消息（直到人为终止）

Storm和Hadoop架构组件功能对应关系

Hadoop Storm
应用名称 Job Topology
系统角色 JobTracker Nimbus
TaskTracker Supervisor
组件接口 Map/Reduce Spout/Bolt

Storm集群采用“Master—Worker”的节点方式：

Master节点运行名为Nimbus（雨云）的后台程序，负责在集群范围内分发代码、为Worker分配任务和监测故障。

Worker节点运行名为“Supervisor（监管器）的后台程序，负责监听它所在机器分配的工作，即根据Nimbus分配的任务决定启动或停止Worker进程，一个Worker节点上同时运行若干个Worker进程

Storm使用Zookeeper来作为分布式协调组件，负责Nimbus和多个Supervisor之间的所有协调工作。

借助Zookeeper，若Nimbus进程或Supervisor进程意外终止，重启时也能读取、恢复之前的状态并继续工作，使得Storm极其稳定

Storm的工作流程：

①Storm客户端提交Topology任务到Nimbus节点；

②Nimbus节点将提交的Topology分成一个个Task 写入Zookeeper

③Supervisor会去Zookeeper集群上认领自己的Task，启动Worker进程；

④Worker进程执行具体Task

Spark Streaming可整合多种输入数据源，如Kafka、Flume、HDFS、TCP套接字。经处理后的数据可存储至文件系统、数据库，或显示在仪表盘里

Spark Streaming的基本原理是将实时输入数据流以时间片（秒级）为单位进行拆分，然后经Spark引擎以类似批处理的方式处理每个时间片数据

图 Spark Streaming执行流程

Spark Streaming最主要的抽象是DStream（Discretized Stream，离散化数据流），表示连续不断的数据流。在内部实现上，Spark Streaming的输入数据按照时间片（如1秒）分成一段一段的DStream，每一段数据转换为Spark中的RDD，并且对DStream的操作最终转变为对相应的RDD的操作。

Spark Streaming

Spark Streaming和Storm最大的区别在于，Spark Streaming无法实现毫秒级的流计算，而Storm可以实现毫秒级响应

Spark Streaming构建在Spark上，采用小批量处理方式，可以同时兼容批量和实时数据处理的逻辑和算法

从编程的灵活性来讲，Storm是比较理想的选择，使用Apache Thrift，可以用任何编程语言来编写拓扑结构（Topology）

Hive

Hive是一个构建于Hadoop之上的数据仓库工具。

某种程度上可以看作是用户编程接口，本身不存储和处理数据。

依赖分布式文件系统HDFS存储数据。

依赖分布式并行计算模型MapReduce处理数据。

定义了简单的类SQL 查询语言——HiveQL

用户可以通过编写的HiveQL语句运行MapReduce任务

Hadoop生态系统中Hive与其他部分的关系

Hive在很多方面和关系数据库类似，但它的底层依赖的是HDFS和MapReduce。

Hive与关系数据库的对比

对比项目 Hive 关系数据库
数据插入 支持批量导入 支持单条和批量导入
数据更新 不支持 支持
索引 支持 支持
分区 支持 支持
执行延迟 高 低
扩展性 好 有限

（1）数据插入：因为Hive主要用来支持大规模数据集上的数据仓库应用程序的运行，常见操作是全表扫描，所以单条插入功能对Hive并不实用

（2）数据更新：更新是传统数据库中很重要的特性，Hive不支持数据更新。Hive是一个数据仓库工具，而数据仓库中存放的是静态数据，所以Hive不支持对数据进行更新。

（3）索引：Hive在hive 0.7版本后已经可以支持索引了。但Hive不像传统的关系型数据库那样有键的概念，它只提供有限的索引功能，使用户可以在某些列上创建索引来加速一些查询操作，Hive中给一个表创建的索引数据被保存在另外的表中。

•（4）分区：传统的数据库提供分区功能来改善大型表以及具有各种访问模式的表的可伸缩性，可管理性和提高数据库效率。Hive也支持分区功能，Hive表组织成分区的形式，根据分区列的值对表进行粗略的划分，使用分区可以加快数据的查询速度。

•（5）执行延迟：因为Hive构建于HDFS与MapReduce上，所以对比传统数据库来说Hive的延迟比较高，传统的SQL语句的延迟少于一秒，而HiveQL语句的延迟会达到分钟级。

•（6）扩展性：传统关系数据库很难横向扩展，纵向扩展的空间也很有限。相反Hive的开发环境是基于集群的，所以具有较好的可扩展性。

Hive系统架构

①Hive组成模块

②Hive工作原理

  1. 用户接口模块：包括CLI、HWI、JDBC、ODBC、Thrift Server等

CLI是Hive自带的一个命令行界面；

HWI（Hive Web Interface）是Hive的一个简单网页界面；

JDBC、ODBC以及Thrift Server可以向用户提供进行编程访问的接口。

  1. 驱动模块：包括编译器、优化器、执行器等，所有命令和查询都会进入到驱动模块，通过该模块对输入进行解析编译，对需求的计算进行优化，然后按照指定的步骤执行。

  2. **元数据存储模块（Metastore）：**是一个独立的关系数据库，通常是与MySQL数据库连接后创建的一个MySQL实例，也可以是Hive自带的derby数据库实例。

    元数据存储模块中保存表模式和其他系统元数据，如表的名称、表的列及其属性、表的分区及其属性、表的属性、表中数据所在位置信息等。

a)SQL语句转换成MapReduce的基本原理

b)Hive中SQL查询转换成MapReduce作业的过程

Hive常见的应用场景

(1)日志分析：大部分互联网公司使用hive进行日志分析，包括百度、淘宝等。

• 1)统计网站一个时间段内的pv、uv

• 2)多维度数据分析

(2)海量结构化数据离线分析

第9章 数据分析方法

数据挖掘和机器学习简介

机器学习

研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域。

数据挖掘

是指从大量的数据中通过算法搜索隐藏于其中信息的过程。

机器学习算法的分类：

  1. 有监督学习：训练数据既有特征(feature)又有标签(label)，通过训练，让机器可以自己找到特征和标签之间的联系，在面对只有特征没有标签的数据时，可以判断出标签。
  2. 无监督学习：训练样本的标记信息未知，目标是通过对无标签训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础，此类学习任务中研究最多、应用最广的是"聚类" (clustering)，其他无监督算法还有：密度估计(densityestimation)、异常检测（anomaly detection) 等。
  3. 半监督学习：训练集同时包含有标签样本数据和无标签样本数据，不需要人工干预，让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习。

典型的机器学习和数据挖掘算法

分类，聚类，回归分析，关联规则，神经网络，深度学习

分类

基于已有的样本预测新样本的所属类别。

分类的主要用途和场景是“预测”。

例如

  • 将给定的电子邮件分配给“垃圾邮件”或“非垃圾邮件”类；

  • 根据观察到的患者特征（性别，血压，某些症状的存在或不存在等）为给定患者分配诊断。

  • 信用评级、风险等级、欺诈预测等

分类算法的训练和评价

  • 留出法（Holdout）: 将数据集D划分为两个互斥的集合，其中一个集合作为训练集S， 另一个作为测试集T。在S上训练出模型后， 用T来评估其测试误差，作为对泛化误差的估计。
  • 交叉验证（k-fold Cross-validation): 将数据集分割成k个子样本。在每次运行时，使用一个不同的子样本作为测试集，其余的K-1子样本作为训练集。 用k次运行的平均来估计这个方法的性能。这种方法减少了训练集/测试集的随机性，有益于大数据集。

常用的分类算法包括朴素贝叶斯、逻辑回归、决策树、随机森林、支持向量机等。

决策树

决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

决策树是一种监督学习方法，就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

最经典的决策树算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，可以处理离散属性样本的分类，C4.5和CART算法则可以处理更加复杂的分类问题。

决策树-ID3

Iterative Dichotomiser 3，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法。

决策树学习的关键在于如何选择最优的划分属性，即对于二元分类而言，尽量使划分的样本属于同一类别，即“纯度”最高的属性。

“信息熵（information entropy）：度量特征（features）的纯度。

1948年，香农 (Shannon)在他著名的《通信的数学原理》论文中指出：“信息是用来消除随机不确定性的东西”，并提出了“信息熵”的概念（借用了热力学中熵的概念），来解决信息的度量问题。

变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。

信息增益（information gain）使用属性a对样本集D进行划分所获得的“信息增益”的计算方法是，用样本集的总信息熵减去属性a的每个分支的信息熵与权重（该分支的样本数除以总样本数）的乘积。

信息增益越大，意味着用属性a进行划分所获得的“纯度提升”越大。因此，优先选择信息增益最大的属性来划分。

决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，会导致整棵树的分支过多，也就导致了过拟合。

剪枝（pruning）的目的是为了避免决策树模型的过拟合。

决策树的剪枝策略：

  • 预剪枝（pre-pruning）：在构造决策树的过程中，先对每个结点在划分前进行估计，如果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。

  • 后剪枝（post-pruning）：先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。

泛化能力（generalization ability）是指机器学习算法对新鲜样本的适应能力。学习的目的是学到隐含在数据背后的规律，对具有同一规律的学习集以外的数据，经过训练的网络也能给出合适的输出，该能力称为泛化能力。

ID3算法的缺点

缺点：信息增益偏向取值较多的属性

原因：当某个属性的取值较多时，根据此特征划分更容易得到确定性更强的子集划分结果，因此划分之后的熵更低，则信息增益更大，因此信息增益比较偏向取值较多的属性。

解决方法 :信息增益比（ C4.5算法 ）

聚类

聚类把全体数据实例组织成一些相似组，而这些相似组被称作簇。

聚类技术通常又被称为无监督学习，与监督学习不同的是，在簇中那些表示数据类别的分类或者分组信息是没有的。

数据之间的相似性是通过定义一个距离或者相似性系数来判别的。

应用场景

  • 商业，聚类分析发现不同的客户群，通过对不同的客户群的特征的刻画，被用于研究消费者行为，寻找新的潜在市场。
  • 在生物，聚类分析对动植物和基因进行分类，以获取对种群固有结构的认识。
  • 在保险行业，聚类分析通过平均消费来鉴定汽车保险单持有者的分组，同时可以根据住宅类型、价值、地理位置来鉴定城市的房产分组。
  • 在互联网应用，聚类分析被用来在网上进行文档归类。
  • 在电子商务，聚类分析通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，帮助企业了解客户，向客户提供更合适的服务。
  • 网络社区发现，社会关系网络中，能够显示根据兴趣、职业、地域、背景而形成的真实的社会团体。从而可以进行人物分析、职业推荐、圈子推荐、好友推荐、校友发现以及精准广告投放。

什么是好的聚类方法?

  • 好的聚类方法需要产生高质量的聚类结果，这些簇必须满足：

  • 高的内部相似度（簇内越紧密越好）

  • 低的外部相似度 （簇间越分离越好）

聚类质量度量指标

  1. Compactness(紧密性)

    以簇内误差的平方和（Sum of the Squared Error ,SSE）

    作为度量标准(计算每一个类各点到聚类中心的距离)：

  2. Separation(间隔性)

    如：计算各聚类中心两两之间平均距离。

聚类算法类型

  1. 划分法 (partitioning methods)
  2. 层次法(hierarchical methods)
  3. 基于密度的方法(density-based methods)
  4. 基于网格的方法(grid-based methods)

划分聚类方法

给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分， 每一个划分就代表一个簇，k<n。

条件：每一个簇至少包含一个对象；每一个对象属于且仅属于一个簇。

代表算法： K-means(k-均值聚类)、 K-medoids等算法。

K-means步骤：

1、首先确定一个k值，即希望将数据集经过聚类得到k个集合。

2、从数据集中随机选择k个数据点作为质心（每个簇的均值向量，即向量各维取平均即可）。

3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。

4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。

5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），算法终止。

6、如果新质心和原质心距离变化很大，需要迭代3~5步骤

K-Means方法的优劣

优点:

容易理解，聚类效果不错。

算法复杂度低。时间复杂度为O(tkn), 其中n对样本数, k是类簇数, t是 迭代次数。通常情况下 k, t << n.

不足：

必须事先给定簇的数量k；

对初始的簇中心敏感，不同选取方式会得到不同结果；

不能处理噪声和离群点；

不适合于发现非凸形状的簇

层次聚类方法

凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇， 然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。

分裂的层次聚类：采用自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。

代表的算法：BRICH、CURE、ROCK等算法。

BIRCH 算法：利用了一个树结构来帮助快速的聚类，这个特殊的树结构叫聚类特征树（CF-tree）。

BIRCH算法：适合于数据量大，类别数K也比较多的情况。运行速度很快，只需要单遍扫描数据集就能进行聚类

密度聚类方法

只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。**

代表算法：

DBSCAN、OPTICS、DENCLUE

DBSCAN
原理

DBSCAN将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

①初始状态，给出一个数据集D，并设置半径ε和密度阈值MinPts，将D中的所有对象标记为"unvisited"（未被访问）

②随机从D中选取一个未被访问的对象p，并标记为“visited”（已被访问）；

③检查p的ε-邻域内是否至少包含MinPts个对象（即p是否是核心对象），若不是，则将p标记为噪声点；

④否则，为p创建一个新的簇C，把p的ε-邻域中所有对象放入候选集合N中，并迭代的将N中不属于其它簇的对象加入到新簇C中，将N中的"unvisited"的对象q标记为"visited"，若q的ε-邻域是否至少包含MinPts个对象，则将q的ε-邻域中所有的对象加入到C中，直到C不再扩大，N为空的时候，此时簇C完成聚类，并输出。

⑤继续从D中随机选取未被访问的对象s，同样使用（2）中的聚类方法，直到对象集D中所有对象都被访问。

优点：

能够发现任意形状的簇，并有效识别离群点；

不需要事先知道要形成的簇类的数量；

对数据库中样本的顺序不敏感，即Pattern的输入顺序对结果的影响不大，但对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动；

缺点

聚类之前需要人工选择Eps和minPts这两个参数；

当数据量增大时，要求较大的内存支持；

不能很好地反映高维数据和数据集已变化的密度；

由于算法使用了全局性表征密度的参数，因此当各个类的密度不均匀，或类间的距离相差很大时，聚类的质量较差。

网格聚类方法

基于网格的聚类算法出发点不再是平面而是空间。

在该空间中，有限个网格代表数据，聚类就是按一定的规则将网格合并。

基于网格的聚类算法由于处理数据时是独立的，仅仅依赖网格结构中每一维的单位数，因此处理速度很快。

但是此算法对参数十分敏感，速度快的代价是精确度不高，通常需要与其他聚类算法结合使用。

代表算法： CLIQUE、STING等算法。

回归分析

是确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。通常用于预测分析，时间序列模型以及发现变量之间的因果关系

回归分析分类

按照涉及的变量的多少

分为一元回归和多元回归分析；多元回归有一个以上的自变量，而一元回归只有一个自变量。

按照因变量的多少

分为简单回归分析和多重回归分析

按照自变量和因变量之间的关系类型

分为线性回归分析和非线性回归分析。

一元线性回归

线性回归使用最佳的拟合直线（也就是回归线） 建立因变量(Y) 和一个或多个自变量(X)之间的联系。 用一个等式来表示它。

最小二乘法用于拟合回归线最常用的方法。

Logistic Regression逻辑回归

Logistic回归主要在流行病学中应用较多，比较常用的情形是探索某疾病的危险因素，根据危险因素预测某疾病发生的概率，等等。例如，想探讨胃癌发生的危险因素，可以选择两组人群，一组是胃癌组，一组是非胃癌组，两组人群肯定有不同的体征和生活方式等。这里的因变量就是是否胃癌，即“是”或“否”，自变量就可以包括很多了，例如年龄、性别、饮食习惯、幽门螺杆菌感染等。自变量既可以是连续的，也可以是分类的。

逻辑回归用来计算“事件=Success”和“事件=Failure”的概率。

常用于二分类问题。

简单、可并行化、可解释强，深受工业界喜爱。

逻辑回归是基于sigmoid函数构建的模型。sigmod函数公式如下：

h(x)=11+e−xh(x)=\frac{1}{1+e^{-x}}

中间范围内函数斜率最大，对应Y的大部分数值变化

Y轴数值范围在 0~1 之间

X轴数值范围没有限制，当X大于一定数值后，Y无限趋近于1，小于一定数值后，Y无限趋近于0

当 X=0 时，Y=0.5

逻辑回归模型通过在线性回归模型的基础上，套一个sigmoid函数来实现，不管X取什么样的值，Y值都被非线性地映射在 0~1 之间，实现二分类。

公式中，y理解为样本x为正例的概率，而1-y则可以理解为样本x为负例时的概率。二者的比值**y/(1-y)**被称为odds，即几率，反映x作为正例的相对可能性，对几率取对数就得到了线性回归模型。

逻辑回归优点

  1. 直接对分类可能性进行建模，无需实现假设数据分布，避免了假设分布不准确所带来的问题。

  2. 形式简单，模型的可解释性非常好，特征的权重可以看到不同的特征对最后结果的影响。

  3. 除了类别，还能得到近似概率预测，对许多需利用概率辅助决策的任务很有用。

缺点：

  1. 准确率不是很高，因为形式非常的简单，很难去拟合数据的真实分布。

  2. 本身无法筛选特征。

关联规则Association Rules：

反映一个事物与其他事物之间的相互依存性和关联性，用于从大量数据中挖掘出有价值的数据项之间的相关关系。

经典案例“啤酒和纸尿裤搭配售卖

•关联规则应用场景有：

•优化货架商品摆放

•交叉销售和捆绑销售 等

•常用算法：Apriori 算法 FP-growth算法等

关联规则:给定一组事务，寻找预测“某些项将会随其他项的出现而出现”的规则。

{面包，啤酒}→{牛奶}

蕴含符号“→”表现共现关系，而不是因果关系

规则评估标准——支持度、置信度

支持度（support）：关联数据在数据集中出现的次数或所占的比重。

support(X→Y)=P(X∪Y)=∣X∪Y∣∣D∣support(X\to{Y})=P(X\cup{Y})=\frac{|{X\cup{Y}}|}{|D|}

置信度（confidence）：置信度表示Y数据出现后，X数据出现的可能性，也可以说是数据的条件概率。

confidence(X⇐Y)=P(X∣Y)=P(XY)P(Y)confidence(X\Leftarrow{Y})=P(X|Y)=\frac{P(XY)}{P(Y)}

强关联规则：满足最小支持度和最小置信度的关联规则。

候选项集:用来获取频繁项集。

频繁项集:在所有训练元组中同时出现的次数超过人工定义的阈值的项集（支持度>=最小支持度的集合），即候选项集中满足支持度条件的项集保留，不满足条件的舍弃。

频繁项集——基本原则

1.任意一个频繁项集，它所有的非空子集都必须是频繁的。

2.如果一个项集是不频繁的，那他的超集一定是不频繁的。

在Apriori算法中，通常使用支持度作为判断频繁项集的标准。

Apriori算法的目标是找到最大的K项频繁集。

**频繁项集产生：**目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset)

Apriori的算法步骤

输入：数据集合D，支持度阈值α

输出：最大的频繁k项集

1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。

2）挖掘频繁k项集

a) 扫描数据计算候选频繁k项集的支持度

b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。

c) 基于频繁k项集，连接生成候选频繁k+1项集。

3） 令k=k+1，转入步骤2。

FP-growth算法(FP, Frequent Pattern)

FP-growth算法只需要对数据库进行两次扫描。而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定的模式是否频繁，因此FP-growth算法要比Apriori算法快。

FP-growth算法第一遍对所有数据元素出现次数进行计数，第二遍只需考虑那些频繁的元素。

发现频繁项集的基本过程分为两步，

构建FP树

从FP树中挖掘频繁项集。

FP-growth的一般流程如下：

•1：先扫描一遍数据集，得到频繁项为1的项目集，定义最小支持度（项目出现最少次数），删除那些小于最小支持度的项目，然后将原始数据集中的条目按项目集中降序进行排列。

•2：第二次扫描，创建项头表（从上往下降序），以及FP树。

•3：对于每个项目（可以按照从下往上的顺序）找到其条件模式基（CPB，conditional patten base）,递归调用树结构，删除小于最小支持度的项。如果最终呈现单一路径的树结构，则直接列举所有组合；非单一路径的则继续调用树结构，直到形成单一路径即可

神经网络

神经网络是一种模拟人脑的神经网络以期能够实现类人工智能的机器学习技术。

人脑中的神经网络是一个非常复杂的组织。成人的大脑中估计有1000亿个神经元之多。

神经元是神经系统最基本的结构和功能单位。

神经元模型MP结构

神经元模型是一个包含输入，输出与计算功能的模型。

输入类比为神经元的树突，输出类比为神经元的轴突，计算则可以类比为细胞核。

一个典型的神经元模型：包含有3个输入，1个输出，以及2个计算功能。中间的箭头线称为“连接”。每个上有一个“权值”。

一个神经网络的训练算法就是让权重的值调整到最佳，以使得整个网络的预测效果最好。

a来表示输入，w来表示权值。每个有向箭头表示值的加权传递。

在初端，传递的信号大小仍然是a，端中间有加权参数w，经过加权后的信号会变成aw，因此在连接的末端，信号的大小就变成了aw。

如果将神经元图中的所有变量用符号表示，计算公式如图，z是在输入和权值的线性加权和叠加了一个函数g的值。MP模型中，函数g是sgn函数（阶跃函数），当x＞0时f(x)=1，当x＜0时f(x)=-1。

神经元模型理解：

有一个数据，称之为样本。样本有四个属性，其中三个属性已知（特征），一个属性（目标）未知。需要通过三个已知属性预测未知属性。

假设特征与目标之间确实是线性关系，并且已经得到表示这个关系的权值w1，w2，w3。那么，可以通过神经元模型预测新样本的目标。

1943年发布的MP模型，简单，但是权重的值都是预先设置的，因此不能学习。

把神经元的输入向前传递获得输出的过程称为前馈（feedforward）。

单层神经网络（感知器）

1958年，计算科学家Rosenblatt提出了由两层神经元组成的神经网络。起名为“感知器” （Perceptron）

感知器模型结构

在原来MP模型的“输入”位置添加神经元节点，标志其为“输入单元”。其余不变。

有两个层次，输入层里的“输入单元”只负责传输数据，不做计算。

输出层里的“输出单元” 需要对前面一层的输入进行计算，叫计算层。

拥有一个计算层的网络称之为“单层神经网络”。

感知器中的权值是通过训练得到的。感知器类似一个逻辑回归模型，可以做线性分类任务。

可以用决策分界形象表达分类的效果。决策分界就是在二维的数据平面中划出一条直线，当数据的维度是3维的时候，就是划出一个平面，当数据的维度是n维时，就是划出一个n-1维的超平面。

BP神经网络

•1986年，Rumelhar和Hinton等人提出了反向传播（Backpropagation，BP）算法，解决了两层神经网络所需要的复杂计算量问题，带动了业界使用两层神经网络研究的热潮。

•假设预测目标是一个向量，只需要在“输出层”再增加节点

•使用向量和矩阵来表示层次中的变量。a(1)，a(2)，z是网络中传输的向量数据。W(1)和W(2)是网络的矩阵参数。

•偏置节点（bias unit）本质上是一个只含有存储功能，且存储值永远为1的单元。偏置单元与后一层的所有节点都有连接，设这些参数值为向量b。偏置的存在是为了更好的拟合数据。

在两层神经网络中，使用平滑函数sigmoid作为函数g（称作激活函数active function）

面对复杂的非线性分类任务，两层（带一个隐藏层）神经网络可以很好分类。

输入层的节点数与特征的维度匹配，输出层的节点数与目标的维度匹配。

隐藏层的节点数由设计者指定，节点数设置的多少，影响到整个模型的效果。

如何决定隐藏层的节点数？目前业界没有完善的理论来指导，一般是根据经验设置。较好的方法是预先设定几个可选值，通过切换这几个值来看整个模型的预测效果，选择效果最好的值作为最终选择。这种方法又叫做Grid Search（网格搜索）。

机器学习模型训练的目的，是使得参数尽可能的与真实的模型逼近。

具体做法：先给所有参数赋上随机值来预测训练数据中的样本。样本的预测目标为yp，真实目标为y。定义一个值损失loss，目标就是使对所有训练数据的损失和尽可能的小。均方误差（MSE）

loss = (yp - y)2

如果将神经网络预测的矩阵公式带入到yp中，可以把损失写为关于参数的函数，称为损失函数（loss function）。

问题：如何优化参数（改变网络的权重和偏置），能够让损失函数的值最小。优化问题

梯度下降算法（SGD）：每次计算参数在当前的梯度（求导），然后让参数向着梯度的反方向前进一段距离，不断重复，直到梯度接近零时截止。一般这个时候，所有的参数恰好达到使损失函数达到一个最低值的状态。

SGD定义了改变权重和偏置的方法：

ω1←ω1−η∂L∂ω1\omega _1\leftarrow\omega _1-\eta\frac{\partial{L}}{\partial{\omega_1}}

η是一个常数，称为学习率（learning rate），决定了训练网络速率的快慢。当∂L/∂w1是正数时，w1会变小；当∂L/∂w1是负数 时，w1会变大。用这种方法去逐步改变网络的权重w和偏置b，损失函数会缓慢地降低

在神经网络模型中，由于结构复杂，每次计算梯度的代价很大。

需要使用反向传播算法（back propagation），简称BP算法，适合于多层神经元网络的一种学习算法，建立在梯度下降法的基础上。

BP网络的输入输出关系实质上是一种映射关系：一个n输入m输出的BP神经网络所完成的功能是从n维欧氏空间向m维欧氏空间中一有限域的连续映射，这一映射具有高度非线性。

反向传播算法主要由两个环节(激励传播、权重更新)反复循环迭代，直到网络的对输入的响应达到预定的目标范围为止。

两层神经网络应用于语音识别，图像识别，自动驾驶等多个领域。

仍然存在若干的问题：

训练耗时久，可能会出现局部最优解问题，使得神经网络的优化较为困难。

隐藏层的节点数需要调参，使用不太方便。

多层神经网络（深度学习）

首先有一个“预训练”（pre-training）的过程，可以方便的让神经网络中的权值找到一个接近最优解的值，之后再使用“微调”(fine-tuning)技术来对整个网络进行优化训练。

这两个技术的运用大幅度减少了训练多层神经网络的时间。他给多层神经网络相关的学习方法赋予了一个新名词–“深度学习”。

预训练是提前已经给你一些初始化的参数，这个参数不是随机的，而是通过其他类似数据集上面学得的

多层神经网络中的层数增加很多有什么好处？

具有更深入的表示特征，随着网络的层数增加，每一层对于前一层次的抽象表示更深入。

在神经网络中，每一层神经元学习到的是前一层神经元值的更抽象的表示。例如第一个隐藏层学习到的是“边缘”的特征，第二个隐藏层学习到的是由“边缘”组成的“形状”的特征，第三个隐藏层学习到的是由“形状”组成的“图案”的特征，最后的隐藏层学习到的是由“图案”组成的“目标”的特征。通过抽取更抽象的特征来对事物进行区分，从而获得更好的区分与分类能力。

更强的函数模拟能力：由于随着层数的增加，整个网络的参数就越多。神经网络本质就是模拟特征与目标之间的真实关系函数的方法，更多的参数意味着其模拟的函数可以更加的复杂，可以有更多的容量（capcity）去拟合真正的关系。

通过研究发现，在参数数量一样的情况下，更深的网络往往具有比浅层的网络更好的识别效率。

这点在ImageNet的多次大赛中得到了证实。从2012年起，每年获得ImageNet冠军的深度神经网络的层数逐年增加，2015年最好的方法GoogleNet是一个多达22层的神经网络。

多层神经网络训练：

ReLU函数在训练多层神经网络时，更容易收敛，并且预测性能更好。

ReLU函数不是传统的非线性函数，而是分段线性函数。表达式非常简单，就是y=max(x,0)。在x大于0，输出就是输入，在x小于0时，输出保持为0。这种函数的设计启发来自于生物神经元对于激励的线性响应，当低于某个阈值后就不再响应的模拟。

训练的主题仍然是优化和泛化。

当使用足够强的计算芯片（例如GPU图形加速卡）时，梯度下降算法以及反向传播算法在多层神经网络中的训练仍然工作的很好。

目前学术界主要的研究既在于开发新的算法，也在于对这两个算法进行不断的优化，例如，增加了一种带动量因子（momentum）的梯度下降算法。

在深度学习中，泛化技术变的比以往更加的重要。是因为神经网络的层数增加了，参数也增加了，表示能力大幅度增强，很容易出现过拟合现象。

前馈神经网络（FF），工作原理通常遵循以下规则：

1.所有节点都完全连接

2.激活从输入层流向输出，无回环

3.输入和输出之间有一层（隐含层）

RNN递归神经网络

引入不同类型的神经元——递归神经元，在网络中每个隐含神经元会收到它自己的在固定延迟（一次或多次迭代）后的输出。

RNN主要被使用在上下文很重要的时候——即过去的迭代结果和样本产生的决策会对当前产生影响。最常见的上下文的例子是文本——一个单词只能在前面的单词或句子的上下文中进行分析。

循环神经网络很难训练，导致在实际应用中很难处理长距离的依赖。长短时记忆网络(成功解决了原始循环神经网络的缺陷，在语音识别、图片描述、自然语言处理等许多领域中成功应用。

LSTM长短时记忆网络引入了一个存储单元，一个特殊的单元，当数据有时间间隔（或滞后）时可以处理数据。

存储单元实际上由一些元素组成，称为门，它们是递归性的，并控制信息如何被记住和遗忘。

LSTM的结构复杂

Autoncoder（AE）自动编码器，通过重建输入的神经网络训练过程，隐藏层向量具有降维的作用。特点是编码器会创建一个隐藏层（或多个隐藏层）包含了输入数据含义的低维向量。然后有一个解码器，会通过隐藏层的低维向量重建输入数据。

帮助数据分类、可视化、存储。

数据分析工具

Excel

SPSS

Weka

深度学习框架

  • TensorFlow
  • Keras
  • PyTorch
  • Caffe
  • Deeplearning4j

深度学习框架是一种界面、库或工具，无需深入了解底层算法的细节的情况下，能够更容易、更快速地构建深度学习模型。

深度学习框架利用预先构建和优化好的组件集合定义模型，为模型的实现提供了一种清晰而简洁的方法。

一个良好的深度学习框架具备关键特征：

优化的性能

易于理解和编码

良好的社区支持

并行化的进程，以减少计算

自动计算梯度

第10章 数据可视化

10.1 数据可视化概述

数据可视化是指将大型数据集中的数据以图形图像形式表示，并利用数据分析和开发工具发现其中未知信息的处理过程。

基本思想是将数据库中每一个数据项作为单个图元素表示，大量的数据集构成数据图像，同时将数据的各个属性值以多维数据的形式表示，可以从不同的维度观察数据，从而对数据进行更深入的观察和分析。

雷达图是以从同一点开始的轴上表示的三个或更多个定量变量的二维图表的形式，显示多变量数据的图形方法。

依靠可视化手段进行数据分析可以让数据变得更加通俗易懂，有助于用户更加方便快捷地理解数据的深层次含义，有效参与复杂的数据分析过程，提升数据分析效率，改善数据分析效果。

可视化技术可以支持实现多种不同的目标：

  1. 观测、跟踪数据
  2. 分析数据
  3. 辅助理解数据
  4. 增强数据吸引力

可视化典型案例：

  • 安全供应商Norse打造了一张能够反映全球范围内黑客攻击频率的地图（http://map.ipviking.com），利用 “蜜罐”攻击陷阱显示出所有实时渗透攻击活动。地图中的每一条线代表的都是一次攻击活动，借此可以了解每一天、每一分钟甚至每一秒世界上发生了多少次恶意渗透。

  • 2014年1月25日晚间，央视与百度合作，启用百度地图定位可视化大数据播报春节期间全国人口迁徙情况引起广泛关注。
  • “世界国家健康与财富之间的关系”利用可视化技术，把世界上200个国家，从1810年到2010年历时200年其各国国民的健康、财富变化数据（收集了1千多万个数据）制作成三维动画进行了直观展示（http://www.moojnn.com/Index/whn）。

3D可视化是描绘和理解数据的一种手段，是数据的一种表征形式。3D可视化以一种独特的立体视角为用户呈现数据，可以帮助用户发现一些在2D模式下无法察觉的内容。

大数据可视化方法

文本可视化

  1. 文字是传递信息最常用的载体。
  2. 文本可视化的作用有以下四点：
  3. 理解 - 理解主旨
  4. 组织 - 组织、分类信息
  5. 比较 - 对比文档信息
  6. 关联 - 关联文本的 pattern 和其他信息

•对文本的理解需求分成三级：词汇级（Lexical Level）、语法级（Syntactic Level）和语义级（Semantic Level）。词汇级用各类分词算法，语法级用一些句法分析算法，语义级用主题抽取算法。

•文本数据预处理将无效数据过滤，提取有效词等；文本特征抽取是指提取文本的关键词、词频分布、语法级的实体信息、语义级的主题等；文本特征的度量是指在多种环境或多个数据源所抽取的文本特征进行深层分析，如相似性、文本聚类等。

文本可视化类型

•文本数据大致分为三种：单文本、文档集合和时序文本数据。对应的文本可视化也可分为三类：

  • 文本内容的可视化

标签云（Word Clouds或Tag Clouds）是一种典型的文本可视化技术。将关键词根据词频或其他规则进行排序，按照一定规律进行布局排列，用大小、颜色、字体等图形属性对关键词进行可视化。一般用字号大小代表该关键词的重要性，该技术多用于快速识别网络媒体的主题热度。

•基于关键词的文本内容可视化

•文档散（DocuBurst ）也是基于关键词的文本可视化，不过它还通过径向布局体现了词的语义等级。如下图所示，外层的词是内层词的下义祠，颜色饱和度的深浅用来体现词频的高低。

•Document Cards

•文档卡片（Document Cards） 结合了文档中的关键词和关键图片进行可视化，布局在一张小卡片中。

其中的关键图片是指采用智能算法抽取并根据颜色分类后的代表性图片。

•时序文本内容可视化

•时序数据是指具有时间或顺序特性的文本，例如一篇小说故事情节的变化，或一个新闻事件随时间的演化。

•ThemeRiver主题河流是一种经典的时序文本可视化方法。光阴似水，用河流来隐喻时间的变化几乎所有人都能非常好地理解。

•横轴表示时间，每一条不同颜色线条视作一条河流，每条河流表示一个主题，河流的宽度代表在当前时间点上的一个度量（如主题的强度）。这样既可以在宏观上看出多个主题的发展变化，又能看出在特定时间点上主题的分布。

•TIARA结合了标签云，通过主题分析技术（latent dirichlet allocation，LDA），将文本关键词根据时间点放置在每条色带上，用词的大小表示关键词在该时刻出现的频率。TIARA帮助用户快速分析文本具体内容随时间变化的规律，而不是仅仅一个度量带变化。

  • 文本关系的可视化

•文本关系可视化：研究的是文本或文档集合中的关系信息，比如文本的相似性、互相引用的情况、链接等。说到关系布局，一般都是树或图。

•Word Tree单词树把文本中的句子按树形结构布局，可以很好的看出一个单词在文本中出现的频率和单词前后的联系。

  • 文本多层面信息的可视化

•多层面或多维度是指从多个角度或提取多种特征对文本集合分析。

•Parallel Tag Clouds平行标签云结合了平行坐标和标签云视图。每一列是一个层面的标签云，然后连接的折线展现了选中标签在多个层面的分布。

网络数据可视化

•网络数据，称作图数据，由节点（nodes）和边（edges）构成，用来描述实体间关系的一种结构

•实体：人、事、物

•例如：人与人之间的关系、城市之间的道路连接、科研论文之间的引用都组成了网络

•网络数据可视化常用方法：

•节点—链接法

相邻矩阵法

节点—链接法：节点表示对象，边表示节点之间的关系，如果图的每条边有方向，称为有向图（directed graph），如微博的关注就是有向的 如果图的每条边没有方向，称为无向图（undirected graph），如微信好友就是无向的

优点：最自然直接的表达方式，易于理解、接受

•节点—链接法的图简化

•在尽量不减少图信息的前提下，用最精简的图结构去表现数据背后的特征规律

•简化方法：基于节点；基于边；其它方法

•边绑定：在保持信息量不变的前提下，将图上互相靠近的边捆绑成一束，达到化繁为简的效果

•能够有效的减少在图绘制中边的混乱程度。能够提供给用户复杂连接图的全局概览，同时通过边的粗细与颜色深度也可以提供给用户图中主要连接关系的信息。

•相邻矩阵法

•N*N的矩阵，代表N个节点，矩阵内的位置(i, j)表达了第i个节点和第j个节点之间的关系

可以用数值矩阵，也可以将数值映射到色彩空间，表达简单易用；

节点之间的直接关系表达显著；

规避边的交叉
缺点：

不易从相邻矩阵中挖掘去隐藏的 信息；节点之间的关系传递表达弱

时空数据可视化

•时空数据是指具有时间元素并随时间变化而变化的空间数据，是描述地球环境中地物要素信息的一种表达方式。

•涉及到各式各样的数据，如地球环境地物要素的数量、形状、纹理、空间分布特征、内在联系及规律等的数字、文本、图形和图像等,不仅具有明显的空间分布特征，而且具有数据量庞大、非线性以及时变等特征。

•时空数据的可视化表达手段可分为静态可视化和动态可视化。

•时空数据静态可视化，一般是以二维地图上叠加可以描述时间变化的要素，来描述时空属性数据与空间范围内的变化特征。这些用于表达时空属性数据的要素可以通过不同的符号、注记、标绘符号、统计图表等多种方式来表达，也可以将多个时间的专题地图同时展示进行对比。

•时空数据动态可视化表达 ：可采用动态地图、三维GIS等多种手段展现时空数据。将时空数据在动态变化的地图或三维场景中呈现出来，可以直观生动地表示各种空间信息的变化过程。

多维数据可视化

散点图（Scatter Plot）是最为常用的多维可视化方法。二维散点图将多个维度中的两个维度属性值集合映射至两条轴，在二维轴确定的平面内通过图形标记的不同视觉元素来反映其他维度属性值。

投影是能够同时展示多维的可视化方法之一。VaR将各维度属性列集合通过投影函数映射到一个方块形图形标记中，并根据维度之间的关联度对各个小方块进行布局。

平行坐标是研究和应用最为广泛的一种多维可视化技术，将维度与坐标轴建立映射，在多个平行轴之间以直线或曲线映射表示多维信息。

可视化工具

信息图表工具

Excel

Google Chart API

Echarts

D3

Visual.ly

Tableau

大数据魔镜是一款优秀的国产数据分析软件，丰富的数据公式和算法可以让用户真正理解探索分析数据，用户只要通过一个直观的拖放界面就可创造交互式的图表和数据挖掘模型。

地图工具

地图工具在数据可视化中较为常见，在展现数据基于空间或地理分布上有很强的表现力，可以直观地展现各分析指标的分布、区域等特征。

当指标数据要表达的主题跟地域有关联时，可以选择以地图作为大背景，从而帮助用户更加直观地了解整体的数据情况，同时也可以根据地理位置快速地定位到某一地区来查看详细数据。

1. Google Fusion Tables

让一般使用者也可以轻松制作出专业的统计地图。该工具可以让数据表呈现为图表、图形和地图，帮助发现一些隐藏在数据背后的模式和趋势。

2. Modest Maps

是一个小型、可扩展、交互式的免费库，提供了一套查看卫星地图的API，只有10KB大小，是目前最小的可用地图库，开源项目，有强大的社区支持，是在网站中整合地图应用的理想选择。

3. Leaflet

Leaflet是一个小型化的地图框架，通过小型化和轻量化来满足移动网页的需要。

时间线工具

时间线是表现数据在时间维度的演变的有效方式，通过互联网技术，依据时间顺序，把一方面或多方面的事件串联起来，形成相对完整的记录体系，再运用图文的形式呈现给用户。

Timetoast Xtimeline Gephi