作者：周中元,王菁
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
大数据挖掘技术与应用试读：
前言
从20世纪80年代中期开始，我一直在做数据分析工作——最初是做数据库管理信息系统的研发工作，接着从事数据建模工作，后来又做数据仓库系统研发，以及数据共享与交换平台构建的工作。从2015年起，我又开始从事行业大数据分析与数据挖掘工作。2017年年底，因为年龄的原因，我不再从事一线的研发工作，转而扮演技术顾问的角色，并应邀开办大数据技术讲座。出乎意料的是，讲座的反响非常热烈，并陆续接到各种讲课的邀请：有科普性质的，也有专业研讨性质的；既有二三十人的课堂讨论式讲座，也有三四百人的礼堂演讲式讲座，还有听众更广泛的中国电子科技集团内部视频会议方式的讲座。一年来，共开办了20多场大数据技术专题讲座，制作的讲课用幻灯片多达600多张。
2018年5月，我的老领导，也是中国电科首席科学家、大数据与人工智能方面的知名专家，看了我的幻灯片后，建议我以此为素材，结合自己多年的工作经验，写一本大数据技术方面的专著。在领导和同事们的鼓励下，从2018年6月份开始，我一头扎进写作中，经过4个月的努力，终于完成了初稿。由于是第一次写书，很多方面没有经验，遇到了很多困难。幸得中国电子科技集团公司第二十八研究所C4ISR技术国防科技重点实验室主任丁峰研究员鼎力相助，他指派王菁博士协助我整理书稿。王菁博士不仅重新绘制了书中的图、表，补充编写了逻辑回归算法，还为每章增加了思考与练习题，并负责书稿出版的所有事务性工作。
目前，国家正在大力倡导和鼓励大数据技术和产业的发展。但一年多来，通过与关心大数据技术的各个层次人员接触，我发现在具体承担技术决策、管理和研发任务的人员中，有些人对大数据技术的实现途径、能力与限定、关键环节的认识不够透彻，这很容易造成技术决策和方向选择出现偏差。因此，在编写本书时，我不仅要通俗易懂地介绍大数据挖掘技术全貌，还要讲解技术细节和技术难点，以免把这本书写成纯粹的科普读物。书中既要有通俗的比喻，也涉及严谨的数学公式推导；所参考的书籍既有经典、严谨的《数据挖掘 概念与技术》和《信息检索导论》，也有通俗易懂的《世界是随机的 大数据时代的概率统计学》和《图解机器学习》。这是一项十分艰巨的任务，希望这种尝试能够为各个层次的读者都带来帮助。
最后还要感谢我的家人对我的理解和支持，他们免除了我所有的家庭杂务，以使我有充足的时间和精力潜心写作。周中元2018年11月于南京第1章大数据概述1.1 从AlphaGo说起
2016年3月9日，发生了一件轰动全球的故事——Google的围棋计算机AlphaGo与李世石之间的世纪大战开始了！最终结果出乎绝大多数人的预料，AlphaGo以4:1的压倒性优势获得胜利。
计算机之所以能战胜人类围棋选手，是因为机器思考的方式与人类的不同，它不是靠逻辑推理，而是靠大数据和智能算法。
在数据方面，Google使用了数十万局围棋高手之间对弈的数据来训练AlphaGo。算法方面有两个关键技术，一个是将棋盘上的状态变成一个获胜概率模型，另一个是启发式搜索算法（保证搜索限制在非常有限的范围内）。
近年来，各种媒体（包括微信这样的自媒体）热衷于报道类似AlphaGo的大数据方面的消息，大数据技术和大数据应用引起了大众的普遍关注。由于政府的积极倡导、实力公司的大量投入和大众的热捧，针对大数据应用的投资大幅度增加。大量资金的涌入，使得大数据专业队伍迅速扩大，业已形成全世界范围的、形形色色的大数据技术生态圈。圈中的人们乐此不疲地分享着自己的最新技术创造和发明，已经越来越忽视先前奉为圭臬的技术专利保护。在互联网上经常可以看到一些非常精巧的设计被公布出来，原创者只要求使用者注明出处便分文不取，有时甚至只需点赞即可。在这样宽松的环境中，各种各样的大数据新技术自然如雨后春笋般地层出不穷，于是幸福的烦恼不期而至——初涉者感到无所适从。本书尝试对时下常见的大数据技术和产品工具进行较为全面的梳理和点评，希望能够为工程管理者、大数据技术初涉者提供帮助。1.2 大数据定义
大数据技术是伴随着近20年信息技术的高速发展而出现的。究其原因，其一是互联网、物联网和传感器技术的飞速发展，正在以前所未有的速度源源不断地产生着海量数据，原有的各种信息系统的稳定发展所累积的数据也起到了推波助澜的作用；其二是互联网和移动业务系统催生了如海量信息联机检索等新型应用，这需要有别于传统技术的支持；其三是信息技术的发展使其能够对海量数据进行联机分析，对纷乱的历史数据进行脱机分析处理，以发现其中蕴含的价值。
如今，大数据技术的发展已势不可挡。那么，到底什么是大数据呢？与大多数新兴技术类似，在其发展初期，尚无一个权威的“大数据”定义。由此可见，大数据技术还在不断发展和成熟的过程中，各方尚未达成一致的观点。全球闻名的维基百科对大数据的定义是，所涉及的数据量规模巨大到无法通过惯用的人工和技术，在合理的时间内完成截取、管理、处理，并整理成为人类能够解读的信息。这样的解释忽视了大数据中一个极为重要的因素——大数据技术。
鉴于此，本书给出大数据的一个描述性定义。大数据是指一个海量、异构、快速增长中的数据集，已经难以用原有的技术去存储和处理这些数据，必须研发新的技术来应对这样的应用场景，这些新的技术就是大数据技术。因此，大数据通常是“大数据集+大数据技术”。
大数据技术描述了一种新的技术和构架，用集群、并行处理的方式存储、处理大规模数据，借助批处理、流式处理、图处理等多种数据处理模型，从大规模的数据中提取价值。
另外，经常有人无法厘清云计算、大数据、人工智能之间的关系。简单地说，物联网和互联网产生大量的数据，这些数据需要存储和处理，这就需要有云计算了。云计算的作用就是对海量数据进行集中存储和处理。海量数据上传到云计算平台后，需要对其进行分析和挖掘，这就是大数据研究的内容。大数据是基于海量数据进行分析从而发现一些隐藏的规律、现象、原理等。而人工智能是建立在大数据基础上的，人工智能不仅要分析数据，还要根据分析的结果做出行动，如无人驾驶、自动医学诊断等。云计算、大数据、人工智能之间的关系如图1-1所示。图1-1 云计算、大数据、人工智能之间的关系1.3 大数据产生的原因
从字面上看，大数据就是数量巨大的数据，或者称为海量数据。实际上，大数据是一个较为抽象的概念，数量巨大只是其中的一个表面的特性。大数据是网络信息时代的客观存在，其产生的意义并不在于掌握庞大的数据量，而在于对这些数据进行专业存储和处理，并从中挖掘和提取所需要的知识和信息。技术突破来源于实际的产品需求，如果将大数据比作一种产业，那么降低存储成本，提升运行速度和计算速度，以及对数据进行多维度的分析加工，实现并提升数据的价值，这是大数据这种产业实现盈利的关键，也是大数据产生的真正原因。
1. 存储成本的大幅下降
以往存储数据的成本非常高，许多大型的互联网公司各自为政，为了保证数据的存储安全性和传输通畅性，需要进行定期维护和数据清理，机房部署和人力成本昂贵。新型的数据存储服务出现后，衍生了很多新的商业模式，集中建设数据中心，大大降低了单位计算和存储的成本。现在建造网站已经不需要购买服务器，也不需要聘用管理人员，通过大数据云计算的商业模式即可获得资源，而存储成本的下降，也改变了人们对数据的看法，更愿意将久远的历史数据保存下来。有了这些数据的沉淀，人们才会想着如何加以利用，通过时间对比，发现其价值与关联。
2. 运行、计算速度的提升
20世纪90年代，传输一个20MB的文件需要花费约一天的时间，如今仅需数秒即可完成传输。分布式系统框架Hadoop、Spark、Storm，并行运行机制HDFS、MapReduce，为海量数据提供了计算的便利性，大大提升了对原始数据进行清洗、挖掘、分析的运行效率，使得数据的价值得到进一步提升。
3. 脑力劳动的解放
今天我们看到的AlphaGo的获胜，以及Siri、微软小冰等智能对话，其背后都有大数据的支撑。也就是说，大数据让计算机变得更加智慧，大数据为计算机灌输了人类的思想，大数据带来了智慧的价值，从而有效解放了人类的脑力劳动。1.4 大数据发展历程
至今，人类社会经历过两次“数据爆炸”。东汉元兴元年（公元105年）宦官蔡伦改进造纸术，以及北宋庆历时期（1041—1048年）民间艺人毕昇发明活字印刷术，使得图书进入了普通百姓家，从而引发了第一次“数据爆炸”，其在世界文明发展进程中所起的作用不可估量。今天，大数据技术引发了更大规模的第二次“数据爆炸”，它正在悄然影响和改变着社会的方方面面。
20多年的大数据发展可以划分成如下3个阶段。
1. 萌芽阶段
20世纪90年代，随着数据挖掘理论和数据库技术的逐步成熟，一批商业智能工具和知识管理技术开始应用，如数据仓库、专家系统、知识管理系统等。这个阶段的数据基本上是系统营运数据。
2. 成熟阶段
21世纪的最初10年，Web2.0应用迅猛发展，非结构化数据大量产生，传统处理方法难以应对，从而带动了大数据技术的快速发展，Hadoop平台开始大行其道。这个阶段的数据基本上是用户输入数据。
3. 大规模应用阶段
2010年至今，大数据应用渗透到各行各业，数据驱动决策，信息社会智能化程度大幅度提高。这个阶段的数据增加了大量的传感器数据。
目前，人类社会已进入大数据时代，数据资源已经与物资资源、人力资源平起平坐，成为三大国家战略资源之一。2012年，美国政府发布《大数据研究和发展计划》；2015年，中国国务院发布《促进大数据发展行动纲要》。1.5 大数据的特征
大数据处理与以往的数据处理有很多明显的区别。
从数据收集方式看，传统数据的收集通常带有明确的目的，因此数据的价值高、质量好；在大数据时代，数据收集通常没有明确的任务，待数据收集完成后，再通过数据分析得出结论，即“先有数据，后找其价值”。
从数据本身看，大数据具有以往数据所没有的一些特征。
关于大数据的特征，业内从不同的视角提出了很多特征。2001年，道格·莱尼（Doug Laney）提出了大数据的3V模型，包括数量（Volume）、速度（Velocity）和种类（Variety）。后来，在3V模型的基础上又补充了一些特征，其中得到公认的有价值（Value）和真实性（Veracity），由此形成了大数据的5V模型，如图1-2所示。基于大数据5V模型的大数据特征如图1-3所示。图1-2 大数据的5V模型图1-3 基于大数据5V模型的大数据特征
大数据量是指超大的数据量，如此巨大的数据量已经超出了传统数据处理的能力，由此引发各种大数据处理技术；高速度是指数据产生速度如此之快，以致传统人工参与处理的方式已不适用；多样化是指数据种类繁多，使擅长处理结构化数据的关系型数据库显得力不从心；价值密度低是指从大数据中发掘其中的价值如同沙里淘金，弥足珍贵；数据质量差是指大数据的质量通常比想象的要糟糕很多，必须进行大量的数据预处理。
除大数据量这个特征外，大数据并不一定同时具备其他特征。在采用新的数据处理方法后，可以发现大数据中深藏的规律、知识或价值，但这需要数据量积累到足够大时才能实现。1.6 数据的度量
大数据最根本的特征是超大的数据量。那么，多大的量才能称为大数据呢？这就要涉及数据度量的问题。
数据度量的基本单位是字节（byte，B）。通常，1B有8位（bit），一个英文字母占1B，一个汉字占2B。常用数据度量单位是KB、MB、GB、TB、PB、EB、ZB等，每一级相差1K（1K=1024）。大数据的50数据量通常是指PB及以上级别的数据量，即2B以上的数据量。
同任何度量一样，当数值大到一定程度时，人们很难直观判断其大小，往往需要借助某些已知的事物作为参照物。例如，存储一部《红楼梦》约需1.7MB，存储一部高清晰度的电影约需1GB，那么1PB存储容量就可以存储约100万部高清晰度的电影。
2017年，IDC在其发布的Data Age 2025中预测，到2025年，全球大数据总量将达到163ZB，且呈现如下特征：全球数据总量的近20%将成为影响日常生活的关键数据；全球每天每个人与联网设备互动的次数约为4800次；全球数据分析总量将增至5.2ZB；超过25%的数据将成为实时数据，物联网实时数据将占其中的95%；生产力推动型和嵌入式数据、非娱乐性图片和视频将成为推动数据量增长的新动力。1.7 大数据思维
近几年，智能手机正在悄然改变着人们的生活习惯，购物、理财、社交、娱乐、健身、学习、查阅，智能手机似乎无所不能。有些人甚至可以连续数日宅在家里独自与手机为伴，似乎一机在手，别无他求。这些巨大且深刻的变化如润物细无声般改变着人类社会，也因此带来了一些观念上的改变。
事实上，大数据时代确实给数据处理理念带来巨大冲击，主要表现在如下三个方面。
1. 要全体不要抽样
以往因为数据采集能力不足，通信流量受限，数据存储和处理能力低下，进行大数据分析时通常只能采用抽样分析的方法，因此很难全面、准确地反映全体数据的特征。如今，数字通信技术和计算机技术的飞速发展，使得数据处理能力发生翻天覆地的变化，已经有能力处理全体数据了。
2. 要效率不要绝对精确
小量的样本数据因为需要代表全体成员，所以样本数据的细微误差可能演变成不可容忍的错误。相比之下，海量数据比采样数据更有能力容纳不精确的数据。事实上，来自现实世界的各种数据本身不可能是完美无缺的，大量数据中一定包含一些错误的数据。在大数据处理中，很多问题的答案并不是只有一个，但要求能够及时给出答案。例如，利用互联网搜索引擎查询资料，用户希望能够快速查到想要的结果，查到的结果往往有多个，用户并不在乎这些结果多么精确，因为用户自己有鉴别能力。
3. 要相关不要因果
以往我们的学习研究要求是“知其然且知其所以然”。这样究其根源的学问态度使得学习成果更加牢固，研究成果更加深刻。但是，在大数据时代，因为数据源源不断地产生，很多情况下及时处理数据已经应接不暇，深究数据之间的因果关系实在是难以完成的任务。事实上，在数据之间的相关关系中蕴含了很多非常有价值的东西，有些甚至是我们从来没有意识到的。这方面的例子在如今的电商个性化推荐系统中可以说是屡见不鲜的。了解相关关系比深究因果关系简单得多，而找出数据之间的相关关系正是大数据处理的强项。在大数据时代，我们可以改变认识世界的方式，让数据说话，更多地通过数据之间的相关关系（而不是因果关系）了解世界。而且在很多场景中，了解相关关系就足够了。例如，旅行者往往知道什么时候订机票可以拿到好的折扣，他不一定知道航空公司的机票销售策略，但这没有关系。
中国古代的很多谚语就是这种只知相关不知因果的思维方式所形成的。古时人们通过大量、长期观测和观察，总结出了很多相关的规律，但他们并不知道其中的原理，如气象谚语“早霞不出门，晚霞行千里”，哲理谚语“放虎归山，必有后患”等。当然也有一些谚语因为当年的样本不够，总结出来就成了歪理，甚至是迷信，如“左眼跳灾，右眼跳财”。1.8 科学研究范式的发展
若上升到科学研究探索规律的方式，可以说大数据技术引发了一种全新的科学研究范式。
数千年来，人类对科学研究形成了4种研究范式。
1. 经验范式
人类早期的科学研究多以观测和实验记录为基础，从记录中发现科学规律，这称为经验范式或实验范式，即第一科学研究范式。经验范式的杰出代表人物是欧几里得、托勒密等，他们是通过观察获得数学模型的雏形，然后利用数据来细化模型，这当然需要长期积累数据记录和研究经验。经验范式实际上是归纳总结的思维方式。
2. 理论范式
由于受到实验条件限制，经验范式难以完成对所有自然现象的精确理解。因此，科学家尝试尽量简化实验模型，去掉一些复杂的干扰因素，只留下关键因素，然后通过演算进行归纳总结，这就是理论范式，即第二科学研究范式。理论范式的杰出代表人物是笛卡儿、牛顿等，他们采用大胆假设、小心求证的方法，用较为系统的数学、物理等科学原理而不再是经验来认识世界，因此凡事都要掌握其因果关系，其研究结果往往是非常完美的公式。理论范式实际上融入了演绎推理的思维方式。
3. 计算范式
在发明了第一台电子计算机ENIAC后，人类社会进入了电子计算时代。科学家们发现，利用计算机可以对复杂现象进行模拟仿真，从而推演出越来越多复杂的现象，如模拟核试验、天气预报等。随着计算机仿真越来越多地取代实验，逐渐成为科研的常规方法，这称为计算范式，即第三科学研究范式。计算范式具有“大众共同创造历史”的特点，不再只靠科学巨星引领整个世界的发展。在信息时代，人们发现，并非所有规律都可以用简单的原理来描述，而且要找到其因果关系是非常困难的。另外，随着人们对世界的认识越来越清晰，发现世界本身存在很大的不确定性。不确定性使得以往的思维方式不再适用，于是对难以用公式或规律表示的不确定性改用概率模型来表示。
4. 数据密集范式
近年来，随着互联网、物联网的高速发展，数据量出现了爆炸性增长。如今人们发现，计算机不仅能进行模拟仿真，还能对巨量的数据进行分析总结，从而得到以往无法发现的科学规律，这称为数据密集范式，即第四科学研究范式。数据密集范式的核心是大数据思维，就是从大量数据中直接找到答案，即使不知道原因，我们也愿意接受这个答案。
计算范式与数据密集范式的区别：在计算范式中，数据是配角，人们先提出理论，再收集数据，然后通过计算来验证；在数据密集范式中，数据是主角，人们先收集大量数据，然后通过计算得出之前未知的结论。1.9 大数据的影响及应用
现今，大数据技术的应用领域越来越多，如人们熟知的电子商务和智能交通，政府热衷的电子政务和智慧城市，科学研究领域的生物医学，安防领域的智能识别和舆情监测，普通大众喜爱的体育和娱乐业，以及商务领域的金融、汽车、餐饮、电信、能源、物流等。
例如，在生物医学领域，大数据可以帮助人们实现流行病预测、智慧医疗、健康管理，还可以帮助人们解读DNA，了解更多的生命奥秘；在市场营销方面，人们利用大数据技术对海量数据进行分析和挖掘，实现对用户精准化、个性化的营销；在政府工作中，人们获取、组织、分析和决策大数据，利用大数据技术提供建模、规划、预测和研判，帮助政府进行决策；在军事应用方面，参谋指挥员可以对相关的海量信息进行整合，从而获取有用情报等。
在国外，较为著名的公司均已开展大数据应用方面的相关研究，较为典型的应用领域包括在线搜索、社交网络、电子商务、医疗、交通等。同时，各大互联网公司及IT解决方案提供商也纷纷利用已有的海量历史数据开展相关的应用研究工作。具有代表性的专业领域应用包括，Google公司基于大数据技术优化文本/语音/视频/图像的在线搜索方法，实现了书写纠错、机器翻译、基于社会热点理解的趋势图应用、客户情绪分析、交易风险等大数据应用；百度利用大数据技术改进了多媒体搜索及智能搜索方法，并实现了品牌的商业推广、互联网舆情分析等大数据应用；Facebook、Amazon、阿里巴巴、京东基于大数据技术实现了面向用户的个性化推荐、产品的设计优化、物流配送等。
综上所述，大数据技术起源于商业、互联网和金融，广泛发展并应用于社会管理、智慧城市、智能交通、疾病预防、国防军事等领域，并已渗透到社会的各行各业中，正在改变着人类的生活方式。它就像一股浪潮汹涌澎湃而来，掀起了新时代的狂潮。我们唯有顺应时代发展的潮流，才能在激烈的技术变革中争取主动。1.10 大数据计算模式及产品
大数据计算模式是指依据大数据的不同数据特征和计算特征，从多样性的计算问题和需求中提炼、归纳出各种抽象概念、方法与模型。在现实世界中，大数据处理的问题复杂多样，难以通过一种单一的计算模式涵盖一切不同的应用需求，而不同计算模式的发展与呈现，给予了大数据技术和应用的强大驱动力。近年来，学术界和业界研究并推出了多种不同的大数据计算模式。
1. 批处理计算模式
批处理计算模式是通过并行计算方式实现针对大规模数据的批量计算的，其典型产品有MapReduce、Spark等，这些产品均提供庞大且设计精良的并行计算软件框架，可以自动完成计算任务的并行化处理，以及计算数据和任务的自动划分，从而大大减轻了软件开发人员的负担。
2. 流式计算模式
流式计算模式是针对流数据的高实时性计算模式。在一些应用中，数据价值随时间的流逝而降低，因此最好在事件出现时便立即对其进行处理，而不是缓存起来进行批处理。2011年，Storm系统带着“流式计算”的标签华丽登场，它依靠其分布式、简单运维、高度容错、无数据丢失等特点，成为业界的大数据明星，弥补了Hadoop延迟大、响应缓慢、运维复杂的缺点。随后，S4、Streams、Puma、Flume、SuperMario等流数据实时计算模式相继诞生，成为了瞬间建模或计算处理的典型产品。
3. 图计算模式
图计算模式是以图论为基础，用图结构表述现实世界，基于大规模图结构的计算模式。大数据运算中的许多应用核心是关联性计算，图计算模式能够良好地表达数据之间的这种关联性。现在已经出现了许多图计算平台和引擎，如专注于图结构化存储分析的图数据库Neo4j、InfiniteGraph等，Google推出的新计算框架Pregel，CMU发布的开源版本GraphLab，以及Spark的支持图计算的GraphX模块。另外，Giraph、PowerGraph、Hama等产品均可以实现复杂的图数据挖掘。
4. 查询分析计算模式
查询分析计算模式是为了解决对大规模数据的关联与查询分析问题而产生的。传统的数据查询分析以结构化数据为主，因此关系型的数据库系统可以一统天下。但是，大数据时代往往是半结构化和非结构化数据为主，结构化数据为辅，且大数据应用通常是对不同类型的数据进行内容检索、交叉对比、深度挖掘和综合分析。面对多种多样的应用需求，多家公司相继开发了分布式查询计算模式产品，代表产品包括Dremel、Hive、Cassandra、Impala等。
综上所述，依据大数据处理的多样性需求，学术界和业界推出了多种典型和重要的计算模式，也研发了对应的计算系统和工具，读者可以通过后续的深入学习，在大数据应用实践中选择适宜的计算模式和系统工具，完成自己的大数据应用工作。思考与练习（1）________是一种高实时性的计算模式。（A）批处理计算（B）流式计算（C）查询分析计算（D）图计算答案：（B）流式计算（2）请简要说明云计算、大数据、人工智能三者之间的关系。答案：简单地说，物联网和互联网产生大量的数据，这些数据需要存储和处理，这就需要云计算。云计算的作用就是将海量数据集中存储和处理。海量数据上传到云计算平台后，需要对数据进行分析和挖掘，这就是大数据研究的内容。大数据是对海量数据进行分析，从而发现一些隐藏的规律、现象、原理等；而人工智能是在大数据的基础上更进一步，人工智能会分析数据，然后根据分析结果做出行动，如无人驾驶、自动医学诊断等。第2章数据收集
数据收集是数据处理的第一个步骤。相比以往，大数据时代的数据收集要求能够收集更多的数据，而且通常要求实现数据的自动收集。
按照数据来源区分，数据收集可以分为来自互联网的外部数据收集和来自企业内部网络的内部数据收集两类。2.1 外部数据收集
互联网上的数据数不胜数，现在网页数量已经超过200亿个，在其中寻找有用的数据有如大海捞针。如今，全世界超过17亿的Web用户使用Google、百度等Web搜索引擎寻找自己想要的信息，所有这一切都要归功于互联网找寻数据的神器——网络爬虫。2.1.1 网络爬虫原理
互联网的发明催生了互联网站，世界上第一个网站http://info.cern.ch/是由英国人蒂姆·伯纳斯-李（Tim Berners-Lee）于1991年8月6日建立的，随后出现的越来越多的网站引发了对网站内容搜索的需求。
网络爬虫是按照一定的规则，自动地抓取互联网信息的一种程序或脚本。早在1990年，加拿大麦基尔大学（McGill University）的三名学生Alan Emtage、Peter Deutsch和Bill Wheelan编写了程序Archie，它利用脚本程序自动搜索网上各个ftp主机中的文件，并对其中的有关信息建立索引，然后使用者就可以采用一定的表达式通过这个索引文件进行查询。
美国Nevada System Computing Services大学于1993年开发了新的搜索工具，增加了对网页的搜索。搜索工具的核心是搜索文件内容的搜索模块。在工作时，它像爬虫或蜘蛛一样在网络间“爬来爬去”，因此称之为网络爬虫或网络蜘蛛。
网络爬虫的工作原理如图2-1所示。网络爬虫工作时，是从初始网页的地址URL开始，找到这些初始网页上用于链接其他网页的URL列表，将其存入待“爬”的地址簿，然后对地址簿中的每个地址根据策略（深度、宽度、最佳）逐个搜索，从互联网上下载、保存网页，分析并获取网页中符合条件的新的URL链接。对于新获得的URL，将其存入待“爬”的地址簿；对于已经处理完毕的网页，将其内容存入数据库作为镜像缓存，而其URL地址则存入已搜索的集合，以避免重复搜索。这样的过程不断重复，直到满足停止搜索的条件为止。图2-1 网络爬虫的工作原理2.1.2 搜索排序策略
地址簿中的地址通常会有许多个，如何确定地址搜索的先后次序就是网页的获取策略问题。不同的策略会对搜索效果产生很大的影响。常用的获取策略有深度优先策略、宽度优先策略、最佳优先策略等。
如果把初始网页看作树根，逐层链接的网页看作各层树节点，链接关系看作树枝，那么地址簿就像是一棵倒置的树。
1. 深度优先策略
深度优先策略使用的是堆栈技术，其具体步骤如下所述。（1）将初始网页节点地址压入栈中；（2）从栈中依次弹出一个节点地址，搜索其下一级的所有节点；（3）将第（2）步中新发现的节点压入栈中；（4）重复第（2）步和第（3）步，直到没有发现新的网页节点为止。
图2-2所示的是深度优先策略的范例。图中虚线箭头表示网络爬虫爬行的顺序，并附以数字标示。对于同一个主题，门户网站提供的链接往往最具价值，随着每一层的深入，网页的价值会相应地下降，过度深入抓取网页获取的价值不大。因此，深度优先策略容易“钻牛角尖”。图2-2 深度优先策略的范例
2. 宽度优先策略
宽度优先策略使用队列技术来实现，其具体步骤如下所述。（1）将初始网页节点地址存入队列中；（2）每次从队列首位取出一个节点地址，搜索其下一级的所有节点；（3）将第（2）步中新发现的节点存入队列末尾；（4）重复第（2）步和第（3）步，直到没有发现新的网页节点为止。
图2-3所示的是宽度优先策略的范例。宽度优先策略可以尽可能覆盖范围更广的网页，一般而言较深度优先策略更合理些。但若希望聚焦某些价值更大的网站，宽度优先策略可能会出现偏离主题的情况。宽度优先策略犹如读一本文摘，主题游散，通常只适合消遣。图2-3 宽度优先策略的范例
不管是深度优先策略还是宽度优先策略，它们都只与位置相关，与网页内容的优劣无关，因此其搜索效果很难令人满意。现在大多数搜索引擎采用最佳优先策略来提高爬虫的效率。
3. 最佳优先策略
所谓最佳优先策略，就是按照网页分析算法，对所有候选地址URL中存放的信息进行相关性分析，预测候选URL与主题的相关性，然后根据相关性高低次序进行抓取。它只访问经过网页分析算法预测“有用”的网页。
相关度预测分析属于信息检索的相关性分析专题，简而言之就是通过一定的算法模型，预测两个数据对象之间的相似程度。数据对象主要是指文本，常见的算法模型有布尔模型、向量空间模型、概率模型和语言模型等。相关内容将在第6章中详细介绍。2.1.3 Web网络图
若将网络爬虫在网上爬行的轨迹记录下来，得到的就是一张Web网络图。Web网络图是一张有向图，在这张图中，将网页看作图中的一个节点，网页间的每个链接看作图中的一个有向边。Web图非常有用，可用于链接分析。
图2-4所示的是由图2-3所示范例得到的Web网络图。图2-4 由图2-3所示范例得到的Web网络图
有了Web网络图，就可以对图中的每个链接的价值进行评价分析，这就是链接分析，然后按照分析结果优先搜索价值高的网页，从而改善搜索结果页面的排序。最著名的链接分析算法是PageRank和HITS。
图2-5所示的是50个网页的Web网络图范例。图2-5 50个网页的Web网络图范例
通常，被更多节点链接的节点是更重要的节点。例如，图2-5中的节点9比节点38更重要，因为前者有9个节点与其链接，后者只有2个节点与其链接。
另外，对于同一个链接，不同节点的价值也不一样。例如，图2-5中的节点16有4个链入，节点7只有3个链入，但节点7被节点9和节点2链入，因这两个链入节点分别有9个和7个链入，节点9和节点2均属于重要节点，所以节点7比节点16更重要。2.1.4 构建爬虫系统
了解爬虫的基本工作原理后，就可以动手开发用于收集互联网数据的爬虫系统了。这似乎不是一件简单的事。幸运的是，在开源生态圈方兴未艾的今天，人们可以借助开源系统容易且快速地构建自己的爬虫系统，Apache Nutch和Heritrix就是两个可以完全满足此类需求的开源系统。
这里的Apache指的是Apache软件基金会（Apache Software Foundation，ASF，http://www.apache.org/foundation/）。ASF创建于1999年7月，它是专门为支持开源软件项目而办的非营利组织。时至今日，ASF旗下的开源项目众多，应用范围广泛，影响很大。Apache这个名字源自北美的一个印第安部落的名称，这个部落以高超的军事素养和超人的忍耐力著称，在19世纪后半期对侵占他们领土的入侵者进行了反抗。
Apache是当今世界上最大的开源基金会，共收录了350多个开源项目（包括鼎鼎大名的Apache HTTP Server），现有730名个人会员，7000位Apache代码提交者，52个正在Apache孵化器中孵化的项目。
Nutch（http://nutch.apache.org/）是一个开源的、基于Java语言的搜索引擎，诞生于2002年8月。Nutch支持多种主流底层存储技术，包括Apache的Hadoop、HBase和Solr等。有趣的是，Hadoop居然是Nutch的衍生产品（在3.1节中将介绍这一情况）。
Nutch不仅是一个爬虫系统，它还包含全文检索和搜索，主要由爬虫（Crawler）、索引器（Indexer）、查询器（Searcher）三个部分组成。爬虫主要用于从网络上抓取网页，并为这些网页建立索引。查询器主要利用这些索引，根据用户的查找关键词检索出查找结果。
爬虫主要关心的是数据文件。数据文件主要分三类，即网络数据库（Web Database）、分段（Segment）、索引（Index）。这三类数据文件存储在爬行结果目录下的db目录中，分别以WebDB、segments和index作为子目录名。
WebDB文件夹中存储的是网页实体和链接实体。网页实体是关于实际网页的特征信息，包括网页内的链接数量、本网页重要度评分、抓取此网页的时间等。链接实体描述的是两个网页实体之间的链接关系。Web网络图就存放在此！
爬虫在一次抓取循环中抓取的网页存储在一个分段（Segment）文件夹中，分段文件夹是以产生的时间来命名的，以便删除过期的文件。
索引器为所有抓取的网页创建索引。Nutch利用Lucene技术进行索引。Lucene也是Apache的一个开源全文检索引擎程序库。
Heritrix也是一个开源的、基于Java语言的网络爬虫，可以在SourceForge开源站点（http://sourceforge.net/projects/archive-crawler/）下载Heritrix。Heritrix创建于2003年年初，最初用于网上资源的集中管理，建立网络数字图书馆。Heritrix的工作原理与Nutch的大致相同，不同之处如下所述。（1）Nutch集成了Lucene，非常便于对抓取内容进行索引和检索，而Heritrix则需要用户自己负责文件的格式转换、索引和检索。但Heritrix的功能强大，可以专注于网络信息的下载。（2）Nutch只获取并保存可索引的内容，且可以对下载的内容进行过滤、修改；而Heritrix适用于各种类型的信息，并力求保持网页原貌。另外，Nutch用新内容替换旧内容，Heritrix则是不断添加内容。（3）Nutch采用命令行运行和控制，而Heritrix有Web控制管理界面。Nutch的定制能力一般，而Heritrix的参数较多。
其实，在互联网飞速发展的今天，网上页面数量高达数百亿，其中约30%的页面是重复的，页面间指向相同Web信息的URL数量巨大，并有动态页面的存在。因此，网络爬虫在给定时间内只能下载少量的网页，即使能够提取全部页面，也没有足够的空间来存储页面信息。2.2 内部数据收集
互联网上数据包罗万象，通过互联网可以极大地拓宽人们的视野，以便迅速且多方位地了解外面的世界。然而对于一个企业而言，其日常的生产管理活动产生的大量数据对其应该是更具价值的。收集这些内部数据应该比收集外部数据更加重要，否则就有舍本逐末之嫌。
企业中最有价值的数据主要有客户数据、财务数据、生产数据等。内部数据收集方法与外部数据收集方法有很大的不同。如果将互联网数据比喻成大海里的鱼，那么企业数据就像是鱼塘中的鱼，显然两者的捕鱼方式也会不同。事实上，企业对其内部数据的存储方式和位置应该是掌握的，所以内部数据获取工作不需要由网络爬虫来承担，完全可以自己设计相应的程序。而且，由于企业对哪些内部数据更有价值也应该是一清二楚的，所以不需要在链接分析和获取策略上下很大功夫。但是，这并不是说内部数据收集工作就非常简单了，内部数据反映的是企业的运营状况，价值较高，管理者希望随时掌握这些数据，所以内部数据收集更加强调实时性，以便实现快速响应。
随着信息化手段的普及，企业内部产生的数据量也是不小的，而且还在不断增长着，因此同样存在数据收集的实时性与系统开销大这对矛盾。为此，内部数据收集方式分为推送（Push）和拉取（Pull）两种。推送是指一旦有新的数据产生就立即主动送出，因此具有更高的实时性，但数据传输和处理的工作量较大。拉取则是根据需要读取数据，因此更顾及系统开销，但对数据变化而言会有延迟。
图2-6所示的是数据推送方式示意图，图2-7所示的是数据拉取方式示意图。图2-6 数据推送方式示意图图2-7 数据拉取方式示意图2.2.1 Flume
与构建外部数据收集系统一样，现在也没有必要自己从头开始设计内部数据收集系统了。
可提供帮助的开源系统是Apache Flume（http://flume.apache.org/）。这是一个分布式的海量数据收集系统，同时具备推送和拉取两种数据收集方式，还可以支持发送方定制数据，并可以对数据进行简单处理。Flume最早属于Cloudera公司，2011年被纳入Apache社区。Flume的核心模块有三个，即源头、通道和沉淀器。（1）源头（Source）：负责接收数据，从数据源头接收数据，并将其传递给通道。（2）通道（Channel）：作为一个管道或队列，连接源头和沉淀器。（3）沉淀器（Sink）：从通道批量读取数据，并将其存储到指定的位置。
图2-8所示的是Flume的基本工作原理图。图2-8 Flume的基本工作原理图2.2.2 Chukwa
Chukwa是另一个开源的内部数据收集系统。Chukwa最初是Hadoop的日志处理系统，现在已经发展成为一个开源的数据收集系统，它非常适合云环境下的商业应用。
作为Hadoop软件家族中的一员，Chukwa依赖于Hadoop的其他子项目。例如，通过HDFS存储数据，依赖MapReduce处理数据，以Pig作为高层的数据处理语言等。Chukwa还包含一个功能强大、设置灵活的工具集，可以用来展示、监控和分析已收集的数据。在印度神话中，Chukwa是一只最古老的龟，在它的背上驮着一个名为Maha-Pudma的大象，在大象的背上驮着地球。图2-9所示的Chukwa的Logo，就是按照这个寓意设计的。图2-9 Chukwa的Logo此外，Facebook Scribe和Logstash这两个开源系统也可以用于构建推送模式的内部数据收集系统。Facebook Scribe可以在http://github.com/facebookarchive/scribe上下载，Logstash的下载地址是http://www.elastic.co/products/logstash。思考与练习（1）对所有候选地址URL进行相关性分析时，根据相关性高低选择爬虫抓取次序的是哪种策略？（A）深度优先策略；（B）宽度优先策略；（C）最佳优先策略；答案：（C）（2）请简要描述主要的内部数据收集方式及其优缺点。答案：内部数据收集方式主要分为推送（Push）和拉取（Pull）两种。推送是指一旦有新的数据产生就立即主动送出，因此具有更高的实时性，但数据传输和处理的工作量较大。拉取则是根据需要读取数据，因此更顾及系统开销，但对数据变化而言会有延迟。第3章数据存储
数据收集后，就应该考虑如何存储数据了。面对大数据的超大容量和快速增长的态势，如何存储是一个大问题。
以前常采用购买专用存储设备的方法来解决数据的存储问题。随着数据量的激增，传统的存储方式会造成扩展存储容量的费用大幅上涨，也存在难以承受的数据并发访问的压力。在大数据时代，集中式存储已经被分布式存储所替代，也就是采用集群化方案，在集群系统中的多台计算机的磁盘上分布式存储数据。
在集群系统中，数据的存储方式分为文件存储和数据库存储两种。（1）文件存储就是将大数据按文件形式分布式存储在集群系统中供用户访问。采用这种方式的鼻祖是Google公司的分布式文件管理系统GFS，本书主要介绍GFS的开源实现——分布式文件系统（Hadoop Distributed File System，HDFS）。（2）数据库存储是用数据库的形式将数据分布式存储在集群系统中。由于大数据时代的数据库需要存储多种类型的数据，也因应用已经从原来的事务处理扩展到Web2.0等多样的应用，所以数据库形式已经突破了经典的关系型数据库，发展出列族数据库、文档数据库、键值数据库、图数据库等新型数据库。这些数据库统称NoSQL数据库。3.1 文件存储
如前所述，在大数据时代，必须用集群化的方案来存储数据。因此，与传统的集中式文件系统相比，大数据时代的数据文件存储加入了分布式存储管理，就技术实现而言要复杂很多。
如何将巨量的数据库分散存储在计算机集群系统中？如何保证这些分散存储的数据在需要时又能自然地聚拢如初以供用户访问？如何高效率地读取这些分布式存储的数据？如何保证所有分散存储数据的安全可靠？这些都是分布式文件存储系统必须解决的问题。3.1.1 Hadoop简介
在介绍HDFS前，有必要先介绍一下Hadoop。
Hadoop起源于Nutch，它以HDFS和MapReduce为核心，HDFS为海量数据提供存储功能，而MapReduce则为海量数据提供计算功能。利用Hadoop系统可以轻松地架构分布式存储系统，开发大规模的数据处理应用。
Hadoop的创始人和第一功臣是道格·卡廷（Doug Cutting）。1997年年底，卡廷用Java开发了一款搜索产品，这就是后来名噪一时的Lucene。作为第一个提供全文检索的开源函数库，Lucene具有划时代的意义，后来的搜索引擎几乎都是用它来研发的。其实，Lucene是卡廷夫人姓名的中间名字，Nutch源自他的牙牙学语的儿子将吃饭发成“Nutch”音，而Hadoop则是他的儿子给一头吃饱了的棕黄色大象起的名字。
Lucene只是一个函数库，并不是一个独立的搜索引擎。卡廷后来打算以Lucene为基础，打造一个完整的Web搜索引擎，这就是Nutch。
Nutch需要处理数十亿的网页，但如何存储从网页中获取的海量数据呢？正在他一筹莫展时，Google发表的研究成果给卡廷带来了福音。
2003年，Google发表了一篇论文来描述其分布式文件系统GFS（Google File System）。受此启发，卡廷带领团队开发了Nutch的分布式文件系统HDFS。
解决了海量数据的存储问题后，接下来的问题是如何处理这些海量数据。
2004年，Google在“Operating System Design and Implementation”会议上发布了一项研究报告MapReduce: Simplified Data Processing on Large Clusters，介绍了运行在GFS上的分布式大规模数据运算框架。卡廷又开始带领团队将这个想法变成开源的大数据计算框架。为了更好地支持这个框架，他们将HDFS作为数据存储平台。2006年2月，由于HDFS和MapReduce显得愈加重要，其作用已经远远超过Nutch，所以卡廷将它们从Nutch中独立出来，成为一套完整、独立的软件，起名Hadoop。2008年年初，又将其升格为Apache的顶级项目。
由于Hadoop中HDFS具有很强的数据管理能力，以及MapReduce处理任务时的高效率及其开源特性，使其在同类分布式系统中独占鳌头，并在众多行业中得到广泛应用。现在，Hadoop已经发展成为一个项目集合或生态圈，在其核心HDFS和MapReduce之外扩展出很多子项目，作为其补充或提供更高层的服务。3.1.2 HDFS设计原则
在HDFS设计之初，设计者非常有远见，明确地设定了如下设计原则。（1）存储超大文件：HDFS要能够管理超大容量的文件，典型的文件容量是从GB级别到TB级别。（2）存储多种应用对象：这些大容量文件可以包含很多应用对象，如网页文档、日志记录等。一个文件实际上是由数亿（甚至数十亿）个对象组成的TB级的数据集。（3）离线批处理数据访问：应用场景设定为离线批量数据处理，而不是交互式即时数据访问。（4）容忍硬件故障：为了尽可能降低集群系统的建设成本，允许系统采用廉价的、故障率较高的PC服务器作为集群中的存储和运算节点。（5）数据读/写操作的限定：HDFS采用“一次写入、多次读取”的数据读/写方式，文件仅支持在尾部追加式写操作，不允许在其他位置对文件进行任何修改，其目的是尽可能简化数据一致性控制机制，从而提高数据操作效率。（6）支持多种硬件平台：HDFS可以运行在不同的平台上，如Linux集群、各种云平台等。（7）就近计算原则：为了减少数据在网络中的传输量，数据计算应尽可能就近进行，通常运算所用的数据就在本节点。这种设计可以明显提高大数据的整体计算效率。3.1.3 HDFS的基本术语
HDFS的基本术语包括数据块、命名节点、数据节点、从命名节点、命名空间、客户端和通信协议。
1. 数据块
文件系统管理数据的最小单位不是字节，而是数据块。在大数据环境下，管理的文件体量大幅度增加，数据块的体量较以往也有大幅度增加，从原来的以KB为计量单位，直接跃升到以MB为计量单位。Hadoop1.×的数据块大小是64MB，Hadoop2.×的数据块大小为128MB。这样的数据块体量明显大于普通文件系统中的数据块体量（如Linux为1KB），增加数据块体量的目的是为了减少寻址开销。即使如此，对于HDFS管理的最小的GB级别文件，一个文件至少也要占数百个数据块。
2. 命名节点和数据节点
在任何一个文件管理系统中，都是将一小部分存储单元用于存储管理信息，而将绝大部分存储单元用于存储数据。在HDFS中，存储管理信息的那部分节点称为命名节点（Name Node），存储数据的那部分节点称为数据节点（Data Node）。
命名节点维护着整个文件系统的文件目录树，包括记录文件树信息和记录对文件树的各种操作信息。这两部分信息分别记录在两个文件中，即镜像文件（FsImage）和日志文件（EditLog）。
如图3-1所示，镜像文件用于维护文件系统的树形结构，以及文件树中所有的文件和文件夹的元数据；而日志文件记录了对文件所有的新建、删除、重命名等操作。图3-1 命名节点结构示意图
数据节点是HDFS的工作节点，负责数据的存储和读取，可以根据客户端或命名节点的调度来进行数据的存储和检索，并且向命名节点定期发送自己所存储的块的列表。
3. 从命名节点
由于文件很大，导致镜像文件开始时就很大（通常达GB级别以上），而日志文件则随着运行时不断记录所发生的文件操作而持续变大。HDFS的所有更新操作均写入日志文件，而不直接写入镜像文件，因此不能让日志文件太大，否则会影响效率，这是引入从命名节点的原因之一。
怎么防止日志文件过大呢？来看图3-2所示的从命名节点的工作过程。
从命名节点（Secondary Name Node）有两个主要作用，一是定时清空命名节点上的日志文件（可以将其理解成命名节点的日志文件后期处理的转运站），二是可以作为命名节点的延期备份（恢复时会丢失检查点之后的数据）。所谓检查点，实际上就是备份时间点，在这个时刻将数据记录下来，如果系统出现故障，可以从这个时刻恢复数据。图3-2 从命名节点帮助清理日志文件过程示意图
4. 命名空间
HDFS的命名空间包括目录、文件和块。命名空间管理是指对目录、文件和块进行类似文件系统的新建、修改、删除等基本操作。因此，命名空间所管理的资源是有限的。
5. 客户端
客户端可以有3种呈现形式：可以通过命令行工具访问HDFS的数据；也可以用应用程序的方式进行访问，此时HDFS提供了一套Java API，方便编程实现对文件的各种操作；还可以通过Web界面来查看整个文件系统的情况，包括集群概况，命名节点、数据节点的信息、快照、运行进程，浏览文件系统等，方法是登录http://［NameNodeIP］:50070。图3-3所示的是通过Web登录查看HDFS的界面示例。图3-3 通过Web登录查看HDFS的界面示例
6. 通信协议
HDFS部署在集群上，它们之间的通信协议是构建在TCP/IP协议基础之上的。客户端通过一个可配置的端口向命名节点主动发起TCP链接，并使用客户端协议与命名节点进行交互；命名节点与数据节点之间则使用数据节点协议进行交互；客户端与数据节点的交互是通过远程过程调用（Remote Procedure Call，RPC）来实现的。命名节点不会主动发起RPC，而是响应来自客户端和数据节点的RPC请求。图3-4所示的是客户端、命名节点、数据节点之间交互示意图。图3-4 客户端、命名节点、数据节点之间交互示意图3.1.4 HDFS运行架构
HDFS的运行架构示意图如图3-5所示。图3-5 HDFS运行架构示意图
用户在使用HDFS时，可以通过文件名访问文件。而在系统内部，一个文件会被分成若干个数据块（分布存储在若干个数据节点上），在数据访问过程中，命名节点不参与数据的传输。
HDFS采用主从结构模型，一个HDFS集群包括一个主节点（命名节点）和若干个从节点（数据节点）。
命名节点作为集群的管理服务器，负责管理文件系统的命名空间、客户端对文件的访问。
数据节点负责处理文件系统客户端的读/写请求，在命名节点的统一调度下进行数据块的新建、删除和复制等操作。每个数据节点会周期性地向命名节点发送“心跳”信息，报告自己的状态。对于没有及时发送心跳信息的数据节点，命名节点将其标注为“宕机”。
为了改善命名节点的性能，提高可靠性，HDFS还设置了从命名节点。
试读结束[说明：试读内容隐藏了图片]