九、聚类算法

1、聚类算法介绍

  • 一种无监督学习
  • 应用案例
    • 市场细分
    • 社交关系分析
    • 计算中心组织
    • 天文数据分析

2、k-均值算法

（1）K均值 (K-means)算法输入、输出

输入

  • k，将输入分为k个簇
  • x，输入的训练集，n*m矩阵，n个特征，m个数据

输出

  • c，m维向量，c(i)表示第i个输入属于的簇

（2）K均值 (K-means)算法过程

随机初始化K个聚类中心 μ1, μ2, μ3, ...,μK为n维向量
重复 {
(1)簇分配：
	for i = 1 to m
		c(i) := 最接近x(i)的聚类中心uk的索引k（k的取值为1~K）
(2)移动聚类中心：
	for k = 1 to K
		uk := 所有标记为k的点的均值中心
} 直到 聚类中心不变

问题：

  • 对于没有点分配给他的聚类中心，可以选择删掉他，或者随机化一个点给他
  • 对于没有明确分界线的训练样本，也可以使用k均值

（3）K均值 (K-means)算法的代价函数（优化目标函数）

相关定义如上

$$ J(c,\mu) = \frac{1}{m} \sum_{i=1}^{m}||x^{(i)} - \mu_{c^{(i)}}||^2 $$ 代价函数，又称之为失真函数

算法执行过程中，

  • (1)簇分配实际上是 关于c对于J最小化的过程二\(\mu\)不变
  • (2)移动聚类中心 实际上是最小化J关于\(\mu\)值的过程，而c不变

3、如何初始化K均值算法

  • 选择一个K （K < m）
  • 随机选择K个训练样例
  • 设置μ1, μ2, μ3, …,μK依次等于者K个样例

当k很小（2~10） 执行k均值算法10到1000次，选择出代价函数最小的那个聚类的结果作为结果

当k很大 执行1次k均值算法就能得到很好的结果

4、如何选择聚类数目K

（1）肘部算法（Elbow Method）

绘制出代价函数和聚类数目K的函数：

若得到一条类似于人类肘部的函数（单调减） 那么这个肘点就是我们选择的K；

若得到的是比较平滑的线那么，就很难选择合适的K。

（2）根据你的业务目的（下游目的、后续目的）选择K

比如为选择T恤的尺寸聚类，根据具体的市场需求选择K

5、维数约简（数据压缩）

（1）、含义

  • 舍弃一些冗余的特征变量，将2维转化为1维，或者3位转换为2维以此类推

（2）作用

  • 调高算法运行速度
  • 可视化数据

（3）、位数简约算法

  • 主成分分析（PCA）算法

（4）PCA的公式表述

寻找一个低维度的面，使得所有输入X到这个面的距离（投影误差）最短

要将n维样本约简到k维，寻找k个k维的向量u1，u2，…, uk；然后将样本数据映射到这k个向量展开的子空间上，最小化投影误差

看起来类似于线性回归，但是不全是

（5）PCA的实现过程

数据预处理

  • 拿到某组m个无标签样本的训练集，首先进行均值归一化（mean normalization），或者说是特征缩放，参见特征缩放

假设，要将n维样本约简到k维。

首先计算协方差矩阵\(\Sigma\)，为n*n的矩阵 $$ \Sigma = \frac{1}{m} \sum_{i=1}^{m}(x^{(i)})(x^{(i)})^{T} $$ 向量化后 $$ \Sigma = \frac{1}{m} X^TX $$

然后找到一个能计算\(\Sigma\)奇异值分解(eigenvectors)的库函数 在octave中

[U,S,V] = svd(Sigma);
%或者eig(Sigma)
Ureduce = U(:,1:k);
%U 是n*n的矩阵，每一列组成的向量就是我们需要u1, u2, ...,uk。（只抽取前k个）
%叫做Uredure，n*k的矩阵

最后计算

$$ z^{(i)} = U_{redure}^T x^{(i)} $$

在octave中，用于计算一个映射

z = Ureduce'*x
  • \(x^{(i)}\)是n*1维的向量
  • \(z^{(i)}\)是k*1维的向量
  • 最后得到的z就是将维后的样本

或者在octave中直接计算，用于计算训练集

Z =  X * Ureduce;
  • Z 是m*k的矩阵
  • X 是m*n的矩阵

（5）从压缩过的数据恢复到原数据

$$ X_{approx}^{(i)} = U_{reduce} z^{(i)} $$

（6）如何选择PCA算法中K（主成分的数量）

概念 平均投影误差： $$ \frac{1}{m} \sum_{i=1}^{m} ||x^{(i)} - x_{approx}^{(i)} ||^2 $$

数据总变化 $$ \frac{1}{m} \sum_{i=1}^{m} ||x^{(i)}||^2 $$

得到一个计算差异性的公式 $$ \frac{ \frac{1}{m} \sum_{i=1}^{m} ||x^{(i)} - x_{approx}^{(i)}||^2 }{ \frac{1}{m} \sum_{i=1}^{m} ||x^{(i)}||^2 } \le 0.01 $$ 这样程PCA算法保留了原数据的99%的差异性

步骤 选择一个要保留的差异性 若使用的是 octave

[U,S,V] = svd(Sigma);

其中的S是一个仅主对角线有数据，其他位置为零的n*n的矩阵 $$ 得到一个计算差异性的公式 = 1 - \frac{ \sum_{i=1}^{k} S_{ii} } { \sum_{i=1}^{n} S_{ii} } $$

（7）使用PCA的应用和建议

  • 调高训练效率——对于有监督学习训练集(x,y)，忽略标签y，得到无标签数据集x，使用PCA算法降维得到z（同时得到Ureduce），在和标签y组合起来的到新的有标签训练集(z,y)来进行训练。当有新的样本到来，在使用Ureduce进行降维后，在应用到模型上。
  • 压缩数据
  • 数据可视化
  • 最好不要用来防止过拟合
  • 一开始最好不要使用PCA优化算法，直到算法运行的十分之慢在尝试使用

十、异常检测

1、异常检测介绍

例子： 一个飞机引擎制造商，当你生产的飞机引擎，从生产线上流出时，你需要进行QA (质量控制测试)。而作为这个测试的一部分，你测量了飞机引擎的一些特征变量。比如，你可能测量了，引擎运转时产生的热量，或者引擎的振动等等。采集这些特征变量，你就有了一个数据集 从x(1)到x(m) 如果你生产了m个引擎的话，这都是你的无标签数据。

异常检测问题可以定义如下： 我们假设，后来有一天，你有一个新的飞机引擎，从生产线上流出。而你的新飞机引擎，有特征变量x-test。所谓的异常检测问题就是，我们希望知道，这个新的飞机引擎是否有某种异常。

因此，当我们建立了x的概率模型之后，对于新的飞机引擎，也就是x-test 如果概率p低于阈值ε，那么就将其标记为异常。

p(Xtest) < ε 标记为异常
p(Xtest) >= ε 正常

用途

  • 检查网站用户是否被盗号，或者是异常用户
  • 工业生产领域，预估产品是否存在问题
  • 计算机集群，异常节点检测

2、高斯分布（正态分布）

公式 $$ p(x; \mu, \sigma^2) = \frac{1}{\sqrt{2\pi}\sigma} exp (- \frac{(x-\mu)^2}{2\sigma ^2}) $$ 说明

  • 图形为一个钟形曲线
  • \(\mu\)，表示图形中心的位置，表示数据集的均值
  • \(\sigma\)，表示图形的高度和宽度，表示数据集的标准差

3、使用高斯分布实现异常检测算法

说明

训练集：m个无标签训练样本的训练集，每个样本为n维向量特征，所以训练集X为m*n的矩阵

那么假设对于每个特征都符合正态分布，且相互独立，则有： $$ p(x) = p(x_1, \mu_1, \sigma_1^2 )p(x_2, \mu_2, \sigma_2^2 )…p(x_n, \mu_n, \sigma_n^2) = \prod_{j=1}^n p(x_j,\mu_j, \sigma_j^2) $$

  • x为n维向量

步骤

  • 选择合适的特征组成训练集
  • 计算出\(\mu_1, …, \mu_n, \sigma_1, …, \sigma_n\)
  • 给一个新的样本x，计算\(p(x)\)
    • 如果\(p(x)< \epsilon\) ，异常
    • 否则正常

4、如何构建一个异常检测系统

（1）评价异常检测算法的性能

假设我们有一些带有标签的数据，y=0代表正常，y=1代表异常

将这些样本分为训练集，交叉验证集（CV），测试集，比例为：6:2:2

使用训练集训练异常检测算法。然后在交叉验证集检测。检测方法见6、偏斜类（skewed classes） 同时选择\(\epsilon \)

（2）如何选择异常检测和监督学习算法

既然训练集带有标签，为什么不选择监督学习的算法呢？如何选择？

以下情况选择异常检测算法

  • 正样本的数目很少（0~20个，监督学习不足以学到很多特征）
  • 负样本的数目很多

以下情况选择监督学习算法

  • 正负样本都很多

（3）如何选择特征变量

绘制每个特种变量的直方图，观察是否是高斯分布（octave语法：hist(x,50)） 对于是高斯分布的变量，直接送入算法 对于不是高斯分布的变量，通过一个变换（例如\(log(x+c),x^c\)），拟合高斯分布

然后通过误差分析检测，分析特征变量选择，添加新的特征，这个特征变量可以是由现存的特征经过合理组合得到的

5、多元高斯分布

参数：\(\mu\)是n维向量， \(\Sigma\) 为n*n的矩阵，表示协方差（见5、维数约简（数据压缩））

公式：

$$ p(x; \mu, \Sigma) = \frac{1}{(2\pi)^{\frac{n}{2}} | \Sigma|^{\frac{1}{2}} } exp(-\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)) $$

  • 其中\(|\Sigma|\) 表示行列式，在octave中使用det函数计算

（1）算法实现

给予训练集：\({ x^{(1)},x^{(2)},…,x^{(m)} }\)，每个x为n维向量

计算\(\mu, \Sigma\)： $$ \mu = \frac{1}{m} \sum_{i=1}^m x^{(i)} $$ $$ \Sigma = \frac{1}{m} \sum_{i=1}^{m}(x^{(i)} - \mu)(x^{(i)} - \mu)^{T} $$

对于一个新的样本x计算： $$ p(x; \mu, \Sigma) = \frac{1}{(2\pi)^{\frac{n}{2}} | \Sigma|^{\frac{1}{2}} } exp(-\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)) $$

标记异常： $$ p(x) < \epsilon $$

（2）普通和多元高斯分布的关系

普通高斯分布是多元高斯分布的特例

（2）如何选择两种模型

普通模型

  • 更加常用，但是如果要捕捉两个特征变量有相关性，需要构造新的特征变量例如(x = cpu负载/内存)
  • 运算量小
  • m可以很小

多元高斯模型

  • 不常用，当时可以捕捉到特征变量之间的相关性
  • 运算量大
  • 必须满足m>n或者说，\(\Sigma\)可逆，一般来说满足 m>10n，避免出现线性相关性的特征

十一、推荐系统

研究推荐系统的动机：

  • 科技公司内最大的应用
  • 可以作为学习算法自动选取随机变量的例子

1、预测电影评分

给你一些电影和用户，用户对某些电影进行打分，要求通过这些数据，预测出用户没打过分电影的分数

电影名用户A用户B用户C用户D浪漫指数x1动作指数x2
电影155000.90
电影25??01.00.01
电影3?40?0.990
电影400540.11.0
电影5005?00.9

用户可以给电影评分0~5

定义

  • \(n_u\)表示用户的数目
  • \(n_m\)表示电影的数目
  • \(r(i,j)=1\)表示用户j评价的电影i
  • \(y^{(i,j)}\) 表示用户j给电影i的评分
  • \(m^{(j)}\)表示用户j评价过的电影的数目

2、基于内容的推荐系统

假设每部电影都含有几个特征来描述，例如电影有x1表示电影的浪漫指数，x2表示电影的动作性，所以 \(x^{(i)}\)表示第i个电影的特征，此时为3维向量（加上x0=1）

对于每个用户j，训练参数\(\theta^{(j)}\) 为3（根据内容的特征数得到）维向量，训练的过称为：将每个已评价的电影的特征为训练集的X，电影的评分为y，X-y构成的有便签训练集，使用监督学习（如线性回归）算法训练处参数。再带入未评分的电影的特征得到预测的评分。

假设使用线性回归算法，数学上的描述为： 最小化问题： 给一组\(x^{(i)},…,x^{(n_m)}\)，来学习 \(\theta^{(1)}, …,\theta^{(nu)}\) $$ min \frac{1}{2m^{(j)}} \sum_{i:r(i,j)=1} ( (\theta^{(j)})^T (x^{(i)}) - y^{(i,j)} )^2 + \frac{\lambda}{2m^{(j)}} \sum_{k=1}^n (\theta_k^{(j)})^2 $$ 梯度下降法 $$ \displaystyle \min_{\theta^{(1)},\dots,\theta^{(n\_m)}} \frac{1}{2}\sum_{j=1}^{n\_u}\sum_{i:r(i,j)=1}\left((\theta^{(j)})^T x^{(i)}-y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n\_u}\sum_{k=1}^n(x_k^{(j)})^2 $$

其他参考线性回归

3、协同过滤法构建推荐算法

特点：自动学习需要的特征

电影名用户A\(\theta^{(1)}\)用户B\(\theta^{(2)}\)用户C\(\theta^{(3)}\)用户D\(\theta^{(4)}\)浪漫指数x1动作指数x2
\(x^{(i)}\)电影15500??
\(x^{(i)}\)电影25??0??
\(x^{(i)}\)电影3?40???
\(x^{(i)}\)电影40054??
\(x^{(i)}\)电影5005???

假设每部电影的特征未知，例如电影有x1表示电影的浪漫指数，x2表示电影的动作性，但是\(x^{(i)}\)是未知的。 假设我们采访得知每个用户对电影的各种特征的评分，\(\theta^{(j)}\)，例如： \(\theta^{(1)} = [0;5;0]\)，表示，用户A对浪漫性的电影给5分，对动作性电影给0分，同理\(\theta^{(2)} = [0;5;0]\)，\(\theta^{(3)} = [0;0;5]\)，\(\theta^{(4)} = [0;0;5]\) 。 那么对于电影1，\((\theta^{(1)})^T X^{(1)}=5\)，\((\theta^{(2)})^T X^{(1)}=5\)，\((\theta^{(3)})^T X^{(1)}=0\)，\((\theta^{(4)})^T X^{(1)}=0\)，可以看出电影1的x1 = 1.0，x2=0

最小化问题： 给一组\(\theta^{(1)}, …,\theta^{(n_u)}\) 来学习\(x^{(i)},…,x^{(n_m)}\) $$ min \frac{1}{2} \sum_{j:r(i,j)=1} ( (\theta^{(j)})^T - y^{(i,j)} )^2 + \frac{\lambda}{2m^{(j)}} \sum_{k=1}^n (\theta_k^{(j)})^2 $$

梯度下降的算法： $$ \displaystyle \min_{x^{(1)},\dots,x^{(n\_m)}} \frac{1}{2}\sum_{i=1}^{n\_m}\sum_{j:r(i,j)=1}\left((\theta^{(j)})^T x^{(i)}-y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{i=1}^{n\_m}\sum_{k=1}^n(x_k^{(i)})^2 $$

而，与根据内容的推荐相比，求解的方程相同。

协同过滤法 随机初始化\(\theta\) -> 得到 x，再得到 \(\theta\)，依次迭代

也就是说： a.给一组\(x^{(i)},…,x^{(n_m)}\)，来学习 \(\theta^{(1)}, …,\theta^{(nu)}\) $$ \displaystyle \min_{\theta^{(1)},\dots,\theta^{(n\_m)}} \frac{1}{2}\sum_{j=1}^{n\_u}\sum_{i:r(i,j)=1}\left((\theta^{(j)})^T x^{(i)}-y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n\_u}\sum_{k=1}^n(\theta_k^{(j)})^2 $$

b.给一组\(\theta^{(1)}, …,\theta^{(n_u)}\) 来学习\(x^{(i)},…,x^{(n_m)}\) $$ \displaystyle \min_{x^{(1)},\dots,x^{(n\_m)}} \frac{1}{2}\sum_{i=1}^{n\_m}\sum_{j:r(i,j)=1}\left((\theta^{(j)})^T x^{(i)}-y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{i=1}^{n\_m}\sum_{k=1}^n(x_k^{(i)})^2 $$

a. sum-每个用户(sum-关于该用户的每个电影的评分) b. sum-每个电影(sum-关于该电影的每个用户的评分)

合并起来，为一个最小化问题 $$ J(x^{(i)},…,x^{(n_m)},\theta^{(1)}, …,\theta^{(nu)}) = \frac{1}{2} \sum_{j:r(i,j)=1} \left((\theta^{(j)})^T x^{(i)}-y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{i=1}^{n\_m}\sum_{k=1}^n(x_k^{(i)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n\_u}\sum_{k=1}^n(\theta_k^{(j)})^2 $$

注意 不需要添加：x0=1

算法步骤

  • 随机初始化化\(x^{(i)},…,x^{(n_m)},\theta^{(1)}, …,\theta^{(nu)}\)
  • 使用梯度下降或者高级算法迭代求参数 假设使用梯度下降法

\(i=1,…,n_m\)

$$ x_k^{(i)} = x_k^{(i)} - \alpha( \sum_{j:r(i,j)=1} ( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} )\theta_k^{(j)} + \lambda x_k^{(i)}) $$ \(j=1,…,n_u\) $$ \theta_k^{(j)} = \theta_k^{(j)} - \alpha( \sum_{i:r(i,j)=1} ( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} )x_k^{(i)} + \lambda \theta_k^{(i)}) $$

  • 对于一个用户的参数 \(\theta \) 和得到的电影的特征的\(x\) 得到用户未评分的电影的得分：\(\theta^Tx\)

4、向量化协同过滤算法实现

（1）参数向量化

电影名用户A用户B用户C用户D浪漫指数x1动作指数x2
电影155000.90
电影25??01.00.01
电影3?40?0.990
电影400540.11.0
电影5005?00.9
  • n_m = 5，表示产品的数目
  • n_u = 4，表示用户的数目
  • \(y^{(i,j)}\) 用户j对用产品j的评分

$$ Y = \begin{bmatrix} 5&5&0&0\
5&?&?&0\
?&4&0&?\
0&0&5&4\
0&0&5&? \end{bmatrix} $$

Y矩阵的另一种描述： $$ Y = \begin{bmatrix} (\theta^{(1)})^T (x^{(1)}) & (\theta^{(2)})^T (x^{(1)}) & \cdots & (\theta^{(n_u})^T (x^{(1)}) \
(\theta^{(1)})^T (x^{(2)}) & (\theta^{(2)})^T (x^{(2)}) & \cdots & (\theta^{(n_u})^T (x^{(2)}) \
\vdots & \vdots & \ddots & \vdots \
(\theta^{(1)})^T (x^{(n_m)}) & (\theta^{(2)})^T (x^{(n_m)}) & \cdots & (\theta^{(n_u})^T (x^{(n_m)}) \
\end{bmatrix} $$

  • \(\theta^{(j)}\)表示用户j的模型
  • \(x^{(i)}\)表示产品i的特征
  • \( (\theta^{(j)})^T (x^{(i)}) \)表示用户j对用产品j的评分

所有产品的特征的矩阵 $$ X = \begin{bmatrix} \cdots & (x^{(1)})T & \cdots \
\cdots & (x^{(2)})T & \cdots \
\vdots & \vdots & \vdots\
\cdots & (x^{(n_m)})T & \cdots \
\end{bmatrix} $$

  • 每一行表示一个产品的特征

所有用户的模型的矩阵

$$ \Theta = \begin{bmatrix} \cdots & (\theta^{(1)})T & \cdots \
\cdots & (\theta^{(2)})T & \cdots \
\vdots & \vdots & \vdots\
\cdots & (\theta^{(n_u}))T & \cdots \
\end{bmatrix} $$

这样Y矩阵可以这么描述

$$ Y = X\Theta^{T} $$

（2） 低秩矩阵分解（协同过滤算法）

对于每一个产品i，我们学习一个特征\(x^{(i)}\)（n维向量）

如何找到一些产品j与产品i相关（相似、可能会购买）？ $$ small || x^{(i)} - x^{(i)} || $$

（3）均值归一化

不使用归一化，那么对于某些用户没有评价过的产品将得到零分

过程 原矩阵 $$ Y = \begin{bmatrix} 5&5&0&0&?\
5&?&?&0&?\
?&4&0&?&?\
0&0&5&4&?\
0&0&5&?&? \end{bmatrix} $$ 均值向量 $$ \mu = \begin{bmatrix} 2.5\
2.5\
2\
2.25\
1.25 \end{bmatrix} $$ 归一化后的Y矩阵 $$ Y = \begin{bmatrix} 2.5&2.5&-2.5&-2.5&?\
2.5&?&?&-2.5&?\
?&2&-2&?&?\
-2.25&-2.25&2.75&1.75&?\
-1.25&-1.25&3.75&-1.25&? \end{bmatrix} $$

对于也测结果，用户j对产品i的评分 $$ (\theta^{(j)})^T(x^{(i)}) + \mu_i $$

十二、大规模机器学习

1、大数据集机器学习

  • 在处理大数据训练集之前，先随机抽取少量训练样本，绘制学习曲线，观察出现的是高偏差还是高方差
    • 高偏差（欠拟合），使用大数据对模型训练有益
    • 高方差（过拟合），使用大数据对训练模型没有显著提升，所以要提高特征变量数

2、随机梯度下降

以线性回归为例：

算法描述： 1、打乱数据集 2、 重复 {    for i:= 1,…,m{      \(\theta_j := \theta_j - \alpha( h_\theta^{(i)} -y^{(i)} )x_j^{(i)} \) (for j = 0,…,n)    } } 直到收敛

  • 一般重复1~10就足够了，这取决于样本大小m的值

3、小批量梯度下降

算法描述： 假设b = 10，m = 1000 重复 {    for i = 1,11,21,31,…,991 {      \(\theta_j := \theta_j - \alpha\frac{1}{m} \sum_{k=i}^{i+9} (h_\theta(x^{(k)})-y^{(k)})x_j^{(k)} \) (for every j=0,..,n)    } } 直到收敛

  • b=2~100

4、如何检测大数据下算法是否收敛

在随机梯度下降中

定义： $$ cost(\theta,(x^{(i)},y^{(i)})) = \frac{1}{2}(h_\theta(x^{(i)}) - y^{(i)})^2 $$

在学习过程中，计算\(cost(\theta,(x^{(i)},y^{(i)}))\)，在使用\(x^{(i)},y^{(i)})\)更新\(\theta\)之前

最后为了检查收敛性，每进行1000（假设）次迭代，就计算出前一步计算的cost函数的均值，绘制出图形

动态选定学习参数\(\alpha\)，例如 $$ \alpha = \frac{const1}{iterationNumber + const2} $$

5、在线学习

（1）算法描述

（假设使用逻辑回归） 一直重复 {    当用户给予一组新的数据(x,y)    使用(x,y)更新\(\theta\):     \(\theta_j := \theta_j - \alpha(h_\theta^{(x)}-y)x_j\) (j=0,…,n) }

  • 实际上每各个训练数据只被使用了一次，让后丢弃，对于拥有大流量的网站，会拥有很好的效果

（2）在线学习的例子

产品搜索（预估点击率CTR）

  • 用户输入关键字，提供最佳的10个推荐结果
  • x = 产品的特征，有许多搜索关键词构成。
  • y = 1 表示用户将会认同这个产品，否则 y = 0

6、映射约减和数据并行性

假设我们要处理线性回归问题，m = 400，使用梯度下降

  • 将数据等切分为几份（4份，每份100个）
  • 将数据子集分给4台设备计算求和项\( temp_j = \sum h_\theta^{(i)} -y^{(i)} )x_j^{(i)} \)
  • 将4个结果临时传送给一台机器，进行合并操作，完成\(\theta \) 的更新

运用映射约简的前提：

  • 将机器学习的问题描述成训练样本的某种求和（包含\(\sum\)项）