1.无监督学习：简介

聚类算法：第一个无监督学习算法（无标签的数据）

什么是无监督学习呢？
对比：监督学习问题指的是，我们有一系列标签，然后用假设函数去拟合它，作为对比，在无监督学习中，我们的数据并没有任何标签，无监督学习要做的就是将这系列没有标签的数据输入到算法中，然后我们要让算法找到隐含在数据中的结构。例如聚类算法，当然还有一些其他的无监督学习算法，而不单单是簇。

在这里我们有一系列点，却没有标签。因此，我们的训练集可以写成只有x^(1)， x^(2)….. 一直到x^(m)。我们没有任何标签y。因此，图上画的这些点没有标签信息。也就是说，在非监督学习中，我们需要将一系列无标签的训练数据，输入到一个算法中，然后我们告诉这个算法，快去为我们找找这个数据的内在结构给定数据。我们可能需要某种算法帮助我们寻找一种结构。图上的数据看起来可以分成两个分开的点集（称为簇），一个能够找到我圈出的这些点集的算法，就被称为聚类算法。

这将是我们介绍的第一个非监督学习算法。当然，此后我们还将提到其他类型的非监督学习算法，它们可以为我们找到其他类型的结构或者其他的一些模式，而不只是簇。

我们将先介绍聚类算法。此后，我们将陆续介绍其他算法。那么聚类算法一般用来做什么呢？

在这门课程的早些时候，我曾经列举过一些应用：比如市场分割。也许你在数据库中存储了许多客户的信息，而你希望将他们分成不同的客户群，这样你可以对不同类型的客户分别销售产品或者分别提供更适合的服务。社交网络分析：事实上有许多研究人员正在研究这样一些内容，他们关注一群人，关注社交网络，例如Facebook，Google+，或者是其他的一些信息，比如说：你经常跟哪些人联系，而这些人又经常给哪些人发邮件，由此找到关系密切的人群。因此，这可能需要另一个聚类算法，你希望用它发现社交网络中关系密切的朋友。我有一个朋友正在研究这个问题，他希望使用聚类算法来更好的组织计算机集群，或者更好的管理数据中心。因为如果你知道数据中心中，那些计算机经常协作工作。那么，你可以重新分配资源，重新布局网络。由此优化数据中心，优化数据通信。

2.K-均值算法

K-均值是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。

K-均值是一个迭代算法，假设我们想要将数据聚类成n个组，其方法为:

第一步是随机生成两点（聚类中心（两类））
K均值算法是一个迭代算法，它会做两件事，第一件是簇分配，第二个是移动聚类中心。算法内部每次内循环的第一步是要进行簇分配，即我要遍历图中的每个绿点，然后根据每个点是与红色聚类中心更近，还是蓝色聚类中心更近，来将每个数据点分配给两个聚类中心之一。

具体来说
1.遍历你的数据集
然后将每个点染成红色或蓝色，这取决于点是更接近蓝色聚类中心还是红色聚类中心。

2.移动聚类中心
将两个聚类中心，也就是红色和蓝色的叉，将其移动到同色的点的均值处，所以接下来要做的是找到所有红色的点，求出所有红色点的平均位置，然后把红色的聚类中心移动到这里，蓝色聚类中心同理。

3.簇分配步骤：
再次检查所有的无标签数据，然后根据这些点与红色还是蓝色聚类中心更近，将其涂成蓝色或者红色，再重新分配给红色或者蓝色聚类中心。再计算出所有同色点的平均位置，移动红色/蓝色聚类中心。

4.重复2,3，直到你继续进行K均值算法的迭代，聚类中心也不会再改变了，并且点的颜色也不会再改变了。此时，K均值已经聚合了。

更规范的格式写出K均值算法：

接受两个输出：
1.K，表示你想从数据中聚类处的簇的个数
2.一系列无标签的只用x表示的数据集（无监督学习，不需要y值）

同时非监督学习的K均值算法中，约定x^(i)是一个n维实数向量。

K均值聚类算法要做的事：

第一步是初始化K个聚类中心，记作u1,u2...uK。
簇分配步骤：(1)迭代，用c(i)表示第1到第K个最接近x^(i)的聚类中心（看看它离哪个聚类中心更近一些），将其染成对应的颜色。

(2)移动聚类中心
如果存在一个没有点的聚类中心会怎么样？
这时最常见的做法是直接移除那个聚类中心，并最终得到K-1个簇，而不是K个簇。

K均值算法另一个常见应用，它可以用来解决分离不佳的簇的问题。

3.优化目标

之前学习的算法都有一个优化目标函数或者说代价函数，K均值算法也有一个优化目标函数，或者一个用于最小化的代价函数。

求解这个优化目标函数，一方面是因为这将帮助我们对学习算法进行调试，确保K均值算法运行正确。第二点也是最重要的一点，我们也要运用它帮助K均值算法找到更好的簇，并且避免局部最优解。

K均值算法要做的事情就是它要找打c^(i)和ui，也就是能最小化代价函数J的c和u。这个代价函数有时也叫失真代价函数或者K均值算法的失真。

K均值算法实际做的就是，它把两个系列的变量，把它们分成两半，第一组是变量c，然后是变量u。首先它会最小化J关于变量c，接着最小化J关于变量u，然后保持迭代。

我们可以用这个是真函数来调试K均值算法，并帮助我证明K均值是收敛的，并且能够正常运行。

如何用这个方法帮助K均值找到更好的簇？以及帮助K均值避免局部最优解？

4.随机初始化

如何初始化K均值聚类算法？如何使算法避开局部最优解？

我通常用来初始化K均值聚类的方法是随机挑选K个训练样本 ，然后设定u1到uk，让它们等于这K个样本。

上图才是真正的K均值算法初始化的方法，在你实现K均值聚类时，最好使用这种方法。即使随机状态可能会让你的算法最终可能会收敛得到不同的结果，这取决于聚类的初始化状态，随机初始化的状态不同，K均值最后可能会得到不同的结果。

具体而言，K均值算法可能会落到局部最优，就不能很好的最小化畸变函数J。如果你担心K均值算法落在局部最优，如果你想让K均值算法找到最有可能的聚类，我们可以尝试多次随机初始化，并运行K均值算法很多次，以此来保证我们最终能得到一个足够好的结果，一个尽可能好的局部或全局最优值。

选取运行100次的畸变函数值中最小的那一个！事实证明，如果你运行K均值算法时，所用的聚类数相当小，那么多次随机初始化，通常能够保证你能找到较好的局部最优解。保证你能找到更好的聚类。如果K值很大，那么多次使用K均值算法就不会有太大改善。

5.选取聚类数量

K均值聚类中如何选择聚类数量？如何选择参数K的值？
比较好的方法仍然是通过观察可视化的图，或者通过观察聚类算法的输出等，即比较好的方法是手动选择聚类的数目。

在无监督学习中，数据没有标签，因此并不总是有一个明确的答案。因此，用一个自动化的算法来选择聚类数量很困难。

肘部法则：
我们所要做的是改变K，也就是聚类总数，我们先用一个类来聚类，所有的数据都会分到一个类中，然后计算代价函数，即畸变函数J，把它画出来，然后我们再用两个类来跑K均值算法，可能多次随机初始化，也可能只初始化一次，但是在两类的情况下，一般畸变值会小一些，然后再画在这里。再用三个类来跑K均值聚类，很可能得到一个更小的畸变值，再画回到图里，再用四类五类去跑均值算法，最终会得到一条曲线显示随着聚类数量的增多，畸变值下降的曲线。
肘部法则就是观察这个图，可以看到这条曲线有一条肘部，类比于人的肘部。

这将是一种用来选择聚类个数的合理方法。

但也许没有清晰的拐点！所以它是一种值得尝试的方法，但是你不能期望它能解决任何问题。

另外一种，如果下游目标能给你一个评估标准，那么决定聚类数量更好的方式是看哪个聚类数量能更好地应用于后续目的。

这就给了我们另一种方法去选择聚类数量，你可以从下游的角度去思考多少个分类能满足下游要求。

大部分时候聚类数量K仍然是通过手动、人工输入或者我们的经验来决定，一种可以尝试的方法是使用“肘部法则”，但是不能期望每次都有好的效果。选择聚类数量，更好的思路是问自己，运行K均值聚类的目的是什么？

聚类参考资料：

降维(Dimensionality Reduction)

6.动机一：数据压缩

第二种无监督学习问题：降维
你想要使用降维的目的？
一是数据压缩。数据压缩不仅能让我们对数据进行压缩，使数据占用更少的内存或硬盘空间，它还能让我们对学习算法进行加速。

什么是降维？
cm和英寸作为两个特征值，描述的都是物体的长度，存在一定的数据冗余。如果我们能把数据从二维减少到一维，就能减少这种冗余。

那么我们把数据从二维降到一维，究竟意味着什么？

总结一下：如果允许我们通过投影这条绿线上所有的原始样本来近似原始的数据集，那么我只需要一个数就能指定点在直线上的位置，即只用一个数字就可以指定每个训练样本的位置。
这样就能把内存（数据空间）的需求减半。这将允许我们让学习算法运行的更快，同时这也是数据压缩中更有趣的一种应用。

从三维降到二维：

这样的处理过程可以被用于把任何维度的数据降到任何想要的维度，例如将1000维的特征降至100维。

正如我们所看到的，最后，这将使我们能够使我们的一些学习算法运行也较晚，但我们会在以后的视频提到它。

7.动机二：数据可视化

降维的第一个应用时压缩数据
第二个应用就是可视化数据

它能很好的帮助我们对学习算法进行优化，让我们能更好的了解我们的数据，帮助我们更好的对数据进行可视化。

如何可视化这些数据？
如果你有50维的特征，你很难绘制50维的数据。怎么样才能很好的检查这些数据呢？

只用一个数字来概述这50个数字！

但是当你观察降维算法的输出时，你会发现z通常不是你所期望的具有物理意义的特征，我们需要去弄清楚这些特征是什么意思？

通过z1和z2能让你快速捕捉在不同的国家之间两个维度的变化。

记下来PCA（主成分分析），可以进行降维操作，也可以用来实现我们之前提到的压缩数据。

8.主成分分析问题

降维问题最常用的算法叫做主成分分析（PSA）算法，我们先讨论PCA的公式描述（试着用公式准确的表述PCA的用途）

点到投影点的距离比较小！所以PCA所做的是：它会找一个低维平面，然后将数据投影到上面，使蓝色线段的平方最短，这些蓝色线段的长度被称为投影误差。即它会试图寻找一个投影平面对数据进行投影，使得最小化这个距离。

应用PCA之前，通常需要先进行均值归一化和特征规范化，使得特征x1,x2，其均值为0并且其数值在可比较的范围之内。

这也是为什么，主成分分析会选择红色的直线而不是洋红色的直线。

PCA做的就是如果想将数据从二维降到一维，我们要试着找一个向量，假设为u^(i)，使得数据投影后，能够最小化投影误差的方向。该向量不分正负，因为它定义的是同一条直线。

对于N维降到K维，这时不只是想找单个向量，来对数据进行投影，而是想寻找K个方向，来对数据进行投影，来最小化投影误差。对于三维向量，即想把所有的数据点投影到这k个向量展开的线性子空间上。

更正式的，我们想要找出能够最小化投影距离的方式，来对数据进行投影，也就是数据点和投影后的点之间的距离。投影误差就是该点与二维平面上对应的投影点之间的距离，最小化平方投影。

有点类似于线性回归，但PCA不是线性回归，尽管有一点相似，但是是两种不相同的算法。线性归回做的是用所有的x值来预测y。在PCA中特征值都是一样的，计算的是同等的特征值x1,x2...xn。

总计一下PCA所做的事：它试图找到一个低维平面，来对数据进行投影，以便最小化投影误差的平方，以及最小化每个点与投影后的对应点之间的距离的平方值。

怎么找到对数据投影的这个低维平面？

9.主成分分析算法

自主使用主成分分析算法，并且能够用PCA对自己的数据进行降维。

在使用PCA之前，首先要做的是进行数据预处理，执行均值标准化，对数据进行特征缩放（分母sj是特征j的一些测量值（最大值减去最小值），或者是一个特征j的标准偏差）

做完PCA的数据预处理以后，我们要去寻找最小化投影距离的向量了（我们需要想出一个方法计算两个东西，一个是计算这些向量例如u(1),u(2)，如何来计算这些数据？）：

数学上的证明很复杂。
下面是求解过程，我们想要把n维向量降到k维，我们首先要做的是计算协方差，协方差用∑表示，不用于数学求和公式，它表示的是一个矩阵，如何求解矩阵sigma的特征向量？

Octave要使用命令svd()，svd代表奇异值分解，这是一个更高级的分解算法，高级的线性代数应用。eig()函数也可以用来做相同的事，但是svd()函数更稳定。协方差矩阵总是满足在数学上的一个性质叫做正定矩阵。其他编程语言中也会有类似的线性代数库求解奇异值矩阵，它得到的是一个nn矩阵。而你真正需要的是U矩阵，这个U矩阵也将是一个nn矩阵，这个矩阵的列就是u^(1), u^(2), u^(3)...等。

所以我们想要减少数据的维数从n维降到k维，我们需要做的就是提取前k个向量，即我们想投影到数据的方向。

接下来从svd线性代数的数值过程中得到了矩阵U S D，我们将用U矩阵的前k个列获取u(1)-u(k)的向量，一个n*k的矩阵，把它成为Ureduce，这是一类U矩阵被降维的版本，将使用它来对数据进行降维。

接下来计算z！z是k为向量，x将是我们数据集中的例子。

计算矩阵的正确向量化公式：

没有数学证明，但是因为代码量比较少，按照这个步骤进行操作，你的降维算法是可以运行的很好的。

PCA算法是尝试找到一个线或者一个面把数据投影到这个面或者线上以便于最小化平方投影误差。

10.选择主成分的数量

怎么选择PCA算法中的k？

我们希望在平均均方误差与训练集方差的比例尽可能小的情况下选择尽可能小的k值。

如果我们希望这个比例小于1%，就意味着原本数据的偏差有99%都保留下来了，如果我们选择保留95%的偏差，便能非常显著地降低模型中特征的维度了。

我们可以先令k=1，然后进行主要成分分析，获得Ureduce和z，然后计算比例是否小于1%。如果不是的话再令k=2，如此类推，直到找到可以使得比例小于1%的最小k 值（原因是各个特征之间通常情况存在某种相关性）。

还有一些更好的方式来选择k，当我们在Octave中调用“svd”函数的时候，我们获得三个参数：[U, S, V] = svd(sigma)。

其中的S是一个n×n的矩阵，只有对角线上有值，而其它单元都是0，我们可以使用这个矩阵来计算平均均方误差与训练集方差的比例。

在压缩过数据后，我们可以采用如下方法来近似地获得原有的特征：

11.重建的压缩表示

之前把1000维降维到100维的特征向量，如果这是一个压缩方法，那么对应应该有一种近似表示，可以把压缩的数据回到原来的表示：

即原始数据的重构：

12.主成分分析法的应用建议

如何选择K，如何选择低维表示z的维度？

降低维数可以提高算法的运算效率，如何具体去做PCA的一些具体建议？

在计算机视觉中，你有100*100个像素点，如果x^(i)特征向量包含10000个像素强度值，这就是10000维的特征向量。对于这种高维的特征向量，运行学习算法将变得非常缓慢。如果你要使用10000维的特征向量进行logistic回归，或者输入神经网络，或支持向量机，或其他你想要的操作，因为数据太大，包含10000个数字，将会是你的算法运行的非常慢，幸运的是，用PCA算法，可以减少数据的维度，从而使算法运行的更加高效。首先检查已经被标记的训练集，并抽取输入，抽取出这些x，把y先临时放到一边，就得到了一个无标签的训练集。10000维的样本，仅仅抽取了输入的向量，接着用PCA得到原始数据的低维表示，变成了1000维。这就给了我们一个新的训练集，一个新的训练样本，可以把这个低维的训练样本输入可能是神经网络或者是回归算法。对于一个新样本，也是通过PCA算法进行转换后输入到学习算法中。
最后注意一点：PCA所做的是定义一个从x到z的映射，这个映射只能通过在训练集上运行PCA来定义，具体而言，PCA学习的这个映射所做的就是计算一系列参数，进行特征缩放和均值归一化，它还计算Ureduce。
但我们应该只在训练集上拟合这些参数，而不是交叉验证集或者是测试集上。在训练集上找到这些参数后，你可以把这个映射用在交叉验证集或者测试集上的其他样本上。

总结一下：当运行PCA时，仅仅在训练集上的数据上运行，不能用在交叉训练集和测试集数据上，定义了x到z的映射后，可以将这个映射用在交叉验证集或者测试集上的其他样本上。

总而言之，我们讨论了PCA算法的以下应用：
压缩数据
加速学习算法
选择k：需要保留99%的方差
可视化应用

此外，有一种常见的对PCA算法的误用。（尝试使用PCA去防止过拟合）
通过减少数据维度来解决过拟合不是一种很好的方式，相比于正则化。
它会扔掉一部分特征，转换为无标签数据，所以即使99%方差信息被保留，它也有可能扔掉了一些有用信息。

使用PCA的比较好的方式是使用它来提高算法的运算速度，但是使用PCA防止过拟合不是一个好应用，应该使用正则化来防止过拟合。

滥用问题：

有些人在设计机器学习系统的时候，可能会写下这样一个计划：
建议：应该首先考虑使用最原始的数据x(i)，只有这么做不能达到目的的情况下，才考虑使用PCA和z(i)，因此使用PCA之间，与其考虑减少数据维度，不如考虑放弃PCA这一步，在原始数据上直接训练算法往往是更好的。只有当你的算法运行速度很慢，或内存不足，或硬盘空间太大，因此你需要去压缩数据表示，即有强有力的证据证明x(i)不能有效的工作再用PCA。