1.1 概述
聚类算法又叫无监督算法，其目的是将数据划分有意义或有用的组或簇，划分一般是基于业务需求或建模需求，也可以是探索数据的分布和自然结构，比如在商业中，如果我们手头有大量的当前和潜在客户的信息，我们可以使用聚类将客户划分为若干组，以便进一步分析和开展营销活动，最有名的客户价值判断模型RFM，就常常和聚类分析共同使用。再比如，聚类可以用于降维和矢量量化（vector quantization），可以将高维特征压缩到一列当中，常常用于图像，声音，视频等非结构化数据，可以大幅度压缩数据量。
1.2 sklearn中的聚类算法
聚类算法在sklearn中有两种表现形式，一种是类，需要实例化，训练并使用接口和属性来调用结果，另一种是函数function，只需要输入特征矩阵和超参数，即可返回聚类的结果和各种指标。
输入的数据格式：cluster模块中实现的算法可以采用不同类型的矩阵作为输入，所有方法都接收形状[n_samples，n_features]的标准特征矩阵，这些可以从sklearn.feature_extraction模块中的类中获得。对于亲和力传播，光谱聚类和DBSCAN，还可以输入形状[n_samples，n_sam ples]的相似性矩阵，我们可以使用sklearn.metrics.pairwise模块中的函数来获取相似性矩阵。
1.3 kmeans是如何工作的
kmeans算法将一组N个样本的特征矩阵X划分为K个无交集的簇，直观上看是簇就是一组组聚合在一起的数据，在一个簇中的数据就认为是同一类，簇就是聚类的结果表现。
簇中所有数据的均值通常被称为这个簇的“质心”（centroids）。在一个二维平面中，一簇数据点的质心的横坐标就是这一簇数据点的横坐标的均值，质心的纵坐标就是这一簇数据点的纵坐标的均值。同理可推广至高维空间。
在KMeans算法中，簇的个数K是一个超参数，需要我们人为输入来确定。KMeans的核心任务就是根据我们设定好的K，找出K个最优的质心，并将离这些质心最近的数据分别分配到这些质心代表的簇中去。具体过程可以总结如下：
a)随机抽取K个样本作为最初的质心
b)开始循环：将每个样本点分配带离他们最近的质心，生成K个簇，对于每个簇，计算所有被分到该簇的样本点的平均值作为新的质心
c)当质心的位置不再发生变化，迭代停止，聚类完成
那什么情况下，质心的位置会不再变化呢？当我们找到一个质心，在每次迭代中被分配到这个质心上的样本都是一致的，即每次新生成的簇都是一致的，所有的样本点都不会再从一个簇转移到另一个簇，质心就不会变化了。
1.4 簇内误差平方和的定义和解惑
聚类算法聚出的类有什么含义呢？这些类有什么样的性质？我们认为，被分在同一个簇中的数据是有相似性的，而不同簇中的数据是不同的，当聚类完成之后，我们就要分别研究每个簇中样本都有什么样的性质，从而根据不同的需求定制不同的营销策略。聚类算法的目的是追求“簇内差异小，簇外差异大”。而这个“差异“，由样本点到其所在簇的质心的距离来衡量。
对于一个簇来说，所有样本点到质心的距离之和越小，就可以认为这个簇中的样本越相似，簇内差异就越小，而距离的衡量方法有多种，令x表示簇中的一个样本点，表示该簇中的质心，n表示每个样本点中特征的数目，i表示组成点x的每个特征，这改样本点到质心的距离可以由以下公式距离来度量：
如我们采用欧几里得距离，则一个簇中所有样本点到质心的距离的平方和为：
将一个数据集中的所有簇的簇内平方和相加，就得到了整体平方和（Total Cluster Sum of Square），又叫做total inertia。Total Inertia越小，代表着每个簇内样本越相似，聚类的效果就越好。因此KMeans追求的是，求解能够让Inertia最小化的质心。实际上，在质心不断变化不断迭代的过程中， 总体平方和是越来越小的。我们可以使用数学来证明，当整体平方和最小的时候，质心就不再发生变化了。如此，K-Means的求解过程，就变成了一个最优化问题（KMeans中，我们在一个固定的簇数K下，最小化总体平方和来求解最佳质心，并基于质心的存在去进行聚类，而且，整体距离平方和的最小值其实可以使用梯度下降来求解）。
而这些组合，都可以由严格的数学证明来推导。在sklearn当中，我们无法选择使用的距离，只能使用欧式距离。因此，我们也无需去担忧这些距离所搭配的质心选择是如何得来的了。
1.5 Kmean算法的时间复杂度
除了模型本身的效果外，我们还会使用算法复杂度来度量算法，算法的复杂度分为时间复杂度和空间复杂度，时间复杂度是指执行算法所需要的计算工作量，常用大O符号表示，而空间复杂度就是指执行这个算法所需要的内存空间，如果一个算法的效果很好，但需要的时间复杂度和空间复杂度都很大，那我们将会权衡算法的效果和所需的计算成本之间，比如我们在降维算法和特征工程那两章中，我们尝试了一个很大的数据集下KNN和随机森林所需的运行时间，以此来表明我们降维的目的和决心。
KMeans算法的平均复杂度是O(k*n*T)，其中k是我们的超参数，所需要输入的簇数，n是整个数据集中的样本量，T是所需要的迭代次数（相对的，KNN的平均复杂度是O(n)）。在最坏的情况下，KMeans的复杂度可以写作O（），其中n是整个数据集中的样本量，p是特征总数。在实践中，比起其他聚类算法，k-means算法已经快了，但它一般找到Inertia的局部最小值。 这就是为什么多次重启它会很有用。
1.6 sklearn.cluster.KMeans
class sklearn.cluster.KMeans (n_clusters=8, init=’k-means++’, n_init=10, max_iter=300, tol=0.0001,precompute_distances=’auto’, verbose=0, random_state=None, copy_x=True, n_jobs=None, algorithm=’auto’)
n_clusters是KMeans中的k，表示着我们告诉模型我们要分几类。这是KMeans当中唯一一个必填的参数，默认为8类，但通常我们的聚类结果会是一个小于8的结果。通常，在开始聚类之前，我们并不知道n_clusters究竟是多少，因此我们要对它进行探索。
示例后期补
1.7 聚类算法的模型评估指标
不同于分类和回归模型，聚类算法的模型评估不是一件简单的事。在分类中，有直接结果的输出，并且在分类的结果中有对错之分，所以们我可以使用预测的准确度，混淆矩阵，ROC曲线等等指标来进行评估。回归中，由于要拟合数据，我们有SSE均方误差，有损失函数来衡量模型的拟合程度。但这些衡量指标都不能够使用于聚类。
聚类模型的结果不是某种标签输出并且聚类的结果是不确定的，其优劣由业务需求或者算法需求来决定，并且没有永远的正确答案。那我们如何衡量聚类的效果呢？KMeans的目标是确保“簇内差异小，簇外差异大”，我们就可以通过衡量簇内差异来衡量聚类的效果。Inertia是用距离来衡量簇内差异的指标，因此，我们是否可以使用Inertia来作为聚类的衡量指标呢？Inertia越小模型越好嘛。
可以使用Inertia来衡量，但是这个指标的缺点和极限太大，首先Inertia不是有界的，Inertia是越小越好，是0最好，但我们不知道，一个较小的Inertia究竟有没有达到模型的极限，能否继续提高。第二Inertia的计算太容易受到特征数目的影响，数据维度很大的时候，Inertia的计算量会爆炸，不适合用来一次次评估模型。第三是Inertia受到超参数K的阴线，随着K越大，Inertia注定会越来越小，但是并不代表模型的效果越来越好。第四Inertia对数据的分布有劫色，它假设数据满足凸分布即数据在二维平面图像上看起来是一个凸函数的样子），并且它假设数据是各向同性的（isotropic），即是说数据的属性在不同方向上代表着相同的含义。但是现实中的数据往往不是这样。所以使用Inertia作为评估指标，会让聚类算法在一些细长簇，环形簇，或者不规则形状的流形时表现不佳。
当真实标签已知的时候：虽然在聚类算法中不输入真实的标签，但不代表我们拥有的数据中不一定具有真实的标签，或是一定没有任何参考信息，当然，在现实中，拥有真实标签的情况非常少见（几乎是不可能的）。如果拥有真实标签，我们更倾向于使用分类算法。但不排除我们依然可能使用聚类算法的可能性。如果我们有样本真实聚类情况的数据，我们可以对于聚类算法的结果和真实结果来衡量聚类的效果。常用的有以下三种方法：
当真实标签未知的时候，使用轮廓系数来衡量：在99%的情况下，我们都是对没有真实标签的数据进行探索，也就是对不知道真正答案的数据进行聚类，这样的聚类，是完全依赖于评价簇内的稠密程度（簇内差异小）和簇间的离散程度（簇外差异大）来评估聚类的效果，其中轮廓系数是最常用的聚类算法的评价指标，它是对每个样本来定义的，它能够同时衡量：
1）样本与其自身所在的簇中的其他样本的相似度a,等于样本与同一簇中所有其他点之间的平均聚类
2）样本与其他簇中的样本的相似度b,等于样本与下一个最近的簇中所有点之间的平均距离
根据距离的要求，簇内差异小，簇外差异大，我们希望b永远大于a，并且越大越好，单个样本的轮廓系数的计算公式为：s=这个公式可以解析为：
轮廓系数的范围是（-1,1），其中值越接近1表示样本与自己所在的簇中的样本很相似，并且与其他簇中的样本很不相似，当样本点与簇外的样本更相似的时候，轮廓系数就为负，当轮廓系数为0的时候，则代表两个簇中的样本相似度一致，两个簇本应该是一个簇，可以总结为轮廓系数越接近1越好，负数则表示聚类效果非常差。
如果一个簇中的大多数样本具有比较高的轮廓系数，则簇会有较高的总轮廓系数，则整个数据集的平均轮廓系数越高，则聚类是最合适的，如果许多样本点具有低轮廓系数甚至负值，则聚类是不合适的，聚类的超参数K可能设定得太大或者太小。
当真实标签未知的时候，除了轮廓系数，还可以用卡林斯基-哈拉巴斯系数（Calinski-Harabaz Index，简称CHI，也称为方差比标准），戴维斯-布尔丁指数（Davies-Bouldin）以及权变矩阵（Contingency Matrix）可以使用。
Calinski-Harabaz指数越高越好。对于有k个簇的聚类而言，Calinski-Harabaz指数s(k)写作如下公式：
在线性代数中，一个n×n矩阵A的主对角线（从左上方至右下方的对角线）上各个元素的总和被称为矩阵A的迹（或迹数），一般记作 。数据之间的离散程度越高，协方差矩阵的迹就会越大。组内离散程度低，协方差的迹就会越小， 也就越小，同时，组间离散程度大，协方差的的迹也会越大， 就越大，这正是我们希望的，因此Calinski-harabaz指数越高越好。虽然calinski-Harabaz指数没有界，在凸型的数据上的聚类也会表现虚高。但是比起轮廓系数，它有一个巨大的优点，就是计算非常快速。
1.8 sklearn中的轮廓系数
在sklearn中，我们使用模块metrics中的类silhouette_score来计算轮廓系数，它返回的是一个数据集中，所有样本的轮廓系数的均值。但我们还有同在metrics模块中的silhouette_sample，它的参数与轮廓系数一致，但返回的是数据集中每个样本自己的轮廓系数。
1.9 重要参数init & random_state & n_init:初始质心怎么选？
在kmeans中一个重要的环节就是放置质心，如果有足够的时间，kmeans一定收敛，但inertia可能收敛到局部最小值，是否能够到真正最小值很大程度取决于质心的初始化，init就是决定质心初始化的参数。初始质心放置的位置不同，聚类的结果很可能也会不一样，一个好的质心可以让kmeans避免更多的计算，让算法收敛的更快。如果使用”随机“的方法在样本点中抽取k个样本作为初始质心，这种方法显然不符合”稳定且更快“的需求。为此，我们可以使用random_state参数来控制每次生成的初始质心都在相同位置，甚至可以画学习曲线来确定最优的random_state是哪个整数。一个random_state对应一个质心随机初始化的随机数种子。如果不指定随机数种子，则sklearn中的K-means并不会只选择一个随机模式扔出结果，而会在每个随机数种子下运行多次，并使用结果最好的一个随机数种子来作为初始质心。我们可以使用参数n_init来选择，每个随机数种子下运行的次数。这个参数不常用到，默认10次，如果我们希望运行的结果更加精确，那我们可以增加这个参数n_init的值来增加每个随机数种子下运行的次数。然而这种方法依然是基于随机性的。
在sklearn中，我们使用参数init ='k-means ++'来选择使用k-means ++作为质心初始化的方案。通常来说，我建议保留默认的"k-means++"的方法。
init：可输入"k-means++"，"random"或者一个n维数组。这是初始化质心的方法，默认"k-means++"。输入"k-means++"：一种为K均值聚类选择初始聚类中心的聪明的办法，以加速收敛。如果输入了n维数组，数组的形状应该是(n_clusters，n_features)并给出初始质心。
random_state：控制每次质心随机初始化的随机数种子
n_init：整数，默认10，使用不同的质心随机初始化的种子来运行k-means算法的次数。最终结果会是基于Inertia来计算的n_init次连续运行后的最佳输出
1.10 重要参数max_iter & tol：让迭代停下来
当质心不再移动，Kmeans算法就会停下来。但在完全收敛之前，我们也可以使用max_iter，最大迭代次数，或者tol，两次迭代间Inertia下降的量，这两个参数来让迭代提前停下来。有时候，当我们的n_clusters选择不符合数据的自然分布，或者我们为了业务需求，必须要填入与数据的自然分布不合的n_clusters，提前让迭代停下来反而能够提升模型的表现。
max_iter：整数，默认300，单次运行的k-means算法的最大迭代次数
tol：浮点数，默认1e-4，两次迭代间Inertia下降的量，如果两次迭代之间Inertia下降的值小于tol所设定的值，迭代就会停下
