优化Dunn指数计算？

Question

Dunn索引是一种评估聚类的方法。值越高越好。它的计算方法是：最小的群集间距离（即，任何两个群集质心之间的最小距离）除以最高的群集内距离（即，任何群集中的任何两个点之间的最大距离）。

我有一个用于计算邓恩指数的代码段：

def dunn_index(pf, cf):
    """
    pf -- all data points
    cf -- cluster centroids
    """
    numerator = inf
    for c in cf: # for each cluster
        for t in cf: # for each cluster
            if t is c: continue # if same cluster, ignore
            numerator = min(numerator, distance(t, c)) # find distance between centroids
    denominator = 0
    for c in cf: # for each cluster
        for p in pf: # for each point
            if p.get_cluster() is not c: continue # if point not in cluster, ignore
            for t in pf: # for each point
                if t.get_cluster() is not c: continue # if point not in cluster, ignore
                if t is p: continue # if same point, ignore
                denominator = max(denominator, distance(t, p))
    return numerator/denominator

问题是，这异常缓慢：对于由5000个实例和15个群集组成的示例数据集，最坏的情况是上述函数需要执行超过3.75亿的距离计算。实际上，它要低得多，但即使是按簇已经对数据进行排序的最佳情况，也要进行大约2500万次距离计算。我想节省时间，而且我已经尝试过直线距离与欧几里得距离，这不好。

如何改进此算法？

Answer 1

TLDR：重要的是，此问题是在二维]中设置的。对于大尺寸，这些技术可能无效。

在2D中，我们可以计算O(n log n)时间中每个群集的直径（群集内距离），其中n是使用凸包的群集大小。向量化用于加快剩余操作的速度。文章结尾提到了两种可能的渐近改进；欢迎捐款;）

---

设置和伪造数据：

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方法定义一个this函数，用于计算最大的簇内距离。

# 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()
对于Dunn指数计算，我假设我们已经计算了点，聚类标签和聚类质心。

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
对于具有1000个集群大小的i.i.d. ~U[1,1000]个集群，这在我的机器上需要2.2秒。

当簇数很大时，还有两个与优化有关的其他机会：

• 首先，我正在使用蛮力O(k^2)方法计算最小群集间距离，其中k是群集数。如讨论的O(k log(k))，这可以减少为here。

• 第二，max(diameter(pts[labels==i]) for i in np.unique(labels))要求k通过大小为n的数组。对于许多小型集群，这可能成为瓶颈。可以通过按簇对分区进行预分区来解决此问题，但目前我还无法想到一种以矢量化方式完成此操作的优雅方法。

Answer 2

这与优化算法本身无关，但是我认为以下建议之一可以提高性能。