系统介绍大数据算法设计与分析技术的教材,内容丰富,结构合理,旨在讲述和解决大数据处理和应用中相关算法设计与分析的理论和方法,切实培养读者设计、分析与应用算法解决大数据问题的能力
本书是国内系统介绍大数据算法设计与分析技术的教材,内容丰富,结构合理,旨在讲述和解决大数据处理和应用中相关算法设计与分析的理论和方法,切实培养读者设计、分析与应用算法解决大数据问题的能力。不仅适合计算机科学、软件工程、大数据、物联网等学科的本科生和研究生使用,而且可供其他相近学科的本科生和研究生使用。同时,该教材还可作为从事大数据相关领域工程技术人员的自学读物。
本书特点:
前沿、实用的内容。总结了大数据算法设计与分析的新技术和新理念,梳理了当前大数据相关应用中所需要的算法设计与分析的方法。书中的部分内容代表了学术界全新的前沿技术,首次出现在国内外的教科书上。
清晰、严谨的叙述。针对大数据算法设计与分析中的主要方法,通过介绍原理、举例说明、算法分析等多个角度进行阐述,清晰地讲解算法设计方法,严谨地分析和证明算法的特性,有利于培养读者独立设计与分析大数据算法的能力。
新颖、宽泛的习题。习题部分来自领域内相关文献,部分来自大数据相关开发领域的实际问题,有利于培养读者解决问题的创新思维。
王宏志 哈尔滨工业大学计算机科学与技术学院副教授、博士生导师,加利福尼亚大学尔湾分校访问学者,获得微软学者、中国出色数据库工程师、IBM博士英才等称号。研究方向包括大数据管理、数据质量、图数据管理。发表学术论文140余篇,出版学术专著两本。主持各类项目十余项,包括国家自然科学基金项目3项、国家支撑计划课题1项、国家博士后特别资助项目1项,参加国家973项目、863项目、自然科学基金重点项目等多个项目。担任4个国际期刊的编委,并30余次担任国内外多个知名数据库会议程序委员会委员。2014~2015年任CCF
YOCSEF哈尔滨分论坛主席,CCF高级会员,中国数据库专业委员会委员,中国计算机应用专业委员会委员。在爱课程网、学堂在线、好大学在线上首次开设“大数据算法”在线课程,先后有超过2万余名同学参加了这门课程的学习。
前 言
第1章 绪论1
1.1 大数据概述1
1.1.1 什么是大数据1
1.1.2 无处不在的大数据1
1.1.3 大数据的特点3
1.1.4 大数据的应用4
1.2 大数据算法5
1.2.1 大数据上求解问题的过程6
1.2.2 大数据算法的定义7
1.2.3 大数据的特点与大数据算法9
1.2.4 大数据算法的难度9
1.2.5 大数据算法的应用10
1.3 大数据算法设计与分析11
1.3.1 大数据算法设计技术11
1.3.2 大数据算法分析技术12
1.4 本书的内容13
习题13
第2章 时间亚线性算法14
2.1 时间亚线性算法概述14
2.1.1 平面图直径问题的亚线性算法14
2.1.2 排序链表搜索的亚线性算法16
2.1.3 两个多边形交集问题的多项式时间算法17
2.2 最小生成树代价估计18
2.2.1 连通分量个数估计算法18
2.2.2 最小生成树代价估计算法20
2.3 时间亚线性判定算法概述23
2.4 数组有序的判定算法25
2.5 串相等判定算法27
习题28
第3章 空间亚线性算法29
3.1 空间亚线性算法概述29
3.2 水库抽样31
3.3 寻找频繁元素的非随机算法32
3.3.1 频繁元素的精确解33
3.3.2 频繁元素的Misra-Gries算法33
3.4 估算不同元素的数量35
3.4.1 基本算法35
3.4.2 改进算法38
3.5 寻找频繁元素的随机算法42
3.5.1 略图法42
3.5.2 计数最小略图45
3.6 估计频率矩47
3.6.1 频率矩的AMS估计算法47
3.6.2 基于拔河略图的频率矩估计51
3.6.3 使用稳定分布估计范数53
习题57
第4章 外存算法概述60
4.1 外存存储结构与外存算法概述60
4.2 外存算法示例:外存排序算法64
4.2.1 外存归并排序算法64
4.2.2 外存多路快速排序算法68
4.2.3 外存计算的下界74
4.3 外存数据结构示例:外存搜索树77
习题78
第5章 外存查找结构80
5.1 B树80
5.2 加权平衡B树87
5.3 持久B树90
5.4 缓存树94
5.5 KDB树98
5.6 O树103
习题107
第6章 外存图数据算法109
6.1 线性表排名及其应用109
6.1.1 线性表排名问题109
6.1.2 欧拉回路114
6.1.3 父子关系判定115
6.1.4 前序计数116
6.1.5 计算子树大小117
6.2 时间前向处理方法117
6.2.1 DAG形式逻辑表达式计算问题118
6.2.2 最大独立集合算法121
6.3 缩图法124
6.3.1 基于缩图法的图连通分量计算半外存算法124
6.3.2 基于缩图法的图连通分量计算全外存算法126
6.3.3 最小生成树算法128
6.4 广度优先搜索和深度优先搜索128
6.4.1 有向图的BFS和DFS129
6.4.2 无向图的BFS134
6.4.3 无向图更高效的BFS算法136
6.5 单源最短路径139
6.5.1 竞赛树140
6.5.2 Dijkstra算法的I/O高效版本145
习题149
第7章 MapReduce算法概述150
7.1 MapReduce基础150
7.1.1 MapReduce的基本模型151
7.1.2 mapper和reducer152
7.1.3 partitioner与combiner155
7.2 MapReduce算法设计方法157
7.2.1 局部聚合158
7.2.2 两种重要的算法设计模式——词对法和条块法163
7.2.3 二次排序168
7.2.4 MapReduce算法设计与算法实现技巧168
习题170
第8章 MapReduce算法例析171
8.1 连接算法171
8.1.1 普通连接算法171
8.1.2 相似连接算法184
8.2 图算法192
8.2.1 基于广度优先搜索的MapReduce图处理算法193
8.2.2 PageRank的MapReduce算法197
8.2.3 最小生成树的MapReduce算法200
8.2.4 使用图算法的注意事项202
习题203
第9章 超越MapReduce的并行大数据处理204
9.1 基于迭代处理平台的并行算法204
9.2 基于图处理平台的并行算法212
9.2.1 并行结点计算213
9.2.2 并行结点计算的平台215
9.2.3 基于并行结点计算的单源最短路径算法的设计与实现219
9.2.4 计算子图同构221
习题223
第10章 众包算法224
10.1 众包的定义224
10.2 众包的实例225
10.3 众包的要素和关键技术228
10.3.1 众包的流程228
10.3.2 众包的报酬230
10.3.3 众包中的关键技术230
10.4 众包算法例析232
习题237
参考文献238
前言本书的缘起“大数据”在今天成为一个非常时尚的概念,其影响已经远远超过了计算机学科本身,甚至影响到了自然科学、社会科学、人文科学等。由于其深远的影响和广泛的应用,大数据一直得到IT从业人员的重视,他们对大数据相关理论、技术的学习有着强烈的需求。
“算法设计与分析”是计算机科学的重要主题,进行大数据计算,“算法设计与分析”是必不可少的步骤,可以说,算法设计是“大数据落地”的关键之一。然而,虽然在今天的书店里,关于大数据的书籍数不胜数,但真正从“算法设计与分析”角度关注大数据的书却很少。究其原因,当前“大数据算法”的知识体系还远不完备,因为“大数据”是计算机学科的增长点之一,“大数据算法”的内涵和外延也不断发生着变化,而且大数据上算法设计与分析得到的知识驳杂,难以梳理出一个明晰的知识体系。而大数据不同方面的从业人员,对“大数据算法”的理解也不尽相同。作者曾经调研过国内外和“大数据算法”相关的课程,其教学内容的差异非常大。
因而,笔者写了本书,作为一种勇敢的尝试,试图兼顾深度和广度来介绍“大数据算法”。其缘起有三。
其一,笔者从本科加入了李建中教授领导的哈尔滨工业大学数据库研究中心,留校工作到现在。随着“数据”在计算机学科扮演的角色日益重要,中心的名字经历了“数据库研究中心”到“知识与数据工程研究中心”到“海量数据计算研究中心”到“国际大数据研究中心”的变化,并且一直是围绕“数据”的计算开展研究。在中心良好的学术氛围下,笔者进行了十几年“数据”计算的研究,也一直在思考“数据为中心的计算到底需要何种特别的算法设计技术”这一问题,有一些不成熟的心得,希望与读者分享。
其二,机械工业出版社王彬编辑在2013年全国大数据会议上邀请笔者写一本和“大数据”、“算法”相关的书,促使笔者去思考和学习,试图梳理出一条“大数据算法”的脉络。
其三,在网易云课堂的孙志岗总监的鼓动下,笔者在2014年开设了自己的第一门MOOC课程“大数据算法”,2014年夏季学期笔者在哈尔滨工业大学作为全校选修课也开设了“大数据算法”这门课程,这督促着笔者不得不从教学内容到教学方法上去思考如何表述“大数据算法”。在教学过程中,很多学习这门课程的学生询问教材的事情,很遗憾,笔者只能提供一个参考文献列表,而无法推荐教材,这也促使笔者撰写这样一本书。
本书的特点本书对大数据计算中涉及的算法设计与分析技术进行了介绍,针对大数据对算法的要求,主要涉及四个方面:亚线性算法、外存算法、并行算法和众包算法。书中给出了多个算法,并对其进行了分析,尽可能使本书适用于各个层次的读者。
书中每一章涉及一类大数据算法设计技术,算法主要用自然语言、伪代码和例子来描述,力图使本书介绍的算法易懂易用。由于为大数据设计算法,在“大数据”上进行实验的成本比较高,因此“算法分析”在“大数据算法”中扮演着更重要的角色,本书也在算法分析方面投入了相当的笔墨。有不同需求的读者可以着重阅读本书不同的部分。
由于“大数据”涉及的内容较广,本书围绕大数据的特点着重介绍大数据算法设计与分析的方法,和大数据分析、大数据系统、大数据编程等书籍具有互补性,可以相互参照进行阅读。
本书适合作为本科生和研究生“大数据”或者“大数据算法”课程的教材,也可以作为“算法设计与分析”等课程的补充教材或课外读物。同时,本书也适合大数据领域从业人员参考。
由于本书是一种新的尝试,涉及的内容非常宽且又是变化迅速,尽管笔者尽全力来写本书(其中的一部分内容甚至来自于2015年发表的文献),但是由于笔者水平有限,在本书内容的安排、表述、推导等方面的各种不当之处在所难免,敬请读者在阅读本书的过程中,不吝提出宝贵的建议,以改进本书。读者的任何意见和建议请发至邮箱wangzh@hit.edu.cn。
致使用本书的教师本书涉及了多方面内容,对于教学而言,本书适用于多门课程的教学,并可以作为“数据结构”、“算法设计与分析”、“数据库系统原理”等课程的补充教材,教师可以从本书中选择适合教学的内容,例如,第5章适合作为“数据库系统原理”这门课“数据库索引”部分的补充教学内容,第4章适合作为“数据结构”这门课“排序”部分的补充教学内容。
针对不同层次的教学可以选择不同的内容。针对本科生或者职业培训的教学可以侧重于算法设计,着重讲授算法本身和算法的应用场景,而对算法分析可以略讲;针对研究生的教学可以在讲算法设计的同时利用更多的时间来讲授算法的分析和推导。
本书每章后包含一些习题,供学生巩固所学内容。
致使用本书的学生希望本书为学生提供“大数据算法”方面的入门指导,我们尽量让描述通俗易懂,但是一些算法、数据结构或者分析本身比较复杂,有些算法分析远看略显“高冷”,请在阅读时不要畏惧,可以按照相关的证明过程和推理步骤仔细梳理证明的脉络。对于本书涉及的一些可能没有学过的知识,通过“补充知识”部分进行了介绍。
要阅读本书,希望读者有一些算法和程序设计方面的基础,“数据结构”和“算法设计与分析”是本书的先修课程,如果读者没有学过这方面的课程,可以通过阅读《算法导论(原书第3版)》� 「檬橛苫�械工业出版社出版,ISBN:978-7-111-40701-1。——编辑注�∪缦抡陆谧匝�相关知识:第1~12章、第15~17章、第18章、第22~24章。本书第2章和第3章涉及一些概率分析知识,如果不需要掌握概率分析的技术而仅读懂本书,本书提供的补充知识足以帮助你理解证明过程;如果希望系统掌握概率分析,可以先阅读一下《概率与计算》�ⅰ「檬橛苫�械工业出版社出版,ISBN:978-7-111-20805-1。——编辑注�⒌牡�1~6章,奠定概率分析方面的基础,再阅读本书第2章和第3章中的证明。本书第7~9章涉及了并行算法,但并不需要读者具备并行体系结构和并行计算相关的知识,因为当前平台(如Hadoop等)已经提供了足够方便的接口,可以让读者在不具备这些知识的前提下实现数据密集型并行算法。
致使用本书的专业技术人员本书可以作为一本关于大数据算法的参考手册,供专业技术人员参考。本书各章节具有一定的独立性,读者可以单独查阅感兴趣的主题。
如果读者是一名开发人员,可以根据需要选择本书中的算法进行实现或者以此为参考设计软件当中的新算法。本书提供的伪代码可以很容易地翻译成某种程序设计语言所对应的代码。
在选择和设计算法的过程中,如果需要对算法复杂度有一定了解,本书将可以单独描述的算法复杂度结论以“引理”、“定理”的形式给出,可以直接参考这些结论,而不用详细阅读其证明。
不同类型的大数据应用和本书的不同章节相关。如果应用涉及数据量很大,而内存、计算时间等限制比较严格,请参考本书第2章和第3章;如果应用中数据源源不断到来,必须根据当前接收到的数据进行计算,请参考本书第3章;如果应用中数据存储在外存中,而内存受限,请参考本书第4~6章;如果数据存储在集群中,需要多台计算机并行计算,请参考本书第7~9章;如果应用需要只有人具备的知识,请参考本书第10章。
致谢本书的成书感谢哈尔滨工业大学的李建中教授、高宏教授以及国际大数据研究中心诸位同事的指导和建议,以及在专业上的帮助。
在本书的撰写过程中,哈尔滨工业大学的李可利、张美范、毛运东、王鑫鹏、孙芳媛、周剑、李明达、马钰、田家源、徐扬、张笑影、甘小楚、郭欣彤、李宁宁等同学在资料搜集、整理、文本校对、制图等多个方面提供了帮助和支持,在此表示感谢。
非常感谢我的爱人黎玲利博士,感谢她在我撰写这本书的过程中对我的支持。她除了给我爱和家庭的温暖,还阅读了本书全文并给出了许多专业的建议。
在本书的成书过程中我和机械工业出版社保持愉快的合作,感谢机械工业出版社的王彬编辑和朱劼编辑对我的帮助与支持。
还要感谢在哈尔滨工业大学和MOOC选修我课程的同学,你们的意见和建议对本书的写作大有裨益。
最后,笔者关于大数据方面的研究和本书的写作得到了国家重点基础研究发展计划(973)(编号:2012CB316200)、国家自然科学基金(编号:61472099)和国家科技支撑计划基金(编号:2015BAH10F00)的部分资助。
王宏志2015年6月7日于哈尔滨
我得说,《大数据算法》这本书的逻辑结构和叙述方式,真的是我读过的技术类书籍里比较出彩的。它没有采用那种“先理论后实践”的线性推进模式,而是将理论讲解、算法解析、实际案例和关键概念融为一体,形成了一个非常流畅且富有启发性的阅读体验。作者擅长用一种“提问-解答”的方式来引导读者思考,每个章节的开篇都会提出一个与大数据应用相关的问题,然后通过介绍相关的算法和技术来逐步解答。这种方式让我感觉自己不是在被动地接受信息,而是在主动地参与到知识的构建过程中。书中对于一些复杂算法的讲解,也做到了化繁为简,通过类比和场景化的方式,让原本可能令人生畏的数学和统计学概念变得易于理解。我尤其喜欢其中关于模型评估和调优的部分,作者详细介绍了各种评估指标的意义,以及如何通过交叉验证、网格搜索等方法来优化模型性能。这本书让我认识到,掌握大数据算法不仅仅是学习一套工具,更重要的是培养一种分析问题、解决问题的思维方式。
评分这本书给我的感觉,就像是打开了一扇通往人工智能大门的关键之匙。我之前一直对机器学习和深度学习这些概念感到有些遥不可及,但《大数据算法》通过对各种核心算法的深入剖析,让我逐渐理解了它们的运作机制和应用场景。作者在讲解过程中,非常注重理论与实践的结合,他不仅详细解释了算法的数学原理,还会通过大量的实际案例来展示这些算法是如何在现实世界中解决问题的,比如在图像识别、自然语言处理、用户行为分析等领域。我尤其喜欢书中关于模型选择和优化的章节,它让我明白了在不同的应用场景下,应该如何选择最适合的算法,以及如何通过调整参数来提升模型的性能。读这本书的过程中,我感觉自己仿佛置身于一个算法的实验室,亲手操作并感受着不同算法带来的强大能力。这本书不仅仅是传授知识,更重要的是启发思考,让我对大数据和人工智能的未来充满了更深的期待和探索的动力。
评分这是一本让我感到“硬核”但又充满惊喜的书。在我拿到《大数据算法》之前,我以为它会是一本充斥着数学公式和枯燥代码的枯燥读物,但事实证明我大错特错了。它在保持技术深度的同时,巧妙地融入了大量的案例研究和实际应用分析,让我对大数据算法的理解不再停留在理论层面。书中对各种经典算法的讲解,比如决策树、支持向量机、聚类算法等,都非常细致,并且会深入剖析其背后的数学原理,但又不会过度依赖纯粹的数学推导,而是通过图形化和概念化的方式辅助理解。我尤其欣赏作者在分析不同算法的优缺点以及适用场景时的洞察力。他会详细列举出在面对不同类型的数据、不同业务需求时,应该优先考虑哪些算法,以及如何根据实际情况进行调整和优化。读这本书的过程,就像是在与一位经验丰富的算法工程师进行深入的交流,他不仅会告诉你“是什么”,还会告诉你“为什么”以及“怎么做”。我感觉自己对如何选择和应用大数据算法有了更系统、更全面的认识,这对于我未来在数据驱动的决策过程中,无疑将起到重要的指导作用。
评分从一个对大数据完全陌生的初学者角度来看,《大数据算法》这本书给我带来的震撼是巨大的。它让我明白,看似庞杂海量的数据,其实都可以被有效的算法所驾驭,并从中提炼出驱动商业价值的洞察。作者并没有把我当作一个拥有深厚数学背景的专家,而是耐心地从最基础的概念讲起,逐步引入数据处理、特征提取、模型构建、算法选择以及结果解释等各个环节。我特别赞赏书中对于数据可视化在理解和呈现算法结果方面的作用的强调,这一点在很多同类书籍中是被忽略的。它让我意识到,即使是最复杂的算法,最终也需要通过清晰直观的可视化方式,才能让非技术人员也能理解其价值。我感觉这本书就像一座灯塔,照亮了我在大数据领域探索的迷茫之路。它不仅教会了我“做什么”,更重要的是教会了我“为什么这样做”,以及“如何做得更好”。读完这本书,我感觉自己对大数据算法有了更清晰、更具象的认知,也更有信心去深入学习和实践了。
评分这本书真是让我大开眼界!我一直对如何从海量数据中挖掘出有价值的信息感到好奇,而《大数据算法》恰恰满足了我的这份渴望。它没有像我之前看过的很多技术书籍那样,一上来就堆砌那些晦涩难懂的公式和理论,而是循序渐进地引导我进入大数据分析的世界。作者以非常生动形象的比喻,将一些原本抽象的概念变得通俗易懂。比如,在讲解数据清洗的重要性时,他会用“垃圾进,垃圾出”这样直观的说法,让我立刻明白数据质量的重要性。在介绍一些核心算法时,他会结合实际的业务场景,比如推荐系统、欺诈检测等,让我能清晰地看到这些算法是如何在现实世界中发挥作用的。我尤其喜欢其中关于特征工程的部分,它让我意识到,如何将原始数据转化为算法能够理解并利用的特征,是整个分析流程中至关重要的一环。书中还提供了很多实际操作的建议,虽然我还没来得及亲自去实践,但光是阅读这些内容,就感觉自己离成为一名合格的大数据分析师又近了一步。我迫不及待地想把书里介绍的那些方法应用到我的工作项目中,相信一定能带来意想不到的惊喜。这本书对于我来说,不仅仅是一本技术手册,更像是一位经验丰富的朋友,在我探索大数据海洋时,为我指引方向,点亮前行的道路。
评分正在学习,有收获了,分享一下
评分好
评分偏重理论,需要花时间多看几遍
评分挺好
评分教授要求买来看的~的确很有价值的一本书
评分清晰、严谨的叙述。针对大数据算法设计与分析中的主要方法,通过介绍原理、举例说明、算法分析等多个角度进行阐述,清晰地讲解算法设计方法,严谨地分析和证明算法的特性,有利于培养读者独立设计与分析大数据算法的能力。
评分专业用书。。。。。。。。。。。
评分了解大数据和大数据算法,值得看,专业性和应用性都能顾及到。
评分这本偏学术,有一定难度。配合实践类的书一起看效果更佳。
本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度,google,bing,sogou 等
© 2025 book.idnshop.cc All Rights Reserved. 静思书屋 版权所有