什么是 kmeans 算法

KMeans 是一种简单但功能强大的无监督学习算法，用于将数据划分为预先定义的 K 个簇。通过识别数据点之间的相似性和差异，KMeans 聚类提供了有价值的见解，可用于各种目的，例如客户细分、异常检测和图像压缩。

算法步骤

KMeans 是一种迭代算法，它根据数据点与预定义的 k 个质心的接近程度将数据点分配给聚类。这些质心充当每个簇的中心点，并在迭代过程中进行调整，以最小化簇内平方和。

  1. 初始化：随机选择 K 个数据点作为初始簇中心。

  2. 分配步骤：将每个数据点分配给最近的簇中心，形成K个簇。通常，这一步使用欧氏距离来度量数据点与簇中心之间的距离。

距离公式为：

\(\(d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}\)\)

其中 \(x\) 和 \(y\) 分别是数据点和簇中心的坐标，\(n\) 是维度。

  1. 更新步骤：更新每个簇的中心点，新的簇中心是该簇所有点的均值。

公式为：

\(\(\mu_k = \frac{1}{|S_k|} \sum_{\mathbf{x}_i \in S_k} \mathbf{x}_i\)\)

其中 \(\mu_k\) 是簇 \(k\)的新中心，\(S_k\) 是分配给簇 \(k\)的点集。

  1. 重复步骤：重复步骤2 和步骤3 直到簇中心不再变化或变化很小，或者达到预设的迭代次数。

aaa

算法特点

目标函数

KMeans 试图最小化簇内的方差，其目标函数是：

\[J = \sum_{k=1}^{K} \sum_{\mathbf{x}_i \in S_k} || \mathbf{x}_i - \mu_k ||^2\]

其中，\(K\) 是簇的数量，\(x_i\) 是数据点，\(\mu_k\) 是簇 \(k\) 的中心。

计算复杂度

KMeans 算法的计算复杂度通常是 \(O(n×K×I×d)\)，其中 \(n\) 是样本数，\(K\) 是簇的数量，\(I\) 是迭代次数，\(d\) 是每个样本的维度。

案例分享

加载数据集

import pandas as pd

# Load the provided dataset
file_path = 'sample_data/Mall_Customers.csv'
df = pd.read_csv(file_path)

# Display the first few rows of the dataset
df.head()

image-20231206154049361

特征选择

from sklearn.preprocessing import StandardScaler

# Selecting the relevant columns
df_cluster = df[['Age', 'Annual Income (k$)', 'Spending Score (1-100)']]

# Normalizing the data
scaler = StandardScaler()
df_scaled = scaler.fit_transform(df_cluster)

使用肘部法选择K值

from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# Applying K-means clustering
# Using the Elbow method to find the optimal number of clusters
wcss = []
for i in range(1, 11):
    kmeans = KMeans(n_clusters=i, init='k-means++', random_state=42)
    kmeans.fit(df_scaled)
    wcss.append(kmeans.inertia_)

# Plotting the Elbow graph
plt.figure(figsize=(10, 6))
plt.plot(range(1, 11), wcss)
plt.title('The Elbow Method')
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()

image-20231206154705304

aaa

从图中可以看到簇的数量应该选择 5。

应用 KMeans

import seaborn as sns

# Choosing 5 clusters based on the Elbow Method
kmeans = KMeans(n_clusters=5, init='k-means++', random_state=42)
kmeans.fit(df_scaled)

# Adding the cluster labels to the original dataframe
df['Cluster'] = kmeans.labels_

# Visualization of clusters based on Annual Income and Spending Score
plt.figure(figsize=(10, 6))
sns.scatterplot(data=df, x='Annual Income (k$)', y='Spending Score (1-100)', hue='Cluster', palette='viridis')
plt.title('Clusters of Customers')
plt.xlabel('Annual Income (k$)')
plt.ylabel('Spending Score (1-100)')
plt.legend(title='Cluster')
plt.show()

image-20231206154723000

解释结果

分析生成的簇及其特征。根据领域知识和评估指标评估聚类的质量。

from yellowbrick.cluster import SilhouetteVisualizer

fig, ax = plt.subplots(2, 2, figsize=(15,8))
num_clusters = [ 3, 4, 5,6]
for i, k in enumerate(num_clusters):
    km = KMeans(n_clusters=k,
                random_state=42)
    q, mod = divmod(i, 2)
    visualizer = SilhouetteVisualizer(km,
                                      colors='yellowbrick',
                                      ax=ax[q-1][mod])
    visualizer.fit(df_scaled)

image-20231206154747354

KMeans 聚类是一种通用且广泛使用的数据分析和模式识别算法。通过将相似的数据点分组在一起，KMeans 聚类提供了宝贵的见解，可以推动决策并揭示数据中隐藏的关系。

聚类质量评价方法有哪些？

聚类质量评价是对聚类算法效果的度量，可以帮助我们衡量聚类结果的好坏。

以下是常见的聚类质量评价方法：

  • SSE（Sum of Squared Errors，误差平方和）

SSE是指聚类中各个点到所属类中心点距离的平方和，该值越小表示聚类效果越好。

  • 轮廓系数（Silhouette Coefficient）

测量每个样本到其聚类内其他样本的平均距离（凝聚度）与到最近非所属聚类的样本的平均距离（分离度）之间的差异。

该系数综合考虑了聚类内部的样本之间距离和聚类之间的样本距离。系数的值在 -1到1 之间，越接近1表示样本聚类效果越好。

  • GAP统计量（Gap Statistic）

该统计量通过比较实际数据和随机数据之间的差异来评价聚类质量。当实际数据的聚类结果比随机数据的结果更好时，GAP统计量的值越大。

  • DB指数（Davies-Bouldin Index）

该指数考虑了聚类内部的样本分散和聚类之间样本的分散情况。该指数的值越小表示聚类效果越好。

  • CH指数（Calinski-Harabasz Index）

该指数通过聚类之间的类别间差异和聚类内部的类别差异进行衡量，越大表示聚类效果越好。

不同的聚类算法和任务特性可能对应着不同的评价指标，因此需要针对具体问题和算法选择合适的评价指标。

aaa

KMeans 聚类的初始值 k 怎么选取？

使用 KMeans 聚类的关键考虑因素之一是确定最佳聚类数量 K。虽然没有确定的方法来找到完美的 K，但有几种技术可以帮助指导决策过程。

  1. 肘部法：

  2. 运行 KMeans 算法多次，每次使用不同的K值。

  3. 对于每个K值，计算成本函数（簇内误差平方和）。

  4. 绘制 K 值与成本函数的关系图。

  5. 成本随 K 值增加而减少，因为 K 越大，簇越小，簇内误差越小。

  6. 找到成本下降明显变缓的点，“肘部”，这个点就是合理的K值。

  7. 轮廓系数：计算不同 K 值的平均轮廓系数，并选择使该系数最大化的一个。

轮廓系数是一种评估聚类效果好坏的指标，它结合了聚类的凝聚度和分离度。对于数据集中的单个样本，轮廓系数是这样计算的：

  • 计算凝聚度 \(a(i)\)：对于每个样本 \(i\)，计算它与所在簇内其他样本的平均距离。这个平均距离代表了凝聚度 \(a(i)\)

  • 计算分离度 \(b(i)\)：对于同一个样本 \(i\)，计算它与下一个最近簇的所有样本的平均距离。这个最小的平均距离代表了分离度 \(b(i)\)

  • 计算轮廓系数 \(s(i)\)：对于每个样本 \(i\)，它的轮廓系数 \(s(i)\) 是通过以下公式计算的：

    \(\(s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}\)\)

    其中：

    • \(a(i)\) 是样本 \(i\) 与其自身簇内其他样本的平均距离（凝聚度）。
    • \(b(i)\) 是样本 \(i\) 与最近簇内所有样本的平均距离（分离度）。
    • \(s(i)\) 的值域在 [−1,1]。

  • 总体轮廓系数：数据集的总体轮廓系数是所有样本轮廓系数的平均值。一个高的平均轮廓系数表明聚类具有较好的凝聚度和分离度。

  • 领域知识：利用你的领域专业知识，根据特定问题或上下文确定合适的 k 值。

为什么在计算 K-means 之前要将数据点在各维度上归一化？

原因主要有以下几点：

  1. 距离度量的均衡性

K-means 算法在聚类过程中使用距离度量（如欧几里得距离）来确定数据点之间的相似性。如果数据的不同维度具有不同的量级（例如，一个维度的范围是 0-1，另一个维度的范围是 0-1000），那么量级较大的维度将对距离计算产生更大的影响，这会导致聚类结果偏向于这些维度。归一化确保所有维度在距离计算中具有相同的重要性。

  1. 加快算法收敛

未归一化的数据可能导致聚类过程中出现较大的数值变化，这可能会使算法收敛速度变慢。归一化通过减少数值范围的差异，有助于加快算法的收敛速度。

  1. 防止数值问题

在某些情况下，未归一化的数据可能导致数值计算问题，如溢出或下溢。归一化可以减少这些问题的风险。

  1. 提高算法的适应性

对数据进行归一化可以提高算法对不同量级和分布的数据的适应性，使其在更广泛的数据集上都能有效工作。

KMeans 聚类的优缺点？

优点

  1. 简单易懂

KMeans 算法结构简单，容易理解和实现。它的算法过程清晰：选择初始质心，分配数据点，更新质心，重复直到收敛。

  1. 计算效率高

在大多数情况下，KMeans 的计算效率较高，特别是对于大数据集。它的时间复杂度通常比其他聚类算法低。

  1. 广泛适用性

KMeans 可以应用于各种类型的数据集，特别是在数据维度不太高时效果较好。

  1. 易于实现并行化

KMeans 的步骤可以很容易地并行处理，这使得它在大规模数据集上也能高效运行。

  1. 适合发现球形簇

在数据集中形成的簇近似于球形时，KMeans 的性能很好。

缺点

  1. 需要预先指定簇的数量

KMeans 需要在算法开始前确定簇的数量（K值），这在实际应用中可能是一个难点，因为正确的簇数量通常是未知的。

  1. 对异常值敏感

KMeans 对噪声和异常值非常敏感。异常值可能会极大地扭曲簇的质心。

  1. 初始质心的选择影响大

算法的结果可能对初始质心的选择非常敏感。不好的初始质心选择可能导致次优的聚类结果。

  1. 难以发现非凸形状的簇

KMeans 假设簇是凸形的，这限制了它在发现复杂形状簇的能力。

  1. 固定大小的簇

KMeans 倾向于发现大小相近的簇，这可能不是某些数据集的最佳聚类方式。

  1. 难以处理高维数据

在高维空间中，距离度量变得不太可靠，这可能影响 KMeans 在高维数据上的性能。

aaa

介绍一下KMeans++算法？

KMeans++ 是 KMeans 算法的一个改进版本，主要改进在于初始质心的选择方法。在传统的 KMeans 算法中，初始质心是随机选择的，这可能导致聚类结果不稳定且有时效果不佳。

KMeans++ 提出了一种更加精确和高效的初始质心选择方法，可以显著提高聚类结果的质量和稳定性。

KMeans++ 的步骤

  1. 初始化第一个质心

从数据集中随机选择一个数据点作为第一个质心。

  1. 选择后续质心

对于每一个还未选择为质心的数据点，计算它与已选择的质心中最近一个的距离的平方。选择下一个质心的概率与这个距离平方成正比。这个步骤重复执行直到所有 K 个质心被选出。

  1. 数据点分配

就像传统的 KMeans 那样，每个数据点被分配到最近的质心所代表的簇。

  1. 更新质心位置

计算每个簇的平均位置，并将质心移动到这个平均位置。

  1. 迭代直到收敛

重复数据点分配和质心更新的步骤，直到满足停止条件（例如，质心的移动距离小于某个阈值，或者达到预设的迭代次数）。

KMeans++ 的优点

  1. 更好的初始质心

通过这种概率模型来选择初始质心，KMeans++ 能够更好地捕捉数据集的内在结构，减少对初始点选择的依赖。

  1. 改善聚类质量

与随机初始化相比，KMeans++ 往往能够找到更优的聚类结果。

  1. 减少迭代次数

由于初始质心选择得更合理，通常需要更少的迭代次数就可以达到收敛。

  1. 提高算法的稳定性

减少了由随机初始质心带来的结果波动。

尽管 KMeans++ 在很多方面改进了传统 KMeans 算法，但它仍然继承了 KMeans 的一些局限性，比如对噪声和异常值敏感，以及在处理非球形簇或高维数据时的局限性。此外，KMeans++ 在选择初始质心时的计算成本会比传统 KMeans 算法高，尤其是在大规模数据集上。