机器学习 | KMeans聚类分析详解

数据STUDIO

发布于 2021-06-24 10:02:10

3.6K0

发布于 2021-06-24 10:02:10

文章被收录于专栏：数据STUDIO

大量数据中具有"相似"特征的数据点或样本划分为一个类别。聚类分析提供了样本集在非监督模式下的类别划分。聚类的基本思想是"物以类聚、人以群分"，将大量数据集中相似的数据样本区分出来，并发现不同类的特征。

聚类模型可以建立在无类标记的数据上，是一种非监督的学习算法。尽管全球每日新增数据量以PB或EB级别增长，但是大部分数据属于无标注甚至非结构化。所以相对于监督学习，不需要标注的无监督学习蕴含了巨大的潜力与价值。聚类根据数据自身的距离或相似度将他们划分为若干组，划分原则是组内样本最小化而组间距离最大化。

常见聚类算法聚类效果对比图

聚类分析常用于数据探索或挖掘前期

没有先验经验做探索性分析
样本量较大时做预处理

常用于解决

数据集可以分几类；每个类别有多少样本量
不同类别中各个变量的强弱关系如何
不同类型的典型特征是什么

一般应用场景

群类别间的差异性特征分析
群类别内的关键特征提取
图像压缩、分割、图像理解
异常检测
数据离散化

当然聚类分析也有其缺点

无法提供明确的行动指向
数据异常对结果有影响

本文将从算法原理、优化目标、sklearn聚类算法、算法优缺点、算法优化、算法重要参数、衡量指标以及案例等方面详细介绍KMeans算法。

KMeans

K均值（KMeans）是聚类中最常用的方法之一，基于点与点之间的距离的相似度来计算最佳类别归属。

KMeans算法通过试着将样本分离到个方差相等的组中来对数据进行聚类，从而最小化目标函数（见下文）。该算法要求指定集群的数量。它可以很好地扩展到大量的样本，并且已经在许多不同领域的广泛应用领域中使用。

被分在同一个簇中的数据是有相似性的，而不同簇中的数据是不同的，当聚类完毕之后，我们就要分别去研究每个簇中的样本都有什么样的性质，从而根据业务需求制定不同的商业或者科技策略。常用于客户分群、用户画像、精确营销、基于聚类的推荐系统。

算法原理

从个样本数据中随机选取个质心作为初始的聚类中心。质心记为

\mu_1^{(0)},\mu_2^{(0)},\cdots,\mu_k^{(0)},

定义优化目标

J(c,\mu)=\min\sum_{i=1}^M||x_i-\mu_{c_i}||^2

开始循环，计算每个样本点到那个质心到距离，样本离哪个近就将该样本分配到哪个质心，得到K个簇

c_i^t<-arg\,\min_k||x_i-\mu_{k}^t||^2

对于每个簇，计算所有被分到该簇的样本点的平均距离作为新的质心

\mu_{k}^{(t+1)}<-arg\,\min_u\sum^b_{i:c_i^t=k}||x_i-\mu||^2

直到收敛，即所有簇不再发生变化。

KMeans迭代示意图

优化目标

KMeans 在进行类别划分过程及最终结果，始终追求"簇内差异小，簇间差异大"，其中差异由样本点到其所在簇的质心的距离衡量。在KNN算法学习中，我们学习到多种常见的距离 ---- 欧几里得距离、曼哈顿距离、余弦距离。

在sklearn中的KMeans使用欧几里得距离：

d(x,\mu)=\sqrt{\sum_{i=1}^{n}(x_i-\mu_i)^2}

则一个簇中所有样本点到质心的距离的平方和为：

Cluster\,Sum\,of\,Square(CSS)=\sum_{j=0}^{m}\sum_{i=1}^{n}(x_i-\mu_i)^2

Total\,Cluster\,Sum\,of\,Square=\sum_{l}^{k}CSS_l

其中，为一个簇中样本的个数，是每个样本的编号。这个公式被称为簇内平方和(cluster Sum of Square)，又叫做Inertia。

而将一个数据集中的所有簇的簇内平方和相加，就得到了整体平方和(Total Cluster Sum of Square)，又叫做Total Inertia。Total Inertia越小，代表着每个簇内样本越相似，聚类的效果就越好。因此 KMeans 追求的是，求解能够让Inertia最小化的质心。

KMeans有损失函数吗？损失函数本质是用来衡量模型的拟合效果的，只有有着求解参数需求的算法，才会有损失函数。KMeans不求解什么参数，它的模型本质也没有在拟合数据，而是在对数据进行一种探索。另外，在决策树中有衡量分类效果的指标准确度accuracy，准确度所对应的损失叫做泛化误差，但不能通过最小化泛化误差来求解某个模型中需要的信息，我们只是希望模型的效果上表现出来的泛化误差很小。因此决策树，KNN等算法，是绝对没有损失函数的。

虽然在sklearn中只能被动选用欧式距离，但其他距离度量方式同样可以用来衡量簇内外差异。不同距离所对应的质心选择方法和Inertia如下表所示, 在KMeans中，只要使用了正确的质心和距离组合，无论使用什么样的距离，都可以达到不错的聚类效果。

距离度量	质心	Inertia
欧几里得距离	均值	最小化每个样本点到质心的欧式距离之和
曼哈顿距离	中位数	最小化每个样本点到质心的曼哈顿距离之和
余弦距离	均值	最小化每个样本点到质心的余弦距离之和

sklearn.cluster.KMeans

语法：

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')

参数与接口详解见文末附录

例：

>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [10, 2], [10, 4], [10, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([1, 1, 1, 0, 0, 0], dtype=int32)
>>> kmeans.predict([[0, 0], [12, 3]])
array([1, 0], dtype=int32)
>>> kmeans.cluster_centers_
array([[10.,  2.],
       [ 1.,  2.]])

KMeans算法优缺点

优点

KMeans算法是解决聚类问题的一种经典算法，算法简单、快速。
算法尝试找出使平方误差函数值最小的个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。

缺点

KMeans方法只有在簇的平均值被定义的情况下才能使用，且对有些分类属性的数据不适合。
要求用户必须事先给出要生成的簇的数目。
对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。
不适合于发现非凸面形状的簇，或者大小差别很大的簇。
KMeans本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性影响。所以在聚类前对数据（具体的说是每一个维度的特征）做归一化（点击查看归一化详解）和单位统一至关重要。此外，异常值会对均值计算产生较大影响，导致中心偏移，因此对于"噪声"和孤立点数据最好能提前过滤。

KMeans算法优化

KMeans算法虽然效果不错，但是每一次迭代都需要遍历全量的数据，一旦数据量过大，由于计算复杂度过大迭代的次数过多，会导致收敛速度非常慢。

由KMeans算法原来可知，KMeans在聚类之前首先需要初始化个簇中心，因此 KMeans算法对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。因初始化是个"随机"过程，很有可能个簇中心都在同一个簇中，这种情况 KMeans 聚类算法很大程度上都不会收敛到全局最小。

想要优化KMeans算法的效率问题，可以从以下两个思路优化算法，一个是样本数量太大，另一个是迭代次数过多。

MiniBatchKMeans 聚类算法

mini batch 优化思想非常朴素，既然全体样本当中数据量太大，会使得我们迭代的时间过长，那么随机从整体当中做一个抽样，选取出一小部分数据来代替整体以达到缩小数据规模的目的。

mini batch 优化非常重要，不仅重要而且在机器学习领域广为使用。在大数据的场景下，几乎所有模型都需要做mini batch优化，而MiniBatchKMeans就是mini batch 优化的一个应用。直接上模型比较MiniBatchKMeans和KMeans两种算法计算速度（样本量1,000,000）

KMeans用时接近 6 秒钟，而MiniBatchKMeans 仅用时不到 1 秒钟

且聚类中心基本一致

>>> KMeans.cluster_centers_
array([[-2.50889102,  9.01143598],
       [-6.88150415, -6.88090477],
       [ 4.63628843,  1.97271152],
       [-8.83895916,  7.32493568]])

>>> MiniBatchKMeans.cluster_centers_
array([[-2.50141353,  8.97807161],
       [-6.88418974, -6.87048909],
       [ 4.65410395,  1.99254911],
       [-8.84903186,  7.33075289]])

mini batch优化方法是通过减少计算样本量来达到缩短迭代时长，另一种方法是降低收敛需要的迭代次数，从而达到快速收敛的目的。收敛的速度除了取决于每次迭代的变化率之外，另一个重要指标就是迭代起始的位置。

2007年Arthur, David, and Sergei Vassilvitskii三人发表了论文"k-means++: The advantages of careful seeding" http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf，他们开发了'k-means++'初始化方案，使得初始质心（通常）彼此远离，以此来引导出比随机初始化更可靠的结果。

'k-means++' 聚类算法

'k-means++'聚类算法是在KMeans算法基础上，针对迭代次数，优化选择初始质心的方法。sklearn.cluster.KMeans 中默认参数为 init='k-means++'，其算法原理为在初始化簇中心时，逐个选取个簇中心，且离其他簇中心越远的样本越有可能被选为下个簇中心。

算法步骤：

从数据即中随机（均匀分布）选取一个样本点作为第一个初始聚类中心
计算每个样本与当前已有聚类中心之间的最短距离；再计算每个样本点被选为下个聚类中心的概率，最后选择最大概率值所对应的样本点作为下一个簇中心

P(X)=\frac{D(x)^2}{\sum_{x\in\chi}D(x)^2}

重复上步骤，直到选择个聚类中心

'k-means++'算法初始化的簇中心彼此相距都十分的远，从而不可能再发生初始簇中心在同一个簇中的情况。当然'k-means++'本身也具有随机性，并不一定每一次随机得到的起始点都能有这么好的效果，但是通过策略，我们可以保证即使出现最坏的情况也不会太坏。

'k-means++' code:

def InitialCentroid(x, K):
    c1_idx = int(np.random.uniform(0, len(x))) # Draw samples from a uniform distribution.
    centroid = x[c1_idx].reshape(1, -1)  # choice the first center for cluster.
    k = 1
    n = x.shape[0] # number of samples
    while k < K:
        d2 = []
        for i in range(n):
            subs = centroid - x[i, :]  # D(x) = (x_1, y_1) - (x, y)
            dimension2 = np.power(subs, 2) # D(x)^2
            dimension_s = np.sum(dimension2, axis=1)  # sum of each row
            d2.append(np.min(dimension_s))
        new_c_idx = np.argmax(d2)
        centroid = np.vstack([centroid, x[new_c_idx]])
        k += 1
    return centroid

重要参数

初始质心

KMeans算法的第一步"随机"在样本中抽取个样本作为初始质心，因此并不符合"稳定且更快"的需求。因此可通过random_state参数来指定随机数种子，以控制每次生成的初始质心都在相同位置。

一个random_state对应一个质心随机初始化的随机数种子。如果不指定随机数种子，则 sklearn中的KMeans并不会只选择一个随机模式扔出结果，而会在每个随机数种子下运行多次，并使用结果最好的一个随机数种子来作为初始质心。我们可以使用参数n_init来选择，每个随机数种子下运行的次数。

而以上两种方法仍然避免不了基于随机性选取个质心的本质。在sklearn中，我们使用参数init ='k-means++'来选择使用'k-means++'作为质心初始化的方案。

init : 可输入"k-means++"，"random"或者一个n维数组。这是初始化质心的方法，默认"k-means++"。输入"k- means++":一种为K均值聚类选择初始聚类中心的聪明的办法，以加速收敛。如果输入了n维数组，数组的形状应该是(n_clusters，n_features)并给出初始质心。 random_state : 控制每次质心随机初始化的随机数种子。 n_init : 整数，默认10，使用不同的质心随机初始化的种子来运行KMeans算法的次数。最终结果会是基于Inertia来计算的n_init次连续运行后的最佳输出。

迭代停止

max_iter : 整数，默认300，单次运行的KMeans算法的最大迭代次数。 tol : 浮点数，默认1e-4，两次迭代间Inertia下降的量，如果两次迭代之间Inertia下降的值小于tol所设定的值，迭代就会停下。

衡量指标

聚类模型的结果不是某种标签输出，并且聚类的结果是不确定的，其优劣由业务需求或者算法需求来决定，并且没有永远的正确答案。那么如何衡量聚类的效果呢?

衡量簇内差异来衡量聚类的效果

簇内平方和：Total_Inertia 肘部法（手肘法）认为图上的拐点就是的最佳值。

# 应用肘部法则确定 kmeans方法中的k
from scipy.spatial.distance import cdist # 计算两个输入集合的每对之间的距离。
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.datasets import make_blobs
plt.style.use('seaborn')
plt.rcParams['font.sans-serif']=['Simhei'] #显示中文
plt.rcParams['axes.unicode_minus']=False #显示负号
X, y = make_blobs(n_samples=5000, centers=4, cluster_std = 2.5, n_features=2,random_state=42)
K=range(1,10)

# 直接计算sse
sse_result=[]
for k in K:
    kmeans=KMeans(n_clusters=k, random_state=666)
    kmeans.fit(X)
    sse_result.append(sum(np.min(cdist(X,kmeans.cluster_centers_,'euclidean'),axis=1))/X.shape[0])
plt.figure(figsize=(16,5))
plt.subplot(1,2,1)
plt.plot(K,sse_result,'gp-')
plt.xlabel('k',fontsize=20)
plt.ylabel(u'平均畸变程度')
plt.title(u'肘部法则确定最佳的K值(1)',fontdict={'fontsize':15})

# 第二种，使用inertia_
L = []
for k in K:
    kmeans = KMeans(n_clusters=k, random_state=666)
    kmeans.fit(X)
    L.append((k, kmeans.inertia_))
a = pd.DataFrame(L)
a.columns = ['k', 'inertia']
plt.subplot(1,2,2)
plt.plot(a.k, a.inertia,'gp-')
plt.xlabel('k',fontsize=20)
plt.ylabel('inertia')
plt.title(u'肘部法则确定最佳的K值(2)',fontdict={'fontsize':15})
plt.xticks(a.k)
plt.show();

输出结果:

但其有很大的局限：

它的计算太容易受到特征数目的影响。
它不是有界的，Inertia是越小越好，但并不知道合适达到模型的极限，能否继续提高。
它会受到超参数的影响，随着越大，Inertia注定会越来越小，但并不代表模型效果越来越好。
Inertia对数据的分布有假设，它假设数据满足凸分布，并且它假设数据是各向同性的（ isotropic），所以使用Inertia作为评估指标，会让聚类算法在一些细长簇，环形簇，或者不规则形状的流形时表现不佳。

其他衡量指标

1、真实标签已知时

可以用聚类算法的结果和真实结果来衡量聚类的效果。但需要用到聚类分析的场景，大部分均属于无真实标签的情况，因此以下模型评估指标了解即可。

模型评估指标	说明
互信息分普通互信息分metrics.adjusted_mutual_info_score (y_pred, y_true)调整的互信息分metrics.mutual_info_score (y_pred, y_true)标准化互信息分metrics.normalized_mutual_info_score (y_pred, y_true)	取值范围在(0,1)之中越接近1，聚类效果越好在随机均匀聚类下产生0分。
V-measure:基于条件上分析的一系列直观度量同质性:是否每个簇仅包含单个类的样本metrics.homogeneity_score(y_true, y_pred)完整性:是否给定类的所有样本都被分配给同一个簇中metrics.completeness_score(y_true, y_pred) 同质性和完整性的调和平均，叫做V-measuremetrics.v_measure_score(labels_true, labels_pred)三者可以被一次性计算出来: metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)	取值范围在(0,1)之中越接近1，聚类效果越好由于分为同质性和完整性两种度量，可以更仔细地研究，模型到底哪个任务做得不够好。对样本分布没有假设，在任何分布上都可以有不错的表现在随机均匀聚类下不会产生0分。
调整兰德系数metrics.adjusted_rand_score(y_true, y_pred)	取值在(-1,1)之间，负值象征着簇内的点差异巨大，甚至相互独立，正类的兰德系数比较优秀，越接近1越好对样本分布没有假设，在任何分布上都可以有不错的表现，尤其是在具有"折叠"形状的数据上表现优秀，在随机均匀聚类下产生0分。

轮廓系数

对没有真实标签的数据进行探索，常用轮廓系数评价聚类算法模型效果。

样本与其自身所在的簇中的其他样本的相似度a，等于样本与同一簇中所有其他点之间的平均距离。
样本与其他簇中的样本的相似度b，等于样本与下一个最近的簇中的所有点之间的平均距离。

根据聚类的要求"簇内差异小，簇外差异大"，我们希望b永远大于a，并且大得越多越好。单个样本的轮廓系数计算为:

s = \frac{b-a}{max(a,b)}\\a组内差异，b组间差异

取值范围越大越好。

越接近 1 表示样本与自己所在的簇中的样本很相似，并且与其他簇中的样本不相似，当样本点与簇外的样本更相似的时候，轮廓系数就为负。
当轮廓系数为 0 时，则代表两个簇中的样本相似度一致，两个簇本应该是一个簇。

语法：

from sklearn.metrics import silhouette_score
# 返回所有样本的轮廓系数的均值
from sklearn.metrics import silhouette_samples
# 返回的是数据集中每个样本自己的轮廓系数
silhouette_score(X,y_pred)
silhouette_score(X,cluster_.labels_)
silhouette_samples(X,y_pred)

例：

L = []
for i in range(2, 20):
    k = i
    kmeans = KMeans(n_clusters=i)
    kmeans.fit(X)
    L.append([i, silhouette_score(X, kmeans.labels_)])
a = pd.DataFrame(L)
a.columns = ['k', '轮廓系数']
plt.figure(figsize=(8, 5), dpi=70)
plt.plot(a.k, a.轮廓系数,'gp-')
plt.xticks(a.k)
plt.xlabel('k')
plt.ylabel('轮廓系数')
plt.title('轮廓系数确定最佳的K值',fontdict={'fontsize':15})

输出结果：

轮廓系数看出，k=3时轮廓系数最大，肘部法的拐点亦是k=3，从数据集可视化图（文末案例）中也能看出数据集可以清洗分割3个簇（虽然初始创建了四个簇，但上面两个簇边界并不清晰，几乎连到一起）。

轮廓系数有很多优点，它在有限空间中取值，使得我们对模型的聚类效果有一个"参考"。并且轮廓系数对数据的分布没有假设，因此在很多数据集上都表现良好。但它在每个簇的分割比较清洗时表现最好。

其它评估指标

评估指标	sklearn.metrics
卡林斯基-哈拉巴斯指数 Calinski-Harabaz Index	calinski_harabaz_score (X, y_pred)
戴维斯-布尔丁指数Davies-Bouldin	davies_bouldin_score (X, y_pred)
权变矩阵Contingency	cluster.contingency_matrix (X, y_pred)

这里简单介绍卡林斯基-哈拉巴斯指数，有个簇的聚类而言， Calinski-Harabaz指数写作如下公式:

S(k) = \frac{Tr(B_k)}{Tr(W_k)}\times\frac{N-k}{k-1}

其中为数据集中的样本量，为簇的个数(即类别的个数)，是组间离散矩阵，即不同簇之间的协方差矩阵，是簇内离散矩阵，即一个簇内数据的协方差矩阵，而表示矩阵的迹。在线性代数中，一个矩阵的主对角线(从左上方至右下方的对角线)上各个元素的总和被称为矩阵A的迹(或迹数)，一般记作。

数据之间的离散程度越高，协方差矩阵的迹就会越大。组内离散程度低，协方差的迹就会越小，也就越小，同时，组间离散程度大，协方差的的迹也会越大，就越大，因此Calinski-harabaz指数越高越好。

虽然calinski-Harabaz指数没有界，在凸型的数据上的聚类也会表现虚高。但是比起轮廓系数，其计算非常快速。

案例

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples, silhouette_score
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import numpy as np
import pandas as pd
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=6000, centers=4, cluster_std = 2.5, n_features=2,center_box=(-12.0, 12.0),
                  random_state=42)
data = pd.DataFrame(X)
fig, axes = plt.subplots(3, 2)
fig.set_size_inches(18, 27)
n_clusters = 2
for i in range(3):
    for j in range(2):
        n_clusters = n_clusters
        clusterer = KMeans(n_clusters=n_clusters, random_state=10).fit(X)
        cluster_labels = clusterer.labels_
        silhouette_avg = silhouette_score(X, cluster_labels)
        print("For n_clusters =", n_clusters,
              "The average silhouette_score is :", silhouette_avg)
        sample_silhouette_values = silhouette_samples(X, cluster_labels)
        colors = cm.nipy_spectral(cluster_labels.astype(float) / n_clusters)
        axes[i,j].scatter(X[:, 0], X[:, 1]
                    ,marker='o'
                    ,s=8
                    ,c=colors
                   )
        centers = clusterer.cluster_centers_
        axes[i,j].scatter(centers[:, 0], centers[:, 1], marker='x',
                    c="red", alpha=1, s=200)
        axes[i,j].set_title(f"The visualization of the clustered data when n_Clusters = {n_clusters}.")
        axes[i,j].set_xlabel("Feature space for the 1st feature")
        axes[i,j].set_ylabel("Feature space for the 2nd feature")
        axes[i,j].text(0,-17,f"The average silhouette_score is :\n\n{silhouette_avg}",fontsize=10)
        n_clusters += 1
plt.show()

输出结果：

扩展--其他聚类算法

DBSCAN

从向量数组或距离矩阵执行DBSCAN聚类。

一种基于密度的带有噪声的空间聚类。它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据集中发现任意形状的聚类。

基于密度的空间聚类与噪声应用。寻找高密度的核心样本，并从中扩展星团。适用于包含相似密度的簇的数据。

DBSCAN算法将聚类视为由低密度区域分隔的高密度区域。由于这种相当通用的观点，DBSCAN发现的集群可以是任何形状，而k-means假设集群是凸形的。DBSCAN的核心组件是核心样本的概念，即位于高密度区域的样本。因此，一个集群是一组彼此接近的核心样本(通过一定的距离度量)和一组与核心样本相近的非核心样本（但它们本身不是核心样本）。算法有两个参数，min_samples和eps，它们正式定义了我们所说的密集。较高的min_samples或较低的eps表示较高的密度需要形成一个集群。

根据定义，任何核心样本都是集群的一部分。任何非核心样本，且与核心样本的距离至少为eps的样本，都被算法认为是离群值。

而主要控制参数min_samples宽容的算法对噪声（在嘈杂和大型数据集可能需要增加此参数），选择适当的参数eps至关重要的数据集和距离函数,通常不能在默认值。它控制着点的局部邻域。如果选择的数据太小，大多数数据根本不会聚集在一起（并且标记为-1表示"噪音"）。如果选择太大，则会导致关闭的集群合并为一个集群，并最终将整个数据集作为单个集群返回。

例：

>>> from sklearn.cluster import DBSCAN
>>> import numpy as np
>>> X = np.array([[1, 2], [2, 2], [2, 3],
...               [8, 7], [8, 8], [25, 80]])
>>> clustering = DBSCAN(eps=3, min_samples=2).fit(X)
>>> clustering.labels_
array([ 0,  0,  0,  1,  1, -1])
>>> clustering
DBSCAN(eps=3, min_samples=2)

eps float, default=0.5 两个样本之间的最大距离，其中一个样本被认为是相邻的。这不是集群内点的距离的最大值，这是为您的数据集和距离函数选择的最重要的DBSCAN参数。 min_samples int, default=5 被视为核心点的某一邻域内的样本数（或总权重）。这包括点本身。
更多DBSCAN聚类请参见 https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN

层次聚类

层次聚类Hierarchical Clustering 通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。

层次聚类的合并算法通过计算两类数据点间的相似性，对所有数据点中最为相似的两个数据点进行组合，并反复迭代这一过程。

简单来说通过计算每一个类别的数据点与所有数据点之间的欧式距离来确定它们之间的相似性，距离越小，相似度越高。并将距离最近的两个数据点或类别进行组合，生成聚类树。

例：

>>> from sklearn.cluster import AgglomerativeClustering
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [4, 2], [4, 4], [4, 0]])
>>> clustering = AgglomerativeClustering().fit(X)
>>> clustering
AgglomerativeClustering()
>>> clustering.labels_
array([1, 1, 1, 0, 0, 0])

层次化聚类是一种通用的聚类算法，它通过合并或分割来构建嵌套的聚类。集群的层次结构表示为树（或树状图）。树的根是收集所有样本的唯一集群，叶子是只有一个样本的集群。

聚类对象使用自底向上的方法执行分层聚类: 每个观察从它自己的聚类开始，然后聚类依次合并在一起。连接标准决定了用于合并策略的度量。

最大或完全连接使簇对观测之间的最大距离最小。
平均连接使簇对的所有观测值之间的平均距离最小化。
单连接使簇对的最近观测值之间的距离最小。
当与连通性矩阵联合使用时，团聚向量聚合也可以扩展到大量的样本，但是当样本之间不加连通性约束时，计算开销就大了：它在每一步都考虑所有可能的合并。

更多层次聚类请参见 https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html#sklearn.cluster.AgglomerativeClustering

附录

KMeans参数

n_clusters int, default=8 要聚成的簇数，以及要生成的质心数。
init {‘k-means++’, ‘random’, ndarray, callable}, default=’k-means++’ 这是初始化质心的方法，输入"k- means++": 一种为K均值聚类选择初始聚类中心的聪明的办法，以加速收敛。如果输入了n维数组，数组的形状应该是(n_clusters，n_features)并给出初始质心。
n_init int, default=10 使用不同的质心随机初始化的种子来运行KMeans算法的次数。最终结果会是基于Inertia来计算的n_init次连续运行后的最佳输出。
max_iter int, default=300 单次运行的KMeans算法的最大迭代次数。
tol float, default=1e-4 两次迭代间Inertia下降的量，如果两次迭代之间Inertia下降的值小于tol所设定的值，迭代就会停下。
precompute_distances {‘auto’, True, False}, default=’auto’ 预计算距离(更快，但需要更多内存)。 'auto': 如果 n_samples * n_clusters > 1200万，不要预先计算距离。这对应于使用双精度来学习，每个作业大约100MB的内存开销。 True: 始终预先计算距离。False：从不预先计算距离。
verbose int, default=0 计算中的详细模式。
random_state int, RandomState instance, default=None 确定质心初始化的随机数生成。使用int可以是随机性更具有确定性。
copy_x bool, default=True 在预计算距离时，若先中心化数据，距离的预计算会更加准确。如果copy_x为True(默认值)，则不会修改原始数据，确保特征矩阵X是c-contiguous。如果为False，则对原始数据进行修改，在函数返回之前放回原始数据，但可以通过减去数据平均值，再加上数据平均值，引入较小的数值差异。注意，如果原始数据不是c -连续的，即使copy_x为False，也会复制，这可能导致KMeans 计算量显著变慢。如果原始数据是稀疏的，但不是CSR格式的，即使copy_x是False的，也会复制一份。
n_jobs int, default=None 用于计算的作业数。计算每个n_init时并行作业数。这个参数允许KMeans在多个作业线上并行运行。给这个参数正值n_jobs，表示使用 n_jobs 条处理器中的线程。值-1表示使用所用可用的处理器。值-2表示使用所有可能的处理器-1个处理器，以此类推。并行化通常以内存为代价增加计算（这种情况下，需要存储多个质心副本，每个作业一个）
algorithm {“auto”, “full”, “elkan”}, default=”auto” 使用KMeans算法。经典的EM风格的算法是"full"的。通过使用三角不等式，"elkan"变异在具有定义明确的集群的数据上更有效。然而，由于分配了额外的形状数组(n_samples、n_clusters)，它会占用更多的内存。目前，"auto" 为密集数据选择 "elkan" 为稀疏数据选择"full"。

KMeans属性

cluster_centers_ ndarray of shape (n_clusters, n_features) 收敛到的质心坐标。如果算法在完全收敛之前已停止（受到'tol'和'max_iter'参数的控制），这些返回的内容将与'labels_'中反应出的聚类结果不一致。
labels_ ndarray of shape (n_samples,) 每个样本对应的标签。
inertia_ float 每个样本点到它们最近的簇中心的距离的平方的和，又叫做"簇内平方和"。
n_iter_ int 实际迭代的次数。