Dunn指数是一种评估聚类的方法。数值越高越好。它通过最低的聚类间距离（即任意两个聚类中心之间的最小距离）除以最高的聚类内距离（即任意聚类中任意两点之间的最大距离）来计算。

我有一个计算Dunn指数的代码片段：

def dunn_index(pf, cf):    """    pf -- 所有数据点    cf -- 聚类中心    """    numerator = inf    for c in cf: # 对于每个聚类        for t in cf: # 对于每个聚类            if t is c: continue # 如果是同一个聚类，忽略            numerator = min(numerator, distance(t, c)) # 寻找聚类中心之间的距离    denominator = 0    for c in cf: # 对于每个聚类        for p in pf: # 对于每个点            if p.get_cluster() is not c: continue # 如果点不在聚类中，忽略            for t in pf: # 对于每个点                if t.get_cluster() is not c: continue # 如果点不在聚类中，忽略                if t is p: continue # 如果是同一个点，忽略                denominator = max(denominator, distance(t, p))    return numerator/denominator

问题是这个计算速度非常慢：对于一个包含5000个实例和15个聚类的示例数据集，上述函数在最坏情况下需要进行超过3.75亿次距离计算。实际上，这个数字要低得多，但即使是在数据已经按聚类排序的最佳情况下，也需要大约2500万次距离计算。我希望能减少计算时间，我已经尝试过使用矩形距离和欧几里得距离，但效果不佳。

如何改进这个算法？

回答：

TLDR：重要的是，问题是在二维中设置的。对于高维度，这些技术可能无效。

在二维中，我们可以使用凸包在O(n log n)时间内计算每个聚类的直径（聚类内距离），其中n是聚类大小。使用向量化来加速剩余操作。在文章末尾提到了两种可能的渐进式改进，欢迎贡献 😉

设置和伪数据：

import numpy as npfrom scipy import spatialfrom matplotlib import pyplot as plt# 设置伪数据np.random.seed(0)n_centroids = 1000centroids = np.random.rand(n_centroids, 2)cluster_sizes = np.random.randint(1, 1000, size=n_centroids)# 标签从1到n_centroids包括labels = np.repeat(np.arange(n_centroids), cluster_sizes) + 1points = 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函数，用于计算最大的聚类内距离，基于这个使用凸包的方法。

# 基于凸包计算直径 def diameter(pts):  # 需要至少3个点来构建凸包  if pts.shape[0] <= 1:    return 0  if pts.shape[0] == 2:    return ((pts[0] - pts[1])**2).sum()  # 最远的两个点将作为凸包的顶点  hull = spatial.ConvexHull(pts)  candidates = pts[spatial.ConvexHull(pts).vertices]  return spatial.distance_matrix(candidates, candidates).max()

对于Dunn指数的计算，我假设我们已经计算了点、聚类标签和聚类中心。

如果聚类数量很大，以下基于Pandas的解决方案可能表现良好：

import pandas as pddef dunn_index_pandas(pts, labels, centroids):  # O(k n log(n)) 其中k是聚类数，n是点数；聚类越均匀，性能越好  max_intracluster_dist = pd.DataFrame(pts).groupby(labels).agg(diameter_pandas)[0].max()  # O(k^2) 其中k是聚类数；可以减少到O(k log(k))  # 获取聚类中心之间的成对距离  cluster_dmat = spatial.distance_matrix(centroids, centroids)  # 用+inf填充对角线：在“min”计算中忽略到自身的零距离  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)) 其中k是聚类数，n是点数；聚类越均匀，性能越好  max_intracluster_dist = max(diameter(pts[labels==i]) for i in np.unique(labels))  # O(k^2) 其中k是聚类数；可以减少到O(k log(k))  # 获取聚类中心之间的成对距离  cluster_dmat = spatial.distance_matrix(centroids, centroids)  # 用+inf填充对角线：在“min”计算中忽略到自身的零距离  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)# 返回值 2.15# 在2.2秒内%time dunn_index_pandas(points, labels, centroids)# 返回 2.15# 在885毫秒内

对于1000个聚类，具有i.i.d. ~U[1,1000]的聚类大小，在我的机器上这需要2.2秒。对于这个例子（许多小聚类），使用Pandas方法这个数字下降到0.8秒。

当聚类数量很大时，还有两个进一步的优化机会：

• 首先，我使用暴力O(k^2)方法计算最小的聚类间距离，其中k是聚类数量。这可以减少到O(k log(k))，如这里讨论的那样。

• 其次，max(diameter(pts[labels==i]) for i in np.unique(labels))需要对大小为n的数组进行k次遍历。对于许多聚类，这可能成为瓶颈（如这个例子）。这在使用Pandas方法时有所缓解，但我预计这可以进一步优化很多。对于当前参数，大约三分之一的计算时间花在计算聚类间或聚类内距离之外。