如何在二维numpy数组中找到簇大小？

Question

我的问题是这样的：

我有一个二维的numpy数组，里面填满了0和1，并且有一个吸收边界条件（所有外面的元素都是0），比如说：

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

我想创建一个函数，这个函数接收这个数组和它的线性维度L作为输入参数（在这个例子中L = 10），然后返回这个数组中各个“簇”的大小列表。

这里说的“簇”是指数组中孤立的1的组合。

数组元素[i][j]是孤立的，如果它周围的所有邻居都是0，而它的邻居是：

[i+1][j]
[i-1][j]
[i][j+1]
[i][j-1]

所以在之前的数组中，我们有7个簇，大小分别是(2,1,2,6,1,1,1)。

我尝试通过创建两个函数来完成这个任务，第一个是递归函数：

def clust_size(array,i,j):

    count = 0

    if array[i][j] == 1:

        array[i][j] = 0

        if array[i-1][j] == 1:

            count += 1
            array[i-1][j] = 0
            clust_size(array,i-1,j)

        elif array[i][j-1] == 1:

            count += 1
            array[i-1][j] = 0
            clust_size(array,i,j-1)

        elif array[i+1][j] == 1:

            count += 1
            array[i-1][j] =  0
            clust_size(array,i+1,j)

        elif array[i][j+1] == 1:

            count += 1
            array[i-1][j] = 0
            clust_size(array,i,j+1)

    return count+1         

这个函数应该返回一个簇的大小。每当这个函数找到一个值为1的数组元素时，它就会增加计数器“count”的值，并把这个元素的值改为0，这样每个'1'元素就只会被计算一次。

如果这个元素的某个邻居是1，那么这个函数就会在那个元素上再次调用自己。

第二个函数是：

def clust_list(array,L):

    sizes_list = []

    for i in range(1,L-1):
        for i in range(1,L-1):

           count = clust_size(array,i,j)

           sizes_list.append(count)

    return sizes_list

这个函数应该返回一个包含簇大小的列表。for循环从1迭代到L-1，因为所有外面的元素都是0。

但是这个方法不行，我看不出哪里出错了……

我在想，是否有更简单的方法来实现这个功能。

Answer 1

如果你把这个问题转成字符串的话，其实是个比较简单的问题。

import numpy as np                                       
arr=np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],           
              [0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],           
              [0, 0, 1, 1, 1, 1, 1, 1, 1, 0,],   #modified        
              [0, 0, 0, 0, 0, 0, 1, 0, 1, 0,],           
              [0, 0, 0, 0, 0, 0, 1, 0, 0, 0,],           
              [0, 0, 0, 0, 1, 0, 1, 0, 0, 0,],           
              [0, 0, 0, 0, 0, 1, 1, 0, 0, 0,],           
              [0, 0, 0, 1, 0, 1, 0, 0, 0, 0,],           
              [0, 0, 0, 0, 1, 0, 0, 0, 0, 0,],           
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])           

arr = "".join([str(x) for x in arr.reshape(-1)])         
print [len(x) for x in arr.replace("0"," ").split()] 

输出结果

[1, 7, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1] #Cluster sizes

Answer 2

我觉得你的方法差不多是对的，只是每次你递归调用函数 clust_size 时，都在不断地重新初始化变量 count。我建议把 count 这个变量放到 clust_size 的输入参数里，然后在你嵌套的 for 循环的第一次调用时，把 count 重新设置为 0。

这样的话，你每次调用 clust_size 时都可以写成 count=clust_size(array, i ,j, count)。我没有测试过，但我觉得这样应该可以工作。

希望这对你有帮助。

Answer 3

我理解你在寻找“聚类”的问题，实际上和在二进制图像中找“连通区域”是一个道理。二进制图像就是只有0和1两种值的图像，而连通区域是指那些相连的部分，通常是通过4个方向（上下左右）来判断的。你可以在这个维基百科页面上看到几种识别连通区域（或者你说的“聚类”）的算法：

http://en.wikipedia.org/wiki/Connected-component_labeling

一旦这些连通区域或者“聚类”被标记出来，你就可以很轻松地找到你想要的任何信息，比如面积、相对位置或者其他任何你需要的信息。

Answer 4

这看起来像是一个渗透问题。

如果你安装了scipy，可以通过下面的链接找到答案。

http://dragly.org/2013/03/25/working-with-percolation-clusters-in-python/

from pylab import *
from scipy.ndimage import measurements

z2 = array([[0,0,0,0,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,0],
    [0,0,1,0,1,0,0,0,1,0],
    [0,0,0,0,0,0,1,0,1,0],
    [0,0,0,0,0,0,1,0,0,0],
    [0,0,0,0,1,0,1,0,0,0],
    [0,0,0,0,0,1,1,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]])

这段代码会帮你识别出聚类。

lw, num = measurements.label(z2)
print lw
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 1, 0, 2, 0, 0, 0, 3, 0],
   [0, 0, 0, 0, 0, 0, 4, 0, 3, 0],
   [0, 0, 0, 0, 0, 0, 4, 0, 0, 0],
   [0, 0, 0, 0, 5, 0, 4, 0, 0, 0],
   [0, 0, 0, 0, 0, 4, 4, 0, 0, 0],
   [0, 0, 0, 6, 0, 4, 0, 0, 0, 0],
   [0, 0, 0, 0, 7, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

接下来这段代码会计算它们的面积。

area = measurements.sum(z2, lw, index=arange(lw.max() + 1))
print area
[ 0.  2.  1.  2.  6.  1.  1.  1.]

这个结果是你所期待的，虽然我觉得从视觉上看，你应该能看到一个有8个成员的聚类。