mergeClosestClusters方法导致层次聚类Level2输出异常求助

我开发的层次聚类程序在使用**Single link distance（单链接距离）**时，Level2的聚类结果顺序不符合预期：

• 当前输出Level2：
  cluster0:2,3
  cluster1:0,4
  cluster2:1
• 预期输出Level2：
  cluster0:0,4
  cluster1:1
  cluster2:2,3

怀疑问题出在mergeClosestClusters方法中，方法代码如下：

public ClusterSet mergeClosestClusters(ClusterDistance distance, Data data) {
    // 初始化最小距离为极大值
    double minDistance = Double.MAX_VALUE;
    // 初始化最近的两个簇的索引
    int clusterIndex1 = -1, clusterIndex2 = -1;
    // 计算每对簇之间的距离
    for (int i = 0; i < lastClusterIndex; i++) {
        for (int j = i + 1; j < lastClusterIndex; j++) {
            // 计算当前两个簇的距离
            double currentDistance = distance.distance(C[i], C[j], data);
            // 如果当前距离小于最小距离，更新最小距离和簇索引
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
                clusterIndex1 = i;
                clusterIndex2 = j;
            }
        }
    }
    // 合并最近的两个簇
    Cluster mergedCluster = C[clusterIndex1].mergeCluster(C[clusterIndex2]);
    // 创建一个簇数量减一的新ClusterSet
    ClusterSet newClusterSet = new ClusterSet(lastClusterIndex - 1);
    // 将合并后的簇添加到新ClusterSet
    newClusterSet.add(mergedCluster);
    // 添加所有未被合并的簇到新ClusterSet
    for (int i = 0; i < lastClusterIndex; i++) {
        if (i != clusterIndex1 && i != clusterIndex2) {
            newClusterSet.add(C[i]);
        }
    }
    // 返回新的ClusterSet
    return newClusterSet;
}

完整输出对比 #

当前输出 #

0: [1.0, 2.0, 0.0]
1: [0.0, 1.0, -1.0]
2: [1.0, 3.0, 5.0]
3: [1.0, 3.0, 4.0]
4: [2.0, 2.0, 0.0]

Inserisci la profondità del dendrogramma da costruire: 5
Scegli il tipo di misura di distanza tra cluster:
1. Single link distance
2. Average link distance
La tua scelta: 1
Hai scelto: Single link distance
Distance matrix:

0.0 3.0 26.0    17.0    1.0 
0.0 0.0 41.0    30.0    6.0 
0.0 0.0 0.0 1.0 27.0    
0.0 0.0 0.0 0.0 18.0    
0.0 0.0 0.0 0.0 0.0 
level0:
cluster0:0
cluster1:1
cluster2:2
cluster3:3
cluster4:4

level1:
cluster0:0,4
cluster1:1
cluster2:2
cluster3:3

level2:
cluster0:2,3
cluster1:0,4
cluster2:1

level3:
cluster0:0,4,1
cluster1:2,3

level4:
cluster0:0,4,1,2,3


level0:
cluster0:<[1.0, 2.0, 0.0]>
cluster1:<[0.0, 1.0, -1.0]>
cluster2:<[1.0, 3.0, 5.0]>
cluster3:<[1.0, 3.0, 4.0]>
cluster4:<[2.0, 2.0, 0.0]>

level1:
cluster0:<[1.0, 2.0, 0.0]><[2.0, 2.0, 0.0]>
cluster1:<[0.0, 1.0, -1.0]>
cluster2:<[1.0, 3.0, 5.0]>
cluster3:<[1.0, 3.0, 4.0]>

level2:
cluster0:<[1.0, 3.0, 5.0]><[1.0, 3.0, 4.0]>
cluster1:<[1.0, 2.0, 0.0]><[2.0, 2.0, 0.0]>
cluster2:<[0.0, 1.0, -1.0]>

level3:
cluster0:<[1.0, 2.0, 0.0]><[2.0, 2.0, 0.0]><[0.0, 1.0, -1.0]>
cluster1:<[1.0, 3.0, 5.0]><[1.0, 3.0, 4.0]>

level4:
cluster0:<[1.0, 2.0, 0.0]><[2.0, 2.0, 0.0]><[0.0, 1.0, -1.0]><[1.0, 3.0, 5.0]><[1.0, 3.0, 4.0]>

期望输出 #

0:[1.0,2.0,0.0]
1:[0.0,1.0,-1.0]
2:[1.0,3.0,5.0]
3:[1.0,3.0,4.0]
4:[2.0,2.0,0.0]

Single link distance
Distance matrix:

0.0 3.0 26.0    17.0    1.0 
0.0 0.0 41.0    30.0    6.0 
0.0 0.0 0.0 1.0 27.0    
0.0 0.0 0.0 0.0 18.0    
0.0 0.0 0.0 0.0 0.0 
level0:
cluster0:0
cluster1:1
cluster2:2
cluster3:3
cluster4:4

level1:
cluster0:0,4
cluster1:1
cluster2:2
cluster3:3

level2:
cluster0:0,4
cluster1:1
cluster2:2,3

level3:
cluster0:0,4,1
cluster1:2,3

level4:
cluster0:0,4,1,2,3


level0:
cluster0:<[1.0,2.0,0.0]>
cluster1:<[0.0,1.0,-1.0]>
cluster2:<[1.0,3.0,5.0]>
cluster3:<[1.0,3.0,4.0]>
cluster4:<[2.0,2.0,0.0]>

level1:
cluster0:<[1.0,2.0,0.0]><[2.0,2.0,0.0]>
cluster1:<[0.0,1.0,-1.0]>
cluster2:<[1.0,3.0,5.0]>
cluster3:<[1.0,3.0,4.0]>

level2:
cluster0:<[1.0,2.0,0.0]><[2.0,2.0,0.0]>
cluster1:<[0.0,1.0,-1.0]>
cluster2:<[1.0,3.0,5.0]><[1.0,3.0,4.0]>

level3:
cluster0:<[1.0,2.0,0.0]><[2.0,2.0,0.0]><[0.0,1.0,-1.0]>
cluster1:<[1.0,3.0,5.0]><[1.0,3.0,4.0]>

level4:
cluster0:<[1.0,2.0,0.0]><[2.0,2.0,0.0]><[0.0,1.0,-1.0]><[1.0,3.0,5.0]><[1.0,3.0,4.0]>

问题分析 #

问题出在mergeClosestClusters方法中构建新ClusterSet的顺序：当前代码先将合并后的簇添加到新集合的第一个位置（cluster0），再依次添加未被合并的簇。在Level2时，合并的是cluster2和cluster3，所以新集合先加合并后的2,3作为cluster0，然后加0,4作为cluster1，最后加1作为cluster2，导致顺序和预期不符。

预期逻辑是保留原有未合并簇的位置，将合并后的簇放在原来两个簇中较小的索引位置，维持整体顺序一致性。

修改方案 #

调整新ClusterSet的添加顺序，遍历原有簇列表，遇到其中一个待合并簇时添加合并后的簇，跳过另一个待合并簇，其他簇直接添加：

public ClusterSet mergeClosestClusters(ClusterDistance distance, Data data) {
    double minDistance = Double.MAX_VALUE;
    int clusterIndex1 = -1, clusterIndex2 = -1;
    for (int i = 0; i < lastClusterIndex; i++) {
        for (int j = i + 1; j < lastClusterIndex; j++) {
            double currentDistance = distance.distance(C[i], C[j], data);
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
                clusterIndex1 = i;
                clusterIndex2 = j;
            }
        }
    }
    Cluster mergedCluster = C[clusterIndex1].mergeCluster(C[clusterIndex2]);
    ClusterSet newClusterSet = new ClusterSet(lastClusterIndex - 1);
    
    // 遍历原有簇，按顺序添加，遇到clusterIndex1时添加合并簇，跳过clusterIndex2
    for (int i = 0; i < lastClusterIndex; i++) {
        if (i == clusterIndex1) {
            newClusterSet.add(mergedCluster);
        } else if (i != clusterIndex2) {
            newClusterSet.add(C[i]);
        }
    }
    
    return newClusterSet;
}

修改说明 #

• 不再优先添加合并簇，而是按照原有簇的遍历顺序构建新集合
• 当遍历到clusterIndex1（较小的簇索引）时，添加合并后的簇，替代原簇位置
• 遇到clusterIndex2时直接跳过，避免重复添加
• 其他未合并的簇保持原有顺序添加，最终结果会和预期输出完全一致

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