java实现梯度上升算法_机器学习之PCA与梯度上升法

主成分分析(Principle Component Analysis&＃xff0c;简称&＃xff1a;PCA)是一种非监督学习的机器算法&＃xff0c;主要用于数据的降维。

PCA 基本原理

以有2个特征的二维平面举例&＃xff0c;如图&＃xff1a;

横轴表示特征1&＃xff0c;纵轴表示特征2&＃xff0c;其中4个点表示二维的特征样本。如果要对样本进行降维降到一维&＃xff0c;可以将这些点映射到横轴、纵轴或者其它轴上如&＃xff1a;

映射到不同的轴后样本间间距会不一样&＃xff0c;而要找的就是让样本间间距最大的轴。假定这个轴方向为 $w &＃61; (w1, w2)$。

对于样本间间距可以用方差 $Var(x) &＃61; \frac{1}{m}\sum_{i&＃61;1}^m(x_i-\overline x)^2$ 来衡量&＃xff0c;方差越大&＃xff0c;样本间越稀疏。

接着进行均值归0(demean)处理&＃xff0c;即 $\overline x &＃61; 0$&＃xff0c;使得 $Var(x) &＃61; \frac{1}{m}\sum_{i&＃61;1}^m(x_i)^2$。均值归0处理使得原始样本发生了变化转换成了新的样本 $X$。将其映射到轴 $w$ 上又得到新的样本 $X_{pr}$&＃xff0c;此时的方差为&＃xff1a;

$$

Var(X_{pr}) &＃61; \frac{1}{m}\sum_{i&＃61;1}^m(X_{pr}^{(i)})^2

$$

因为 $X_{pr}^{(i)}$ 是一个向量 $(X_{pr1}^{(i)}, X_{pr2}^{(i)})$&＃xff0c;所以实际的方差表示为&＃xff1a;

$$

Var(X_{pr}) &＃61; \frac{1}{m}\sum_{i&＃61;1}^m||X_{pr}^{(i)}||^2

$$

最后计算 $||X_{pr}^{(i)}||$&＃xff0c;如图所示&＃xff1a;

$||X_{pr}^{(i)}|| &＃61; X^{(i)}·w$ ($w$ 为单位向量)&＃xff0c;如此得到了想要的目标函数&＃xff1a;

求 $w$ 使得 $Var(X_{pr}) &＃61; \frac{1}{m}\sum_{i&＃61;1}^m(X^{(i)}·w)^2$ 最大&＃xff1b;对于多维特征&＃xff0c;即 $\frac{1}{m}\sum_{i&＃61;1}^m(X_1^{(i)}w_1&＃43;X_2^{(i)}w_2&＃43;...&＃43;X_n^{(i)}w_n)^2$ 最大。

梯度上升法解决PAC问题

在梯度上升法中&＃xff0c;$&＃43;\eta\nabla f$ 代表了 $f$ 增大的方向。

对于 PAC 的目标函数&＃xff1a;求 $w$ 使得 $f(X) &＃61; \frac{1}{m}\sum_{i&＃61;1}^m(X_1^{(i)}w_1&＃43;X_2^{(i)}w_2&＃43;...&＃43;X_n^{(i)}w_n)^2$ 最大&＃xff0c;可以使用梯度上升法来解决。

$f(X)$ 的梯度为&＃xff1a;

$$

\nabla f &＃61; \begin{pmatrix} \frac{\partial f}{\partial w_1} \\\ \frac{\partial f}{\partial w_2} \\\ \cdots \\\ \frac{\partial f}{\partial w_n} \end{pmatrix} &＃61; \frac{2}{m} \begin{pmatrix} \sum_{i&＃61;1}^{m}(X_1^{(i)}w_1&＃43;X_2^{(i)}w_2&＃43;...&＃43;X_n^{(i)}w_n)X_1^{(i)} \\\ \sum_{i&＃61;1}^{m}(X_1^{(i)}w_1&＃43;X_2^{(i)}w_2&＃43;...&＃43;X_n^{(i)}w_n)X_2^{(i)} \\\ \cdots \\\ \sum_{i&＃61;1}^{m}(X_1^{(i)}w_1&＃43;X_2^{(i)}w_2&＃43;...&＃43;X_n^{(i)}w_n)X_n^{(i)} \end{pmatrix} &＃61; \frac{2}{m} \begin{pmatrix} \sum_{i&＃61;1}^{m}(X^{(i)}w)X_1^{(i)} \\\ \sum_{i&＃61;1}^{m}(X^{(i)}w)X_2^{(i)} \\\ \cdots \\\ \sum_{i&＃61;1}^{m}(X^{(i)}w)X_n^{(i)} \end{pmatrix} &＃61; \frac{2}{m}·X^T(Xw)

$$

注&＃xff1a;这里略去了转换过程。

利用梯度公式 $\nabla f &＃61; \frac{2}{m}·X^T(Xw)$ 的梯度上升法实际上是批量梯度上升法(还有随机梯度上升法和小批量梯度上升法&＃xff0c;本文不涉及)。

梯度上升法求主成分

求第一主成分

首先定义一组有两个特征的数据集 $X$&＃xff0c;共100个样本&＃xff1a;

import numpy as np

X &＃61; np.empty((100, 2))

X[:, 0] &＃61; np.random.uniform(0., 100., size&＃61;100)

X[:, 1] &＃61; 0.75 * X[:, 0] &＃43; 3. &＃43; np.random.normal(0, 10., size&＃61;100)

$X$ 可视化如图&＃xff1a;

demean() 方法对 $X$ 进行均值归0处理&＃xff1a;

def demean(X):

return X - np.mean(X, axis&＃61;0)

X_demean &＃61; demean(X)

均值归0处理后的 $X\_demean$ 可视化如图&＃xff1a;

f() 方法求函数 $f$ 的值&＃xff1a;

def f(w, X):

return np.sum(X.dot(w) ** 2) / len(X)

df() 方法根据梯度公式 $\nabla f &＃61; \frac{2}{m}·X^T(Xw)$ 求梯度&＃xff1a;

def df(w, X):

return X.T.dot(X.dot(w)) * 2 / len(X)

gradient_ascent() 方法为梯度上升法的过程&＃xff0c;在 n_iters 次循环中&＃xff0c;每次获得新的 $w$&＃xff0c;如果新的 $w$ 和旧的 $w$ 对应的函数 $f$ 的值的差值满足精度 epsilon&＃xff0c;则表示找到了合适的 $w$&＃xff1a;

def gradient_ascent(X, initial_w, eta, n_iters&＃61;1e4, epsilon&＃61;1e-8):

w &＃61; direction(initial_w)

cur_iter &＃61; 0

while cur_iter

gradient &＃61; df(w, X)

last_w &＃61; w

w &＃61; w &＃43; eta * gradient

w &＃61; direction(w) # 将w转换成单位向量

if(abs(f(w, X) - f(last_w, X))

break

cur_iter &＃43;&＃61; 1

return w

其中调用了一个方法 direction()&＃xff0c;用于将 $w$ 转换成单位向量&＃xff1a;

def direction(w):

return w / np.linalg.norm(w)

接着使用梯度上升法&＃xff0c;先设定一个初始的 $w$ 和学习率 $\eta$&＃xff1a;

initial_w &＃61; np.random.random(X.shape[1])

eta &＃61; 0.001

直接调用 gradient_ascent() 方法&＃xff1a;

w &＃61; gradient_ascent(X_demean, initial_w, eta)

将得到的 $w$ 与样本可视化如图($w$ 以直线表示)&＃xff1a;

求前n个主成分

前面求出了第一主成分&＃xff0c;如何求出下一个主成分呢&＃xff1f;以二维特征为例&＃xff0c;如图&＃xff1a;

样本 $X^{(i)}$ 在第一主成分 $w$ 上的分量为 $(X_{pr1}^{(i)}, X_{pr2}^{(i)})$&＃xff0c;下一个主成分上的分量 $X^{&＃39;(i)} &＃61; X^{(i)} - (X_{pr1}^{(i)}, X_{pr2}^{(i)})$&＃xff0c;因此只需将数据在第一主成分上的分量去掉&＃xff0c;再对新的数据求第一主成分即可。

first_n_component() 方法用于求 $X$ 的前 n 个主成分&＃xff0c;在 for 循环中每次求主成分时都设定一个随机的 $w$(initial_w)&＃xff0c;得到一个主成分后就去掉在这个主成分上的分量 X_pca &＃61; X_pca - X_pca.dot(w).reshape(-1, 1) * w&＃xff1a;

def first_n_component(n, X, eta&＃61;0.001, n_iters&＃61;1e4, epsilon&＃61;1e-8):

X_pca &＃61; X.copy()

X_pca &＃61; demean(X_pca)

res &＃61; []

for i in range(n):

initial_w &＃61; np.random.random(X_pca.shape[1])

w &＃61; gradient_ascent(X_pca, initial_w, eta)

res.append(w)

X_pca &＃61; X_pca - X_pca.dot(w).reshape(-1, 1) * w

return res

降维映射

得到了多个主成分后&＃xff0c;就可以通过这些主成分将高维数据映射到低维数据。

对于有 m 个样本&＃xff0c;n 个特征的高维数据 $X$(m*n)&＃xff0c;主成分分析后得到前 k(k

$$

X &＃61; \begin{pmatrix} X_1^{(1)} X_2^{(1)} \cdots X_n^{(1)} \\\ X_1^{(2)} X_2^{(2)} \cdots X_n^{(2)} \\\ \cdots \cdots \cdots \cdots \\\ X_1^{(m)} X_2^{(m)} ... X_n^{(m)} \end{pmatrix}, W_k&＃61; \begin{pmatrix} W_1^{(1)} W_2^{(1)} \cdots W_n^{(1)} \\\ W_1^{(2)} W_2^{(2)} \cdots W_n^{(2)} \\\ \cdots \cdots \cdots \cdots \\\ W_1^{(k)} W_2^{(k)} ... W_n^{(k)} \end{pmatrix}

$$

n 维降维到 k 维后的新数据为&＃xff1a;$X_k &＃61; X·W_k^T$。

在这个降维的过程中可能会丢失信息。如果原先的数据中本身存在一些无用信息&＃xff0c;降维也可能会有降燥效果。

也可以将降维后的新数据恢复到原来的维度&＃xff1a;$X_m &＃61; X_k·W_k$。

实现 PCA

定义一个类 PCA&＃xff0c;构造函数函数中 n_components 表示主成分个数即降维后的维数&＃xff0c;components_ 表示主成分 $W_k$&＃xff1b;

函数 fit() 与上面的 first_n_component() 方法一样&＃xff0c;用于求出 $W_k$&＃xff1b;

函数 transform() 将 $X$ 映射到各个主成分分量中&＃xff0c;得到 $X_k$&＃xff0c;即降维&＃xff1b;

函数 transform() 将 $X_k$ 映射到原来的特征空间&＃xff0c;得到 $X_m$。

import numpy as np

class PCA:

def __init__(self, n_components):

self.n_components &＃61; n_components

self.components_ &＃61; None

def fit(self, X, eta&＃61;0.001, n_iters&＃61;1e4):

def demean(X):

return X - np.mean(X, axis&＃61;0)

def f(w, X):

return np.sum(X.dot(w) ** 2) / len(X)

def df(w, X):

return X.T.dot(X.dot(w)) * 2 / len(X)

def direction(w):

return w / np.linalg.norm(w)

def first_component(X, initial_w, eta, n_iters, epsilon&＃61;1e-8):

w &＃61; direction(initial_w)

cur_iter &＃61; 0

while cur_iter

gradient &＃61; df(w, X)

last_w &＃61; w

w &＃61; w &＃43; eta * gradient

w &＃61; direction(w)

if(abs(f(w, X) - f(last_w, X))

break

cur_iter &＃43;&＃61; 1

return w

X_pca &＃61; demean(X)

self.components_ &＃61; np.empty(shape&＃61;(self.n_components, X.shape[1]))

for i in range(self.n_components):

initial_w &＃61; np.random.random(X_pca.shape[1])

w &＃61; first_component(X_pca, initial_w, eta, n_iters)

self.components_[i:] &＃61; w

X_pca &＃61; X_pca - X_pca.dot(w).reshape(-1, 1) * w

return self

def transform(self, X):

return X.dot(self.components_.T)

def inverse_transform(self, X):

return X.dot(self.components_)

​

Scikit Learn 中的 PCA

Scikit Learn 中的 PCA 使用的不是梯度上升法&＃xff0c;而是使用的相应的数学方法。使用方式如下&＃xff1a;

from sklearn.decomposition import PCA

pca &＃61; PCA(n_components&＃61;1)

参数 n_components 表示主成分个数。

由于 PCA 降维会丢失原数据的信息&＃xff0c;Scikit Learn 中的 PCA 在 0

pca &＃61; PCA(0.95)

即保留原数据 95% 的信息&＃xff0c;此时程序会自动得到一个 components_。

借助 kNN 看 PCA

现在借助于 kNN 分类算法来看一看 PCA 的优势。首先使用一个正规的手写数据集 MNIST 数据集&＃xff0c;获取样本数据集的程序为&＃xff1a;

import numpy as np

from sklearn.datasets import fetch_mldata

mnist &＃61; fetch_mldata("MNIST original")

X, y &＃61; mnist[&＃39;data&＃39;], mnist[&＃39;target&＃39;]

# MNIST 数据集已经默认分配好了训练数据集和测试数据集&＃xff0c;即前60000个数据为训练数据

X_train &＃61; np.array(X[:60000], dtype&＃61;float)

y_train &＃61; np.array(y[:60000], dtype&＃61;float)

X_test &＃61; np.array(X[60000:], dtype&＃61;float)

y_test &＃61; np.array(y[60000:], dtype&＃61;float)

先不使用 PCA 来看看 kNN 算法的效率:

from sklearn.neighbors import KNeighborsClassifier

knn_clf &＃61; KNeighborsClassifier()

%time knn_clf.fit(X_train, y_train)

此时 fit 的过程消耗的时间为&＃xff1a;

CPU times: user 29.6 s, sys: 306 ms, total: 29.9 s

Wall time: 30.7 s

接着验证测试数据集的准确性&＃xff1a;

%time knn_clf.score(X_test, y_test)

此过程消耗的时间为&＃xff1a;

CPU times: user 10min 23s, sys: 2.05 s, total: 10min 25s

Wall time: 10min 31s

并且测试数据集的正确率为0.9688。

然后在来看看 PCA 的优势&＃xff0c;使用 PCA 时&＃xff0c;设定保留信息为 90%&＃xff1a;

from sklearn.decomposition import PCA

pca &＃61; PCA(0.9)

pca.fit(X_train)

X_train_reduction &＃61; pca.transform(X_train)

knn_clf &＃61; KNeighborsClassifier()

%time knn_clf.fit(X_train_reduction, y_train)

此时 fit 的过程消耗的时间为&＃xff1a;

CPU times: user 317 ms, sys: 5.31 ms, total: 323 ms

Wall time: 323 ms

接着验证测试数据集的准确性&＃xff1a;

X_test_reduction &＃61; pca.transform(X_test)

%time knn_clf.score(X_test_reduction, y_test)

此过程消耗的时间为&＃xff1a;

CPU times: user 1min 15s, sys: 469 ms, total: 1min 15s

Wall time: 1min 17s

可以看出使用 PCA 后时间的消耗大大减少&＃xff0c;而测试数据集的正确率为0.9728&＃xff0c;不仅正确率没有降低还增加了&＃xff0c;这是因为这里的降维过程丢失的信息是无用的信息从而达到了降燥效果。

源码地址