如何对分组数据向量聚类：每个聚类含各组一个样本

我有一个包含4个唯一分组的数据集，每组有70个观测值，每个观测值是一个4维数值向量。我希望构建大小为4的聚类——每个聚类必须包含来自每个分组的一个观测值，同时最小化聚类内的欧氏距离。这个问题和稳定婚姻问题有点关联，但分组更多，不完全一样。能用贪心算法解决也可以。

部分不同分组中的向量值完全相同，这些可以直接归为同一聚类（每组各1个相似样本）。难点在处理剩余不匹配的向量，它们有的相似度高，有的低。我常用R语言（统计编程背景），但如果有更简便的Python方案也可以参考。

数据示例：

myvec <- runif(400)
mat <- matrix(data = myvec, ncol = 4, nrow = 100)
groupings <- c(rep(c("a","b","c","d"),25))
dat <- cbind(as.data.frame(mat), groupings)
names(dat) <- c("val1","val2","val3","val4","group")
head(dat)

核心思路分两步：

• 先匹配完全相同的向量：快速处理无争议的聚类，减少后续计算量
• 对剩余观测值用贪心算法：每次选择聚类内欧氏距离最小的跨分组组合，逐步分配观测值

R语言实现 #

1. 处理完全匹配的向量 #

library(dplyr)
library(tidyr)

# 为每个向量生成唯一标识（方便跨分组匹配）
dat <- dat %>%
  rowwise() %>%
  mutate(vec_id = paste(val1, val2, val3, val4, sep = ",")) %>%
  ungroup()

# 筛选出在4个分组中都存在的向量
common_vecs <- dat %>%
  count(vec_id, group) %>%
  pivot_wider(names_from = group, values_from = n, values_fill = 0) %>%
  filter(a > 0, b > 0, c > 0, d > 0) %>%
  pull(vec_id)

# 生成完全匹配的聚类并移除已使用的观测值
matched_clusters <- list()
current_dat <- dat

for (vec in common_vecs) {
  # 从每个分组取一个该向量的样本
  cluster <- current_dat %>%
    filter(vec_id == vec) %>%
    group_by(group) %>%
    slice(1) %>%
    ungroup()
  
  matched_clusters[[length(matched_clusters) + 1]] <- cluster
  # 移除已匹配的样本
  current_dat <- current_dat %>% anti_join(cluster, by = c("val1", "val2", "val3", "val4", "group"))
}

2. 贪心算法分配剩余样本 #

# 拆分剩余数据为单独分组
groups_split <- split(current_dat, current_dat$group)
group_a <- groups_split$a
group_b <- groups_split$b
group_c <- groups_split$c
group_d <- groups_split$d

remaining_clusters <- list()

# 循环直到任一分组无剩余样本
while (nrow(group_a) > 0 && nrow(group_b) > 0 && nrow(group_c) > 0 && nrow(group_d) > 0) {
  min_avg_dist <- Inf
  best_idx <- c(1, 1, 1, 1)
  
  # 随机采样减少计算量（数据量大时可选）
  sample_size <- 1000
  total_combs <- nrow(group_a) * nrow(group_b) * nrow(group_c) * nrow(group_d)
  
  if (total_combs > sample_size) {
    idx_a <- sample(1:nrow(group_a), sample_size, replace = TRUE)
    idx_b <- sample(1:nrow(group_b), sample_size, replace = TRUE)
    idx_c <- sample(1:nrow(group_c), sample_size, replace = TRUE)
    idx_d <- sample(1:nrow(group_d), sample_size, replace = TRUE)
  } else {
    # 生成所有可能的组合索引
    idx_a <- rep(1:nrow(group_a), each = nrow(group_b)*nrow(group_c)*nrow(group_d))
    idx_b <- rep(1:nrow(group_b), each = nrow(group_c)*nrow(group_d))
    idx_c <- rep(1:nrow(group_c), each = nrow(group_d))
    idx_d <- 1:nrow(group_d)
  }
  
  # 遍历采样组合，找出平均距离最小的聚类
  for (i in 1:length(idx_a)) {
    vec_a <- as.numeric(group_a[idx_a[i], 1:4])
    vec_b <- as.numeric(group_b[idx_b[i], 1:4])
    vec_c <- as.numeric(group_c[idx_c[i], 1:4])
    vec_d <- as.numeric(group_d[idx_d[i], 1:4])
    
    # 计算聚类内所有两两欧氏距离的平均值
    dists <- c(
      sqrt(sum((vec_a - vec_b)^2)),
      sqrt(sum((vec_a - vec_c)^2)),
      sqrt(sum((vec_a - vec_d)^2)),
      sqrt(sum((vec_b - vec_c)^2)),
      sqrt(sum((vec_b - vec_d)^2)),
      sqrt(sum((vec_c - vec_d)^2))
    )
    avg_dist <- mean(dists)
    
    if (avg_dist < min_avg_dist) {
      min_avg_dist <- avg_dist
      best_idx <- c(idx_a[i], idx_b[i], idx_c[i], idx_d[i])
    }
  }
  
  # 提取最优聚类并移除已选样本
  best_cluster <- rbind(
    group_a[best_idx[1], ],
    group_b[best_idx[2], ],
    group_c[best_idx[3], ],
    group_d[best_idx[4], ]
  )
  remaining_clusters[[length(remaining_clusters) + 1]] <- best_cluster
  
  group_a <- group_a[-best_idx[1], ]
  group_b <- group_b[-best_idx[2], ]
  group_c <- group_c[-best_idx[3], ]
  group_d <- group_d[-best_idx[4], ]
}

# 合并所有聚类并添加聚类ID
all_clusters <- c(matched_clusters, remaining_clusters)
final_dat <- bind_rows(lapply(1:length(all_clusters), function(i) {
  all_clusters[[i]] %>% mutate(cluster_id = i)
}))

Python语言实现 #

1. 处理完全匹配的向量 #

import pandas as pd
import numpy as np

# 生成示例数据（与R示例一致）
np.random.seed(123)
myvec = np.random.uniform(size=400)
mat = myvec.reshape(100, 4)
groupings = np.repeat(['a', 'b', 'c', 'd'], 25)
dat = pd.DataFrame(mat, columns=['val1', 'val2', 'val3', 'val4'])
dat['group'] = groupings

# 为每个向量生成唯一元组标识
dat['vec_id'] = list(zip(dat['val1'], dat['val2'], dat['val3'], dat['val4']))

# 筛选出在4个分组中都存在的向量
common_vecs = dat.groupby('vec_id')['group'].nunique()
common_vecs = common_vecs[common_vecs == 4].index.tolist()

# 生成完全匹配的聚类并移除已使用样本
matched_clusters = []
current_dat = dat.copy()

for vec in common_vecs:
    cluster = current_dat[current_dat['vec_id'] == vec].groupby('group').first().reset_index()
    matched_clusters.append(cluster)
    
    # 移除已匹配的样本
    current_dat = current_dat.merge(cluster, on=['val1', 'val2', 'val3', 'val4', 'group'], how='left', indicator=True)
    current_dat = current_dat[current_dat['_merge'] != 'both'].drop('_merge', axis=1)

2. 贪心算法分配剩余样本 #

from itertools import product

# 拆分剩余数据为单独分组
groups_split = {g: df.reset_index(drop=True) for g, df in current_dat.groupby('group')}
group_a = groups_split['a']
group_b = groups_split['b']
group_c = groups_split['c']
group_d = groups_split['d']

remaining_clusters = []

# 循环直到任一分组无剩余样本
while len(group_a) > 0 and len(group_b) > 0 and len(group_c) > 0 and len(group_d) > 0:
    min_avg_dist = np.inf
    best_idx = (0, 0, 0, 0)
    
    # 随机采样减少计算量（数据量大时可选）
    sample_size = 1000
    total_combs = len(group_a) * len(group_b) * len(group_c) * len(group_d)
    
    if total_combs > sample_size:
        idx_a = np.random.choice(len(group_a), sample_size, replace=True)
        idx_b = np.random.choice(len(group_b), sample_size, replace=True)
        idx_c = np.random.choice(len(group_c), sample_size, replace=True)
        idx_d = np.random.choice(len(group_d), sample_size, replace=True)
    else:
        # 生成所有可能的组合索引
        idx_a, idx_b, idx_c, idx_d = zip(*product(range(len(group_a)), range(len(group_b)), range(len(group_c)), range(len(group_d))))
    
    # 遍历采样组合，找出平均距离最小的聚类
    for i in range(len(idx_a)):
        vec_a = group_a.iloc[idx_a[i], :4].values
        vec_b = group_b.iloc[idx_b[i], :4].values
        vec_c = group_c.iloc[idx_c[i], :4].values
        vec_d = group_d.iloc[idx_d[i], :4].values
        
        # 计算聚类内所有两两欧氏距离的平均值
        dists = [
            np.linalg.norm(vec_a - vec_b),
            np.linalg.norm(vec_a - vec_c),
            np.linalg.norm(vec_a - vec_d),
            np.linalg.norm(vec_b - vec_c),
            np.linalg.norm(vec_b - vec_d),
            np.linalg.norm(vec_c - vec_d)
        ]
        avg_dist = np.mean(dists)
        
        if avg_dist < min_avg_dist:
            min_avg_dist = avg_dist
            best_idx = (idx_a[i], idx_b[i], idx_c[i], idx_d[i])
    
    # 提取最优聚类并移除已选样本
    best_cluster = pd.concat([
        group_a.iloc[[best_idx[0]]],
        group_b.iloc[[best_idx[1]]],
        group_c.iloc[[best_idx[2]]],
        group_d.iloc[[best_idx[3]]]
    ]).reset_index(drop=True)
    remaining_clusters.append(best_cluster)
    
    group_a = group_a.drop(best_idx[0]).reset_index(drop=True)
    group_b = group_b.drop(best_idx[1]).reset_index(drop=True)
    group_c = group_c.drop(best_idx[2]).reset_index(drop=True)
    group_d = group_d.drop(best_idx[3]).reset_index(drop=True)

# 合并所有聚类并添加聚类ID
all_clusters = matched_clusters + remaining_clusters
final_dat = pd.concat([cluster.assign(cluster_id=i) for i, cluster in enumerate(all_clusters)], ignore_index=True)

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