Matlab中生成互不连通指定数量聚类的方法咨询

1. 原生k-means能否生成互不连通的聚类？ #

不能。k-means的核心逻辑是最小化每个样本到所属簇质心的平方距离，完全没有空间连通性约束。它只关注样本与质心的距离关系，哪怕两个不连通区域的点到同一质心的距离更近，也会被归为同一簇，这就是你遇到交织现象的原因。Matlab自带的kmeans函数没有任何参数可以强制生成连通聚类。

2. 对k-means结果做后处理得到连通聚类 #

可以通过连通分量分析+标签重分配实现，核心思路是先拆分k-means结果中的非连通簇，再调整标签保证总簇数固定为k。以下是具体步骤和Matlab示例代码：

步骤： #

• 对k-means输出的每个簇，提取对应点集，用密度聚类（如DBSCAN）或邻接图分析找出其中的连通子分量；
• 对拆分出的子分量，计算每个子分量的质心，将小的子分量合并到距离最近的其他簇的连通分量中，最终保持总簇数为k。

示例代码： #

% 假设X是你的N×2点集，k是目标簇数，idx是k-means的初始聚类标签
X = randn(1000,2); % 示例点集
k = 3;
[idx, centroids] = kmeans(X, k);

% 对每个簇做连通分量分析（依赖Statistics Toolbox的DBSCAN）
new_idx = idx;
for i = 1:k
    cluster_pts = X(idx==i, :);
    if size(cluster_pts,1) < 5 % 跳过过小的簇
        continue;
    end
    % 用DBSCAN识别簇内的连通子分量，eps需根据点集密度调整
    [comp_idx, ~] = dbscan(cluster_pts, 0.3, 5);
    unique_comps = unique(comp_idx(comp_idx~=-1)); % 忽略噪声点
    if length(unique_comps) > 1
        % 计算每个子分量的质心
        comp_centroids = zeros(length(unique_comps), 2);
        for j = 1:length(unique_comps)
            comp_pts = cluster_pts(comp_idx==unique_comps(j), :);
            comp_centroids(j,:) = mean(comp_pts);
        end
        % 保留第一个子分量在原簇，其余子分量分配到最近的其他簇
        for j = 2:length(unique_comps)
            comp_pt_idx = find(idx==i & comp_idx==unique_comps(j));
            [~, closest_cluster] = min(pdist2(comp_centroids(j,:), centroids));
            new_idx(comp_pt_idx) = closest_cluster;
        end
    end
end

% 可选：重新计算调整后的簇质心
new_centroids = zeros(k,2);
for i=1:k
    new_centroids(i,:) = mean(X(new_idx==i,:));
end

如果是规则分布的2D点集，也可以将点集转成二值图像，用bwconncomp识别连通分量后映射回点标签，实现成本更低。

3. 更合适的替代聚类方法 #

如果不想做后处理，直接生成固定数量的连通聚类，可以选择以下方法：

3.1 连通k-means（基于图分割实现） #

这是带连通性约束的k-means变种，要求每个簇是空间连通的。可以通过构建点的k近邻图，再用图分割算法拆分出k个连通子图：

X = randn(1000,2);
k = 3;
% 构建10近邻图
G = knngraph(X, 10);
% 用谱聚类实现带连通约束的簇划分（依赖Statistics Toolbox）
idx = spectralcluster(G, k);

3.2 区域生长聚类 #

以k-means生成的质心为种子点，从种子点开始逐步将邻域内距离近的点归入同一簇，天然保证簇的连通性：

X = randn(1000,2);
k = 3;
% 用k-means选取初始种子点
[idx_seed, centroids] = kmeans(X, k);
new_idx = zeros(size(X,1),1);
visited = false(size(X,1),1);

% 初始化种子点的簇标签
for i=1:k
    seed_idx = find(idx_seed==i,1);
    new_idx(seed_idx) = i;
    visited(seed_idx) = true;
end

% 区域生长循环
while ~all(visited)
    for i=1:k
        cluster_pts = X(new_idx==i, :);
        % 找到未访问点中距离当前簇最近的点
        dists = pdist2(X(~visited,:), cluster_pts);
        [min_dist, ~] = min(min(dists,[],2));
        [~, closest_pt_idx] = min(min_dist);
        original_pt_idx = find(~visited, closest_pt_idx);
        new_idx(original_pt_idx) = i;
        visited(original_pt_idx) = true;
        if all(visited)
            break;
        end
    end
end

内容的提问来源于stack exchange，提问作者G. Rab