KMeans++算法理论和实现

缺乏、安全感 2022-02-24 09:06 335阅读 0赞
  • https://github.com/Sean16SYSU/MachineLearningImplement

简述

在Kmeans当中，有两个限制

  • 定义在凸欧式空间上，使得在非凸空间上的聚类效果一般，在非欧式空间上无法计算均值点。
  • 病态初始化问题，由于初始化完全随机，会使得生成的点收到限制，最后聚类的结果不好

第一类问题的主流解决方案就是，转换距离度量的方式，这样能使得做到一定的扩展。但任然没有办法解决非欧式空间的问题。
KMeans++这篇论文主要关注于第二个问题。

  • KMeans的算法和实现就不再赘述了。可以看 K-Means算法理论及Python实现

这里主要描述KMeans++的算法思路（聚焦于初始化）

  1. 先随机选一个点，作为初始的中心

  2. 之后，在其他没有选的点中，找到离已经选好的点最远的点（即，离中心点集中点的最小距离的值，在所有的没有被选中为中心点的点中是距离最大的点）
    X i = a r g m a x i = 0 n ( min ⁡ j = 1 m ∣ ∣ x i − c j ∣ ∣ 2 ) X_i = argmax_{i=0}^n( \min_{j=1}^m{||x_i - c_j||^2}) Xi​=argmaxi=0n​(j=1minm​∣∣xi​−cj​∣∣2)

    • 其中n为点数，m为被选中心数
  3. 选出来的点放入中心集合中，一直到最后选完k个初始化的中心
  4. 之后，接着完成KMeans操作即可

很明显这样的点在一开始的时候就足够的分散，就不会出现病态初始化的问题了，虽然这样的计算量会很大。

Python实现

  1. import numpy as np
  2. def k_means_pp(X, k=3):
  3.     def centroid_pick(X, k):
  4.         node = np.random.randint(0, len(X))
  5.         centroids = [node]
  6.         while len(centroids) < k:
  7.             centroids.append(
  8.                 np.argmax(
  9.                     [np.min([np.linalg.norm(xi - cj) if i not in centroids else -np.inf for cj in centroids ]) for i, xi in enumerate(X)]
  10.                 )
  11.             )
  12.         return np.array(centroids)
  14.     centroids = X[centroid_pick(X, k)]
  15.     y = np.arange(len(X))
  16.     while True:
  17.         y_new = np.arange(len(X))
  18.         for i, xi in enumerate(X):
  19.             y_new[i] = np.argmin([np.linalg.norm(xi - cj) for cj in centroids])
  20.         if sum(y != y_new) == 0:
  21.             break
  22.         for j in range(k):
  23.             centroids[j] = np.mean(X[np.where(y_new == j)], axis=0)
  24.         y = y_new.copy()
  25.     return y

  • 用iris检查

    from sklearn import datasets

    iris = datasets.load_iris()
    test_y = k_means_pp(iris.data)

  • 评估方式

    def evaluate(y, t):

    1. a, b, c, d = [0 for i in range(4)]
    2. for i in range(len(y)):
    3.     for j in range(i+1, len(y)):
    4.         if y[i] == y[j] and t[i] == t[j]:
    5.             a += 1
    6.         elif y[i] == y[j] and t[i] != t[j]:
    7.             b += 1
    8.         elif y[i] != y[j] and t[i] == t[j]:
    9.             c += 1
    10.         elif y[i] != y[j] and t[i] != t[j]:
    11.             d += 1
    12. return a, b, c, d

    def external_index(a, b, c, d, m):

    1. JC = a / (a + b + c)
    2. FMI = np.sqrt(a**2 / ((a + b) * (a + c)))
    3. RI = 2 * ( a + d ) / ( m * (m + 1) )
    4. return JC, FMI, RI

    def evaluate_it(y, t):

    1. a, b, c, d = evaluate(y, t)
    2. return external_index(a, b, c, d, len(y))

得到的结果是






















External index Value
JC 0.6822787660436839
FMI 0.8112427991975698
RI 0.8621633554083885
  • 实验效果

在这里插入图片描述

  • 真实效果

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，335人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Kmeans算法实现

    K-均值算法，是非监督学习中的聚类算法。 基本思想 k-means算法比较简单。在k-means算法中，用cluster来表示簇；容易证明k-means算法收敛等同于所有质

    秒速五厘米秒速五厘米/ 0 赞/ 356 阅读