当前位置:   article > 正文

MinibatchKmeans——牺牲精度换取效率的一种kmeans改良

minibatchkmeans

申明:本代码为chatgpt生成,作者乃菜鸟一枚。 

大致算法流程:

  1. 随机选取k个质心
  2. 根据设定的batch_size大小随机选取batch_size个样本作为代表样本集
  3. 计算代表样本集中每个样本到每个质心的距离,分别归到最近的质心所在簇
  4. 计算当前聚类簇的平均值,作为新的质心(原质心也参与平均值的计算)
  5. 判断是否已经收敛:如果聚类标签不再改变,则结束迭代
  6. 重复执行2-5步,直到算法收敛

参数:参照sklean.Minibatchkmeans,此处参数为:

  1. X:数据集
  2. y_pred_init:标签
  3. n_cluster:簇数
  4. batch_size:代表样本集大小
  5. n_init:随机选取初始质心次数
  6. max_iter:最大迭代次数
  1. # 运行 mini-batch kmeans 算法
  2. minibatch_kmeans(X, y, n_clusters=2, batch_size=5, n_init=1, max_iter=15)

样本集:生成了一个只有30个样本,二维的,分为两类的样本集

  1. # 生成 30 个样本,每个样本有 2个特征,分为 2 类
  2. X = np.concatenate([
  3. np.random.normal(loc=[0, 0], scale=[0.3, 0.3], size=(10, 2)), # 类别 0
  4. np.random.normal(loc=[2, 2], scale=[0.3, 0.3], size=(10, 2)), # 类别 1
  5. ])

 

运行效果展示:

1.初始质心,将所有样本标签初始化为-1,表示未分类

  

 2.随机选取batch(batch_size=5)

 

  3. 计算距离、更新标签

        显然样本4距离质心一更近,故被赋予标签‘0’

 4.更新质心

        下面这张更加明显 

 

 5.把batch中的聚类结果合并到整个数据集中



6.判断收敛 

  1. n_iter_tol = 2 # 连续多少轮聚类结果相同认为已经收敛
  2. # 判断聚类是否已经收敛
  3. if np.array_equal(y_pred, y):
  4. n_iter_same += 1
  5. if n_iter_same >= n_iter_tol:
  6. break
  7. else:
  8. n_iter_same = 0

每轮聚类结果:

 

   

  

    第九轮和第十轮两轮没变化,结束迭代。

 完整代码:

  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3. np.random.seed(42)#删掉该值,每次随机生成样本集
  4. n_iter_tol = 2 # 连续多少轮聚类结果相同认为已经收敛
  5. def minibatch_kmeans(X, y, n_clusters, batch_size, n_init, max_iter):
  6. for i in range(n_init):
  7. # 初始化聚类标签:将所有样本的标签初始化为 -1(表示未知)
  8. y = np.zeros(X.shape[0], dtype=int) - 1
  9. # 初始化聚类质心和上一轮迭代的聚类结果
  10. centroids = X[np.random.choice(X.shape[0], n_clusters, replace=False)]
  11. y_pred = np.zeros(X.shape[0], dtype=np.int32) - 1
  12. # 绘制初始化的聚类质心和所有样本点
  13. plt.scatter(X[:, 0], X[:, 1], c='gray', alpha=0.5)
  14. plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', color='black', s=100)
  15. plt.title("Initialization")
  16. plt.show()
  17. for j in range(max_iter):
  18. print('第', j+ 1, '轮:y_pred=', y_pred)
  19. print('质心:', centroids)
  20. # 随机选择一个 mini-batch
  21. batch_indices = np.random.choice(X.shape[0], batch_size, replace=False)
  22. X_batch = X[batch_indices]
  23. y_pred_batch = y[batch_indices]
  24. print('batch_indices:', batch_indices)
  25. print('选的小样本集', X_batch)
  26. print('小样本集的标签', y_pred_batch)
  27. # 绘制 mini-batch 中的样本点和聚类质心
  28. plt.scatter(X[:, 0], X[:, 1], c='gray', alpha=0.5)
  29. plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', color='black', s=100)
  30. plt.scatter(X_batch[:, 0], X_batch[:, 1], c='blue', alpha=0.5)
  31. plt.title("Iteration %d: Selected mini-batch" % (j+1))
  32. plt.show()
  33. # 计算每个样本到每个质心的距离
  34. distances = np.sqrt(((X_batch - centroids[:, np.newaxis])**2).sum(axis=2))
  35. print('每个质心到每个样本的距离:', distances)
  36. # 将每个样本分配到距离最近的质心所在的聚类
  37. y_pred_batch = np.argmin(distances, axis=0)
  38. print('新y_pred_batch:', y_pred_batch)
  39. for k in range(n_clusters):
  40. # 选出当前聚类簇所属的样本点(包括原来的质心)
  41. cluster_points = np.vstack((X_batch[y_pred_batch == k], centroids[k]))
  42. # 计算当前聚类簇的平均值,作为新的质心
  43. if len(cluster_points) > 0:
  44. centroids[k] = np.mean(cluster_points, axis=0)
  45. # 绘制更新后的聚类质心和未知样本点
  46. plt.scatter(X[:, 0], X[:, 1], c='gray', alpha=0.5)
  47. plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', color='black', s=100)
  48. plt.title("Iteration %d: Update centroids" % (j+1))
  49. plt.show()
  50. # 将 mini-batch 中的聚类结果合并到整个数据集中
  51. y[batch_indices] = y_pred_batch
  52. print('y:',y)
  53. # 绘制 mini-batch 中的聚类结果和未知样本点
  54. plt.scatter(X[:, 0], X[:, 1], c=y, cmap='rainbow', alpha=0.5)
  55. plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', color='black', s=100)
  56. plt.title("Iteration %d: Mini-batch clustering" % (j+1))
  57. plt.show()
  58. print('y_pred:',y_pred)
  59. # 判断聚类是否已经收敛
  60. if np.array_equal(y_pred, y):
  61. n_iter_same += 1
  62. if n_iter_same >= n_iter_tol:
  63. break
  64. else:
  65. n_iter_same = 0
  66. y_pred = y.copy()
  67. # 绘制每个样本归为最近质心所在簇后的聚类结果和未知样本点
  68. distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))
  69. y_pred_final = np.argmin(distances, axis=0)
  70. plt.scatter(X[:, 0], X[:, 1], c=y_pred_final, cmap='rainbow', alpha=0.5)
  71. plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', color='black', s=100)
  72. plt.title("Final clustering")
  73. plt.show()
  74. # 生成 30 个样本,每个样本有 2个特征,分为 2 类
  75. X = np.concatenate([
  76. np.random.normal(loc=[0, 0], scale=[0.3, 0.3], size=(10, 2)), # 类别 0
  77. np.random.normal(loc=[2, 2], scale=[0.3, 0.3], size=(10, 2)), # 类别 1
  78. ])
  79. # 初始化聚类标签:将所有样本的标签初始化为 -1(表示未知)
  80. y = np.zeros(X.shape[0], dtype=int) - 1
  81. # 运行 mini-batch kmeans 算法
  82. minibatch_kmeans(X, y, n_clusters=2, batch_size=5, n_init=1, max_iter=15)
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/713487
推荐阅读
相关标签
  

闽ICP备14008679号