《数据科学与工程算法基础》从概率统计、线性代数和组合优化角度出发,介绍经典的数据科学与工程算法,内容涉及数据分析处理全流程的算法及其数学基础,主要包括抽样算法;尾概率不等式及其应用;典型的哈希技术,如布隆过滤器和局部敏感哈希;数据流模型以及典型Misra Gries算法、Count Sketch算法;随机游走及其应用;EM算法;特征值计算;奇异值分解和主成分分析;矩阵分解;整数规划;子模函数及其应用;模块度及社区发现等。全书配有大量翔实的应用实例可供参考,有相当数量的习题可供读者练习。
《数据科学与工程算法基础》可作为数据科学与大数据技术专业本科生、研究生相关课程的教材或参考书,也可供相关领域技术人员参考。
数据科学与工程专业核心课程系列教材终于要面世了,这是一件鼓舞人心的事。作为华东师范大学数据学院的发起者和见证人,核心课程和系列教材一直是我心心念念的事情。值此系列教材出版发行之际,我很高兴能被邀请写几句话,做个回顾,分享一些感悟,也展望一下未来。
借着大数据热的东风,依托何积丰院士在2007年倡导成立的华东师范大学海量计算研究所,2012年6月,在时任SAP公司CTO史维学博士(Dr.Vishal Sikka)的支持下,我们成立了华东师范大学云计算与大数据研究中心。2013年9月,学校发起成立作为二级独立实体的数据科学与工程研究院,开始在软件工程一级学科下自设数据科学与工程二级学科,开展博士研究生和硕士研究生的培养工作。在进行研究生培养的探索过程中,我们深切感受到计算机类专业本科生人才培养需要反思和改革。因此,到了2016年9月,研究院改制为数据科学与工程学院,随后开始招收数据科学与工程专业本科生,第一届本科生已于2020年毕业。这就是我们学院和专业的简单历史。经过这几年的实践和思考,我们越发坚信当年对“数据科学与工程”这一名称的选择,“数据学院”和“数据专业”已经得到越来越多的认可,学院的师生也逐渐接受“数据人”这一称呼。
这里,我想分享以下几方面的感悟:为什么要办数据专业?怎么办数据专业?教材为什么很重要?对人才培养有什么贡献?
为什么要办数据专业?数据是新能源,这是大家耳熟能详的一句话。说到能源,我们首先想到的是石油,所以大家习惯于把数据比喻成石油。但是,在我们看来,“新能源”对应的英文应该是“New Power”。“Data is Power”,这是我们的基本信念,也是我们要办数据学院的根本动机。数据是人类文明史上第三个重要的Power,之前的两个Power是蒸汽能(steam power)和电能(electric power),它们分别引发了第一次和第二次工业革命。如果说蒸汽能和电能造就了从西方世界开始的两百多年的工业文明,数据能(data power)将把人类带入数字文明时代。数据是数字经济发展的重要生产要素,这个生产要素不同于土地、劳动力,也不同于资本、技术。如果要给数据找一个恰当的比拟物,也许只有19世纪末伟大的发明家尼古拉·特斯拉发明的交流电。数据是新时代的交流电,就像20世纪交流电给世界带来的深刻变化一样,随着人们对数据能认识的提高,我们将进入一个“未来已来,一切重构”的时代。数据学院就像一百多年前的电力学院或电气学院。
怎么办数据专业?我们数据学院脱胎于软件工程学院,在此之前还有计算机科学与工程学院,数据相关的研究和偏向管理的图书情报方向的信息系统学科及专业也密切相关,应用数学、概率统计更是数据分析和处理的理论基础,不可或缺。到底什么样的专业才算是数据专业?最初这对我们来说基本上可以说是一个“灵魂拷问”。为此,我们发起成立了由国内15所高校30多位知名教授组成的“高等学校数据科学与工程专业建设协作组”,并且以协作组成员为班底,成立了“数据科学与工程专业系列教材编委会”,除了协作组成员,还邀请多位有丰富教材编写经验的华东师范大学教师加入编委会,共同策划教材的内容安排。我们相信,有了先进的理念,再加上集体的力量,数据专业建设的探索之路就能走通。截至2020年11月,协作组已召开4次研讨会,确定了CST专业建设路线图,其中C代表Curriculum(培养计划),S代表Syllabus(课程大纲),T代表Textbook(教材建设)。在得知我们的工作后,ACM/IEEE计算机工程学科规范主席约翰.因帕利亚佐(John Impagliazzo)教授邀请我们参与了ACM/IEEE数据科学学科规范的制定。
协作组经过讨论达成共识:数据科学与工程专业课程分为基础课、核心课、方向课三类,核心课是体现专业区分度的一组课程。与数据专业最相近的专业就是计算机科学与工程及软件工程两个专业,我们确定的第一批数据专业区别于这两个专业的8门核心课程是:数据科学与工程导论、数据科学与工程数学基础、数据科学与工程算法基础、应用统计与机器学习、当代数据管理系统、当代人工智能、分布式计算系统、云计算系统。随后我们又确定两门课纳入这个系列,分别是:区块链导论——原理、技术与应用,数据中台初阶教程。数据专业作为一个新专业,三类课程的边界还不清晰,我们将关注重点放在核心课程上,核心课有遗漏的知识点可以纳入基础课或方向课。这样可以保证知识体系的完整性,简单起步,快速迭代。随着实践和认识的深入,逐渐明晰三类课程的边界,形成完善的培养计划。
教材为什么很重要?建设好一个专业,确定培养计划和课程体系固然很重要,但落实在根本上是教材。一套好的教材是建成一个好的专业的前提。放眼看去,无论是国内还是国外,无论是具体某个高校还是国家区域层面,这都是不争的事实,即好的专业都有成体系的好的教材。当然,现在的教材已不仅仅指单纯的一本教科书,还有更深层次的内容,比如说具体的教学内容和教学方式。我们都知道,教材是知识的结晶,是站到巨人肩膀上的台阶。在自然科学领域,确实如此,一百年前我们民族的仁人志士呼唤“赛先生”,在中华大地上科学的传播带来了翻天覆地的变化。
高明,华东师范大学数据科学与工程学院教授,博士生导师。主要从事数据挖掘、知识工程和计算教育学方面的研究。曾获国家科技进步二等奖(主要参与人)、《计算机学报》2014-2019年优秀论文奖、CCF-腾讯犀牛鸟科研基金优秀奖。始终坚持以科研反哺教学的理念,积极参与数据科学与工程学科建设,主要承担本科生和研究生的“数据科学与工程算法基础”教学工作。
胡卉芪,华东师范大学数据科学与工程学院副教授。主要从事数据管理系统、数据算法方面的研究。曾获国家科学技术进步奖、教育部科技进步奖(主要参与人)等奖项。长期参与数据科学与工程学科建设,多年来专注于数据结构、算法方面核心课程的本科生教学与学生培养工作。
术人员参考。
第1章 绪论
1.1 数据分析处理阶段
1.1.1 数据采集
1.1.2 数据预处理
1.1.3 数据存储与管理
1.1.4 数据分析与挖掘
1.1.5 数据可视化
1.2 算法设计原则
1.2.1 数据特点
1.2.2 算法评价
1.2.3 算法设计原则
本章小结
习题1
第2章 抽样算法
2.1 引入
2.2 基本概念
2.2.1 总体与样本
2.2.2 抽样调查
2.3 系统抽样
2.3.1 直线等距抽样
2.3.2 圆形等距抽样
2.3.3 系统抽样特点
2.4 分层抽样
2.5 水库抽样
2.5.1 水库抽样算法
2.5.2 算法分析
2.5.3 分布式水库抽样算法
本章小结
习题2
第3章 尾概率不等式及其应用
3.1 引入
3.2 Markov不等式
3.3 Chebyshev不等式
3.4 Chernoff不等式
3.5 尾概率不等式的应用-Morris算法
3.5.1 Morris算法
3.5.2 Morris+算法
3.5.3 Morris++算法
本章小结
习题3
第4章 哈希技术
4.1 引入
4.2 哈希
4.3 布隆过滤器
4.3.1 布隆过滤器的基本原理
4.3.2 误判率
4.3.3 降低误判率
4.3.4 应用场景
4.4 局部敏感哈希
4.4.1 哈希函数的选择
4.4.2 Shingling
4.4.3 Min-Hashing
4.4.4 基于Min-Hashing的局部敏感哈希过程
4.4.5 应用场景
本章小结
习题4
第5章 数据流模型及频繁项挖掘
5.1 引入
5.2 数据流模型
5.2.1 数据流和数据流模型
5.2.2 数据流子模型
5.2.3 概要数据结构
5.2.4 近似算法
5.3 频繁项挖掘
5.4 确定性近似频数算法Misra Gries
5.4.1 Misra Gries算法
5.4.2 Misra Gries算法分析
5.5 随机近似频数算法Count Sketch
5.5.1 简单抽样算法
5.5.2 Basic Count Sketch算法
5.5.3 Count Sketch算法
5.5.4 Count-Min Sketch
算法
本章小结
习题5
第6章 EM算法
6.1 引入
6.2 最大似然估计方法
6.2.1 似然函数
6.2.2 最大似然估计
6.2.3 混合模型
6.3 EM算法
6.3.1 算法推导
6.3.2 EM算法
6.3.3 EM算法的收敛性
本章小结
习题6
第7章 随机游走及其应用
7.1 引入
7.2 随机过程
7.2.1 马尔可夫过程
7.2.2 随机游走
7.2.3 转移概率矩阵
……
第8章 特征值计算
第9章 奇异值分解与主成分分析
第10章 矩阵分解
第11章 整数规划
第12章 子模函数及其应用
第13章 模块度及社区发现
参考文献