ポイントクラウドクラスター分析 - バイナリ行列から識別クラスタ

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] 

クラスタリングアルゴリズムバイナリの上三角行列を与えます（接続行列と呼ぶことができます）。 A 1は、2つの点が接続されていることを意味します。例えば。ポイントID 0（行0）は、それ自体（列0）、および1,2,3,12,13,14に接続されています。しかし、ポイント4と5は、また、3、12、13を介して到達され、そして14

[ 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.] 

Iは、sは上記からバイナリ行列でrowclustering（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]] 

行のいくつかは、共通のIDを介して接続されているので、今、明らかに15より少ないクラスタが存在する（例えばID 4および5を見て） 。私が持っていたいのです。私はIDXは、rowclusteringの結果であり、ことをしている（S）（IDX、f）のクラスタリングを（）関数を作成しようとしたとfが最初だろう

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

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または接続マトリックス（マトリックス削減？）の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}] 

---

EDIT：

実は、この問題についての何かが私が私がahile前に読んで何かを覚えていました。これは、実際には行列演算のみを使用して計算することができます。非常に気の利いた。あなたの最初の行列は隣接行列（A）であり、対角線上の各ノードの次数を保持する次数行列（D）も指定する必要があります。これらを使用してラプラシアン行列（L）を定義し、次にスペクトルグラフ理論のビットを使用することができます。 （よろしく！）

# Make the undirected version of the graph (no self loops) 
A = (mat + mat.T) * (1 - np.eye(mat.shape[0])) 
# Make the degree matrix 
D = np.diag(A.sum(axis=1) + A.sum(axis=0))/2 
# thats all we need to define the laplacian 
L = D - A 

# The number of zeros eigenvalues of the Laplacian is exactly the number of CCs 
np.isclose(np.linalg.eigvals(L), 0).sum() 

3 

# The connected compoments themselves are identified by rows that have the same nullspace vector 
u, s, vh = np.linalg.svd(L) 
ns = vh[(s >= 1e-13).sum():].conj().T 

array([[-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.19222441, 0.97663659, 0.09607676], 
    [-0.01778075, -0.04721352, 0.44435878], 
    [-0.01778075, -0.04721352, 0.44435878], 
    [-0.01778075, -0.04721352, 0.44435878], 
    [-0.01778075, -0.04721352, 0.44435878], 
    [-0.01778075, -0.04721352, 0.44435878], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ], 
    [-0.32684842, -0.06239247, -0.0197079 ]]) 

ここで、答えを計算しました！解釈するのがちょっと変だ。少しの処理でこれをあなたが望む表現に変えることができます。

# 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]]