TLDR : Важно, что проблема настроена в двухмерном . Для больших размеров эти методы могут быть неэффективными.
В 2D мы можем вычислить диаметр (внутрикластерное расстояние) каждого кластера за O(n log n) время, где n - размер кластера с использованием выпуклых оболочек. Векторизация используется для ускорения оставшихся операций. В конце поста упоминаются две возможные асимптотики c, взносы приветствуются;)
Установочные и фальшивые данные:
import numpy as np
from scipy import spatial
from matplotlib import pyplot as plt
# set up fake data
np.random.seed(0)
n_centroids = 1000
centroids = np.random.rand(n_centroids, 2)
cluster_sizes = np.random.randint(1, 1000, size=n_centroids)
# labels from 1 to n_centroids inclusive
labels = np.repeat(np.arange(n_centroids), cluster_sizes) + 1
points = np.zeros((cluster_sizes.sum(), 2))
points[:,0] = np.repeat(centroids[:,0], cluster_sizes)
points[:,1] = np.repeat(centroids[:,1], cluster_sizes)
points += 0.05 * np.random.randn(cluster_sizes.sum(), 2)
Выглядит примерно так:
Далее мы определим функцию diameter для вычисления наибольшего внутрикластерного расстояния на основе этого подхода с использованием выпуклой оболочки .
# compute the diameter based on convex hull
def diameter(pts):
# need at least 3 points to construct the convex hull
if pts.shape[0] <= 1:
return 0
if pts.shape[0] == 2:
return ((pts[0] - pts[1])**2).sum()
# two points which are fruthest apart will occur as vertices of the convex hull
hull = spatial.ConvexHull(pts)
candidates = pts[spatial.ConvexHull(pts).vertices]
return spatial.distance_matrix(candidates, candidates).max()
Для расчета индекса Данна я предполагаю, что мы уже вычислили точки, метки кластеров и центроиды кластеров.
Если число кластеров велико, следующее решение на основе Pandas может работать хорошо:
import pandas as pd
def dunn_index_pandas(pts, labels, centroids):
# O(k n log(n)) with k clusters and n points; better performance with more even clusters
max_intracluster_dist = pd.DataFrame(pts).groupby(labels).agg(diameter_pandas)[0].max()
# O(k^2) with k clusters; can be reduced to O(k log(k))
# get pairwise distances between centroids
cluster_dmat = spatial.distance_matrix(centroids, centroids)
# fill diagonal with +inf: ignore zero distance to self in "min" computation
np.fill_diagonal(cluster_dmat, np.inf)
min_intercluster_dist = cluster_sizes.min()
return min_intercluster_dist / max_intracluster_dist
В противном случае мы можем продолжить с чистого numpy решения.
def dunn_index(pts, labels, centroids):
# O(k n log(n)) with k clusters and n points; better performance with more even clusters
max_intracluster_dist = max(diameter(pts[labels==i]) for i in np.unique(labels))
# O(k^2) with k clusters; can be reduced to O(k log(k))
# get pairwise distances between centroids
cluster_dmat = spatial.distance_matrix(centroids, centroids)
# fill diagonal with +inf: ignore zero distance to self in "min" computation
np.fill_diagonal(cluster_dmat, np.inf)
min_intercluster_dist = cluster_sizes.min()
return min_intercluster_dist / max_intracluster_dist
%time dunn_index(points, labels, centroids)
# returned value 2.15
# in 2.2 seconds
%time dunn_index_pandas(points, labels, centroids)
# returned 2.15
# in 885 ms
Для кластеров 1000 с размерами кластеров i.i.d. ~U[1,1000] это занимает 2,2. секунд на моей машине. Это число уменьшается до 0,8 секунды при использовании подхода Pandas для этого примера (много небольших кластеров).
Существуют две дополнительные возможности оптимизации, которые актуальны при большом количестве кластеров:
Во-первых, я вычисляю минимальное межкластерное расстояние с помощью метода грубой силы O(k^2), где k - это число кластеров. Это может быть уменьшено до O(k log(k)), как обсуждено здесь .
Во-вторых, max(diameter(pts[labels==i]) for i in np.unique(labels)) требует k передачи по массиву размером n. Со многими кластерами это может стать узким местом (как в этом примере). Это несколько смягчается с помощью подхода pandas, но я ожидаю, что это можно будет оптимизировать намного дальше. Для текущих параметров примерно одна треть вычислительного времени расходуется вне вычислительного интерклюзора внутрикластерных расстояний.