已知簇数且含样本对分离约束的聚类算法选型及Python实现方案咨询

嘿，针对你遇到的带不可共簇约束的聚类需求，确实scikit-learn里没有直接开箱即用的算法支持这类约束，但我们完全可以基于你熟悉的numpy、sklearn、scipy生态来实现，下面给你几个实用的方案：

方案1：约束谱聚类（Constrained Spectral Clustering） #

谱聚类的核心是通过相似矩阵构建样本间的关联关系，咱们刚好可以利用这一点来嵌入不可共簇约束——直接把约束样本对的相似度设为0，相当于强制让它们在谱空间里完全“疏远”，之后再用sklearn的SpectralClustering处理预计算的相似矩阵即可。

代码实现 #

import numpy as np
from sklearn.cluster import SpectralClustering
from sklearn.metrics.pairwise import rbf_kernel

# 模拟你的样本：20个5维特征的样本
np.random.seed(42)
X = np.random.rand(20, 5)
# 转换约束对为0索引（原问题是1索引，这里统一成Python的0索引）
cannot_link_pairs = [(0, 2), (2, 4), (9, 18)]

# 1. 构建带约束的相似矩阵
# 先计算默认RBF核相似矩阵
similarity_matrix = rbf_kernel(X, gamma=1.0)
# 对不可共簇的样本对，将相似度强制设为0
for a, b in cannot_link_pairs:
    similarity_matrix[a, b] = 0.0
    similarity_matrix[b, a] = 0.0

# 2. 用预计算的相似矩阵运行谱聚类
sc = SpectralClustering(n_clusters=3, affinity='precomputed', random_state=42)
labels = sc.fit_predict(similarity_matrix)

# 辅助函数：检查约束是否满足
def check_constraints(labels, cannot_link):
    for a, b in cannot_link:
        if labels[a] == labels[b]:
            print(f"⚠️ 约束违反：样本{a+1}和{b+1}被分到同一簇")
            return False
    print("✅ 所有约束都满足！")
    return True

check_constraints(labels, cannot_link_pairs)

方案2：带约束惩罚的KMeans变体 #

如果你更习惯KMeans的逻辑，咱们可以给KMeans的损失函数加个惩罚项：一旦出现违反不可共簇约束的情况，就给总损失加上一个大的惩罚值，然后通过局部搜索调整簇分配，直到满足所有约束。

代码实现 #

import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import euclidean_distances

def constrained_kmeans(X, n_clusters, cannot_link_pairs, penalty=1000):
    # 先用普通KMeans做初始化
    kmeans = KMeans(n_clusters=n_clusters, random_state=42)
    labels = kmeans.fit_predict(X)
    centers = kmeans.cluster_centers_
    
    # 定义带惩罚的损失函数：簇内平方和 + 违反约束的惩罚
    def calculate_loss(current_labels):
        # 计算簇内平方和（SSE）
        sse = 0
        for c in range(n_clusters):
            cluster_samples = X[current_labels == c]
            if len(cluster_samples) > 0:
                sse += np.sum((cluster_samples - centers[c]) ** 2)
        # 计算惩罚项：每违反一个约束加penalty
        penalty_term = 0
        for a, b in cannot_link_pairs:
            if current_labels[a] == current_labels[b]:
                penalty_term += penalty
        return sse + penalty_term
    
    # 局部搜索优化：调整违反约束的样本
    improved = True
    while improved:
        improved = False
        centers = np.array([X[labels == c].mean(axis=0) for c in range(n_clusters)])
        for a, b in cannot_link_pairs:
            if labels[a] == labels[b]:
                # 找到样本a可以迁移的有效簇（排除当前簇和样本b所在的簇）
                forbidden_clusters = {labels[a]}
                valid_clusters = [c for c in range(n_clusters) if c not in forbidden_clusters]
                if not valid_clusters:
                    raise ValueError("❌ 簇数C不足以满足所有约束，请检查约束条件或增加簇数")
                # 选择距离样本a最近的有效簇
                distances = euclidean_distances(X[a].reshape(1, -1), centers)[0]
                best_cluster = valid_clusters[np.argmin(distances[valid_clusters])]
                # 尝试迁移并检查损失是否降低
                old_loss = calculate_loss(labels)
                labels[a] = best_cluster
                new_loss = calculate_loss(labels)
                if new_loss >= old_loss:
                    # 损失变大，回溯
                    labels[a] = forbidden_clusters.pop()
                else:
                    improved = True
    return labels, centers

# 测试
labels, centers = constrained_kmeans(X, 3, cannot_link_pairs)
check_constraints(labels, cannot_link_pairs)

方案3：后处理调整法（最简易的快速方案） #

如果你的样本量不大，也可以先跑普通KMeans，再手动调整违反约束的样本：把违反约束的样本移动到距离最近且不会触发新约束的簇里。这个方法逻辑最简单，适合快速验证约束效果。

核心思路 #

1. 先用sklearn.KMeans完成初始聚类
2. 遍历所有不可共簇样本对，检查是否有违反情况
3. 对违反的样本，计算它到所有其他簇中心的距离，选择最近且不会和约束样本同簇的簇迁移

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