建站报价,it培训机构学费,公司网站更新,乐平网站目录
1 核心思想
2 K-means算法
2.1 算法概述
2.2 算法步骤
2.3 数学原理
2.4 ‘肘’方法确定K值
2.4.1 原理
2.4.2 步骤
2.4.3 代码实现
2.5 聚类评估方法
2.5.1 SC轮廓系数#xff08;Silhouette Coefficient#xff09;
计算方法
解读
注意事项
2.5.2 Cal…目录
1 核心思想
2 K-means算法
2.1 算法概述
2.2 算法步骤
2.3 数学原理
2.4 ‘肘’方法确定K值
2.4.1 原理
2.4.2 步骤
2.4.3 代码实现
2.5 聚类评估方法
2.5.1 SC轮廓系数Silhouette Coefficient
计算方法
解读
注意事项
2.5.2 Calinski-Harabasz指数
定义
计算公式
评估原理
优点
缺点
适用情况
2.6 优缺点
2.7 改进和扩展
2.8 代码实现 1 核心思想
聚类算法的核心思想是将数据集中的样本划分为若干个不相交的子集即“簇”。每个簇可能对应于一些潜在的概念或类别。聚类算法的目标是让同一簇内的数据样本尽可能相似而不同簇间的数据样本尽可能不相似。这种相似性通常基于数据样本之间的某种距离度量来定义如欧氏距离、余弦相似度等。
聚类算法是无监督学习方法的一种它不需要预先设定数据标签或类别信息而是通过分析数据样本之间的内在规律和特征来自动划分数据类别。聚类算法的种类繁多包括基于划分的聚类算法如K-means、基于层次的聚类算法、基于密度的聚类算法如DBSCAN、基于网格的聚类算法、基于模型的聚类算法等。本处只介绍K-means算法 2 K-means算法
2.1 算法概述
K-means算法是一种基于迭代的聚类算法它试图将数据点划分为K个集群或称为簇使得每个数据点都属于离其最近的均值即聚类中心或质心所对应的集群。K-means算法的核心是更新质心和分配数据点到最近的质心。
2.2 算法步骤
初始化 选择K个点作为初始质心。这可以是随机选择或者通过一些启发式方法如K-means来选择以加速收敛和避免糟糕的局部最优解。分配数据点到最近的质心 对于数据集中的每个数据点计算它与K个质心之间的距离如欧氏距离。将数据点分配给距离它最近的质心所对应的集群。更新质心 对于每个集群计算其内部所有数据点的均值即新的质心。将每个集群的质心更新为该均值。迭代优化 重复步骤2和3直到满足某个停止条件。常见的停止条件包括 质心的位置不再发生显著变化即收敛。达到预设的最大迭代次数。准则函数如SSE的变化小于某个阈值。
2.3 数学原理 距离度量通常使用欧氏距离来度量数据点与质心之间的距离。但在某些情况下也可以使用其他距离度量如曼哈顿距离、余弦相似度等。 准则函数SSEK-means算法使用均方差Sum of the Squared Errors, SSE作为准则函数也称为损失函数。SSE表示每个数据点到其所属集群的质心的距离的平方和。数学上SSE可以表示为 其中Ci是第i个集群的数据点集合μi是第i个集群的质心∣∣x−μi∣∣是数据点x与质心μi之间的距离。
收敛性虽然K-means算法不保证找到全局最优解即SSE的最小值但在某些条件下它可以保证收敛到局部最优解。收敛性通常通过观察质心的变化或SSE的变化来判断。
2.4 ‘肘’方法确定K值
2.4.1 原理
“肘”方法Elbow Method是一种常用于确定K-means聚类算法中最佳聚类数K值的启发式方法。该方法基于SSESum of the Squared Errors误差平方和与聚类数K之间的关系来确定最佳的K值。
2.4.2 步骤
以下是使用“肘”方法确定K值的步骤
计算不同K值的SSE首先对于一系列不同的K值例如从1开始逐渐增加对给定的数据集进行K-means聚类并计算每个K值对应的SSE。绘制SSE图将每个K值及其对应的SSE绘制在一张图表上。通常横轴表示K值纵轴表示对应的SSE。寻找“肘点”在SSE图上观察SSE随K值变化的趋势。通常随着K值的增加SSE会逐渐减小因为更多的聚类可以更好地拟合数据。但是当K值增加到某个点后SSE的减小速度会明显放缓形成一个类似于“肘部”的弯曲点。这个点就是所谓的“肘点”。选择肘点对应的K值根据SSE图上的“肘点”选择对应的K值作为最佳聚类数。这个K值通常表示在增加聚类数时能够获得较大的聚类效果提升与计算成本之间的平衡。
需要注意的是“肘”方法是一种启发式方法其结果可能受到数据分布、噪声等因素的影响。因此在实际应用中可能需要结合其他方法如轮廓系数、Calinski-Harabasz指数等来综合评估聚类效果并选择最佳的K值。
2.4.3 代码实现
在Python中我们可以使用sklearn库的KMeans类来执行K-means聚类并计算不同K值下的SSE误差平方和然后通过绘制图形来找到“肘点”。以下是一个简单的代码示例用于实现这一过程
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs # 生成模拟数据
X, y make_blobs(n_samples300, centers4, cluster_std0.60, random_state0) # 初始化一个空的列表来存储SSE值
sse [] # 遍历不同的K值
for k in range(1, 11): kmeans KMeans(n_clustersk, initk-means, max_iter300, n_init10, random_state0) kmeans.fit(X) sse.append(kmeans.inertia_) # inertia_ 是KMeans类的一个属性它给出了每个点到其最近质心的距离的平方和 # 绘制SSE与K值的关系图
plt.plot(range(1, 11), sse)
plt.title(The Elbow Method showing the optimal k)
plt.xlabel(Number of clusters)
plt.ylabel(SSE)
plt.show() # 根据SSE图找到“肘点”
# 实际应用中可能需要一些启发式规则或手动选择
# 例如可以通过检查SSE的减少率来找到“肘点”
# 这里我们假设“肘点”是SSE开始平缓变化的点
# 注意这是一个简化的示例实际中可能需要更复杂的逻辑来确定“肘点”
在这个例子中我们使用make_blobs函数生成了一个模拟数据集然后遍历了从1到10的不同K值并计算了每个K值下的SSE。然后我们使用matplotlib库绘制了SSE与K值的关系图。
要找到“肘点”通常我们需要观察SSE的减少率。在图中当K值较小时SSE的减少幅度通常很大因为增加聚类数能够显著改善聚类效果。然而当K值增加到一定程度时SSE的减少率会开始放缓形成一个类似于“肘部”的弯曲点。这个“肘点”就是我们要找的K值。
在实际应用中可能需要一些启发式规则或手动选择来确定“肘点”。例如我们可以计算相邻K值之间SSE的减少率并找到减少率开始明显放缓的点。然而需要注意的是“肘点”方法并不是一种严格的数学方法其结果可能会受到数据分布、噪声等因素的影响。因此在实际应用中我们可能需要结合其他方法如轮廓系数、Calinski-Harabasz指数等来综合评估聚类效果并选择最佳的K值。 2.5 聚类评估方法
2.5.1 SC轮廓系数Silhouette Coefficient
轮廓系数Silhouette Coefficient是一种用于评估聚类效果的指标它结合了聚类的凝聚度和分离度两种因素。对于数据集中的每个样本轮廓系数衡量了样本与其所属聚类内其他样本的相似度凝聚度以及样本与其他聚类中样本的不相似度分离度。
计算方法
轮廓系数是针对单个样本的然后取所有样本的平均值得到整个数据集的轮廓系数。对于数据集中的第i个样本其轮廓系数s(i)的计算步骤如下
1. 计算样本i到同聚类其他样本的平均距离a(i)这代表了样本i所属聚类的凝聚度。a(i)越小说明样本i越应该被聚类到该簇。 其中C_i是样本i所属的聚类|C_i|是该聚类的样本数dist(i, j)是样本i和j之间的距离。
2.计算样本i到所有其他聚类中的样本的平均距离的最小值b(i)这代表了样本i与其他聚类的分离度。b(i)越大说明样本i越不属于其他聚类。 其中C_k是除了C_i以外的其他聚类。
3.计算样本i的轮廓系数s(i) 轮廓系数的值域是[-1, 1]。值越接近1表示聚类效果越好样本i越应该被聚类到当前聚类值越接近-1表示聚类效果越差样本i更可能被聚类到错误的聚类中值接近0则表示样本i在两个聚类的边界上。
4.计算整个数据集的轮廓系数取所有样本轮廓系数的平均值。
解读
如果一个聚类中的大多数样本的轮廓系数都比较高则整个聚类的质量是好的。如果一个聚类的轮廓系数较低则可能是由于聚类过大或聚类中包含了一些与其他聚类距离较近的样本。如果一个样本的轮廓系数较低则可能是因为它被错误地分配到了某个聚类中。
注意事项
轮廓系数对于凸形聚类如K-means聚类产生的聚类的效果评估通常比较好但对于非凸形聚类如基于密度的聚类产生的聚类可能不太准确。轮廓系数对样本数量的变化比较敏感如果样本数量过少可能会导致评估结果不准确。在计算轮廓系数时选择合适的距离度量方法如欧氏距离、曼哈顿距离等也是非常重要的。
2.5.2 Calinski-Harabasz指数
Calinski-Harabasz IndexCalinski-Harabasz指数是聚类分析中的一种评估指标主要用于评估聚类效果的好坏。以下是关于Calinski-Harabasz Index的详细介绍
定义
Calinski-Harabasz指数是基于簇内的协方差与簇间的协方差之间的比值进行计算的。该指标值越大代表聚类效果越好。
计算公式 评估原理
Calinski-Harabasz指数通过计算聚类之间的离散度与聚类内部的紧密度之比来确定最佳的聚类数(m - k)/(k - 1)部分是一个修正系数用于平衡聚类数量和样本数量对指标的影响。
当簇的密集且分离较好时Calinski-Harabasz指数的值会更高。这意味着簇内部的数据点紧密聚集而簇与簇之间有明显的分离。因此Calinski-Harabasz指数越大表示聚类效果越好。
优点
计算速度快与轮廓系数等其他聚类评估指标相比Calinski-Harabasz指数的计算速度更快尤其适用于大型数据集。评估效果直观Calinski-Harabasz指数的值直接反映了聚类效果的好坏方便用户根据指标值进行优化。
缺点
对噪声和异常值敏感由于Calinski-Harabasz指数是基于协方差矩阵进行计算的因此它对噪声和异常值比较敏感。在存在噪声或异常值的情况下指标值可能会受到较大影响。适用于具有清晰、凸形状的聚类结构Calinski-Harabasz指数在处理具有清晰、凸形状的聚类结构时表现较好。然而对于非凸形状的聚类结构该指标可能会出现偏差。
适用情况
Calinski-Harabasz指数适用于各种类型的数据集尤其是数据分布相对均匀且没有明显的几何形状的聚类结构。然而在处理具有非凸形状的聚类结构或存在噪声和异常值的数据集时可能需要结合其他聚类评估指标进行综合评估。 2.6 优缺点
优点 原理简单易于实现和解释。处理大数据集时通常比层次聚类等算法更高效。当结果集群是密集的、球状或团状的且集群之间区别明显时效果较好。缺点 需要预先指定集群的个数K这通常是一个难题。对初始质心的选择敏感不同的初始质心可能导致完全不同的聚类结果。对噪声和异常值敏感因为它们可能影响质心的计算和集群的分配。只适用于凸数据集对于非凸数据集可能无法得到理想的聚类效果。
2.7 改进和扩展
K-means一种改进的初始化方法旨在选择更好的初始质心从而加速收敛和避免糟糕的局部最优解。Mini Batch K-means一种适用于大数据集的K-means算法的变体它使用数据集的子集即mini batch来更新质心从而在不牺牲太多精度的情况下提高计算效率。模糊C-meansFCM一种软聚类方法它允许数据点以不同的隶属度属于多个集群从而能够处理更复杂的数据结构和不确定性。谱聚类一种基于图论的聚类方法它首先将数据点视为图中的节点然后构建节点之间的相似度矩阵或称为邻接矩阵最后使用图论中的谱分析方法来划分集群。谱聚类通常能够处理非凸数据集和具有复杂结构的数据集。
2.8 代码实现
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs # 创建一个包含不同数量簇的模拟数据集
X, y_true make_blobs(n_samples300, centers4, cluster_std0.60, random_state0) # 定义畸变程度Distortion的计算函数
def calculate_distortion(X, k): kmeans KMeans(n_clustersk, random_state0).fit(X) return kmeans.inertia_ # 初始化一个列表用于存储不同K值对应的畸变程度
distortions []
for i in range(1, 11): K i distortions.append(calculate_distortion(X, K)) # 绘制K值与畸变程度的曲线
plt.plot(range(1, 11), distortions, markero)
plt.xlabel(Number of clusters)
plt.ylabel(Distortion)
plt.title(The Elbow Method showing the optimal k)
plt.show() # 根据肘部方法选择最佳的K值这里可以手动从图中观察
# 也可以编写一个自动化方法来选择K值例如通过计算畸变程度的二阶导数或者变化率来选择
# 自动化选择K值的示例这里使用简单的斜率变化来模拟
# ... (这部分代码需要根据你的需求来实现) # 假设我们从图中观察到K4时有一个明显的肘部因此选择K4
best_k 4
kmeans KMeans(n_clustersbest_k, random_state0).fit(X)
labels kmeans.predict(X) # 绘制聚类结果
plt.scatter(X[:, 0], X[:, 1], clabels, s50, cmapviridis)
centers kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], cblack, s200, alpha0.5);
plt.show()
在这个例子中我们首先生成了一个模拟数据集然后使用了一个函数来计算不同K值对应的畸变程度。接着我们绘制了K值与畸变程度的曲线图并手动从图中选择了最佳的K值。最后我们使用选定的K值来执行K-means聚类并绘制了聚类结果。
注意在实际应用中肘部可能并不总是那么明显特别是在数据集非常复杂或者噪声很大的情况下。因此你可能需要结合其他方法或者领域知识来确定最佳的K值。
