从两种经典聚类算法入门聚类

本文最后更新于:28 分钟前

从两种经典聚类算法入门聚类

K-Means 「最著名的聚类算法」

  • K-Means是一种迭代算法, 每轮迭代可以用两步来描述:
    • 簇分配(cluster assignment)
    • 移动聚类中心(move centroid step)

2聚类为例 做一个简单的步骤描述:

簇分配

  1. 指定两个聚类中心(它们是随机初始化的, 推荐做法是随机取几个样本点本身作为聚类中心)
  2. 根据距离将每个样本点分配给两个聚类中心的其中一个(染色)

移动聚类中心

在刚才, 我们将样本分成了两类, 现在我们分别计算两类样本的均值, 然后将聚类中心移动到样本均值所在的地方

  • 现在, 我们再执行簇分配, 紧接着再移动聚类中心, 一直迭代的执行下去.
  • 结束条件相当的简单, 当聚类中心在两次迭代中几乎没有发生变化时, 就可以认为算法收敛(注意: 这不意味着就已经找到了最优解, 因为K-Means的收敛位置和初始化有关).

对于K聚类的问题, 无非就是将这个问题扩展到K维, 那么K-Means算法的过程可以用下图描述:

对于K-Means的损失函数(aka. distortion func)来说, K-Means的两个步骤都可以被理解为最小化损失函数的过程.

\(对损失函数 J(c, u) 而言, 簇分配是对于c(样本与簇的距离)的最优化, 而移动聚类中心则是u(簇的位置)的最优化\)

K聚类算法的注意事项「多次随机初始化, K值的选取」

多次随机初始化

  • 显然, K聚类算法的初始化能够相当程度上影响收敛时的结果. 最后的结果很可能是局部最优.
  • 一个简单的解决方案就是多次随机初始化, 在K的值较小时(例如不超过10), 这种方案一般都能找到全局最优

K值的选取

  • K-Means算法有一个隐藏的关键点, 即我们 事先知道将样本分为K类, 只是不知道应该如何归类, 那么这个K要如何确定呢? 或者说 有没有''正确''的K值呢? 答案是: 很难说. 但我们有两种常用的选取K的方案, 至少它能取得不错的结果.
    • 肘部法则.
      • 对同一组样本, 我们取不同的K值来做K-Means, 计算它们的损失函数, 并找到“肘关节”, 如下图左边所示, 这个点很可能就是最优点.
      • 然而这并不是一个常用方案, 因为实际上我们得到的曲线很可能是平滑的, 并不能找到明显的“肘部”
    • 根据需求选取K
      • 虽然很难找到所谓正确的K, 但在实际应用时, 我们可以选取不同的K值以实现不同的目的或策略.
      • 以T-shirt生产尺码为例, K=3 和 K=5 都可以做聚类, 根据应用需求来选择.(选择3种以降低成本, 或是选择5种以更好适应顾客需求, 如下图所示)

SC(Spectral Clustering) 「广泛使用」

相比K-Means等传统算法, 谱聚类的优势: 1. 事实上它可以解决一些K-Means不擅长解决的问题 2. 计算量相对小

下图说明了K-Means和SC的契合情况, 以二维平面点的分布为例, 可以说K-Means擅长解决的是凸(convex)分布, 而不擅长解决很不规则的分布.

简单的描述谱聚类的思想:

把所有的数据看做空间中的点,这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高,通过对所有数据点组成的图进行切图,让切图后不同的子图间边权重和尽可能的低,而子图内的边权重和尽可能的高,从而达到聚类的目的。

接下来简单的推导一下SC的过程

假如有K个类别, 那么要做出K-1次切图(CUT)

看起来整个系统的COST, 就是所有部分两两之间的COST之和, 也就是说假如有A B C三个部分, \(整体COST = W(A,B)+W(B,C)+W(A,C)\). 但实际上这是不对的, 因为没有考虑到每个部分顶点数和边数不同, (除非最理想情况)仅仅minimize这个函数是无法得到最优解的.

在了解以下几点后, 我们就能得出普遍情况下整体COST的计算方法了

  • 考虑顶点和边数量不同. 解决的最好方式就是引入 每个部分的所有顶点的度之和作为分母来平均化 (单个顶点的度, 指的是所有与之相连的边的权重之和)
  • 注意 \(A_补\)是除了A之外的所有其它部分的意思, 假如有A B C三个部分\(W(A, A_补) = W(A,B)+W(A,C)\)

$COST(G) = _{i=1}^K $, 其中 \(\Delta = degree(A) = A中包含的所有顶点的度数之和\)

也可以写作: \(COST = \sum\limits_{i=1}^K \frac{W(A_i, A_{i补})}{\Sigma_{j \in A_i}d_j}, d_j为这个点的度\)

我们已经从直观的角度了解了系统的COST构成, 但在机器学习领域, 我们还需要做的就是将整个问题矩阵化.

  1. 用矩阵表示聚类的结果(其中的\(y_i\)被称为indicator vector)

  1. 用矩阵表示COST FUNC

现在我们已经明确, 只需要将 \(OP^{-1}\)求出来, 就能够得到COST的值, 但对于一次分类的结果, 在计算其COST时, 我们只掌握了两个矩阵的信息, 即聚类的 指示矩阵 Y和距离代价(邻接矩阵)矩阵 W, 所以现在的问题就转变成了, 已知Y和W 求解O和P

  • 求解P的过程如下:

  • 求解O的过程如下:

综上, 我们终于得到了矩阵化表达的COST(也就是\(\hat{Y}\)) \[ COST = \hat{Y}=argmin\{tr(Y^TLY\space (Y^TDY)^{-1}) \} ; \space 其中L(Laplacian \space matrix) = D-W \]