矩阵中簇个数numpy计数

ijnw1ujt  于 2022-12-13  发布在  其他
关注(0)|答案(3)|浏览(159)

在一个只有0和1的对称numpy矩阵中,有没有一种方法来计算“1的连接簇”的数目?
例如下面的numpy矩阵:

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

有两簇相连的1:

9o685dep

9o685dep1#

您可以使用scipy.ndimage.label
如果要标识4个群集,请用途:

from scipy.ndimage import label

_, n = label(a)

print(n)

输出:4
默认结构元素(内核)不包括对角线:

[[0,1,0],
 [1,1,1],
 [0,1,0]]

因此,如果您认为有两个集群(通过对角线连接),请更改默认内核:

from scipy.ndimage import label

kernel = np.ones((3, 3))

_, n = label(a, structure=kernel)
print(n)

输出:2
使用的输入:

a = np.array([[0, 0, 0, 0, 1, 1, 0],
              [0, 0, 0, 0, 1, 1, 0],
              [0, 0, 0, 0, 0, 0, 1],
              [0, 0, 0, 0, 0, 0, 0],
              [1, 1, 0, 0, 0, 0, 0],
              [1, 1, 0, 0, 0, 0, 0],
              [0, 0, 1, 0, 0, 0, 0]])
7ivaypg9

7ivaypg92#

我不认为有一个简单的方法,或者一个提供的函数,你必须使用一个算法。
这个问题的典型算法被称为连通分量标记,它被用于图像处理。该算法在维基百科上有描述:https://en.wikipedia.org/wiki/Connected-component_labeling

qacovj5a

qacovj5a3#

import numpy as np

n = 50
tmp = np.random.rand(n, n)
a = (tmp + tmp.T > 1).astype(int)  # symmetric matrix
visited = np.full((n, n), fill_value=False)
cnt = 0

def paint(i, j, n):
    if not ((0 <= i < n) and (0 <= j < n) and (i <= j)):
        return
    if visited[i, j] or a[i, j] == 0:
        return
    visited[i, j] = True
    paint(i + 1, j, n)  # dfs
    paint(i - 1, j, n)
    paint(i, j + 1, n)
    paint(i, j - 1, n)

for i in range(n):
    for j in range(i, n):
        if (not visited[i, j]) and a[i, j] == 1:
            paint(i, j, n)
            cnt += 1

print(cnt)

当矩阵中有很多one并且n很大时,我的解可能会引发RecursionError

相关问题