Unsupervised Learning
本章节进入无监督学习,相比于Supervised Learning处理的Training Set,{},Unsupervised Learning需要处理的Training Set是unlabeled{
},是需要算法主动去将样本分类.
Clustering
K-means Algorithm
K-means算法是无监督学习算法的一种,下图所示,K表示期望将数据分成的类别个数.
下面这个例子是使用K-means算法将Training Set分为两类.
因为要分成两类,所以随机初始化两个cluster centroids, red/blue
Cluster assignment step
分别计算Training Set与两个cluster centroids之间的距离,距离red最近的将被染成红色,距离blue最近的将被染成蓝色.
Move Centroids
接下来对上图中red/blue的样本分别求均值(means),并作为新的red/blue centroids位置.
不断重复上述步骤直到cluster centroids位置收敛(converged,不再变化)为止,此时将得到样本最终的分类.
下图是K-means算法的伪代码.
注意
1.求样本和centroids的距离可以使用,该值最小时对应的k即是该样本在此次迭代中的分类
2.,其中n是此次迭代中被分类为k的样本数量,q为此次迭代中被分类为k的所有样本
3.如果发现某一分类中不存在任何样本，一般的做法是删掉这个分类.
Optimization objective
之前学过的监督算法中都有代价函数,我们都需要取优化一个目标,对于k-means算法来说也有代价函数,如下图
是指当前所属的分类.
是指cluster centroids.
是指当前所属的分类对应的cluster centroid.
回过头看k-means算法就类似于一个不断迭代求到使得最小的的搭配,之后在带入到求到代价.
Random Initialization
该如何初始化cluster centroids?
随机选取K个训练样本作为初始的cluster centroids即可.
因为cluster centroids选取的随机性,K-means算法很可能找不到global optima,如上图所示.
为了寻找给优的解,我们使用上图所示的Multiple Random Initialization,在得到的所有选择一组使最小的组合即可.
注意:Multiple Random Initialization在K比较小的时候比如<=10时效果显著,如果K非常大比如100,那么这种方法可能不会如预期中的有用,但是无论K大还是小,上文中提到的选取的方法是Prof.推荐的.
Choosing the Number of Clusters
使用Elbow method选择K,但是有时候函数的拐点没有那么明显,所以这种方式一般不推荐.
另一种方式是从需求出发,意思是"主观上你想要将样本分为几类?",比如下图中的服装尺码,从公司角度考量,是希望分3个尺码使得衣服买的更便宜还是分5个尺码让客户有更多的选择.
Dimensionality Reduction
Dimensionality Reduction可以压缩特征(Data Compression),将样本特征种类压缩的好处在于:
1.可以提升算法执行的效率,节省空间/时间
2.可以图形化数据,毕竟如果样本有>=4个特征种类后很难用图形去描绘他们,如果不能用图形化样本那么就没法很好的理解数据,所以我们一般会将特征值种类压缩到2~3,图形化起来更方便.
2D->1D就是将样本投影到直线上,3D->2D就是将样本投影到平面上.
上图中压缩后的特征其实没有具体的意义.
Principal Component Analysis problem formulation
PCA算法是最小化projection error来压缩特征值.
注意PCA算法和Linear Regression之间的区别,如下图:
上图左是Linear Regression,可以看到纵轴是样本对应的y,而且选择去拟合样本的时候cost function是最小化与y之间的误差.上图右是PCA,cost function是最小化projection error,是垂直于压缩后特征空间的距离.
Principal Component Analysis algorithm
目前最流行的实现Dimensionality Reduction(降维)的算法是PCA.算法步骤如下:
1.Feature Scaling/mean normalization
2.求协方差矩阵并通过svd函数求出U
协方差矩阵
此时U是一个n*n的矩阵
3.求对应的新特征矩阵
size(X)=m*n,size(
summary
还原z->x
size(Z)=m*k,size(
how to choose k
执行一次svd的到S,S是一个对角线矩阵,就是矩阵S对角线上的元素.
Advice for Applying PCA
首先总结PCA的作用:
- 数据压缩(降维),带来的好处如下:
- 减少所需存储空间
- 提升算法速度
- 样本可视化
The PCA projection can be thought of as a rotation that selects the view that maximizes the spread of the data, which often corresponds to the “best” view.
上图是使用PCA加速Logistic Regression的过程:
1.首先抛开向量y,对training set中的样本使用PCA得到和
2.构造新的training set,{(),()...()}
3.执行sigmoid函数预测结果即可
注意:cross-validation和test set中的样本直接使用training set应用PCA得到的
不能因为PCA可以压缩特征就使用PCA去防止overfitting,overfitting的问题还是使用regularization处理.
不推荐盲目的使用PCA去处理原样本,至少在使用PCA之前,先尝试使用原样本进行计算,除非是在行不通,比如计算时间是在太久之类的,才考虑使用PCA,毕竟压缩的数据还是可能会丢掉一些重要的信息,而且是在不考虑y的情况下丢掉的(说不定丢掉的是归类的重要特性).
