# 数据挖掘

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

# 基本的方法

# PCA

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

# 随机投影

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

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

(似乎)显然,如果 Pij,i,jP_{ij}, \forall i,j 是从标准正态分布中采样的,那么这里的估计是无偏的,即

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

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

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

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

那么至少以 1ε1- \varepsilon 使下式成立:

(1ε)xx2PxPx2(1+ε)xx2,x,xD.(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.

# 矩阵近似计算

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

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

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

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

后面有随机 SVD 等方法。

# dimension reduction

包括两种办法:

  • 特征选取 (feature selection): 从特征中直接选取子集。
  • 特征提取 (feature extraction): 将特征进行组合,得到数个新的特征。

# LASSO

# 基本概念

  • 训练集 SS
  • 线性模型

    f(x)=j=1dβjxj=βxf(\bm{x}) = \sum_{j=1}^d \beta_j x_j = \bm{\beta}^\top \bm{x}

  • 最小二乘法

最小二乘法得到的 β\bm{\beta} 不是稀疏的。但稀疏解一方面可以加快推理,另一方面可以删除无用特征,提高解释性。

最简单得到稀疏解的方式是加入 l0l_0 范数约束,即

但这是一个组合优化问题,为 NP hard, 难以求解。因此可以退而求其次,改成 l1l_1 范数约束。

但无约束问题更易优化。因此采用拉格朗日乘子法类似的方法,加入正则项优化,也就是

minβ12nyXβ22+λβ1.\min_{\bm{\beta}}\frac{1}{2n} \|\bm{y} - \bm{X\beta}\|_2^2 + \lambda \|\bm{\beta}\|_1.

但是上式不可导,因此可以使用次梯度优化。也就是说,最优解一定使问题的次梯度为 00, 即

0F(β)=1nX(Xβy)+λ(β1).\bm{0} \in \partial F(\bm{\beta}) = \frac{1}{n} \bm{X}^\top (\bm{X\beta} - \bm{y}) + {\color{red}\lambda \cdot \partial(\|\bm{\beta}\|_1)}.

需要注意,次梯度是一个集合。

# 次梯度

对于凸函数 f:DRf:\mathcal{D} \to \mathbb{R}, 其中 D\mathcal{D} 是定义在 dd 维欧氏空间上的凸集,若对 yD\forall y \in \mathcal{D} 满足

f(y)f(x)+g,yx,f(\bm{y}) \geq f(\bm{x}) + \langle\bm{g}, \bm{y} - \bm{x}\rangle,

则称 g\bm{g}ffx\bm{x} 处的次梯度 (subgradient).

# 次梯度的性质

假设 y\bm{y}' 是最优值,则

g,yxf(x)f(y)0.\langle -\bm{g}, \bm{y}'-\bm{x} \rangle \geq f(\bm{x}) - f(\bm{y}') \geq 0.

# 例子

f(x)=xf(x) = |x| 的在 x=0x=0 处的次梯度:

基于定义,有 y0+g,y0|y| \geq 0 + \langle g, y-0\rangle. 也就是 ygy|y| \geq gy. 从而 g[1,1]g \in [-1,1].

所以,次梯度是一个集合。

# LASSO 误差分析

# 循环坐标梯度下降算法

# 压缩感知和 LASSO 模型的区别

  • 压缩感知:

    minβ12nyΦβ22+λβ1\min_{\bm{\beta}} \frac{1}{2n} \|\bm{y} - {\color{red}\Phi}\bm{\beta}\|_2^2 + \lambda \|\bm{\beta}\|_1

  • LASSO:

    minβ12nyXβ22+λβ1\min_{\bm{\beta}} \frac{1}{2n} \|\bm{y} - \bm{X\beta}\|_2^2 + \lambda \|\bm{\beta}\|_1

# 近端梯度法

如果目标函数的形式是

F=g+h,F = g + h,

其中 gg 可微而 hh 不可微,那么可以采用近端梯度法 (Proximal Gradient Method, PGM) 来优化。