# 数据挖掘
数据挖掘 (data mining) 不强调学习,强调从数据中提取信息并形成可理解的结构的过程。
# 基本的方法
# PCA
最基本的方法,永远的折磨,不再讲了。
# 随机投影
z=k1Px,
其中 P 是随机投影矩阵,从标准正态分布中采样得到;x∈Rd,z∈Rk, 且有 k≪d.
(似乎)显然,如果 Pij,∀i,j 是从标准正态分布中采样的,那么这里的估计是无偏的,即
E(∥z∥2)=∥x∥2.
同时,这个投影是近似保距的。可以用下述定理描述:
对 ∀ε∈(0,1/2), 任意样本集 D={x(i)}i=1n, 令投影矩阵 P 为前述从正态分布中采样的随机投影矩阵,若投影维度
k≥e2−e38lnσn,
那么至少以 1−ε 使下式成立:
(1−ε)∥x−x′∥2≤∥Px−Px′∥2≤(1+ε)∥x−x′∥2,∀x,x′∈D.
# 矩阵近似计算
矩阵近似计算的一个方法是矩阵分解。即构造
M′=CB∈Rm×n,
使得 ∥M−M′∥F 最小,且 rank(M′)≤r.
实现该矩阵分解的方式就是 SVD 分解。
后面有随机 SVD 等方法。
# dimension reduction
包括两种办法:
- 特征选取 (feature selection): 从特征中直接选取子集。
- 特征提取 (feature extraction): 将特征进行组合,得到数个新的特征。
# LASSO
# 基本概念
最小二乘法得到的 β 不是稀疏的。但稀疏解一方面可以加快推理,另一方面可以删除无用特征,提高解释性。
最简单得到稀疏解的方式是加入 l0 范数约束,即
但这是一个组合优化问题,为 NP hard, 难以求解。因此可以退而求其次,改成 l1 范数约束。
但无约束问题更易优化。因此采用拉格朗日乘子法类似的方法,加入正则项优化,也就是
βmin2n1∥y−Xβ∥22+λ∥β∥1.
但是上式不可导,因此可以使用次梯度优化。也就是说,最优解一定使问题的次梯度为 0, 即
0∈∂F(β)=n1X⊤(Xβ−y)+λ⋅∂(∥β∥1).
需要注意,次梯度是一个集合。
# 次梯度
对于凸函数 f:D→R, 其中 D 是定义在 d 维欧氏空间上的凸集,若对 ∀y∈D 满足
f(y)≥f(x)+⟨g,y−x⟩,
则称 g 是 f 在 x 处的次梯度 (subgradient).
# 次梯度的性质
假设 y′ 是最优值,则
⟨−g,y′−x⟩≥f(x)−f(y′)≥0.
# 例子
f(x)=∣x∣ 的在 x=0 处的次梯度:
基于定义,有 ∣y∣≥0+⟨g,y−0⟩. 也就是 ∣y∣≥gy. 从而 g∈[−1,1].
所以,次梯度是一个集合。
# LASSO 误差分析
# 循环坐标梯度下降算法
# 压缩感知和 LASSO 模型的区别
- 压缩感知:
βmin2n1∥y−Φβ∥22+λ∥β∥1
- LASSO:
βmin2n1∥y−Xβ∥22+λ∥β∥1
# 近端梯度法
如果目标函数的形式是
F=g+h,
其中 g 可微而 h 不可微,那么可以采用近端梯度法 (Proximal Gradient Method, PGM) 来优化。