1.K-means

KMeans算法通过试图分离 n groups of equal variance（n 个相等方差组）的样本来聚集数据
KMeans算法需要指定类别数量
可通过MiniBatch KMeans进行小批次训练，从而扩展到大数量的样本集上
各簇的描述方式为centroids（质心），即簇内为样本的均值
旨在最小化 inertia（惯性）或 within-cluster sum of squared（簇内平方和）的标准的 centroids（质心），其表达式如下：

image.png

Inertia（惯性）, 或 the within-cluster sum of squares（簇内平方和） criterion（标准）,可以被认为是 internally coherent clusters （内部连通聚类）的 measure （度量）。它有各种缺点:

Inertia（惯性）假设簇是 convex（凸的）且具有 isotropic （各项同性），并不是总是这样。它对 elongated clusters （细长的簇）或具有不规则形状的 manifolds 反应不佳。
Inertia（惯性）不是一个 normalized metric（归一化度量）: 我们只知道 lower values （较低的值）是更好的，并且零是最优的。但是在 very high-dimensional spaces （非常高维的空间）中，欧几里得距离往往会变得 inflated （膨胀）（这就是所谓的 “curse of dimensionality （维度诅咒/维度惩罚）”）。在 k-means 聚类之前运行诸如 PCA之类的 dimensionality reduction algorithm （降维算法）可以减轻这个问题并加快计算速度。
KMeans算法有三个步骤：

第一步，选择 initial centroids （初始质心），最基本的方法是从X数据集中选择K个样本。
初始化完成后，K-means 由下面两个步骤之间的循环组成。
第二步，将每个样本分配到其 nearest centroid （最近的质心）。
第三步，通过取分配给每个先前质心的所有样本的平均值来创建新的质心。计算旧的和新的质心之间的差异，并且算法重复这些最后的两个步骤，直到该值小于阈值。换句话说，算法重复这个步骤，直到质心不再显著移动。
给定足够的时间，K-means 将总是收敛的，但这可能是 local minimum （局部最小）的。这很大程度上取决于 initialization of the centroids （质心的初始化）。因此，通常会进行几次 different initializations of the centroids （初始化不同质心）的计算。帮助解决这个问题的一种方法是 k-means++ 初始化方案，它已经在 scikit-learn 中实现（使用 init='k-means++' 参数）。这将初始化 centroids （质心）（通常）彼此远离，导致比随机初始化更好的结果，如参考文献所示。

可以给出一个参数，以允许 K-means 并行运行，称为 n_jobs。给这个参数一个正值使用许多处理器（默认值: 1）。值 -1 使用所有可用的处理器，-2 使用一个，等等。Parallelization （并行化）通常以 cost of memory（内存的代价）加速计算（在这种情况下，需要存储多个质心副本，每个作业使用一个）。