聚类(Clustering)
聚类是一种无监督学习问题，它的目标是训练没有标签的数据，并把数据分为几个不同的分类，每个分类是一个簇(Cluster)。 目前，K-均值(K-means)算法是一种最常用的聚类算法。
K-均值(K-means)算法
K均值接受两个输入：
- \(K\)（簇的个数）
- 训练集 \({x^{(1)}, x^{(2)}, \dots, x^{(m)}}\)
其中训练集的维度为\(n\)，没有了标签\(y\)，也没有了偏置项\(x_0\)。
它的训练过程如下：
- 随机找出K个点分别作为K个聚类中心点。
- 对每个样本点，找到和它最近的聚类中心点，把样本点归为这个点所对应的簇中。
- 对于每个聚类中心点，把它的坐标重设为该簇中所有样本点坐标的平均值。如果说某个簇中没有任何样本点，通常会舍弃这个聚类中心点，剩下\(K-1\)个；如果要求必须有\(K\)个簇的话，此时可以重新随机选取这个聚类中心点的坐标。
- 重复步骤2、3，直到聚类情况不再变化。
优化目标
定义变量：
- $c^{(i)} = $ 样本\(x^{(i)}\)所属的簇
- $_k = $ 第\(k\)个簇的聚类中心点
- $_{c^{(i)}} = \(样本\)x^{(i)}$所属的簇的聚类中心点
- 代价函数 \(J(c^{(1)}, \dots, c^{(m)}, \mu_1, \dots, \mu_k) = \frac1m\sum_{i=1}^m||x^{(i)} - \mu_{c^(i)}||^2\)，这里代价函数又可称为extortion
则K-均值算法的优化目标为： \[ \min_{\begin{array}{c} c^{(1)}, \dots, c^{(m)} \\ \mu_1, \dots, \mu_k \end{array}} J(c^{(1)}, \dots, c^{(m)}, \mu_1, \dots, \mu_k) \] 结合优化目标来看一下上面提到的训练过程，第二步所做的是保持聚类中心点不变，通过改变样本点所属的簇来最小化代价；而第三步则是保持样本点所属簇不变，通过改变聚类中心点的位置来最小化每个簇内部的距离和误差，提高准确度。
初始化和局部最优
在初始化时，聚类中心的选择有多种不同的方法，其中一种最为常用，其步骤为：
- 确保\(K < m\)
- 随机选\(K\)个样本点
- 把这\(K\)个样本点作为聚类中心
在聚类中也会有局部最优，如在下面的三种分类中，上面的分类就是比较好的结果，而下面两种则是陷入了局部最优的情况。
要确保能得到比较好的分类结果，我们可以尝试多次初始化+进行K-均值聚类的过程(通常为50-1000次之间)，得到多种不同的聚类结果，并取其中代价、误差最小的那种结果。
当\(K\)较小时，这种做法通常能得到相当不错的结果，因为此时能够得出的聚类情况并不非常多，总能找到离最好的聚类较为接近的结果；
而当\(K\)很大时，数据就能有很多中不同的分类方法，也就不那么容易找到很好的结果。
K的选择
在做聚类时，很难确定\(K\)应该为多少，因为常常无法确定到底有多少中类别。
而对于如何选择，一个方法叫做肘部法则(Elbow Method)。Elbow Method的思路是，依次尝试用\(K = 1, 2, \dots\)多个值来尝试进行聚类，并求出Cost Function，再把Cost Function相对\(K\)的关系画在坐标图中。于是，我们或许可以得到这样的一幅图：
这张图看起来很像人的上肢：1到3的部分是上臂，下降较快，而3到8则相当于是前臂，较为平缓。而\(K = 3\)这个点，就相当于手肘的部位，是我们选择的点。
但这种方法通常不会有好的结果，因为得出的图像很可能是模棱两可的，这样我们就没办法找出所谓的“肘部”点。
另一种方法是基于这样的想法：我们做K-均值聚类，通常是为后续的其他工作做铺垫，那么我们在K值的选择上，就去看后续工作的需求是怎样的，需要K为多少比较合适。
降维(Dimensionality Reduction)
降维是除聚类外的另一种无监督学习问题。它有数据压缩和数据可视化的作用。
数据压缩
直观地说，降维就是“降低数据/特征的维度”。比如说有时会有一些表示相同的概念的特征，区别只是在于它们的单位不同，比如千克和磅。而这些特征又可能都不完整，比如前一半数据只有千克的特征，后一半数据只有磅的特征。这时，直接用这两个特征是不行的，需要像下图一样做降维。
如上图所示，原来我们有两个特征\(x_1\)和\(x2\)，我们要做的是：
- 根据原来的数据画出上图中的这些点，
- 画出一条直线，使得所有点到这条线的距离最短。这里直线的选取是为了最小化误差，这点在后面会讲到。
- 把每个点投影到这条直线上，直线是一维的，那么投影上去的点都能用一个实数表示，这个实数就是降维得到的新特征。
该图所示的是二维数据降到一维的例子，其他维度的降维也类似：如三维降到二维则是将样本点都投影到一个平面上。
数据可视化
降维的另一个作用是便于数据分析。我们可以把原数据集中的大量的原始特征通过降维转化为极少数的概括性的新特征。比如说，以一个人为一个样例，我们有这样一些数据：工作收入、股票投资收入、银行存款利息收入、租房收入、日常生活开销、出远门旅行开销、购置电子设备开销。这些数据可以归成两类：收入和开销。那么在做了这样的降维之后，我们可以用新的特征将样本点画在一个坐标系中，以此来观察数据集的生活水平。通过观察点的位置，我们可以看出该样本所记录的人的收入水平和开销水平。
主成分分析(PCA)
主成分分析是降维问题中最常用的算法，它所做的就是找到一个低维的空间，使得降维的误差最小 。这个误差常称为投影误差，因为它可以用所有点到其投影点的距离的平方和来表示。如在上面的例子中，我们的要求就是使得所有点到其在直线上的投影点的距离的平方和最小。
PCA的过程看起来和线性回归很像，但它们有以下不同：
- 在线性回归中，我们拟合出一条直线，希望的是之后根据测试数据的特征\(x\)以及拟合出的直线\(f\)，预测出其标签\(y=f(x)\)；而在PCA中，没有标签\(y\)一说，只有\(x_1\)和\(x_2\)，拟合出来的也不是用来做函数的，而是一个新的维度，在这个维度上，原来在二维平面中的点又有了新的一维坐标。
- PCA和线性回归的拟合时的目标也不同。PCA希望最小化所有点到直线上投影点的距离的平方和最小，而线性回归则是希望所有坐标点的实际标签\(y\)和使用函数预测出的标签\(f(x)\)之间的平方和最小。
数据预处理
在做PCA之前，需要做如下数据预处理：
- 特征均值化(mean normalization)。对样本\(i\)的第\(j\)个特征\(x_j^{(i)}\)，用\(x_j^{(i)}-\mu_j\)来代替，其中\(\mu_j = \frac1m\sum_{i=1}^mx_j{(i)}\)。
- 在有的情况下，还要进行特征缩放。
PCA算法
进行数据预处理。
计算协方差矩阵(covariance matrix)： \[ \Sigma = \frac1m\sum_{i=1}^n(x^{(i)})(x^{(i)})^T \]
计算矩阵\(\Sigma\)的特征向量： \[ [U, S, V] = svd(\Sigma) \]
这里在做降维时，需要的是上一步的\(U\)。它是一个\(n \times n\)的矩阵，当我们想要把\(n\)维数据降为\(k\)维时，就在这里提取\(U\)的前\(k\)列，也就是\(U_{reduce} = U(:, 1:k)\)。
用\(Z = U^TX\)得到降维后的数据。在这个式子中，\(U\)是\(n \times k\)的矩阵，\(X\)是原来的特征矩阵，维度为\(n \times 1\)，则结果\(Z\)就是\(k \times 1\)的矩阵。
参数\(k\)的选择
先讲几个有用的概念：
首先是平均平方投影误差，就是前面提到的投影误差的平方和的均值，其表达式为 \[ \frac1m\sum_{i=1}^m||x^{(i)} - x_{approx}^{(i)}||^2 \] 然后是数据的总方差，代表每个数据的特征向量到全零向量的距离 \[ \frac1m\sum_{i=1}^m||x^{(i)}||^2 \] 我们在选择参数\(k\)时，需要考虑的是找到尽可能小的\(k\)，满足 \[ \frac {\frac1m\sum_{i=1}^m||x^{(i)} - x_{approx}^{(i)}||^2} {\frac1m\sum_{i=1}^m||x^{(i)}||^2} < 0.01 \] 这里0.01代表"99% of variance is retained." 通常，85%到99%的值都是很常用的。
在找\(k\)的时候，一种不错的方法是从\(k=1\)开始尝试，如果不满足上式的条件，则把\(k\)增1，直至找到第一个满足条件的\(k\)为止。
另外在上一节中使用svd求出的特征向量中包含的矩阵\(S\)在这里能用上。在上式中左边的部分可以表示用\(1-\frac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}}\)来代替，那么\(k\)需要满足的条件也就变成了 \[ \frac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}} \ge 0.99 \] 这个方法是只需要调用一次svd即可尝试不同的\(k\)值，效率高。
原始数据的重构造
我们可以根据降维后的数据\(Z\)，重构得到原始的数据\(X\)： \[ X = U_{reduce} \times Z \] 当然，是数据在降维后维度内的投影点的数据。
Some tips
- PCA可以用来加快学习速度。
- 不应该用PCA来减少特征数、防止过拟合，而应该用正则化。
- 先不用PCA，尝试用原始数据，在遇到问题（速度太慢、硬盘/内存不够）时才用PCA压缩一下特征。