山东大学《数据科学导论》：基础与高维分析

需积分: 9 131 浏览量更新于2024-07-17 收藏 2.3MB PDF 举报

"《数据科学基础》(Foundations of Data Science) 是山东大学数据科学导论课程使用的英文教材，该书深入探讨了数据科学领域的核心概念和技术。本书共分为两个主要部分：高维空间理论和最佳-fit子空间与奇异值分解(Singular Value Decomposition, SVD)。在第一章“引言”中，作者概述了数据科学的基础，包括其在当今世界中的重要性和应用背景。章节强调了大数据时代对处理复杂多维度数据的需求。第二章“高维空间”详细讨论了在高维空间中的几何性质。这里涉及的主题有： 1. **大数定律**：解释了在大量数据中的统计规律。 2. **高维几何**：阐述了维度增加对空间结构的影响，如球体在高维中的奇特性质。 3. **单位球的特性**：探讨了体积、等距点集等问题，包括单位球的体积计算以及接近极点区域的体积变化。 4. **随机采样**：介绍如何在高维空间中均匀随机生成点。 5. **高斯分布**：高维环境下的正态分布，其在数据分析中的作用。 6. **随机投影和Johnson-Lindenstrauss引理**：用于降维的有效工具，展示了如何通过随机映射保持数据间的距离关系。 7. **高斯分布的分离**：关于如何在高维空间中区分不同分布的数据。 8. **拟合球形高斯模型**：学习如何将数据拟合到高斯分布模型。 9. **参考文献**：提供了进一步阅读的资料来源。 10. **习题**：通过实践巩固理论知识。第三章转向了关键的数学工具——SVD。SVD是数据处理和分析的核心算法，包括： 1. **简介**：介绍了SVD的概念和在数据科学中的应用。 2. **预备知识**：回顾必要的线性代数基础。 3. **奇异向量**：阐述这些向量在矩阵分解中的关键角色。 4. **奇异值分解**：解释了如何将矩阵分解为三个因子，揭示其结构和意义。 5. **最佳秩-k近似**：讨论如何利用SVD找到最简洁的表示。 6. **左奇异向量**：与右奇异向量一起构成矩阵分解。 7. **SVD的功率方法**：演示求解SVD的一种迭代方法及其优化版本。 8. **奇异向量与特征向量的关系**：对比这两个概念在不同情境下的应用。 9. **SVD的应用**：涵盖了诸如图像压缩、信号处理、数据降维等实际问题。《数据科学基础》以深入浅出的方式讲解了这些概念，为理解并应用数据科学奠定了坚实的理论基础。通过学习这些内容，学生可以掌握处理和分析高维数据的基本技巧，并能在实际项目中有效地解决问题。"

Condition Tail bound

Markov x ≥ 0 Prob(x ≥ a) ≤

E(x)

Chebychev Any x Prob



|x − E(x)| ≥ a



≤

Var(x)

Chernoﬀ x = x

+ x

+ ··· + x

Prob(|x − E(x)| ≥ εE(x))

∈ [0, 1] i.i.d. Bernoulli; ≤ 3e

−cε

E(x)

Higher Moments r positive even integer Prob(|x| ≥ a) ≤ E(x

)/a

Gaussian x =

+ x

+ ··· + x

Prob(|x −

√

n| ≥ β) ≤ 3e

−cβ

Annulus x

∼ N(0, 1); β ≤

√

n indep.

Power Law x = x

+ x

+ . . . + x

Prob



|x − E(x)| ≥ εE(x)



for x

; order k ≥ 4 x

i.i.d ; ε ≤ 1/k

≤ (4/ε

kn)

(k−3)/2

Figure 2.1: Table of Tail Bounds. The Higher Moments bound is obtained by apply-

ing Markov to x

. The Chernoﬀ, Gaussian Annulus, and Power Law bounds follow from

Theorem 2.5 which is proved in the appendix.

2.3 The Geometry of High Dimensions

An important property of high-dimensional objects is that most of their volume is

near the surface. Consider any object A in R

. Now shrink A by a small amount  to

produce a new object (1 − )A = {(1 −)x|x ∈ A}. Then the following equality holds:

volume



(1 − )A



= (1 − )

volume(A).

To see that this is true, partition A into inﬁnitesimal cubes. Then, (1 − ε)A is the union

of a set of cubes obtained by shrinking the cubes in A by a factor of 1 − ε. When we

shrink each of the 2d sides of a d-dimensional cube by a factor f, its volume shrinks by a

factor of f

. Using the fact that 1 − x ≤ e

−x

, for any object A in R

we have:

volume



(1 − )A



volume(A)

= (1 − )

≤ e

−d

Fixing  and letting d → ∞, the above quantity rapidly approaches zero. This means

that nearly all of the volume of A must be in the portion of A that does not belong to

the region (1 − )A.

Let S denote the unit ball in d dimensions, that is, the set of points within distance

one of the origin. An immediate implication of the above observation is that at least a

Lemma 2.6 The surface area A(d) and the volume V (d) of a unit-radius ball in d di-

mensions are given by

A (d) =

2π

Γ(

)

and V (d) =

2π

d Γ(

)

To check the formula for the volume of a unit ball, note that V (2) = π and V (3) =

(

)

π, which are the correct volumes for the unit balls in two and three dimen-

sions. To check the formula for the surface area of a unit ball, note that A(2) = 2π and

A(3) =

2π

√

= 4π, which are the correct surface areas for the unit ball in two and three

dimensions. Note that π

is an exponential in

and Γ





grows as the factorial of

This implies that lim

d→∞

V (d) = 0, as claimed.

2.4.2 Volume Near the Equator

An interesting fact about the unit ball in high dimensions is that most of its volume

is concentrated near its “equator”. In particular, for any unit-length vector v deﬁning

“north”, most of the volume of the unit ball lies in the thin slab of points whose dot-

product with v has magnitude O(1/

√

d). To show this fact, it suﬃces by symmetry to ﬁx

v to be the ﬁrst coordinate vector. That is, we will show that most of the volume of the

unit ball has |x

| = O(1/

√

d). Using this fact, we will show that two random points in the

unit ball are with high probability nearly orthogonal, and also give an alternative proof

from the one in Section 2.4.1 that the volume of the unit ball goes to zero as d → ∞.

Theorem 2.7 For c ≥ 1 and d ≥ 3, at least a 1 −

−c

fraction of the volume of the

d-dimensional unit ball has |x

| ≤

√

d−1

Proof: By symmetry we just need to prove that at most a

−c

fraction of the half of

the ball with x

≥ 0 has x

≥

√

d−1

. Let A denote the portion of the ball with x

≥

√

d−1

and let H denote the upper hemisphere. We will then show that the ratio of the volume

of A to the volume of H goes to zero by calculating an upper bound on volume(A) and

a lower bound on volume(H) and proving that

volume(A)

volume(H)

≤

upper bound volume(A)

lower bound volume(H)

−

To calculate the volume of A, integrate an incremental volume that is a disk of width

and whose face is a ball of dimension d − 1 and radius

1 − x

. The surface area of

the disk is (1 − x

)

d−1

V (d −1) and the volume above the slice is

volume(A) =

√

d−1

(1 − x

)

d−1

V (d −1)dx

剩余464页未读，继续阅读

消失的铁盒

粉丝: 1
资源: 10

山东大学《数据科学导论》：基础与高维分析

Foundations_of_Data_Science_March 2019.pdf

foundations of data science

foundations of data science csdn

Foundations of Data Science（非常优秀英文原版教材）.pdf

计算与推理：数据科学的基础Computational and Inferential: The Foundations of Data Science

Foundations of Computer Science(英文版)

Foundations of Machine Learning And Data Science For Developers

Mathematical Foundations of Data Sciences

Foundation of Data Science

Data Science Foundations Geometry and Topology of Complex Hierarchic epub

最新资源