无监督学习
无监督学习
之间学习的都是监督学习，也就是样本都有标签。
而无监督学习的样本是没有标签的，也就是只有输入x，没有输出标记。
无监督学习就是找到隐含在这类无标签数据中的结构，这类算法称为聚类算法（clustering algorithm）。
K-Means算法
k均值算法，先随机生成两个数据，即聚类中心（cluster centroids）。
然后遍历所有数据，和蓝色聚类中心靠近的，就渲染为蓝色；和红色聚类中心靠近的，就渲染为红色。然后移动聚类中心到同颜色点的均值处。
重复上述步骤，直到聚类完成，聚类中心不再变化，样本的分类也不再变化。
通过图像我们可以直观的了解到，使用K均值算法聚类，输入需要样本特征$x^{(i)}$和聚类中心数K。
具体步骤如下：
循环1是根据聚类中心分类，循环2是根据平均值移动聚类中心。其中$c^{(i)}$表示的是$x^{(i)}$到不同聚类中心，距离最小的那个的聚类中心的索引值。
有时候数据的分类不那么明确，比如T-shirt的尺寸。
同样也可以用K均值算法进行聚类。将T-shirt的尺寸根据身高和体重，分类为S、M、L。
优化目标
K均值算法同样有优化目标，或者说代价函数（这里也叫畸变函数）。
代价函数就是样本到聚类中心距离的平方和，而优化目标就是找到代价函数值最小时的$c^{(i)}$和聚类中心$\mu_{k}$，从下图也可以看出两个循环就是为了得到它们。
随机初始化
在实际运用中，一般来说，都是随机选取K个样本点作为聚类中心而不是像上面那样选择非样本点。当然，K的值要小于m。
通常我们都期望随机选取的聚类中心具有比较好的性质
但人生不如意之事十之八九，有时候选择的聚类中心不理想
就会在训练的过程中，导致局部最优解，如下图中右下角那样的结果。
解决这个问题的方法简单粗暴，就是多次随机初始化聚类中心，得到多个拟合结果，然后挑选出代价最小的分类方法 。
选取聚类数量
关于如何确定K值，是一个很难回答的问题，甚至可以说没有确切的答案。但通常我们会采用以下的方法来帮助确定K的大小。
- 肘部法则（Elbow method）
但有些时候，得到的图像看起来像是连续的，不容易判断“肘部“位置。
所以这个方法没办法适用于所有情况，所以通常推荐的方法是：根据你聚类的目的来确定K的数目（感觉是废话）。
降维(Dimensionality Reduction)
除了聚类之外，还有另一种无监督学习算法，叫做降维。
目标I:数据压缩
降维的作用是消除特征冗余，如下图所示，特征$x_{1}$代表cm而特征$x_{2}$代表inches，含义相同，在图像上呈现出线性关系，完全可以只用一个特征来表示。
更一般的，我们可以把两个冗余的特征用一个新的特征来表示，记为$z_{1}$，如下图。从另一个角度来看，也可以认为是把所有数据投影到了绿色的那条线上。
当然，很多时候冗余的特征不只两个，但原理是一样的，比如以3维为例：
目标II：可视化
特征很多的情况下没办法直接可视化。
这时候需要用到降维。
降维之后的特征可能不具有物理意义，但方便画图。
主成分分析问题规划I
主成分分析问题规划（Principle Component Analysis），是目前最流行的降维算法。举个例子简单说明原理：
图为从2维降到1维，PCA要求样本到投影点的距离的（投影误差）平方和最小。
更一般的情况，从n-D投影到k-D，也就是找到k个向量$u^{(1)},u^{(2)},…,u^{(3)}$作为被投影的线性子空间。再用3D投影到2D为例，记住PCA关键是投影误差要最小
- PCA和线性回归的区别
二者毫无联系，虽然有时看上去图像是一样的，但线性回归时预测输出变量，它的代价函数表示的是拟合模型的输出误差，如图左；PCA的代价函数则是投影误差，如图右。
主成分分析问题规划II
- 特征缩放和均值归一化
- 求出$u^{(i)}$
把数据从n维降到k维。
计算协方差矩阵：
其中$x^{(i)}$是nx1维，所以$\Sigma$是nxn维。写成向量形式：$\Sigma=1 / m\left(X^{T} X\right)$
再用svd对协方差矩阵进行奇异值分解：
最后我们需要的是U矩阵（nxn），取它的k个列向量构成矩阵z，再乘上$x^{(i)}$就可以得到$z^{(i)}$。
主成分数量选择
之前提到过如何选择压缩后的维度k是很困难的，但在PCA中有一种很实用的方法，这一节展开说说。
通常来说，选择的k要让平均投影误差/数据总方差小于0.01，这种情况也称为“99%的方差被保留”，这句话代表了投影降维后的效果好。
从上面的公式可以看出，如果需要选择出合适的K，我们可以尝试不同的K值，直到找到能让公式小于0.01为止。
但这种方法显然效率不高，因此最好使用另一种方法。
之前提到的奇异值分解：$[U,S,V]=svd(Sigma)$，其中的矩阵S是一个对角矩阵，如下图所示，取主对角线中的k个值，满足$1-\frac{\sum_{i=1}^{k} S_{i i} }{\sum_{i=1}^{k} S_{ii} } \leqslant 0.01$即可。
压缩重现
如果能从n维降至k维，同理也就能从k维升至n维。只需要把$z^{(i)}$代入$X_{appox} $=$ U_{radue} \cdot z^{(i)}$。就能求出x近似值。
应用PCA的建议
PCA也可以应用在监督学习算法中，只需要将$x^{(i)}$提取出来即可。另外必须要注意的是，把$x^{(i)}$映射到$z^{(i)}$（即求出U）的过程中只能在训练集中运行。
- PCA的应用
（1）压缩数据，加快算法运行效率
（2）可视化：没得办法，我们只能可视化K<3的数据
（3）不要用PCA来防止过拟合，因为PCA不使用标签y，这可能会导致信息的丢失。用正则化就行了，不要皮。
（4）在使用PCA之前，应该先考虑清楚是否真的有必要使用它，直接用原始数据也许就能得出想要的答案。
