точка-облако кластер-анализ в 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] 

алгоритм кластеризации дает двоичную верхнюю треугольную матрицу (назовем ее матрицей соединения). A 1 означает, что подключены две точки. Например. Точечный идентификатор 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.] 

можно идентифицировать кластеры для каждой строки с 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]] 

Теперь, очевидно, есть меньше скопления, чем 15, поскольку некоторые из строк соединены через общий ID (например, смотреть на ID 4 и 5) , То, что я хочу, чтобы это:

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

Я попытался создать функцию (кластеризация (IDX, е)), что делает это, где IDX, является результатом rowclustering (s) и F будет первым строка в idx, например [0, 1, 2, 3, 12, 13, 14]. Однако эта функция не завершится должным образом. Каким будет правильный код для разрыва функции после всех подключений (идентификаторов idx)?

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

---

EDIT:

На самом деле, что-то об этой проблеме заставило меня вспомнить что-то я прочитал ahile назад. Это можно фактически вычислить, используя только операции с матрицами. Это очень изящно. Ваша начальная матрица - матрица смежности (A), и нам также нужно указать матрицу степени (D), которая содержит степень каждого узла на диагонали. Мы можем использовать их для определения матрицы Лапласа (L), а затем использовать немного спектральной теории графов. (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 ]]) 

Теперь мы вычислили ответ! Его немного странно интерпретировать. Немного обработки может преобразовать это в желаемое представление.

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