基于加权密度和最大最小距离的Kmeans聚类算法

P33、基于加权密度和最大最小距离的Kmeans聚类算法 本程序实现一种基于加权密度和最大最小距离的Kmeans聚类算法，利用加权密度法选取初始聚类中心点集，减少了离群点对聚类结果的影响，通过最大最小距离准则启发式地选择聚类中心，避免了聚类结果陷入局部最优。 最后通过轮廓系数选取最佳聚类中心，并且进行了结果的可视化。 算法逻辑清楚，注释详细，支持

最近在研究聚类算法，发现了一种超有意思的基于加权密度和最大最小距离的Kmeans聚类算法，必须来和大家分享一下😎

算法亮点

这个算法有两个很牛的地方。首先，它利用加权密度法来选取初始聚类中心点集。这就好比给每个点都赋予了一个“重要性”权重，离群点因为自身的独特性，权重相对较低，这样在选取初始中心点时就不容易被它们干扰，大大减少了离群点对聚类结果的影响🧐。

然后呢，它通过最大最小距离准则启发式地选择聚类中心。简单来说，就是在选择聚类中心的时候，会考虑到各个点之间的距离关系，避免聚类结果陷入局部最优的困境。想象一下，如果只按照普通的方式选聚类中心，很可能就被困在某个不太好的局部最优解里了，而这个算法就巧妙地避开了这个问题👏。

代码实现

import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_blobs from sklearn.preprocessing import StandardScaler # 生成示例数据 X, _ = make_blobs(n_samples=1000, centers=3, random_state=42) scaler = StandardScaler() X_scaled = scaler.fit_transform(X) # 计算加权密度 def weighted_density(X, h): n = X.shape[0] density = np.zeros(n) for i in range(n): dist = np.linalg.norm(X - X[i], axis=1) density[i] = np.sum(np.exp(-dist**2 / (2 * h**2))) density = density / np.sum(density) return density # 基于加权密度选择初始聚类中心 def select_initial_centers(X, k, h): density = weighted_density(X, h) centers = [] for _ in range(k): idx = np.argmax(density) centers.append(X[idx]) density[idx] = 0 return np.array(centers) # 计算最大最小距离 def max_min_distance(X, centers): distances = np.linalg.norm(X[:, np.newaxis] - centers, axis=2) min_distances = np.min(distances, axis=1) max_min_dist = np.max(min_distances) return max_min_dist # 基于最大最小距离准则启发式选择聚类中心 def heuristic_centers(X, centers, k): best_max_min_dist = -np.inf best_centers = None for _ in range(10): # 简单的迭代尝试，这里可以根据需要调整 new_centers = [] for i in range(k): dist_to_center = np.linalg.norm(X - centers[i], axis=1) non_cluster_points = X[dist_to_center > 0] if non_cluster_points.size > 0: candidate_center = non_cluster_points[np.argmax(np.linalg.norm(non_cluster_points - centers[i], axis=1))] else: candidate_center = X[np.argmax(np.linalg.norm(X - centers[i], axis=1))] new_centers.append(candidate_center) new_centers = np.array(new_centers) max_min_dist = max_min_distance(X, new_centers) if max_min_dist > best_max_min_dist: best_max_min_dist = max_min_dist best_centers = new_centers return best_centers # Kmeans聚类 def kmeans(X, k, h, max_iter=100): centers = select_initial_centers(X, k, h) centers = heuristic_centers(X, centers, k) for _ in range(max_iter): distances = np.linalg.norm(X[:, np.newaxis] - centers, axis=2) labels = np.argmin(distances, axis=1) new_centers = np.array([X[labels == i].mean(axis=0) for i in range(k)]) if np.allclose(new_centers, centers): break centers = new_centers return centers, labels # 计算轮廓系数 def silhouette_score(X, labels, centers): n = X.shape[0] s = 0 for i in range(n): a = np.mean([np.linalg.norm(X[i] - X[j]) for j in range(n) if labels[j] == labels[i]]) b = np.min([np.mean([np.linalg.norm(X[i] - X[j]) for j in range(n) if labels[j] != labels[i]])]) s += (b - a) / max(a, b) s /= n return s # 运行聚类算法 k = 3 h = 0.5 centers, labels = kmeans(X_scaled, k, h) # 计算轮廓系数并找到最佳聚类中心 scores = [] for i in range(10): # 简单的迭代尝试，这里可以根据需要调整 centers, labels = kmeans(X_scaled, k, h) score = silhouette_score(X_scaled, labels, centers) scores.append(score) best_score_idx = np.argmax(scores) best_centers = centers best_labels = labels # 可视化结果 plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=best_labels) plt.scatter(best_centers[:, 0], best_centers[:, 1], c='red', marker='x') plt.show()

代码分析

数据生成与预处理

# 生成示例数据 X, _ = make_blobs(n_samples=1000, centers=3, random_state=42) scaler = StandardScaler() X_scaled = scaler.fit_transform(X)

这里使用make_blobs生成了1000个样本，分为3类的数据集。然后通过StandardScaler对数据进行标准化处理，让数据具有更好的特征尺度，有利于后续的聚类算法运行。

计算加权密度

def weighted_density(X, h): n = X.shape[0] density = np.zeros(n) for i in range(n): dist = np.linalg.norm(X - X[i], axis=1) density[i] = np.sum(np.exp(-dist**2 / (2 * h**2))) density = density / np.sum(density) return density

这个函数通过计算每个点到其他点的距离，并利用高斯核函数进行加权求和，得到每个点的加权密度。其中h是高斯核的带宽参数，控制着密度计算的平滑程度。

基于加权密度选择初始聚类中心

def select_initial_centers(X, k, h): density = weighted_density(X, h) centers = [] for _ in range(k): idx = np.argmax(density) centers.append(X[idx]) density[idx] = 0 return np.array(centers)

这里根据加权密度的大小，依次选择k个点作为初始聚类中心。每次选择后，将该点的密度设为0，避免重复选择。

计算最大最小距离

def max_min_distance(X, centers): distances = np.linalg.norm(X[:, np.newaxis] - centers, axis=2) min_distances = np.min(distances, axis=1) max_min_dist = np.max(min_distances) return max_min_dist

这个函数计算每个点到最近聚类中心的距离，然后取这些距离中的最大值，作为最大最小距离。

基于最大最小距离准则启发式选择聚类中心

def heuristic_centers(X, centers, k): best_max_min_dist = -np.inf best_centers = None for _ in range(10): # 简单的迭代尝试，这里可以根据需要调整 new_centers = [] for i in range(k): dist_to_center = np.linalg.norm(X - centers[i], axis=1) non_cluster_points = X[dist_to_center > 0] if non_cluster_points.size > 0: candidate_center = non_cluster_points[np.argmax(np.linalg.norm(non_cluster_points - centers[i], axis=1))] else: candidate_center = X[np.argmax(np.linalg.norm(X - centers[i], axis=1))] new_centers.append(candidate_center) new_centers = np.array(new_centers) max_min_dist = max_min_distance(X, new_centers) if max_min_dist > best_max_min_dist: best_max_min_dist = max_min_dist best_centers = new_centers return best_centers

这个函数通过多次迭代尝试，根据最大最小距离准则不断优化聚类中心的选择。每次迭代中，对于每个聚类中心，选择距离它最远的非聚类点作为新的候选中心，然后重新计算最大最小距离，保留最优的聚类中心集合。

Kmeans聚类

def kmeans(X, k, h, max_iter=100): centers = select_initial_centers(X, k, h) centers = heuristic_centers(X, centers, k) for _ in range(max_iter): distances = np.linalg.norm(X[:, np.newaxis] - centers, axis=2) labels = np.argmin(distances, axis=1) new_centers = np.array([X[labels == i].mean(axis=0) for i in range(k)]) if np.allclose(new_centers, centers): break centers = new_centers return centers, labels

这里实现了完整的Kmeans聚类算法流程。首先根据加权密度和最大最小距离准则选择初始聚类中心，然后通过迭代更新聚类中心和样本的聚类标签，直到聚类中心不再变化或者达到最大迭代次数。

计算轮廓系数并找到最佳聚类中心

def silhouette_score(X, labels, centers): n = X.shape[0] s = 0 for i in range(n): a = np.mean([np.linalg.norm(X[i] - X[j]) for j in range(n) if labels[j] == labels[i]]) b = np.min([np.mean([np.linalg.norm(X[i] - X[j]) for j in range(n) if labels[j] != labels[i]])]) s += (b - a) / max(a, b) s /= n return s # 运行聚类算法 k = 3 h = 0.5 centers, labels = kmeans(X_scaled, k, h) # 计算轮廓系数并找到最佳聚类中心 scores = [] for i in range(10): # 简单的迭代尝试，这里可以根据需要调整 centers, labels = kmeans(X_scaled, k, h) score = silhouette_score(X_scaled, labels, centers) scores.append(score) best_score_idx = np.argmax(scores) best_centers = centers best_labels = labels

这里定义了计算轮廓系数的函数，通过多次运行聚类算法并计算轮廓系数，找到轮廓系数最大时对应的聚类中心，认为是最佳聚类中心。

可视化结果

# 可视化结果 plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=best_labels) plt.scatter(best_centers[:, 0], best_centers[:, 1], c='red', marker='x') plt.show()

最后通过matplotlib将聚类结果可视化，不同颜色的点表示不同的聚类类别，红色的叉表示聚类中心。

P33、基于加权密度和最大最小距离的Kmeans聚类算法 本程序实现一种基于加权密度和最大最小距离的Kmeans聚类算法，利用加权密度法选取初始聚类中心点集，减少了离群点对聚类结果的影响，通过最大最小距离准则启发式地选择聚类中心，避免了聚类结果陷入局部最优。 最后通过轮廓系数选取最佳聚类中心，并且进行了结果的可视化。 算法逻辑清楚，注释详细，支持

这个基于加权密度和最大最小距离的Kmeans聚类算法真的很有创新性，通过巧妙的方法解决了离群点和局部最优的问题，代码实现也很清晰易懂😃。希望大家喜欢这篇分享！

你对这个算法有什么看法或者疑问吗🧐？欢迎在评论区留言讨论呀！

#聚类算法 #加权密度 #最大最小距离 #Kmeans