机器学习笔记四：无监督学习

无监督学习是根据类别未知的训练样本解决模式识别中的各种问题

类聚问题Cluster

给定m个未标记的数据集，对其进行分类。使得簇内数据之间具有高的相似性；不同簇数据之间具有高的差异性。

K-means

基于划分的聚类方法，以空间中k个点为中心进行聚类，对最靠近他们的对象归类，不断迭代计算，更新中心点，使得代价最小。

对m个维度为n的数据集

K-means执行步骤：

随机初始化类聚中心：

Randomly initialize K cluster centroids

$\mu_1,u_2,\cdots,u_k\in R^n$

Repeat:

对每个样本数据$x_i$选择距离其最近的类别中心

$c_i = index(1 \to K)\; of\; cluster\; centroid\; closest\; x_i=arg\min_{1\le j\le k}||x_i-\mu_j||$

更新类别中心：

$\mu_j = \frac{1}{|c_j|}\sum_{i\in c_j}x_i$

Until :

$|\mu_j-\mu_j'|\le\epsilon$

其代价函数为：

$J(\mu)=\frac{1}{m}\sum_{i=1}^m||x_i-\mu_{c_i}||^2$

求其对$\mu_j$的偏导时期为零，有：

$\mu_j = \frac{1}{|c_j|}\sum_{i\in c_j}x_i$

当运行K-means的时候，需要有K个聚类中心值，其中K值要比训练样本的数量m小。其中初始化聚类中心这一步十分的重要，如果初始化不好，会造成产生局部最优的结果。

运行多次K-means算法，比较代价函数，选取代价最小的。

类别中心的数目的选择

肘部法则：其中需要做的就是改变K的值，然后运行K-means算法，最后计算代价函数。重复改变K的值按照同样的方法运行，就会得到一条曲线。一般会得到一条曲线，随着K值的不断增加，代价函数的值快速下降，超过某个值后代价函数的下降速度变慢。
实际

k-means算法优缺点对比

优点：

是解决聚类问题的一种经典算法，简单、快速。它的时间复杂度为$O(t\cdot n \cdot k)$其中t为迭代次数，n为样本数，k为所需划分簇的数目。
对处理大数据集，该算法保持可伸缩性和高效性。
当簇近似为高斯分布时，它的效果较好。

缺点：
在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用。
必须实现给出k(要生成的簇的数目)，而且对初值敏感，对于不同的初始值，可能会导致不同结果。
不适用于发现非凸形状的簇或者大小差别很大的簇。
因为求取的是均值，所以其对噪声和孤立点数据敏感。其可作为其它算法的基础，如谱聚类。

数据压缩

将高维的数据通过各种方法降低到低维空间中，也是一种无监督学习问题。

PCA主成分分析

对高维数据寻找一个低维空间，将数据全部投影到该空间上，使投影的误差最小。

步骤：

预处理数据，均值归一化
计算协方差矩阵
$\Sigma=\frac{1}{m}\sum_{i=1}^mx_ix_i^T$
对协方差矩阵进行奇异分解
$svd(\Sigma)=[U,S,V]$
取矩阵U中的前k列
$U_{reduce}=[u_1,u_2,u_3,\cdots,u_k]^T$
高维数据投影到低维空间用坐标变换式子可得：
$z_i=U_{reduce}^T\cdot x_i$

值得注意的是：

$U_{reduce}^T\cdot U_{reduce}=E$

那么已知低维空间的一个数据，也可将其近似复现于高维空间中

$x_{approx}=U_{reduce}\cdot z$

而这里的k值，被称为主成分数量。

主成分数量选择

PCA是使得平均投影误差最小，即：

$\min \frac{1}{m}\sum_{i=1}^m||x_i-x_i^{approx}||^2$

k值的选取：

选取最小的k值使得：

$\frac{\frac{1}{m}\sum_{i=1}^m||x_i-x_i^{approx}||^2}{\frac{1}{m}\sum_{i=1}^m||x_i||^2}\le 0.01$

即保留99%的差异（99% of variance be retained）

当然也可以保留95%，90%。

上式等价于

$1-\frac{\frac{1}{k}\sum_{i=1}^ks_{ii}}{\frac{1}{n}\sum_{i=1}^ns_{ii}}\le 0.01$ $s_{ii}\in S$

奇异分解得到的S矩阵是对角矩阵，对角线上的元素为协方差矩阵的特征值。