K-Means++ 聚类算法的初始质心优化
K-Means 聚类算法是一种经典的聚类算法，它通过迭代的方式将数据点分配到 K 个簇中，使得每个簇内的数据点尽可能接近，而簇与簇之间的数据点尽可能远离。K-Means 算法的一个主要问题是其初始质心的选择，不同的初始质心可能会导致不同的聚类结果。为了解决这个问题，K-Means++ 算法被提出，它通过优化初始质心的选择来提高聚类质量。
K-Means 算法概述
在介绍 K-Means++ 算法之前，我们先简要回顾一下传统的 K-Means 算法的基本步骤：
1. 随机选择 K 个数据点作为初始质心。
2. 将每个数据点分配到最近的质心，形成 K 个簇。
3. 计算每个簇的质心，并更新质心位置。
4. 重复步骤 2 和 3，直到质心不再变化或达到最大迭代次数。
K-Means++ 算法原理
K-Means++ 算法的主要思想是选择更好的初始质心，从而提高聚类质量。以下是 K-Means++ 算法的步骤：
1. 随机选择一个数据点作为第一个质心。
2. 对于数据集中的每个数据点，计算它与已选择质心的距离。
3. 根据距离的平方与所有距离平方和的比例，选择下一个质心。
4. 重复步骤 2 和 3，直到选择 K 个质心。
5. 使用 K-Means 算法的步骤 2 到 4 进行聚类。
K-Means++ 算法代码实现
下面是使用 Python 实现的 K-Means++ 算法的代码：
python
import numpy as np
def initialize_centroids_plusplus(data, k):
centroids = [data[np.random.randint(data.shape[0])]]
for _ in range(1, k):
distances = np.array([min([np.inner(c-x, c-x) for c in centroids]) for x in data])
probabilities = distances / distances.sum()
cumulative_probabilities = probabilities.cumsum()
r = np.random.rand()
for j, p in enumerate(cumulative_probabilities):
if r < p:
centroids.append(data[j])
break
return np.array(centroids)
def k_means_plusplus(data, k, max_iterations=100):
centroids = initialize_centroids_plusplus(data, k)
for _ in range(max_iterations):
clusters = [[] for _ in range(k)]
for x in data:
distances = np.linalg.norm(x - centroids, axis=1)
closest_centroid_index = np.argmin(distances)
clusters[closest_centroid_index].append(x)
new_centroids = np.array([np.mean(cluster, axis=0) for cluster in clusters])
if np.allclose(new_centroids, centroids):
break
centroids = new_centroids
return centroids, clusters
示例数据
data = np.random.rand(100, 2)
k = 3
运行 K-Means++
centroids, clusters = k_means_plusplus(data, k)
打印结果
print("Centroids:", centroids)
print("Clusters:", clusters)
结论
K-Means++ 算法通过优化初始质心的选择，提高了 K-Means 聚类算法的聚类质量。在实际应用中，选择合适的 K 值和优化算法参数对于获得良好的聚类结果至关重要。通过上述代码实现，我们可以看到 K-Means++ 算法的简洁性和高效性。在实际应用中，我们可以根据具体问题调整算法参数，以获得更好的聚类效果。
Comments NOTHING