week 8

1.K-Means algorithm
K均值算法是最普及的clustering算法，算法接受一个无标签的数据集，然后将数据聚类成不同组。本质上其是一个迭代算法，假设我们要将数据聚类成n组，其方法为：
首先随机选择k个点，作为cluster centroid，对于数据集中的每一个数据，将其与最近的聚类中心绑定，与其他的同一个中心点的所有点聚成一类，计算这些同一聚类的点的均值，并将聚类中心移动到这个位置，重复上述步骤直到聚类中心无法再移动。
用$\mu_1,\mu_2,\mu_3...\mu_k$来表示聚类中心，用$c^{(1)}，c^{(2)}，c^{(3)}...c^{(m)} $来存储第i个数据与最近的聚类中心的索引。K-Means algorithm的伪代码如下：
![](https://leanote.com/api/file/getImage?fileId=59964938ab644155da000814)
算法分为2个步骤，第一步是为每一个样本赋值，计算其应该属于的类；第二步是中心的移动，即对聚类中心重新赋值。
K均值算法也可以将没有明显边界的样本族分类，如下图的衬衫尺寸的问题：
![](https://leanote.com/api/file/getImage?fileId=59964938ab644155da000813)

2.optimization objective
K均值最小化问题就是将样本与聚类中心的距离之和最小化，所以其代价方程又称为distortion function：
$J(c_1,c_2...c_m,\mu_1,\mu_2...\mu_k)=\frac 1 m \sum \limits ^m _{i=1}||x^{(i)}-\mu_{c^{(i)}}||$
其中$\mu_{c^{(i)}}$代表与$x^{(i)}$距离最近的聚类中心点，我们的优化目标就是找出使J最小的c和$\mu$，在迭代的过程中J一定是逐渐减小的，否则就出现了错误。

3.random initialization
在运行K-Means算法时我们首先要初始化所有clustering centroid，方法如下：
① 选择$K<m$的实例数量，即聚类中心点的数量要小于实例数量
② 随机选择k个实例，然后令k个中心点和这些实例相等
这可能造成聚类中心点停留在一个局部最小处，如下图所示：
![](https://leanote.com/api/file/getImage?fileId=59964bffab644155da0008c9)
为了解决这个问题，我们通常需要多次运行初始化算法，比较多个代价函数的大小，选择其中最小的一个，但是如果K较大的话就不会有明显的改善。

4.choosing the number of clusters
一般对于聚类数的方法没有明确的规定，都是根据实际问题的需要来选择的，但是可能选择聚类数的时候涉及到一个叫elbow method的方法：
![](https://leanote.com/api/file/getImage?fileId=59964cf8ab644155da0008f8)
很明显，随着K的增长畸变函数不断减小，而且在K=3的时候明显的下降，过了3之后就下降的很慢，所以我们一般会将聚类数定为3。

5.data compression
降维算法是一种unsupervised learning algorithm，有几个可能的原因使你想要降维，首先是data compression，这样做的好处在于减少计算机内存的使用和加快我们采用的学习算法。
关于降维，首先提出一个存在冗余的模型：
![](https://leanote.com/api/file/getImage?fileId=5997b0e7ab644141f900094a)
可以看到这2个参数都是用于表示物体长度的，而且在二者互相转化时还存在由于四舍五入而造成的误差，所以最好只采用一种方式来表示，于是我们可以将所有的点投影到横轴上，如下图所示：
![](https://leanote.com/api/file/getImage?fileId=5997b0e7ab644141f900094b)

6.visualization
降维的第二个动机就是data visualization，首先提出一个模型：
![](https://leanote.com/api/file/getImage?fileId=5997b41fab644144480009ca)
可以看出来在这个模型中存在多个国家，每个国家都有50个特征，将这50维的数据化是不可能的，但要是将其降至二维就可以实现了：
![](https://leanote.com/api/file/getImage?fileId=5997b41fab644144480009c8)

7.principle component analysis
PCA是现在主流的一种降维算法，以二维降至一维的模型为例，我们要做的就是寻找一个vector direction，当我们把所有的数据都投至该向量上时，我们希望投射的平均方差和误差都尽量小：
![](https://leanote.com/api/file/getImage?fileId=5997b41fab644144480009c9)
以此类推，如果要将n维数据降至k维，目标是找到向量$u^{(1)},u^{(2)},u^{(3)}...u^{(k)}$，使得投射的总误差最小。
看起来PCA和linear regression比较相似，但是二者是完全不同的两种算法，直观的理解如下图所示：
![](https://leanote.com/api/file/getImage?fileId=5997b41fab644144480009cb)
其中左边相当于线性回归，其目的在于预测，而右边的主成分分析不需要做任何的预测，只是要使projected error最小化。PCA的一个好处是无参数限制，在计算过程中完全不需要认为设定参数或是根据任何经验模型对计算进行干预，最后结果只与数据有关，对用户是独立的，最大的程度上保留了原有的数据信息。

8.principle component analysis algorithm
利用PCA算法将k维数据降至n维的步骤如下：
① 首先进行均值归一化，我们需要计算出所有特征的均值，然后令$x_j-\mu_j$替换原来的$x_j^{(i)}$,如果特征不在一个数量级上，还需要将其除以标准差$\sigma^2$
② 计算covariance matrix：$\Sigma=\frac 1 m\sum ^n_{i=1}(x^{(i)})(x^{(i)})^T$
③ 计算协方差矩阵的eigenvector，可以在octave中采用singular value decomposition函数来求解：[U,S,V]=svd(sigma)
![](https://leanote.com/api/file/getImage?fileId=59ae09b2ab64413a4b000b44)
上图所示的矩阵U即为一个具有与数据之间最小投射误差的方向向量构成的矩阵，如果我们希望将维度从n维降至k维，我们只需要从U中选取前n个向量，得到一个n*k维度的矩阵，记作$U_{reduce}$，然后通过如下的计算得到要求的新特征的向量$z^{(i)}$：$z^{(i)}$=$U^T_{reduce}*x^{(i)}$，其中x为n*1维的矩阵，因此其结果为k*1维度。

9.choosing the number of principle component
PCA算法主要的用途是减少投射的平均均方误差，训练集的方差为：$\frac 1 m \sum \limits ^m_{i=1}||x^{(i)}||^2$,而我们希望的是在保证平均均方训练集方差和误差的比值尽量小时选取尽量小的k值，也就是说如果这个比例小于1%，那就是说原本数据的99%的偏差都保留了下来；如果我们希望保留95%的偏差，那么模型中特征的维度就会明显地得到降低。
我们可以先令k=1，进行PCA算法，获得$U_{reduce}$和z，然后利用此方法计算这个比例是否小于1%，如果不小于的话继续增加k值，以此类推，直到找到满足上述的k值。
对于k值得选择上还有一个比较好的方法，就是利用octave中的svd函数的时候，我们会获得3个参数，U,V,S，其中S是一个n*n的矩阵，只有对角线上有值，其它位置都为0，我们可以利用这个矩阵来计算平均均方误差与训练集方差的比例：
![](https://leanote.com/api/file/getImage?fileId=59ae108bab64413c80000c8c)
在进行过数据压缩后，我们可以通过采用如下的方法来近似的获得原有的特征：$x^{(i)} _{approx}=U_{reduce} z^{(i)}$,这一过程称为data reconstruction。

10.advice for applying PCA
以一个图像识别的实例为例，如果我们正在对一个100*100像素的图片进行处理，即一共有10000个特征，首先我们要将其压缩至1000个特征以减小运算量，然后对训练集进行学习算法，在预测时采用之前提到的$U_{reduce}$将输入特征x转换成特征向量z，然后在进行预测。
在这一过程中会产生的一些错误：将PCA算法应用于减少过拟合，也就是通过减少特征的方式来减少过拟合的情况，会导致高偏差，其效果不如换为正则化处理。
另一个常见的错误是默认PCA为学习过程中的一部分，这么做虽然会有一些积极的效果，但是在学习的过程中还是从原有特征开始比较好，只有在算法运行过慢时才考虑PCA。