寻求基于兼容性度量的2-3人分组聚类方法（最大化组内兼容性）

需求：将8名人员划分为2人或3人小组，最大化每组内部的兼容性总和，给定的兼容性矩阵如下：

import pandas as pd

compatibility = pd.DataFrame({
    'Alejandro': [0.0, 0.0, 1000.0, 0.0, 1037.0, 1014.0, 100.0, 0.0],
    'Ana': [0.0, 0.0, 15.0, 0.0, 100.0, 0.0, 16.0, 1100.0],
    'Beatriz': [1000.0, 15.0, 0.0, 100.0, 1000.0, 1100.0, 15.0, 0.0],
    'Jose': [0.0, 0.0, 100.0, 0.0, 0.0, 100.0, 1000.0, 14.0],
    'Juan': [1037.0, 100.0, 1000.0, 0.0, 0.0, 1014.0, 0.0, 100.0],
    'Luz': [1014.0, 0.0, 1100.0, 100.0, 1014.0, 0.0, 0.0, 0.0],
    'Maria': [100.0, 16.0, 15.0, 1000.0, 0.0, 0.0, 0.0, 0.0],
    'Ruben': [0.0, 1100.0, 0.0, 14.0, 100.0, 0.0, 0.0, 0.0]
}, index=['Alejandro', 'Ana', 'Beatriz', 'Jose', 'Juan', 'Luz', 'Maria', 'Ruben'])

方法一：整数规划（精确最优解） #

这个问题本质是带约束的组合优化问题，可通过整数规划求解精确最优分组：

1. 核心逻辑

   • 定义二进制变量：y[i][k] 表示第i个人是否被分配到第k组
   • 约束规则：
     • 每个人必须且仅属于一个组：sum(y[i][k] for k in groups) = 1（覆盖所有人员i）
     • 每个组的人数只能是2或3：2 ≤ sum(y[i][k] for i in people) ≤ 3（覆盖所有组k）
     • 总组数固定为3（因为8=3+3+2）
   • 目标函数：最大化所有同组人员对的兼容性总和，即 sum(compatibility.loc[i,j] * y[i][k] * y[j][k] for i<j for k in groups)

2. 代码实现（基于PuLP库）

from pulp import LpProblem, LpVariable, LpMaximize, lpSum

# 人员列表与总组数
people = compatibility.index.tolist()
groups = [0,1,2]

# 创建最大化问题实例
prob = LpProblem("MaximizeCompatibility", LpMaximize)

# 定义分配变量：y[(i,k)]为1表示人员i在组k
y = LpVariable.dicts("Assign", [(i,k) for i in people for k in groups], cat='Binary')

# 设置目标函数
prob += lpSum(compatibility.loc[i,j] * y[(i,k)] * y[(j,k)] 
              for k in groups 
              for i_idx, i in enumerate(people) 
              for j_idx in range(i_idx+1, len(people))
              for j in [people[j_idx]])

# 添加约束：每个人仅属于一个组
for i in people:
    prob += lpSum(y[(i,k)] for k in groups) == 1

# 添加约束：每组人数为2或3
for k in groups:
    prob += lpSum(y[(i,k)] for i in people) >= 2
    prob += lpSum(y[(i,k)] for i in people) <= 3

# 求解并输出结果
prob.solve()
groups_result = {k: [] for k in groups}
for i in people:
    for k in groups:
        if y[(i,k)].value() == 1:
            groups_result[k].append(i)

print("最优分组：")
for g in groups_result.values():
    print(g)

方法二：启发式聚类（近似解） #

若数据量较大，整数规划效率不足，可采用聚类方法快速得到近似最优解：

1. 核心逻辑

   • 将兼容性转化为距离：聚类通常以最小化距离为目标，因此用max_compatibility - compatibility生成距离矩阵（值越小代表兼容性越高）
   • 使用层次聚类（Agglomerative Clustering），设置聚类数目为3，确保每组人数符合2或3的要求

2. 代码实现（基于Scikit-learn）

from sklearn.cluster import AgglomerativeClustering
import numpy as np

# 转换兼容性矩阵为距离矩阵
max_comp = compatibility.max().max()
distance_matrix = max_comp - compatibility.values

# 执行层次聚类
clustering = AgglomerativeClustering(n_clusters=3, metric='precomputed', linkage='complete')
labels = clustering.fit_predict(distance_matrix)

# 整理并输出分组结果
groups_result = {}
for label in set(labels):
    groups_result[label] = [people[i] for i in range(len(people)) if labels[i] == label]

print("近似分组：")
for g in groups_result.values():
    print(g)

结果验证 #

可通过以下代码计算任意分组的总兼容性，验证解的优劣：

def calculate_total_compatibility(groups, comp_matrix):
    total = 0
    for group in groups:
        for i_idx in range(len(group)):
            for j_idx in range(i_idx+1, len(group)):
                total += comp_matrix.loc[group[i_idx], group[j_idx]]
    return total

# 计算示例分组的总兼容性
example_groups = [['Alejandro', 'Ana', 'Beatriz'], ['Jose', 'Juan', 'Luz'], ['Maria', 'Ruben']]
print("示例分组总兼容性：", calculate_total_compatibility(example_groups, compatibility))

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