聚类算法

1 聚类算法简介

学习目标：

1.知道什么是聚类

2.了解聚类算法的应用场景

3.知道聚类算法的分类

1.1 聚类算法介绍

一种典型的无监督学习算法，主要用于将相似的样本自动归到一个类别中。

目的是将数据集中的对象分成多个簇（Cluster），使得同一簇内的对象相似度较高，而不同簇之间的对象相似度较低。与分类不同，聚类不需要事先给定类别标签，算法根据数据本身的特征自动地将数据分组。

在聚类算法中根据样本之间的相似性，将样本划分到不同的类别中，对于不同的相似度计算方法，会得到不同的聚类结果，常用的相似度计算方法有欧式距离法。

1.2 聚类算法在现实中的应用

• 用户画像，广告推荐，Data Segmentation，搜索引擎的流量推荐，恶意流量识别
• 基于位置信息的商业推送，新闻聚类，筛选排序
• 图像分割，降维，识别；离群点检测；信用卡异常消费；发掘相同功能的基因片段

1.3 聚类算法分类

• 根据聚类颗粒度分类

  

• 根据实现方法分类

  • 划分聚类：按照质心分类，主要介绍K-means，通用、普遍
  • 层次聚类：对数据进行逐层划分，直到达到聚类的类别个数
  • 密度聚类：按数据点的密度来形成簇，DBSCAN聚类是一种基于密度的聚类算法
  • 谱聚类：基于图论的聚类算法，计算数据点之间的相似度矩阵
  • …

2 聚类API的初步使用

学习目标：

1.了解Kmeans算法的API

2.动手实践Kmeans算法

2.1 API介绍

• sklearn.cluster.KMeans(n_clusters=8)
  • 参数:
    • n_clusters:开始的聚类中心数量
      • 整型，缺省值=8，生成的聚类数，即产生的质心（centroids）数。
  • 方法:
    • estimator.fit(x)
    • estimator.predict(x)
    • estimator.fit_predict(x)
      • 计算聚类中心并预测每个样本属于哪个类别,相当于先调用fit(x),然后再调用predict(x)

2.2 API使用

随机创建不同二维数据集作为训练集，并结合k-means算法将其聚类，你可以尝试分别聚类不同数量的簇，并观察聚类效果：

• 创建数据集

  import matplotlib.pyplot as plt
  from sklearn.datasets.samples_generator import make_blobs
  from sklearn.cluster import KMeans
  from sklearn.metrics import calinski_harabaz_score
  
  # 创建数据集
  # X为样本特征，Y为样本簇类别， 共1000个样本，每个样本2个特征，共4个簇，
  # 簇中心在[-1,-1], [0,0],[1,1], [2,2]， 簇方差分别为[0.4, 0.2, 0.2, 0.2]
  X, y = make_blobs(n_samples=1000, n_features=2, centers=[[-1, -1], [0, 0], [1, 1], [2, 2]],
                    cluster_std=[0.4, 0.2, 0.2, 0.2],
                    random_state=9)
  
  # 数据集可视化
  plt.scatter(X[:, 0], X[:, 1], marker='o')
  plt.show()
  

  

• 使用k-means进行聚类,并使用CH方法评估

  y_pred = KMeans(n_clusters=2, random_state=9).fit_predict(X)
  # 分别尝试n_cluses=2\3\4,然后查看聚类效果
  plt.scatter(X[:, 0], X[:, 1], c=y_pred)
  plt.show()
  
  # 用Calinski-Harabasz Index评估的聚类分数
  print(calinski_harabasz_score(X, y_pred))
  

  

3 Kmeans算法流程

学习目标

1、理解Kmeans算法的执行过程

3.1 k-means聚类流程

k-means其实包含两层内容：

• K表示初始中心点个数（计划聚类数）
• means求每个类别中样本点的平均值

1、随机设置K个特征空间内的点作为初始的聚类中心

2、对于其他每个点计算到K个中心的距离，未知的点选择最近的一个聚类中心点作为标记类别

3、根据每个类别中的样本点，重新计算出每个聚类的新中心点（平均值）

4、如果计算得出的新中心点与原中心点一样（质心不再移动），那么结束，否则重新进行第二步过程

通过下图解释实现流程：

k-means聚类动态效果图：

3.2 案例练习

• 案例：

1、随机设置K个特征空间内的点作为初始的聚类中心（本案例中设置p1和p2）

2、对于其他每个点计算到K个中心的距离，未知的点选择最近的一个聚类中心点作为标记类别

3、根据每个类别中的样本点，重新计算出每个聚类的新中心点（平均值）

4、如果计算得出的新中心点与原中心点一样（质心不再移动），那么结束，否则重新进行第二步过程【经过判断，需要重复上述步骤，开始新一轮迭代】

5、当每次迭代结果不变时，认为算法收敛，聚类完成，K-Means一定会停下，不可能陷入一直选质心的过程。

4 评价指标

学习目标:

1. 了解 SSE 聚类评估指标
2. 了解 SC 聚类评估指标
3. 了解 CH 聚类评估指标
4. 了解肘方法的作用

4.1 SSE误差平方和

model.inertia_

1. K 表示聚类中心的个数（簇个数）

2. $$C_i$$ 表示簇

3. $$p$$ 表示样本

4. $$m_i$$ 表示簇的质心

   

SSE 越小，表示数据点越接近它们的中心，聚类效果越好。

缺点：SSE通常随着簇数 KKK 的增大而减小，因此不能仅仅依赖SSE来评估聚类效果。

4.2 SC轮廓系数

• from sklearn.metrics import silhouette_score
• silhouette_score(X,y_pred)

轮廓系数是用于评估每个数据点与簇内其他点的相似性（凝聚度）以及与最近簇的相异性（分离度）的度量。轮廓系数的值在-1到1之间，值越大表示聚类效果越好。

其计算过程如下：

• 计算每一个样本 i 到同簇内其他样本的平均距离 a_i，该值越小，说明簇内的相似程度越大
• 计算每一个样本 i 到最近簇 j 内的所有样本的平均距离 b_ij，该值越大，说明该样本越不属于其他簇 j
• 计算所有样本的平均轮廓系数
• 轮廓系数的范围为：[-1, 1]，值越大聚类效果越好

优点：轮廓系数能够综合考虑簇的内部一致性和簇之间的分离度，不依赖于簇的数量。

4.3 肘部法

肘部法可以用来确定最佳 K 值。

• 对于n个点的数据集，迭代计算 k from 1 to n，每次聚类完成后计算 SSE。

• SSE 是会逐渐变小的，因为每个点都是它所在的簇中心本身。

• SSE 变化过程中会出现一个拐点，下降率突然变缓时即认为是最佳 n_clusters 值。

• 在决定什么时候停止训练时，肘部法同样有效，数据通常有更多的噪音，在增加分类无法带来更多回报时，我们停止增加类别。

4.4 CH系数

• from sklearn.metrics import calinski_harabasz_score
• calinski_harabasz_score(X,y_pred)

CH系数结合了聚类的凝聚度（Cohesion）和分离度（Separation）、质心的个数，希望用最少的簇进行聚类。

CH系数值越大表示聚类效果越好。

SSW 的含义：

1. $$C_{pi}$$ 表示质心
2. $$x_i$$ 表示某个样本
3. SSW 值是计算每个样本点到质心的距离，并累加起来
4. SSW 表示表示簇内的内聚程度，越小越好
5. $$m$$ 表示样本数量
6. $$k$$ 表示质心个数

SSB 的含义：

1. $$C_j$$ 表示质心，X 表示质心与质心之间的中心点，$$n_j$$ 表示样本的个数
2. SSB 表示簇与簇之间的分离度，SSB 越大越好

4.5 聚类评估的使用

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.metrics import silhouette_score
from sklearn.metrics import calinski_harabasz_score


if __name__ == '__main__':
    x, y = make_blobs(n_samples=1000,
                      n_features=2,
                      centers=[[-1, -1], [0, 0], [1, 1], [2, 2]],
                      cluster_std=[0.4, 0.2, 0.2, 0.2],
                      random_state=9)

    plt.figure(figsize=(18, 8), dpi=80)
    plt.scatter(x[:, 0], x[:, 1], c=y)
    plt.show()

    estimator = KMeans(n_clusters=4, random_state=0)
    estimator.fit(x)
    y_pred = estimator.predict(x)

    # 1. 计算 SSE 值
    print('SSE:', estimator.inertia_)

    # 2. 计算 SC 系数
    print('SC:', silhouette_score(x, y_pred))

    # 3. 计算 CH 系数
    print('CH:', calinski_harabasz_score(x, y_pred))

5 KMeans算法案例

5.1 案例介绍

已知：客户性别、年龄、年收入、消费指数

需求：对客户进行分析，找到业务突破口，寻找黄金客户

数据集共包含顾客的数据, 数据共有 4 个特征, 数据共有 200 条。接下来，使用聚类算法对具有相似特征的的顾客进行聚类，并可视化聚类结果。

5.2 案例实现

• 确定最佳K值

  import pandas as pd
  from sklearn.cluster import KMeans
  import matplotlib.pyplot as plt
  from sklearn.metrics import silhouette_score
  
  # 聚类分析用户分群
  dataset = pd.read_csv('data/customers.csv')
  dataset.info()
  print('dataset-->\n', dataset)
  X = dataset.iloc[:, [3, 4]]
  print('X-->\n', X)
  mysse = []
  mysscore = []
  # 评估聚类个数
  for i in range(2, 11):
  	mykeans = KMeans(n_clusters=i)
  	mykeans.fit(X)
  	mysse.append(mykeans.inertia_)  # inertia 簇内误差平方和
  	ret = mykeans.predict(X)
  	mysscore.append(silhouette_score(X, ret))  # sc系数 聚类需要1个以上的类别
  plt.plot(range(2, 11), mysse)
  plt.title('the elbow method')
  plt.xlabel('number of clusters')
  plt.ylabel('mysse')
  plt.grid()
  plt.show()
  plt.title('sh')
  plt.plot(range(2, 11), mysscore)
  plt.grid(True)
  plt.show()
  

  通过肘方法、sh系数都可以看出，聚成5类效果最好

  

• 顾客聚类

  dataset = pd.read_csv('data/customers.csv')
  dataset.head()
  X = dataset.iloc[:, [3, 4]].values #全部行，第四第五列  Annual Income (k$) 和 Spending Score (1-100)
  kmeans = KMeans(n_clusters = 5, init = 'k-means++', random_state = 42) #k=5 
  y_kmeans = kmeans.fit_predict(X)
  # 画图展示聚类结果
  plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s = 100, c = 'red', label = 'Standard')
  plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s = 100, c = 'blue', label = 'Traditional')
  plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s = 100, c = 'green', label = 'Normal')
  plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s = 100, c = 'cyan', label = 'Youth')
  plt.scatter(X[y_kmeans == 4, 0], X[y_kmeans == 4, 1], s = 100, c = 'magenta', label = 'TA')
  # kmeans.cluster_centers_:聚类后每类的中心点
  plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s = 300, c = 'black', label = 'Centroids')
  plt.title('Clusters of customers')
  plt.xlabel('Annual Income (k$)')
  plt.ylabel('Spending Score (1-100)')
  plt.legend()
  plt.show()
  

  从图中可以看出，聚成5类，右上角属于挣的多，消费的也多黄金客户群

  

6 聚类注意点

6.1 样本异常数据

K均值（K-Means）是聚类中最常用的方法之一，它基于点与点距离的相似度来计算最佳类别归属。但K均值在应用之前一定要注意两种数据异常：

• 数据的异常值：数据中的异常值能明显改变不同点之间的距离相似度，并且这种影响是非常显著的。因此基于距离相似度的判别模式下，异常值的处理必不可少。

• 数据的异常量纲：不同的维度和变量之间，如果存在数值规模或量纲的差异，那么在做距离之前需要先将变量归一化或标准化。例如，跳出率的数值分布区间是[0，1]，订单金额可能是[0，10000000]，而订单数量则是[0，1000]。如果没有归一化或标准化操作，那么相似度将主要受到订单金额的影响。

6.2 样本数据量过大

数据量过大的时候不适合使用KMeans算法

K-Means在算法稳定性、效率和准确率（相对于真实标签的判别）上表现非常好，并且在应对大量数据时依然如此。它的算法时间复杂度上界为$$n\ast k\ast t$$，其中n是样本量、k是划分的聚类数、t是迭代次数。

当聚类数和迭代次数不变时，K均值的算法消耗时间只跟样本量有关，因此会呈线性增长趋势。

当真正面对海量数据时，使用K均值算法将面临严重的结果延迟，尤其是当K均值被用做实时性或准实时性的数据预处理、分析和建模时，这种瓶颈效应尤为明显。

针对K均值的这一问题，很多延伸算法出现了，MiniBatchKMeans就是其中一个典型代表。

MiniBatchKMeans使用了一个名为Mini Batch（分批处理）的方法计算数据点之间的距离。

MiniBatch的好处是计算过程中不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本（而非全部样本）作为代表参与聚类算法过程。

由于计算样本量少，所以会相应减少运行时间；但另一方面，由于是抽样方法，抽样样本很难完全代表整体样本的全部特征，因此会带来准确度的下降

经过对30000样本点分别使用KMeans 和 MiniBatchKMeans 进行聚类，对比之后运行时间 MiniBatchKMeans 是 K-Means的一半（0.17 vs 0.36），但聚类结果差异性很小。

**结论：**MiniBatchKMeans在基本保持了K-Means原有较高类别识别率的前提下，其计算效率的提升非常明显。因此，MiniBatchKMeans是一种能有效应对海量数据，尽量保持聚类准确性并且大幅度降低计算耗时的聚类算法。