常德论坛网站/游戏代理300元一天

什么是无监督学习？

• 先来看看什么是监督学习，一个典型的监督学习例子：
  
  👆一个带有标签的训练集 ，我们的目标是，找到一条能够区分正样本和负样本的决策边界。在监督学习中，我们有一系列的标签，然后我们需要用假设函数来拟合它。作为对比，在无监督学习中，我们的数据并不带有任何的标签，我们得到的数据是这样的👇：
  
  数据集可直接表示为 x⁽¹⁾,x⁽²⁾…,x⁽ⁿ⁾，没有y标签。
  对于这些数据，我们能做的就是在它们中间找到一些结构，而对于这个训练集，通过无监督学习可以将它分成两个簇，成为聚类算法（Clustering algorithm）👇。
  

K-Means算法

• 假设我们有一个无标签的数据集，如下图所示，我们希望将它分为两个簇，使用K-Means聚类算法，步骤如下：👇
  〇未使用K-Means聚类算法的原数据集。
  
  ①第一步是随即生成两点，这两点就叫做聚类中心(Cluster Centroids)，生成两个聚类中心，是因为我们现在希望将数据集分为两个簇👇。
  
  ②K-Means算法是一个迭代算法，它做两件事，第一步是簇分配（Cluster assignment），而第二步是移动聚类中心（Move centroid）。对于第一步而言，簇分配，是在内循环中遍历每一个数据样本点，也就是上图中的绿点，来给它们分配聚类中心（即上图中的红叉和蓝叉，分配依据是绿点距离红/蓝叉谁更近）。之后根据分配结果，将绿叉染成红色或蓝色。
  
  内循环的第二步，即是移动聚类中心，我们要做的就是将红叉和蓝叉（即聚类中心）移动到红点和蓝点的均值处。我们要做的就是找出所有的红点，计算它们的均值，即所有红点的平均位置，然后把红色的聚类中心移动到那里。对于蓝色聚类中心，我们也要做同样的事情。
  
  原图👆，第一次迭代的结果👇。
  
  同样地，根据每个样本点（此时不再是绿点，而是红点或蓝点）距离聚类中心的距离，重新绘制他们的颜色（重新将他们划入新的聚类）👇。
  
  之后要做的是重新移动聚类中心👇。
  
  重新划分聚类：
  
  移动聚类中心：
  
  此时，再次进行K-Means算法的迭代，聚类不会重新分配了，我们说，此时K-Means已经聚合了。
• 用更正式的方式表述K-Means聚类算法：
  
  ①输入：
  1）K的值，即聚类的个数，稍后会给出判定聚类个数的方法。
  2）一系列无标签的数据集。
  ②我们规定 x⁽ⁱ⁾是一个n维的实数向量。
• K-Means算法在做什么：
  
  ①随机生成K个聚类中心，我们称之为μ₁ , μ₂… ,μ_n ∈ Rⁿ。
  ②簇分配：
  
  我们将每一个样本点，依据它离哪个聚类中心更近一点，将其染成对应的颜色。
  其中，c⁽ⁱ⁾ = ( k | min(||x⁽ⁱ⁾-μ_k||)² )。即找出一个k（k = 1,2,3,…,K）使第i个点（i = 1,2,3,…,m，m规定为训练集的样本点个数）到聚类中心 μ_k 的距离最短，c⁽ⁱ⁾即表示这个最短距离对应的聚类中心k。
  ③移动聚类中心：
  
  如：
  
  此时，μ₂是一个n维向量，因为每一个x⁽ⁱ⁾( i = 1,5,6,10 )都是一个n维向量。
  注：如果在迭代过程中，得到了一个没有样本点与之划分为一个簇的聚类中心，我们一般直接将这个聚类中心移除，这样会得到K-1个簇，而不是K个簇。
• K-Means算法的一个其他应用：分离不佳的簇的问题：
  上图是一个比较理想的数据集，很明显，肉眼可见的可以被分为三个簇，而一般情况下，我们得到的数据集是不良的，如下图👇。
  
  上图👆右边的训练集看起来并不能被分为K个簇。
  K-Means可能的分类结果：
  

优化目标

K-Means算法也有一个优化目标函数（在回归问题中，优化目标函数对应于代价函数）。

• 前情回顾
  
  在K-Means算法运行的过程中，我们要对以上两个值进行跟踪，一个是 c⁽ⁱ⁾ ，它表示的是样本 x⁽ⁱ⁾ 当前所属的簇的索引或者序号。另外一个值是μ_k，它表示第k个聚类中心的位置。
• 此处新添加一个值，即μ_c(i)，它表示的是 c⁽ⁱ⁾ 所对应的聚类中心的位置。
  
• 通过以上这些值，我们就可以写出K-Means算法的优化目标：
  
  即：
  
  其中，J的参数 c⁽ⁱ⁾ ( i = 1,2,…,m ) 和 μ_k ( k = 1,2,…,K ) 会随着算法的运行而不断变化。J的具体值是对这一项进行求和，再除以训练样本的个数以得到平均值：
  
  👆即这个距离的平方值：
  
  K-Means算法要做的就是通过不断的迭代找到最合适的参数 c 和 μ 以使代价函数 J 的值最小。
• 优化代价函数的具体的实现方式：
  
  〇不同于梯度下降的同时更新，此处的更新过程需要分布进行。
  ①K-Means算法的第一步是进行簇分配（i从1到m进行循环），以寻找合适的 c⁽ⁱ⁾ 来使代价函数J的值最小，而此时保持μ的值不变。
  ②第二步是聚类中心的移动（i从1到K进行循环）。此处使用聚类中心的位置 μ_k 来优化代价函数J。
  ③保持迭代，直到代价函数最优。

随机初始化

• 前情回顾：
  
  之前我们没有讨论过，如何选择一个K来对K-Means算法进行初始化。
• 随机初始化：
  
  ①当运行K-Means时，我们应该保持K的值小于m（m表示样本点的个数，这一点是显而易见的，因为让簇的堆数大于样本点的个数是没有任何意义的）。
  ②通常的做法是，随机挑选K个训练样本，并让 μ₁ , … , μ_k 等于这K个样本。
  ③一个具体的例子：令K = 2，即想要寻找两个簇。随机挑选两个训练样本，作为聚类中心。
  
  这就是一个随机初始化K-Means算法的方法。但由于是随机挑选，有时跳出来的样本就不会那么幸运了：
  
  可表述为：（假设K = 2时）μ₁ = x⁽ⁱ⁾，μ₂ = x^(j)，其中 i,j = 1,2,3,…,m。
• K-Means算法可能会落在局部最优：
  
  右上为最优解，右下两张图为局部最优解，显然不是最优解。优化的方法是尝试多次随机初始化，而不是仅仅进行一次随机初始化，以降低得到局部最优解的概率。
• 一个随机初始化的例子：
  
  使K-Means算法迭代100次，典型的K-Means算法迭代次数（循环次数）在 50 到 1000 之间。完成100次循环之后，我们会得到簇分类的100种方法，我们最后要做的是在这100种方法中，选取代价最小的一个。
  
  通常的K值在2 ~ 10 之间，通过多次随机初始化，可以优化K-Means算法以避免局部最优解，通常会得到全局最优解。但是当K在100 和 1000 之间，即K很大时，多次随机初始化对算法的优化并不大。

选取聚类个数K

目前最常用的方法，仍然是通过观察图，手动选择聚类的个数。

• 肘部法则
  
  以不同的K值来运行K-Means算法，并将每一次得到的最优的（可能是通过上述多次随机初始化的方法得到的，也可能是仅通过一次随机初始化得到的，也可能是通过其他初始化的方法得到的，总之取一个）代价函数值和K绘制于图像中，我们明显能观察到这个曲线在趋于收敛：
  
  可以观察到，K = 3 为曲线的“拐点”（不是数学意义上的拐点），因此，我们可以选择 K = 3来作为聚类的值。但是，肘部法则在实际的聚类问题中并不常用，因为通常通过这种方法得到的曲线是相当模糊的：
  
  👆找不到一个明显的拐点。
  总之，肘部法则是值得尝试的，但是不能期待它很好地解决实际问题。
  
  在实际应用K-Means问题中，我们可以通过要解决的问题来选择一个何时的K。
  
  如👆，我们可能需要划分S,M,L三个聚类，因此对于图一可以选择K = 3，而同样的，图二可以选择K = 5。