1.聚类(Clustering)
1.1 介绍
之前的课程介绍的都是监督学习、而聚类属于非监督学习，在一个典型的监督学习中，我们有一个有标签的训练集，我们的目标是找到能够区分正样本和负样本的决策边界，在这里的监督学习中，我们有一系列标签，我们需要据此拟合一个假设函数。与此不同的是，在非监督学习中，我们的数据没有附带任何标签，我们拿到的数据就是这样的：
在这里我们有一系列点，却没有标签。因此，我们的训练集可以写成只有[图片上传失败...(image-820d5f-1583663013801)] ，我们没有任何标签y。因此，图上画的这些点没有标签信息。也就是说，在非监督学习中，我们需要将一系列无标签的训练数据，输入到一个算法中，然后我们告诉这个算法，快去为我们找找这个数据的内在结构给定数据。我们可能需要某种算法帮助我们寻找一种结构。图上的数据看起来可以分成两个分开的点集（称为簇），一个能够找到我圈出的这些点集的算法，就被称为聚类算法。
聚类算法是无监督学习中的一类算法统称，包括多种具体的算法如K-均值算法、均值偏移聚类算法、DBSCAN聚类算法、层次聚类算法等。
用途
聚类算法的常见用途和使用场景有哪些？
在这门课程的早些时候，我曾经列举过一些应用：比如市场分割。也许你在数据库中存储了许多客户的信息，而你希望将他们分成不同的客户群，这样你可以对不同类型的客户分别销售产品或者分别提供更适合的服务。社交网络分析：事实上有许多研究人员正在研究这样一些内容，他们关注一群人，关注社交网络，例如 Facebook， Google+，或者是其他的一些信息，比如说：你经常跟哪些人联系，而这些人又经常给哪些人发邮件，由此找到关系密切的人群。因此，这可能需要另一个聚类算法，你希望用它发现社交网络中关系密切的朋友。我有一个朋友正在研究这个问题，他希望使用聚类算法来更好的组织计算机集群，或者更好的管理数据中心。因为如果你知道数据中心中，那些计算机经常协作工作。那么，你可以重新分配资源，重新布局网络。由此优化数据中心，优化数据通信。
最后，我实际上还在研究如何利用聚类算法了解星系的形成。然后用这个知识，了解一些天文学上的细节问题。好的，这就是聚类算法。这将是我们介绍的第一个非监督学习算法。
1.2 K-均值算法(K-Means Algorithm)
1.2.1 介绍
K-均值是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。
K-均值算法是一个迭代算法，原理也很简单易懂，为什么叫K？因为我们可以取K个随机点，也就是预先想要分的类别数。该算法的运作流程如下：
1.选择K个随机点作为聚类中心(cluster centroids)；
2.遍历数据集中的每个数据，算出每个数据到K个点的距离，将该点和距离最近的聚类中心聚成一类
3.计算出K个类别，每一类包含的数据点的均值，将该类的聚类中心点移动至均值所在的位置。这便是一次迭代过程
4.重复2~3，直至K个聚类中心都停止移动，完成迭代。
下面用图片的方式演示这一过程：
1.绿色为所有的数据点，这里取K = 2，即选出两个随机点作为聚类中心。
2.遍历数据集中的每个数据点，算出其聚类红点和蓝点的距离，从而聚类到红色类或蓝色类
3.计算出红色和蓝色类别，每一类包含的数据点的均值，将该类的聚类中心点移动至均值所在的位置。
4.重复迭代过程，直到聚类中心点不再改变
最后，这些散乱的样本点，便通过K-Means算法聚成了2类。
1.2.2 数学定义
对于K-means算法，我们指定K个聚类中心(cluster centroids)，输入的样本点属于实数域，维度为m个。随机初始化K个聚类中心点 然后重复迭代过程，如下图所示：
式子里表示第i个样本点到第k个聚类中心的最小距离,不过按照惯例，用距离的平方来表示：
。然后
的计算也很简单，即求所有
的均值，就不写出来了。
1.3 优化目标
K-均值算法为何如此火热 ？因为其不仅对于有明显分类情况的数据有效，对于杂乱的堆在一起的数据同样有效，如下图：
左图中的数据，很明显是可以分为3类的，但右边的数据则堆在一起，不那么好分。假定数据的左边分别表示一个人的身高和体重，则我们T恤厂商想利用这些数据生产3类尺寸的衣服，即可利用K均值算法，舍得K = 3(S、M、L三类衣服)。将这些身高体重数据聚类成3类，从而指导生产。
1.3.1 畸变函数
K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此 K-均值的损失函数（又称畸变函数 Distortion function）为：
其中代表和
最近的聚类中心点。我们的的优化目标便是找出使得代价函数最小的
回顾刚才给出的: K-均值迭代算法， 我们知道，第一个循环是用于减小c引起的代价，而第二个循环则是用于减小μ引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数，不然便是出现了错误。
1.4 随机初始化
1.4.1 初始化过程
在运行 K-均值算法的之前，我们首先要随机初始化所有的聚类中心点，即：1. 我们应该选择K < m，这个很好理解，因为m为训练数据的个数，聚类的类别数永远不会超过样本个数。2.随机选择K个训练数据实例，并令这K个中心点 = K个数据实例
1.4.2 潜在的问题
K-均值的一个问题在于，它有可能会停留在一个局部最小值处，而这取决于初始化的情况。即不同的随机初始化的聚类中心点导致的聚类结果可能不同，如下图：
1.是全局最优的聚类、2.和3.则是比较失败的聚类，他们只收敛到了局部最优解，而没达到全局最优，因为1、2、3采用了不同的初始化聚类中心。
1.4.3 解决措施
为了解决这个问题，我们通常需要多次运行 K-均值算法，每一次都重新进行随机初始化，最后再比较多次运行 K-均值的结果，选择代价函数最小的结果。这种方法在K较小的时候还是可行的，但是如果K较大，这么做也可能不会有明显地改善。
1.5 选择聚类数K
没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的。选择的时候思考我们运用 K-均值算法聚类的动机是什么，然后选择能最好服务于该目的标聚类数。
譬如上一个例子，服装厂为了生成SML三种型号的衣服，将聚类数K 设置为3
当人们在讨论， 选择聚类数目的方法时， 有一个可能会谈及的方法叫作“肘部法则”。 关于“肘部法则”， 我们所需要做的是改变K值，也就是聚类类别数目的总数。我们用一个聚类来运行 K 均值聚类方法。这就意味着，所有的数据都会分到一个聚类里，然后计算成本函数或者计算畸变函数J 。 K代表聚类数字。
我们可能会得到一条类似于这样的曲线。 像一个人的肘部。 这就是“肘部法则”所做的，让我们来看这样一个图，看起来就好像有一个很清楚的肘在那儿。好像人的手臂，如果你伸出你的胳膊， 那么这就是你的肩关节、 肘关节、 手。 这就是“肘部法则”。 你会发现这种模式，它的畸变值会迅速下降，从 1 到 2，从 2 到 3 之后，你会在 3 的时候达到一个肘点。在此之后，畸变值就下降的非常慢，看起来就像使用 3 个聚类来进行聚类是正确的，这是因为那个点是曲线的肘点，畸变值下降得很快。
2. 降维(Dimensionality Reduction)
除了之前讨论的聚类，降维将是我们讨论的第二种非监督学习问题。使用降维的原因主要有：
- 1.数据压缩
- 2.数据可视化
2.1 数据压缩Data Compression
数据压缩不仅仅是压缩数据，节省计算机内存或磁盘空间，同时，也能加快我们的学习算法。
2.1.1 降维：2D -> 1D
本例中我们使用降维来展示一下，其在数据压缩方面的效果，假设数据集有2个特征：厘米、英寸，由于这两个特征维度都是表示长度的，即特征高度重合，故我们可以将其压缩一下，将维度从2维变为1维。
具体做法就是，画出一条如图中绿线所示的直线，将所有点投影至线上，这些点在新线上的特征我们可以用z表示，则2维的特征即转化为了1维的特征，很明显地，这次降维可以大幅压缩数据，理论上可以节约1半存储特征的磁盘空间。
2.1.2 降维：3D -> 2D
理论上，我们可以将降维拓展到任意维度，譬如将有1000个特征维降低到100个特征维度，即1000D -> 100 D，不过，出于方便演示的效果，我们下面这个例子是从3维降维到2维：
图1是3维的特征点云，我们将其投影至一个由z1,z2表示的二维平面上，如图2所示。这时，3个维度消失了，我们可以用新的2维z1,z2来表示特征点。新的平面图如图三所示。
2.2 数据可视化
在许多及其学习问题中，如果我们能将数据可视化，我们便能寻找到一个更好的解决方案，降维可以帮助我们。
假使我们有有关于许多不同国家的数据，每一个特征向量都有 50 个特征（如 GDP，人均 GDP，平均寿命等）。如果要将这个 50 维的数据可视化是不可能的。使用降维的方法将其降至 2 维，我们便可以将其可视化了。
这样做的问题在于，降维的算法只负责减少维数，新产生的特征的意义就必须由我们自己去发现了。
2.3 主成分分析算法
降维和聚类一样，是无监督学习中的两类方法，降维中最常用的算法—主成分分析Principal Component Analysis，简称PCA。在 PCA 中，我们要做的是找到一个方向向量（Vector direction），当我们把所有的数据都投射到该向量上时，我们希望投射平均均方误差能尽可能地小。方向向量是一个经过原点的向量，而投射误差是从特征向量向该方向向量作垂线的长度。
下面给出主成分分析问题的描述：问题是要将n维数据降至k维，目标是找到向量,使得总的投射误差最小。
主成分分析与线性回归的比较：
主成分分析与线性回归看上去有些类似，实际上是两种不同的算法。主成分分析最小化的是投射误差（Projected Error），而线性回归尝试的是最小化预测误差。线性回归的目的是预测结果，而主成分分析不作任何预测。
PCA 将n个特征降维到k个，可以用来进行数据压缩，如果 100 维的向量最后可以用 10维来表示，那么压缩率为 90%。同样图像处理领域的 KL 变换使用 PCA 做图像压缩。但 PCA要保证降维后，还要保证数据的特性损失最小。
PCA 技术的一大好处是对数据进行降维的处理。 我们可以对新求出的“主元”向量的重要性进行排序，根据需要取前面最重要的部分，将后面的维数省去，可以达到降维从而简化模型或是对数据进行压缩的效果。同时最大程度的保持了原有数据的信息。
PCA 技术的一个很大的优点是，它是完全无参数限制的。在 PCA 的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。
利用PCA将特征矩阵从n维减少到k维的过程：
第一步:
是均值归一化。我们需要计算出所有特征的均值，然后令，如果特征在不同数量级，任然需要进行特征缩放处理，即将其除以标准差
第二步：
计算协方差矩阵（covariance matrix）协方差矩阵用符号Σ表示，Σ =
第三步：
是计算协方差矩阵Σ的特征向量（eigenvectors），在 Octave 里我们可以利用奇异值分解（singular value decomposition）来求解(过程略)
2.4 选择主成分数
主成分分析算法中，我们需要将n纬特征转化为k纬新的特征，k即为主成分数量，这个数量怎么确定？这里我们需要了解两个概念：
代表训练集的方差
代表投射的均方误差
我们的目标是在满足均方误差/方差小于给定数如1%的情况下，选择尽可能小的k值，譬如从k = 1开始尝试，不满足再尝试k = 2....。这里比值<1%,我们在PCA中可以用保留99%的方差性来表示，这个值用于描述新特征纬度对样本特征保留的度量。保留率越高越好。
当然，有时候也不一定用1%，可能会用5%或者10%等。
2.5 压缩重现
什么是重建的压缩重现？直观点说就是将已经压缩的很少的纬度还原，回到压缩前很多的纬度的近似。
PCA 作为压缩算法。你可能需要把 1000 维的数据压缩 100 维特征，或具有三维数据压缩到一二维表示。所以，如果这是一个压缩算法，应该能回到这个压缩表示，回到你原有的高维数据的一种近似。所以，给定的𝑧(𝑖)，这可能100 维，怎么回到你原来的表示𝑥(𝑖)，这可能是 1000 维的数组?
如上左图，假设压缩算法将原先2纬特征的向量x1,x2压缩到了一纬z,那么怎么由z回到x1、x2的状态？此时，我们需要借助Ureduce。
Xapprox = Ureduce . z,这里Ureduce是nxk的向量，乘以kx1的向量z，则可以近似得到n纬的向量X，n = 2是即可近似还原成二维的特征。如果平方投影误差不大的话，则这个二维特征就近似=x1和x2，如上右图。
2.6 应用建议
假使我们正在针对一张 100×100 像素的图片进行某个计算机视觉的机器学习，即总共 有 10000 个特征。
1. 第一步是运用主要成分分析将数据压缩至 1000 个特征
2. 然后对训练集运行学习算法。
3. 在预测时，采用之前学习而来的𝑈𝑟𝑒𝑑𝑢𝑐𝑒将输入的特征𝑥转换成特征向量𝑧，然后再进行预测
注:如果我们有交叉验证集合测试集，也采用对训练集学习而来的𝑈𝑟𝑒𝑑𝑢𝑐𝑒。 错误的主要成分分析情况:一个常见错误使用主要成分分析的情况是，将其用于减少过 拟合(减少了特征的数量)。这样做非常不好，不如尝试正则化处理。原因在于主要成分分 析只是近似地丢弃掉一些特征，它并不考虑任何与结果变量有关的信息，因此可能会丢失非 常重要的特征。然而当我们进行正则化处理时，会考虑到结果变量，不会丢掉重要的数据。
另一个常见的错误是，默认地将主要成分分析作为学习过程中的一部分，这虽然很多时 候有效果，最好还是从所有原始特征开始，只在有必要的时候(算法运行太慢或者占用太多 内存)才考虑采用主要成分分析。
