Получение границ решения из K-средних (ячейки Вороного) - PullRequest
Новая
       79

Получение границ решения из K-средних (ячейки Вороного)

0 голосов
/ 27 мая 2020

У меня есть реализация K-средних, которая возвращает кластеры. Указанный кластер предназначен для тесселяции города. Что меня интересует, так это получить границу каждого кластера, ячеек Вороного. Мой код выглядит следующим образом: 

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-средних, поскольку, хотя мой пример показывает обычную норму, в реальном мне нужно использовать расстояния, не реализованные ни в одной из известных мне библиотек (время в пути между узлами). Я пробовал использовать scipy Voronoi, но данные по географии скудны, это не однозначно. Другие связанные вопросы, такие как Рисование граничных линий на основе центров кластеров kmeans , имеют многообещающий ответ, но опять же, я не могу уместить свой собственный metri c, и он группируется нежелательным образом.

1 Ответ

0 голосов
/ 28 мая 2020

Боюсь, что с индивидуальной нормой вы будете сами по себе.

Если вы можете получить уравнения окружности, биссектрисы двух точек и центра описанной окружности трех точек (пересечение из трех биссектрис), вы можете создать алгоритм грубой силы, который работает, перечисляя все описанные окружности без точек (это процесс O (n ^ 4) :-(), давая вершины Вороного и соединяя описанные окружности с обычная пара точек, получается ребро Вороного.

...