首页 计算机 机器学习 数据挖掘

# 数据挖掘

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

# 基本的方法

# PCA

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

# 随机投影

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

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

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

E(∥z∥2)=∥x∥2.\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} 为前述从正态分布中采样的随机投影矩阵，若投影维度

k≥8ln⁡nσe2−e3,k \geq \frac{8 \ln \frac{n}{\sqrt{\sigma}}}{e^2 - e^3},

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

(1−ε)∥x−x′∥2≤∥Px−Px′∥2≤(1+ε)∥x−x′∥2,∀x,x′∈D.(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′=CB∈Rm×n,\bm{M}' = \bm{CB} \in \mathbb{R}^{m \times n},

使得 ∥M−M′∥F\|\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⁡β12n∥y−Xβ∥22+λ∥β∥1.\min_{\bm{\beta}}\frac{1}{2n} \|\bm{y} - \bm{X\beta}\|_2^2 + \lambda \|\bm{\beta}\|_1.

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

0∈∂F(β)=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:D→Rf:\mathcal{D} \to \mathbb{R}, 其中 D\mathcal{D} 是定义在 dd 维欧氏空间上的凸集，若对 ∀y∈D\forall y \in \mathcal{D} 满足

f(y)≥f(x)+⟨g,y−x⟩,f(\bm{y}) \geq f(\bm{x}) + \langle\bm{g}, \bm{y} - \bm{x}\rangle,

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

# 次梯度的性质

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

⟨−g,y′−x⟩≥f(x)−f(y′)≥0.\langle -\bm{g}, \bm{y}'-\bm{x} \rangle \geq f(\bm{x}) - f(\bm{y}') \geq 0.

# 例子

f(x)=∣x∣f(x) = |x| 的在 x=0x=0 处的次梯度：

基于定义，有 ∣y∣≥0+⟨g,y−0⟩|y| \geq 0 + \langle g, y-0\rangle. 也就是 ∣y∣≥gy|y| \geq gy. 从而 g∈[−1,1]g \in [-1,1].

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

# LASSO 误差分析

# 循环坐标梯度下降算法

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

  • 压缩感知：

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

  • LASSO:

    min⁡β12n∥y−Xβ∥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) 来优化。