从K-Means(Voronoi单元)中获得决策的边界。

Question

我有一个K-means的实现，它可以返回聚类。所说的聚类是为了给一个城市做esselate。我感兴趣的是得到每个簇的边界，即voronoi单元。我的代码如下。

class K_Means:
  def __init__(self, k=2, tol=0.001, max_iter=300):
      self.k = k
      self.tol = tol
      self.max_iter = max_iter

  def fit(self,data):

      self.centroids = {}

      for i in range(self.k):
          self.centroids[i] = data[i]

      for i in range(self.max_iter):
          self.classifications = {}

          for i in range(self.k):
              self.classifications[i] = []

          for featureset in data:
              distances = [np.linalg.norm(featureset-self.centroids[centroid]) for centroid in self.centroids]
              classification = distances.index(min(distances))
              self.classifications[classification].append(featureset)

          prev_centroids = dict(self.centroids)

          for classification in self.classifications:
              self.centroids[classification] = np.average(self.classifications[classification],axis=0)

          optimized = True

          for c in self.centroids:
              original_centroid = prev_centroids[c]
              current_centroid = self.centroids[c]
              if np.sum((current_centroid-original_centroid)/original_centroid*100.0) > self.tol:
                  print(np.sum((current_centroid-original_centroid)/original_centroid*100.0))
                  optimized = False

          if optimized:
              break

  def predict(self,data):
      distances = [np.linalg.norm(data-self.centroids[centroid]) for centroid in self.centroids]
      classification = distances.index(min(distances))
      return classification

X = df[['order_latitude', 'order_longitude']].to_numpy()
# plt.scatter(*zip(*X))
model = K_Means()
model.fit(X)

我的数据框架是这样的:

    order_latitude  order_longitude
0   38.3477022  -0.4927108
1   38.3624854  -0.4809995
2   38.3416865  -0.5005017
3   38.347822   -0.4882809
4   38.3511359  -0.4866966
5   38.3603331  -0.4869405
6   38.3433719  -0.4964212
7   38.3507314  -0.5098433
8   38.3576242  -0.4829199
9   38.3624383  -0.4878071
10  38.3511359  -0.4866966

我正确地创建了群集, 但我无法创建边界. 我不能使用k-means的库，因为尽管我的例子显示了通常的规范，但在真实的例子中，我需要使用我知道的任何库都没有实现的距离（节点之间的旅行时间）。我试着用scipy Voronoi，但数据在地理上是稀疏的，它不可能实现。其他相关问题如下 根据kmeans聚类中心绘制边界线。 有一个有希望的答案，但我又不能适合我自己的度量，它以一种不需要的方式聚类。

Answer 1

恐怕有了自定义规范，你就得靠自己了。

如果你能够得到一个圆的方程，两个点的二分线和三个点的圆心（三个二分线的交点）的方程，你可以制作一个蛮力算法，通过枚举所有无点的圆周（这是一个O(n^4)的过程:-( )，给出Voronoi顶点，通过连接圆周与公共的一对点，你可以得到Voronoi边。