# 数据挖掘

数据挖掘 (data mining) 不强调学习，强调从数据中提取信息并形成可理解的结构的过程。

# 基本的方法

# PCA

最基本的方法，永远的折磨，不再讲了。

# 随机投影

$$\bm{z} = \frac{1}{\sqrt{k}}\bm{P}\bm{x},$$

其中 $\bm{P}$ 是随机投影矩阵，从标准正态分布中采样得到；$\bm{x} \in \mathbb{R}^d, \bm{z} \in \mathbb{R}^k$, 且有 $k \ll d$.

（似乎）显然，如果 $P_{ij}, \forall i,j$ 是从标准正态分布中采样的，那么这里的估计是无偏的，即

$$\mathbb{E}\left(\|\bm{z}\|^2\right) = \|\bm{x}\|^2.$$

同时，这个投影是近似保距的。可以用下述定理描述：

对 $\forall \varepsilon \in (0, 1/2)$, 任意样本集 $D = \{\bm{x}^{(i)}\}_{i=1}^n$, 令投影矩阵 $\bm{P}$ 为前述从正态分布中采样的随机投影矩阵，若投影维度

$$k \geq \frac{8 \ln \frac{n}{\sqrt{\sigma}}}{e^2 - e^3},$$

那么至少以 $1- \varepsilon$ 使下式成立：

$$(1-\varepsilon)\|\bm{x}-\bm{x}'\|^2 \leq \|\bm{P}\bm{x}-\bm{P}\bm{x}'\|^2 \leq (1+\varepsilon)\|\bm{x}-\bm{x}'\|^2, \quad \forall \bm{x}, \bm{x}' \in D.$$

# 矩阵近似计算

矩阵近似计算的一个方法是矩阵分解。即构造

$$\bm{M}' = \bm{CB} \in \mathbb{R}^{m \times n},$$

使得 $\|\bm{M} - \bm{M}'\|_F$ 最小，且 $\mathrm{rank}(\bm{M}') \leq r$.

实现该矩阵分解的方式就是 SVD 分解。

后面有随机 SVD 等方法。