Punktwolken Cluster-Analyse in Python - Identifizieren von Clustern von Binärmatrix

Question

Als Beispiel I habe die folgenden Eingangsdaten (die Punktwolke ich arbeite mit komplexer ist)

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] 

ein Clustering-Algorithmus gibt eine binäre obere Dreiecksmatrix (lassen Sie uns Verbindungsmatrix nennen). Eine 1 bedeutet, dass zwei Punkte verbunden sind. Z.B. Punkt ID 0 (Zeile 0) ist mit sich selbst verbunden (Spalte 0), und 1,2,3,12,13,14. Aber Punkte 4 und 5 werden ebenfalls über 3 erreicht haben, 12, 13 und 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.] 

kann ich den Cluster pro Reihe mit rowclustering (n) identifizieren, wobei S die binäre Matrix von oben ist.

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 

Und die zurück idx ist:

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

Nun, natürlich gibt es weniger Cluster als 15, weil einige Zeilen über eine gemeinsame ID (zB buchen, ID 4 und 5) verbunden sind, . Was ich haben will ist:

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

Ich habe versucht, eine Funktion (Clustering (idx, f)) zu erstellen, die das tut, wo idx, ist das Ergebnis der rowclustering (e) und f wäre der erste Zeile in idx, z [0, 1, 2, 3, 12, 13, 14]. Diese Funktion wird jedoch nicht ordnungsgemäß beendet. Was wäre der richtige Code, um die Funktion zu unterbrechen, nachdem alle Verbindungen (von IDX-IDs) hergestellt wurden?

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

    return 

Das Problem, das ich versuche zu lösen, ist eine, Art, selbst wachsendes Verfahren. Das Funktionscluster sollte sich selbst aufrufen, bis alle möglichen Punktverbindungen hergestellt sind. Dies könnte auf dem Idx oder (vielleicht besser) auf der Verbindungsmatrix (Matrixreduktion?) Erfolgen.

Jede Hilfe wird sehr geschätzt! Lassen Sie es mich wissen, wenn ich meine Frage klären sollte. Vielen Dank.

Answer 1

Ihr Problem kann so gesehen werden, als ob Sie verbundene Komponenten finden. Sie können networkx verwenden, um eine Lösung zu erhalten, oder Sie können BFS (breite erste Suche) selbst implementieren.

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:

Eigentlich etwas über dieses Problem hat mich an etwas erinnern, ich ahile vor lesen. Dies kann tatsächlich unter Verwendung von nur Matrixoperationen berechnet werden. Es ist sehr geschickt. Ihre Ausgangsmatrix ist die Adjazenzmatrix (A), und wir müssen auch eine Gradmatrix (D) angeben, die den Grad jedes Knotens auf der Diagonale enthält. Wir können diese verwenden, um die Laplace-Matrix (L) zu definieren und dann ein bisschen spektrale Graphentheorie zu verwenden. (yay!)

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

Jetzt haben wir die Antwort berechnet! Es ist nur ein wenig seltsam zu interpretieren. Ein wenig Verarbeitung kann dies in die gewünschte Darstellung umwandeln.

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