原文towardsdatascience.com/mastering-k-means-clustering-065bc42637e4?sourcecollection_archive---------0-----------------------#2024-05-22通过这个逐步 Python 教程从头开始实现 K-Means 算法https://marcusmvls-vinicius.medium.com/?sourcepost_page---byline--065bc42637e4--------------------------------https://towardsdatascience.com/?sourcepost_page---byline--065bc42637e4-------------------------------- Marcus Sena·发表于 Towards Data Science ·阅读时间 8 分钟·2024 年 5 月 22 日–https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5c7adde7e4e88ee31689443db5e31e44.png图片由作者使用 DALL-E 创建。在本文中我将展示如果今天开始学习 K-Means 算法我会如何学习。我们将从基础概念开始并实现一个使用 Numpy 包执行聚类任务的 Python 类。无论你是一个试图建立坚实概念理解的机器学习初学者还是一个有兴趣创建自定义机器学习应用并需要了解算法底层实现的从业者本文都适合你。目录1. 介绍2. K-Means 算法做什么3. Python 实现4. 评估与解释5. 结论与下一步1. 介绍大多数广泛使用的机器学习算法如线性回归、逻辑回归、决策树等都是用来从标记数据中进行预测的即每个输入包含特征值并与一个标签值相关联。这就是所谓的监督学习。然而通常我们需要处理没有标签的大数据集。想象一下一个企业需要根据购买行为、人口统计学、地址等信息了解不同的客户群体从而能够提供更好的服务、产品和促销活动。这类问题可以通过使用无监督学习技术来解决。K-Means 算法是机器学习中广泛使用的无监督学习算法。它简洁而优雅的方法使得将数据集分成 K 个不同的簇成为可能从而可以从未标记的数据中学习模式。2. K-Means 算法做什么如前所述K-Means 算法旨在将数据点划分为给定数量的簇。每个簇中的点是相似的而不同簇中的点有显著的差异。话虽如此一个问题随之而来我们如何定义相似性或差异在 K-Means 聚类中欧几里得距离是最常用的度量相似性的指标。在下图中我们可以清楚地看到 3 个不同的组。因此我们可以确定每个组的中心并且每个点将与最接近的中心关联。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0ec2067871637ccf83430558df44cfbf.png带有 200 个观测值的模拟数据集图片由作者提供。通过这样做从数学角度来说目标是最小化簇内方差即每个点与其最接近的中心之间的相似性度量。执行上述示例中的任务很简单因为数据是二维的且各组之间差异明显。然而随着维度的增加和考虑不同的 K 值我们需要一种算法来处理复杂性。第 1 步选择初始中心随机选择我们需要为算法提供初始中心向量这些向量可以从数据中随机选择或者生成与原始数据相同维度的随机向量。请参见下图中的白色菱形。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/33dd2f443181dc5507406b8ec38c9077.png初始中心是随机选择的图片由作者提供。第 2 步找到每个点到中心的距离现在我们将计算每个数据点到 K 个中心的距离。然后将每个点与离它最近的中心关联。给定一个包含N条数据和M个特征的数据集可以通过以下公式计算到中心c的距离https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/01b720e1312e5eea301af0f6dfa65c36.png欧几里得距离图像通过 codecogs.com 生成。其中k从 1 到K变化D是点 n 到k中心的距离x是点向量c是中心向量。因此对于每个数据点n我们将得到 K 个距离然后我们需要将该向量标记为与最小距离的中心关联https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/6c1fb0e5d6b3deeba9e459fef5ca022c.png图像通过 codecogs.com 生成其中D是一个包含K个距离的向量。第 3 步找到K个质心并进行迭代对于每个K个簇重新计算质心。新的质心是分配给该簇的所有数据点的均值。然后更新质心的位置使用新计算出的质心。检查质心是否发生了显著变化。这可以通过将当前迭代中的质心位置与上一迭代中的质心位置进行比较来完成。如果质心发生了显著变化请返回第 2 步。如果没有算法已收敛过程停止。见下图。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0c157b01ce3cb851db9481f3b53f5786.png质心的收敛作者提供的图片。3. 在 Python 中的实现现在我们已经了解了 K-Means 算法的基本概念是时候实现一个 Python 类了。所使用的包包括 Numpy 进行数学计算、Matplotlib 进行可视化以及 Sklearn 中的 Make_blobs 包用于生成模拟数据。# import required packagesimportnumpyasnpimportmatplotlib.pyplotaspltfromsklearn.datasetsimportmake_blobs该类将具有以下方法初始化方法一个构造方法用于初始化算法的基本参数聚类的值k最大迭代次数max_iter以及当没有显著改善时中止优化的容忍度tol。辅助函数这些方法旨在协助训练过程中的优化如计算欧几里得距离、随机选择初始质心、将每个点分配给最近的质心、更新质心的值以及验证优化是否收敛。拟合与预测方法如前所述K-Means 算法是一种无监督学习技术这意味着它在训练过程中不需要标签数据。这样需要一种单一的方法来拟合数据并预测每个数据点所属的聚类。总误差方法评估优化质量的方法通过计算优化的总平方误差。这将在下一节中详细探讨。以下是完整的代码# helper function for calculating Euclidean distancedefeuclidean_distance(a,b):dnp.sqrt(np.sum((a-b)**2))returndclassKmeans:# construct method for hyperparameter initializationdef__init__(self,k3,max_iter100,tol1e-06):self.kk self.max_itermax_iter self.toltol# randomly picks the initial centroids from the input datadefpick_centers(self,X):centers_idxsnp.random.choice(self.n_samples,self.k)returnX[centers_idxs]# finds the closest centroid for each data pointdefget_closest_centroid(self,x,centroids):distances[euclidean_distance(x,centroid)forcentroidincentroids]returnnp.argmin(distances)# creates a list with lists containing the idxs of each clusterdefcreate_clusters(self,centroids,X):clusters[[]for_inrange(self.k)]labelsnp.empty(self.n_samples)fori,xinenumerate(X):centroid_idxself.get_closest_centroid(x,centroids)clusters[centroid_idx].append(i)labels[i]centroid_idxreturnclusters,labels# calculates the centroids for each cluster using the mean valuedefcompute_centroids(self,clusters,X):centroidsnp.empty((self.k,self.n_features))fori,clusterinenumerate(clusters):centroids[i]np.mean(X[cluster],axis0)returncentroids# helper function to verify if the centroids changed significantlydefis_converged(self,old_centroids,new_centroids):distances[euclidean_distance(old_centroids[i],new_centroids[i])foriinrange(self.k)]return(sum(distances)self.tol)# method to train the data, find the optimized centroids and label each data point according to its clusterdeffit_predict(self,X):self.n_samples,self.n_featuresX.shape self.centroidsself.pick_centers(X)foriinrange(self.max_iter):self.clusters,self.labelsself.create_clusters(self.centroids,X)new_centroidsself.compute_centroids(self.clusters,X)ifself.is_converged(self.centroids,new_centroids):breakself.centroidsnew_centroids# method for evaluating the intracluster variance of the optimizationdefclustering_errors(self,X):cluster_values[X[cluster]forclusterinself.clusters]squared_distances[]# calculation of total squared Euclidean distancefori,cluster_arrayinenumerate(cluster_values):squared_distances.append(np.sum((cluster_array-self.centroids[i])**2))total_errornp.sum(squared_distances)returntotal_error4. 评估与解释现在我们将使用 K-Means 类对模拟数据进行聚类。为此将使用 Sklearn 库中的 make_blobs 包。数据由 500 个二维点组成具有 4 个固定的中心。# create simulated data for examplesX,_make_blobs(n_samples500,n_features2,centers4,shuffleFalse,random_state0)https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0c6ff01bc9de6ffa2c0a4b553b15d86e.png模拟数据作者提供的图片。在使用四个聚类进行训练后我们得到了以下结果。modelKmeans(k4)model.fit_predict(X)labelsmodel.labels centroidsmodel.centroids plot_clusters(X,labels,centroids)https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2beea78e39fb0e4730512b9c829df0ad.pngk4 的聚类作者提供的图片。在这种情况下算法成功地通过 18 次迭代计算出了聚类。然而我们必须记住模拟数据已经知道了最优的聚类数。在实际应用中我们通常不知道这个值。如前所述K-Means 算法的目标是尽量减小类内方差。用于计算该方差的度量是总平方欧几里得距离计算公式为https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/72661e266df6e85c3b4301407fe58c8c.png总平方欧几里得距离公式作者通过 codecogs.com 提供的图片。其中p 是一个簇中的数据点数量c_i 是一个簇的质心向量K 是簇的数量。换句话说上面的公式将数据点到最近质心的距离相加。随着 K 值的增加误差会减小。在极端情况下当 K N 时你会为每个数据点创建一个簇此时误差将为零。Willmott, Paul (2019)。如果我们将误差与簇的数量绘制出来并观察图形“弯曲”的位置我们就能找到最佳簇数。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/cb9e6cb88d7dfb252a6602ef6d826078.png屏幕图作者提供的图像。如我们所见图形呈现“肘部形状”并在 K 4 时弯曲这意味着对于更大的 K 值误差的减少将不再显著。5. 结论和下一步在本文中我们介绍了 K-Means 算法背后的基本概念、用途和应用。此外通过这些概念我们能够从零开始实现一个 Python 类执行模拟数据的聚类并展示如何通过屏幕图找到 K 的最佳值。然而由于我们使用的是无监督技术还有一个额外的步骤。算法可以成功地为簇分配标签但每个标签的含义是数据科学家或机器学习工程师通过分析每个簇的数据来完成的任务。此外我还将留下一些供进一步探索的要点我们的模拟数据使用了二维点。尝试将该算法应用于其他数据集并找到 K 的最佳值。还有其他广泛使用的无监督学习算法如层次聚类。根据问题领域可能需要使用其他误差度量如曼哈顿距离和余弦相似度。尝试研究它们。完整代码可在此处获取[## ML-and-Ai-from-scratch/K-Means 在 main · Marcussena/ML-and-Ai-from-scratch从零开始实现的机器学习和人工智能算法 - ML-and-Ai-from-scratch/K-Means 在 main ·…github.com](https://github.com/Marcussena/ML-and-Ai-from-scratch/tree/main/K-Means?sourcepost_page-----065bc42637e4--------------------------------)请随时使用和改进代码、评论、提出建议并通过LinkedIn、X和Github与我联系。参考文献[1] Sebastian Raschka (2015), 《Python 机器学习》。[2] Willmott, Paul. (2019).机器学习应用数学导论。Panda Ohana 出版社。[3] Géron, A. (2017).动手学机器学习。O’Reilly Media Inc.[4] Grus, Joel. (2015).从零开始学数据科学. O’Reilly Media Inc.