Hoshen-Kopelman聚类检测算法代码调试求助：聚类标记错误

我是编程新手，编写了用于矩阵聚类检测的Hoshen-Kopelman算法代码，旨在识别矩阵中的聚类并计算最大聚类规模与矩阵大小的占比。但测试示例矩阵时发现部分聚类标记错误（如标记为3和6的聚类实际应为同一聚类），恳请协助调试代码。

原代码如下：

import numpy as np
import matplotlib.pyplot as plt

class UnionFind:
    def __init__(self, max_labels):
        self.labels = np.zeros(max_labels, dtype=np.uint8)
        self.labels[0] = 0
        self.n_labels = max_labels

    def find(self, x):
        y = x
        if self.labels[y] != y:
            y = self.labels[y]
        if self.labels[x] != x:
            z = self.labels[x]
            self.labels[x] = y
            x = z
        return y

    def union(self, x, y):
        self.labels[self.find(x)] = self.find(y)
        return self.find(x)

    def make_set(self):
        self.labels[0] += 1
        assert self.labels[0] < self.n_labels
        self.labels[self.labels[0]] = self.labels[0]
        return self.labels[0]


def hoshen_kopelman(matrix, m, n):
    uf = UnionFind(m * n // 2)
    cluster_sizes = {} 

    for i in range(m):
        for j in range(n):
            if matrix[i][j]:
                up = matrix[i - 1][j] if i > 0 else 0
                left = matrix[i][j - 1] if j > 0 else 0
        
                if up == 0 and left == 0:
                    matrix[i][j] = uf.make_set()
                elif up == 0 or left == 0:
                    matrix[i][j] = max(up, left)
                else:
                    matrix[i][j] = uf.union(up, left)

                label = matrix[i][j]
                cluster_sizes[label] = cluster_sizes.get(label, 0) + 1

    largest_cluster_size = max(cluster_sizes.values())
    matrix_size = m * n
    largest_cluster_ratio = largest_cluster_size / matrix_size

    return matrix, largest_cluster_ratio

matrix1 = np.array([
[1, 0, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 1]])

hkm, largest_cluster_ratio = hoshen_kopelman(matrix1, 6, 6)

fig, ax = plt.subplots()
min_val = 0
max_val = 6
m = 6
n = 6
ax.matshow(hkm, cmap=plt.cm.Blues)

for i in range(m):
    for j in range(n):
        c = hkm[i, j]
        ax.text(j, i, str(c), va='center', ha='center')

plt.show()

print("size of the largest cluster(ratio to the matrix size):", largest_cluster_ratio)

测试显示原本属于同一聚类的区域被标记为不同标签（如3和6），且聚类占比计算错误。

问题根源 #

1. UnionFind的find方法不完整：仅做单次标签跳转，未递归找到根节点，也未实现路径压缩，导致无法正确追踪聚类的根标签，不同子标签无法合并到同一根。
2. 聚类大小统计逻辑错误：直接使用矩阵中的当前标签计数，而非该标签对应的根标签，导致同一聚类被拆分统计，最大聚类占比计算错误。
3. UnionFind初始化标签上限不足：m*n//2的设置在极端情况（如全1矩阵）下会触发断言错误，应设置为足够大的值。

修复后的代码 #

import numpy as np
import matplotlib.pyplot as plt

class UnionFind:
    def __init__(self, max_labels):
        self.labels = np.zeros(max_labels, dtype=np.uint8)
        self.next_label = 1  # 单独管理下一个可用标签，避免混淆
        self.n_labels = max_labels

    def find(self, x):
        # 递归实现路径压缩，确保所有节点直接指向根标签
        if self.labels[x] != x:
            self.labels[x] = self.find(self.labels[x])
        return self.labels[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.labels[x_root] = y_root
        return y_root

    def make_set(self):
        assert self.next_label < self.n_labels
        self.labels[self.next_label] = self.next_label
        current_label = self.next_label
        self.next_label += 1
        return current_label


def hoshen_kopelman(matrix, m, n):
    # 设置足够大的标签上限，避免溢出
    uf = UnionFind(m * n + 1)
    cluster_sizes = {} 

    for i in range(m):
        for j in range(n):
            if matrix[i][j]:
                up = matrix[i-1][j] if i > 0 else 0
                left = matrix[i][j-1] if j > 0 else 0
        
                if up == 0 and left == 0:
                    matrix[i][j] = uf.make_set()
                elif up == 0:
                    matrix[i][j] = uf.find(left)  # 直接使用根标签
                elif left == 0:
                    matrix[i][j] = uf.find(up)    # 直接使用根标签
                else:
                    # 合并两个根，并将当前节点设为合并后的根标签
                    matrix[i][j] = uf.union(up, left)

                # 用根标签统计聚类大小
                root_label = uf.find(matrix[i][j])
                cluster_sizes[root_label] = cluster_sizes.get(root_label, 0) + 1

    # 将矩阵中所有标签替换为根标签，方便可视化
    for i in range(m):
        for j in range(n):
            if matrix[i][j] != 0:
                matrix[i][j] = uf.find(matrix[i][j])

    largest_cluster_size = max(cluster_sizes.values()) if cluster_sizes else 0
    matrix_size = m * n
    largest_cluster_ratio = largest_cluster_size / matrix_size

    return matrix, largest_cluster_ratio

matrix1 = np.array([
[1, 0, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 1]])

hkm, largest_cluster_ratio = hoshen_kopelman(matrix1, 6, 6)

fig, ax = plt.subplots()
ax.matshow(hkm, cmap=plt.cm.Blues)

for i in range(hkm.shape[0]):
    for j in range(hkm.shape[1]):
        c = hkm[i, j]
        ax.text(j, i, str(c), va='center', ha='center')

plt.show()

print("最大聚类规模与矩阵大小的占比:", largest_cluster_ratio)

修复说明 #

1. 完善UnionFind的find方法：实现递归式路径压缩，确保所有节点最终直接指向根标签，保证聚类合并的正确性。
2. 调整标签追踪方式：用next_label变量单独管理下一个可用标签，避免原代码中用labels[0]存储的混淆。
3. 修正聚类统计逻辑：每次计数都使用根标签，确保同一聚类的所有节点被统计到同一键下。
4. 统一矩阵标签：最后遍历矩阵将所有非0标签替换为根标签，可视化时同一聚类会显示相同的标签。

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