点击上方“进修编程”，选择“星标”公众号
超级无敌干货，第一时间送达！！！
在本文中，向大家讲解 K-Means 算法，我将从基本概念开始，并实现一个仅使用 Numpy 包执行聚类任务的 Python 类。
无论是试图对概念建立牢固理解的机器学习初学者，还是对创建自定义机器学习应用程序感兴趣并需要了解算法内部工作原理的从业者，本文都适合您。
1. 简介
大多数广泛使用的机器学习算法，例如线性回归、逻辑回归、决策树等，都适用于根据标记数据进行预测，也就是说，每个输入都包含与标签值相关的特征值。这就是所谓的监督学习。
然而，我们经常需要处理大量没有标签的数据。想象一下，一家企业需要根据购买行为、人口统计、地址和其他信息了解不同的客户群体，从而提供更好的服务、产品和促销活动。
可以使用无监督学习技术来解决这些类型的问题。K-Means 算法是机器学习中广泛使用的无监督学习算法。其简单而优雅的方法可以将数据集分成所需数量的 K 个不同簇，从而允许人们从未标记的数据中学习模式。
2. K-Means 算法起什么作用？
如前所述，K-Means 算法试图将数据点划分为给定数量的簇。每个簇内的点相似，而不同簇内的点有相当大的差异。
话虽如此，但有一个问题出现了：我们如何定义相似性或差异性？在 K-Means 聚类中，欧几里得距离是衡量相似性的最常用指标。
在下图中，我们可以清楚地看到 3 个不同的组。因此，我们可以确定每个组的中心，并且每个点都会与最近的中心相关联。
从数学上来说，这样做的目的是尽量减少类内方差，即每个点与其最近的中心之间的相似性的测量。
执行上述示例中的任务很简单，因为数据是二维的，而且组别明显不同。然而，随着维数的增加和考虑不同的 K 值，我们需要一种算法来处理复杂性。
步骤 1：选择初始中心（随机）
我们需要用初始中心向量作为算法的种子，这些向量可以从数据中随机选择，也可以生成与原始数据具有相同维度的随机向量。请参见下图中的白色菱形。
初始中心是随机选取的（图片来自作者）。
步骤 2：找到每个点到中心的距离
现在，我们将计算每个数据点到 K 个中心的距离。然后我们将每个点与最接近该点的中心关联起来。
给定一个具有N 个条目和M 个特征的数据集，到中心c的距离可以通过以下公式给出：
k从 1 到K变化；
D为点n到k中心的距离；
x是点向量；
c是中心向量。
因此，对于每个数据点n，我们将有 K 个距离，然后我们必须将向量标记为具有最小距离的中心：
其中D是具有K 个距离的向量。
步骤 3：找到K 个质心并迭代
对于K 个簇中的每一个，重新计算质心。新的质心是分配给该簇的所有数据点的平均值。然后将质心的位置更新为新计算的质心位置。
检查质心与上一次迭代相比是否发生了显著变化。这可以通过比较当前迭代中的质心位置与上一次迭代中的质心位置来完成。
如果质心发生了显著变化，则返回步骤 2。如果没有，则算法已收敛并且过程停止。参见下图。
质心的收敛（图片由作者提供）。
3. Python 实现
现在我们已经了解了 K-Means 算法的基本概念，是时候实现一个 Python 类了。使用的包是用于数学计算的 Numpy、用于可视化的 Matplotlib 和用于模拟数据的 Sklearn 的 Make_blobs 包。
# 导入所需包import numpy as npimport matplotlib.pyplot as pltfrom sklearn.datasets import make_blobs
该类将具有以下方法：
Init 方法
构造函数方法用于初始化算法的基本参数：聚类的值k、最大迭代次数max_iter以及容差tol值，以便在没有明显改善时中断优化。
辅助函数
这些方法旨在协助训练期间的优化过程，例如计算欧几里得距离、随机选择初始质心、为每个点分配最近的质心、更新质心的值以及验证优化是否收敛。
拟合预测方法
如前所述，K-Means 算法是一种无监督学习技术，这意味着它在训练过程中不需要标记数据。这样一来，就需要一种单一的方法来拟合数据并预测每个数据点属于哪个聚类。
总误差法
通过计算优化的总平方误差来评估优化质量的方法。这将在下一节中进行探讨。
完整代码如下：
# helper function for calculating Euclidean distancedef euclidean_distance(a,b):d = np.sqrt(np.sum((a - b)**2))return dclass Kmeans:# construct method for hyperparameter initializationdef __init__(self, k=3, max_iter=100, tol=1e-06):self.k = kself.max_iter = max_iterself.tol = tol# randomly picks the initial centroids from the input datadef pick_centers(self, X):centers_idxs = np.random.choice(self.n_samples, self.k)return X[centers_idxs]# finds the closest centroid for each data pointdef get_closest_centroid(self, x, centroids):distances = [euclidean_distance(x, centroid) for centroid in centroids]return np.argmin(distances)# creates a list with lists containing the idxs of each clusterdef create_clusters(self, centroids, X):clusters = [[] for _ in range(self.k)]labels = np.empty(self.n_samples)for i, x in enumerate(X):centroid_idx = self.get_closest_centroid(x, centroids)clusters[centroid_idx].append(i)labels[i] = centroid_idxreturn clusters, labels# calculates the centroids for each cluster using the mean valuedef compute_centroids(self, clusters, X):centroids = np.empty((self.k, self.n_features))for i, cluster in enumerate(clusters):centroids[i] = np.mean(X[cluster], axis=0)return centroids# helper function to verify if the centroids changed significantlydef is_converged(self, old_centroids, new_centroids):distances = [euclidean_distance(old_centroids[i], new_centroids[i]) for i in range(self.k)]return (sum(distances) < self.tol)# method to train the data, find the optimized centroids and label each data point according to its clusterdef fit_predict(self, X):self.n_samples, self.n_features = X.shapeself.centroids = self.pick_centers(X)for i in range(self.max_iter):self.clusters, self.labels = self.create_clusters(self.centroids, X)new_centroids = self.compute_centroids(self.clusters, X)if self.is_converged(self.centroids, new_centroids):breakself.centroids = new_centroids# method for evaluating the intracluster variance of the optimizationdef clustering_errors(self, X):cluster_values = [X[cluster] for cluster in self.clusters]squared_distances = []# calculation of total squared Euclidean distancefor i, cluster_array in enumerate(cluster_values):squared_distances.append(np.sum((cluster_array - self.centroids[i])**2))total_error = np.sum(squared_distances)return total_error
4. 评估与解释
现在我们将使用 K-Means 类对模拟数据进行聚类。为此，我们将使用 Sklearn 库中的 make_blobs 包。数据由 500 个二维点和 4 个固定中心组成。
# 为示例创建模拟数据X, _ = make_blobs(n_samples= 500 , n_features= 2 , centers= 4 ,shuffle= False , random_state= 0 )
使用四个聚类进行训练后，我们得到以下结果。
model = Kmeans(k=4)4)model.fit_predict(X)labels = model.labelscentroids =model.centroidsplot_clusters(X, labels, centroids)
在这种情况下，该算法能够通过 18 次迭代成功计算出聚类。但是，我们必须记住，我们已经从模拟数据中知道了最佳聚类数。在实际应用中，我们通常不知道该值。
如前所述，K-Means 算法旨在使簇内方差尽可能小。用于计算该方差的度量是欧几里得距离的平方，如下所示：
p 是一个簇中的数据点的数量；
c_i 是聚类的质心向量；
K 是聚类的数量。
简而言之，上述公式将数据点到最近质心的距离相加。误差随着 K 值的增加而减小。
在 K =N 的极端情况下，每个数据点都有一个聚类，并且该误差为零。
如果我们将误差与聚类数量的关系绘制出来，并观察图形“弯曲”的位置，我们就能够找到最佳聚类数量。
我们可以看到，该图呈“肘形”，在 K = 4 处弯曲，这意味着，对于较大的 K 值，总误差的减少将不那么明显。
5. 结论和下一步
在本文中，我们介绍了 K-Means 算法背后的基本概念、其用途和应用。此外，利用这些概念，我们能够从头开始实现一个 Python 类，该类执行模拟数据的聚类以及如何使用碎石图找到 K 的最佳值。
但是，由于我们处理的是无监督技术，因此还有一个额外的步骤。该算法可以成功地为簇分配标签，但每个标签的含义是数据科学家或机器学习工程师必须通过分析每个簇的数据来完成的任务。
欢迎点赞关注！本人五年项目开发经验接matlab、python程序设计！
— 完 —
