Python中点云聚类分析从二进制矩阵中识别聚类

Question

例如，我有以下输入数据（我使用的点云更复杂）

Data = [1,1,1,1,1],[1,1,2,1,1],[2,2,2,1,1],[3,3,3,1,1],[4,4,4,1,1],[5,5,5,1,1],[50,50,50,1,1],[95,95,95,1,1],[96,96,96,1,1],[97,97,97,1,1],[98,98,98,1,1],[99,99,99,1,1],[2,2,3,1,1],[2,2,1,1,1],[2,2,4,1,1]

聚类算法给出一个二元上三角矩阵（称之为连接矩阵）。1表示两点相连。E、 g.点ID 0（第0行）连接到自身（第0列），以及1、2、3、12、13、14。但是第4点和第5点也可以通过3、12、13和14点到达。在

^{pr2}$

我可以用rowclustering（s）标识每行的簇，其中s是上面的二进制矩阵。在

def rowclustering(s):
    r = 0
    idx = []
    while r < size(s,0):
        row = []
        for i in range(size(s,1)):
            if s[r][i] == 1:
                row = row + [i]
        r = r + 1
        idx = idx + [row]
    return idx

返回的idx是：

idx = [[0, 1, 2, 3, 12, 13, 14], [1, 2, 3, 12, 13, 14], [2, 3, 4, 12, 13, 14], [3, 4, 5, 12, 13, 14], [4, 5, 12, 14], [5], [6], [7, 8, 9], [8, 9, 10], [9, 10, 11], [10, 11], [11], [12, 13, 14], [13, 14], [14]]

现在，显然集群少于15个，因为有些行是通过一个公共ID连接的（例如，查看ID 4和5）。我想要的是：

result = [[0, 1, 2, 3, 4, 5, 12, 13, 14], [6], [7, 8, 9, 10, 11]]

我试图创建一个函数（clustering（idx，f）），其中idx是rowclustering（s）的结果，f将是idx中的第一行，例如[0，1，2，3，12，13，14]。但是，此功能无法正常完成。在所有连接（idx id）建立之后，什么是中断函数的正确代码？在

def clustering(idx,f):
    for i in f:
        f = f + idx[i]
    f = list(set(f))
    clustering(idx,f)

    return

我想解决的问题是一种，自我成长的过程。函数集群应该调用自己，直到所有可能的点连接都建立起来。这可以在idx上实现，或者（也许更好）在连接矩阵上（矩阵约化？）。在

非常感谢任何帮助！如果我要澄清我的问题，请告诉我。谢谢。在

Answer 1

您的问题可以看作是查找连接的组件。您可以使用networkx来获得解决方案，也可以自己实现BFS（广度优先搜索）。在

import networkx as nx
import numpy as np
x = """
[ 1.  1.  1.  1.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.]
[ 0.  1.  1.  1.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.]
[ 0.  0.  1.  1.  1.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.]
[ 0.  0.  0.  1.  1.  1.  0.  0.  0.  0.  0.  0.  1.  1.  1.]
[ 0.  0.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.  1.  0.  1.]
[ 0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  0.  0.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  0.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.]
[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.]
"""
mat = eval('[' + x.replace('.', '.,').replace(']', '],') + ']')
mat = np.array(mat)
G = nx.from_numpy_matrix(np.array(mat))
print(list(nx.connected_components(G)))
[{0, 1, 2, 3, 4, 5, 12, 13, 14}, {6}, {7, 8, 9, 10, 11}]

---

编辑：

实际上，关于这个问题的一些东西让我想起了我之前读过的一些东西。这实际上可以只使用矩阵运算来计算。非常漂亮。你的初始矩阵是邻接矩阵（A），我们还需要指定一个度矩阵（D），它保存对角线上每个节点的度数。我们可以用这些来定义拉普拉斯矩阵（L），然后使用一些谱图论。（耶！）在

^{pr2}$

现在，我们已经计算出答案了！只是有点奇怪。稍加处理就可以将其转换为所需的表示形式。在

# the following is a little numpy trick to find unique rows 
# chopping off the last few decimal places to account for numerical errors
ns_ = np.ascontiguousarray(np.round(ns, 8)).view(np.dtype((np.void, ns.dtype.itemsize * ns.shape[1])))
ns_basis, row_to_cc_id = np.unique(ns_, return_inverse=True)
# Finally we can just use this to convert to the desired output format
groups = [[] for _ in range(len(ns_basis))]
for row, id in enumerate(row_to_cc_id):
    groups[id].append(row)
print(groups)
[[0, 1, 2, 3, 4, 5, 12, 13, 14], [6], [7, 8, 9, 10, 11]]