数据科学基础（英文版）

　　《数据科学基础（英文版）》是“大数据与计算机科学”系列教材之一，由国际著名计算机科学家约翰·霍普克罗夫特教授、阿夫里姆·布鲁姆教授和拉文德兰·坎南教授共同撰写。《数据科学基础（英文版）》包含了高维空间、奇异值分解、随机行走和马尔可夫链、机器学习、大数据问题的算法、聚类随机图等主要内容。全书极大部分的结论都有严格的证明，且从第2章开始，每章后面均附有适量的练习题。《数据科学基础（英文版）》可作为计算机及其相关专业本科生或研究生的教材，也可供专业技术人员参考。

　　作者：（美）阿夫里姆·布鲁姆 作者：约翰·霍普克罗夫特 作者：（印）拉文德兰·坎南阿夫里姆·布鲁姆，丰田工业大学芝加哥分校教授兼首席学术官，1996年担任COLT’96程序委员会主席，2000年担任FOCS’OO程序委员会主席。2007年成为美国计算机协会研究员，2011年获得计算机科学院赫伯特·西蒙教学奖。约翰·霍普克罗夫特，曾获得1986年图灵奖、2005年电气与电子工程师协会哈里古德纪念奖、2007年计算研究协会杰出服务奖、2009年计算机协会Karl V.Karlstrom杰出教育家奖、2010年电气与电子工程师协会约翰·冯·诺依曼奖章，以及2016年中国友谊奖章，这是中国对外国人的最高认可。此外，中国科学院还将他任命为爱因斯坦讲席教授。拉文德兰·坎南，印度班加罗尔微软研究院首席研究员，曾任耶鲁大学计算机科学系教授兼应用数学系教授、卡内基梅隆大学教授。1991年获得由美国数学学会和数学规划学会联合授予的离散数学福克森奖，2011年获得计算机协会高德纳奖，2015年当选美国艺术与科学院院士。

1 Introduction

2 High-Dimensional Space
2．1 Introduction
2．2 The Law of Large Numbers
2．3 The Geometry of High Dimensions
2．4 Properties of the Unit Ball
2．4．1 Volume of the Unit Ball
2．4．2 Volume Near the Equator
2．5 Generating Points Uniformly at Random from a Ball
2．6 Gaussians in High Dimension
2．7 Random Projection and Johnson-Lindenstrauss Lemma
2．8 Separating Gaussians
2．9 Fitting a Spherical Gaussian to Data
2．10 Bibliographic Notes
2．11 Exercises

3 Best-Fit Subspaces and Singular Value Decomposition （SVD）
3．1 Introduction
3．2 Preliminaries
3．3 Singular Vectors
3．4 Singular Value Decomposition （SVD）
3．5 Best Rank-k Approximations
3．6 Left Singular Vectors
3．7 Power Method for Singular Value Decomposition
3．8 Singular Vectors and Eigenvectors
3．9 Applications of Singular Value Decomposition
3．9．1 Centering Data
3．9．2 Principal Component Analysis
3．9．3 Clustering a Mixture of Spherical Gaussians
3．9．4 Ranking Documents and Web Pages
3．9．5 An Application of SVD to a Discrete Optimization Problem
3．10 Bibliographic Notes
3．11 Exercises

4 Random Walks and Markov Chains
4．1 Stationary Distribution
4．2 Markov Chain Monte Carlo
4．2．1 Metropolis-Hasting Algorithm
4．2．2 Gibbs Sampling
4．3 Areas and Volumes
4．4 Convergence of Random Walks on Undirected Graphs
4．5 Electrical Networks and Random Walks
4．6 Random Walks on Undirected Graphs with Unit Edge Weights
4．7 Random Walks in Euclidean Space
4．8 The Web as a Markov Chain
4．9 Bibliographic Notes
4．10 Exercises

5 Machine Learning
5．1 Introduction
5．2 Overfitting and Uniform Convergence
5．3 Illustrative Examples and Occams Razor
5．3．1 Learning Disjunctions
5．3．2 Occams Razor
5．3．3 Application： Learning Decision Trees
5．4 Regularization： Penalizing Complexity
5．5 Online Learning and the Perceptron Algorithm
……

6 Algorithms for Massive Data Problems： Streaming， Sketching， and Sampling
7 Clustering
8 Random Graphs
9 Topic Models， Non-Negative Matrix Factorization， Hidden Markov Models， and Graphical Models
10 Other Topics
11 Wavelets
12 Appendices

References
Index