哪种聚类算法可最大化修正Silhouette得分及hclust低耗替代方案

问题背景 #

我知道可以对不同聚类算法的输出计算轮廓系数，但我的问题与此不同：是否存在专门设计、已有公开实现、或者天然容易产出最高平均轮廓系数的聚类算法？

我调整了轮廓系数的计算规则，以此得到符合我需求的聚类结果，具体定义如下：

• 同簇紧致度指标a(cli)：对簇cli中的每个对象i，计算其到同簇其他所有对象的最大成对距离，再取所有对象该值的均值
• 异簇分离度指标b(cli)：对簇cli中的每个对象i，计算其到其他簇所有对象的最小成对距离，再取所有对象该值的均值
• 单簇轮廓值s(cli) = (b - a) / max(a, b)
• 聚类整体得分：所有簇s(cli)的均值

该指标的设计目标是让输出的簇同时满足两个要求：尽可能少出现和其他簇对象距离很小的样本，同时尽可能少出现和同簇其他对象距离很大的样本。

暴力求解参考实现（R代码） #

# 1. 用户参数设置
# 模拟的样本数量
N = 20
# 簇占比（向量长度即为簇的数量）
cluster_proportions = c(1,1)

# 2. 模拟二维样本坐标并计算距离矩阵
set.seed(328409)
coords <- matrix(data = runif(2*N, -5, 5), ncol = 2)
dm <- as.matrix(dist(coords))
#dm[diag(dm)] <- NA

# 3. 遍历所有可能的聚类方案求最优解
sizes = ceiling(N * cluster_proportions / sum(cluster_proportions))
sizes[which.max(sizes)] <- sizes[which.max(sizes)] + N - sum(sizes)
ncls <- length(sizes)

require(arrangements)
nperms <- npermutations(x = 1:ncls, freq = sizes)
iperm <- ipermutations(x = 1:ncls, freq = sizes)

highest_mean_silhouette_score <- -1
best_clustering <- NULL

for (i in 1:nperms) {
  
  cl <- iperm$getnext()
  
  # 对每个聚类方案计算自定义平均轮廓系数，保留得分最高的结果
  current_mean_silhouette_score <- mean(sapply(1:ncls, function(cli) {
    
    if (sum(cl == cli) == 1) {
      s <- 0
    } else {
    mindists_current_cl_to_other_cls <- apply(dm[cl != cli, cl == cli], 1, min)
    maxdists_current_cl_to_current_cl <- apply(dm[cl == cli, cl == cli], 1, max)
    b <- mean(mindists_current_cl_to_other_cls)
    a <- mean(maxdists_current_cl_to_current_cl)
    s <- (b - a) / max(a,b)
    }
    s
  }))
  
  if (current_mean_silhouette_score > highest_mean_silhouette_score) {
    highest_mean_silhouette_score <- current_mean_silhouette_score
    best_clustering <- cl
    cat("\nCurrent highest mean score = ", highest_mean_silhouette_score)
    cat("\nCurrent best clustering = ", best_clustering)
    plot(coords, pch = 16, col = best_clustering, main = paste0("Current highest mean score = ", highest_mean_silhouette_score), asp = 1)
  }
}

本次仿真的最终结果可视化如下：

显然暴力求解无法应用于实际场景，哪怕仅计算距离矩阵，针对我处理的数据集规模也存在很大挑战。因此我的核心问题是：哪种聚类算法可以得到尽可能接近上述暴力求解的结果？ 要求适用于通用场景，而非仅适配本次仿真示例。

补充测试与衍生问题 #

我测试了R语言的hclust算法，测试代码如下：

# 1. 用户参数设置
# 模拟的样本数量
N = 20

# 2. 模拟二维样本坐标并计算距离矩阵
set.seed(328409)
coords <- matrix(data = runif(2*N, -5, 5), ncol = 2)
dm <- dist(coords)

# 3. 测试层次聚类
hc <- hclust(dm, method = "complete")
dm <- as.matrix(dm)

highest_mean_silhouette_score <- -1
best_clustering <- NULL

for (ncls in 2:N) {
  
  cl <- cutree(hc, k = ncls)
  
  # 对每个聚类方案计算自定义平均轮廓系数，保留得分最高的结果
  current_mean_silhouette_score <- mean(sapply(1:ncls, function(cli) {
    
    if (sum(cl == cli) == 1) {
      s <- 0
    } else {
      mindists_current_cl_to_other_cls <- apply(dm[cl != cli, cl == cli], 1, min)
      maxdists_current_cl_to_current_cl <- apply(dm[cl == cli, cl == cli], 1, max)
      b <- mean(mindists_current_cl_to_other_cls)
      a <- mean(maxdists_current_cl_to_current_cl)
      s <- (b - a) / max(a,b)
    }
    s
  }))
  
  if (current_mean_silhouette_score > highest_mean_silhouette_score) {
    highest_mean_silhouette_score <- current_mean_silhouette_score
    best_clustering <- cl
    cat("\nCurrent highest mean score = ", highest_mean_silhouette_score)
    cat("\nCurrent best clustering = ", best_clustering)
    plot(coords, pch = 16, col = best_clustering, main = paste0("N = ",N,", # clusters = ",ncls,", current highest mean score = ", round(highest_mean_silhouette_score,3)), asp = 1)
  }
}

测试发现method = "complete"（完全连接层次聚类）的轮廓得分表现优于"median"和"average"，在本次2簇的示例中结果和暴力求解完全一致。
但遗憾的是层次聚类仅适用于规模相对较小的数据集，因此衍生问题为：是否存在运行速度更快、内存占用更低的hclust替代方案？

解决方案 #

针对自定义指标的近似最优聚类算法 #

• 带约束的谱聚类：你可以将自定义的a/b指标转化为相似度矩阵的约束条件，谱聚类的时间复杂度为O(n² log n)，远低于普通完全连接层次聚类的O(n³)，可以支撑万级样本量的场景，结果接近全局最优。
• 启发式优化聚类：使用模拟退火、遗传算法等启发式搜索方法，直接将你自定义的平均轮廓系数作为目标函数迭代优化，这类方案可以适配任意自定义目标，样本量不超过10万的场景下都可以得到接近暴力求解的结果。
• 改进版密度聚类：可以将同簇最大距离、异簇最小距离作为参数约束，使用HDBSCAN实现，它的时间复杂度低至O(n log n)，适合大规模数据集，仅需要对参数做少量调优即可达到不错的效果。

完全连接层次聚类的高性能替代方案 #

如果你的测试已经验证完全连接层次聚类的效果符合要求，仅需要提升性能，可以使用以下工具：

• R语言fastcluster包：它的hclust函数接口和原生实现完全兼容，底层采用优化的C++代码实现，速度是原生hclust的2~10倍，内存占用降低40%以上，支持百万级以下样本的聚类。
• 近似层次聚类：如果样本量超过百万，可以使用基于Nyström近似的层次聚类方案，通过采样近似计算距离矩阵，时间复杂度可以降低到O(n√n)，结果误差通常不超过5%。

内容的提问来源于stack exchange，提问作者user6376297