Во-первых, мы делаем pdist с metric = 'chebyshev'
test = np.array([(1, 27),
(1, 27),
(1, 21),
(2, 23),
(3, 25),
(4, 23),
(4, 28),
(4, 27),
(4, 22),
(4, 24),
(5, 26),
(6, 21),
(7, 26),
(7, 20),
(8, 24),
(8, 25),
(8, 23),
(9, 20),
(9, 28),
(9, 21)])
from scipy.spatial.distance import pdist, squareform
c_mat = squareform(pdist(test, metric = 'chebyshev')) <= 1
, теперь c_mat - это в основном график узлов, которые связаны, если они <1 друг от друга в каждом направлении </p>
Чтобы найти полные несвязанные графы, вероятно, есть быстрая операция, которую вы можете сделать в networx, но я просто немного сложнее в numpy, так как я не знаю, какие ключевые слова теории графов искать там.
out = np.ones((c_mat.shape[0], 2))
while out.sum(0).max() >1:
c_mat = c_mat @ c_mat
out = np.unique(c_mat, axis = 0)
Теперь c_mat равно True, если есть какая-либо цепочка, соединяющая две строки, а out - это логические индексы всех отдельных групп. Теперь для возврата результата:
for mask in list(out):
print(np.unique(test[mask], axis = 0))
[[ 9 28]]
[[ 9 20]
[ 9 21]]
[[ 7 26]
[ 8 23]
[ 8 24]
[ 8 25]]
[[ 6 21]
[ 7 20]]
[[ 4 27]
[ 4 28]
[ 5 26]]
[[ 3 25]
[ 4 22]
[ 4 23]
[ 4 24]]
[[ 2 23]]
[[ 1 21]]
[[ 1 27]]
Вы также можете использовать эти логические индексы для доступа к строкам данных в вашем оригинале DataFrame
РЕДАКТИРОВАТЬ 1:
Теперь мы можем значительно ускорить это, используя тот факт, что входные данные отсортированы по полусортировке. Но для этого нам нужно numba
from numba import jit
@jit
def find_connected(data, dist = 1):
i = list(range(data.shape[0]))
j = list(range(data.shape[0]))
l = data.shape[0]
for x in range(1, l):
for y in range(x, l):
v = np.abs(data[x] - data[y])
if v.max() <= dist:
i += [x, y]
j += [y, x]
if v.min() > dist:
break
d = [1] * len(i)
return (d, (i, j))
, теперь нам нужно загрузить это в разреженную матрицу
from scipy.sparse import csr_matrix
c_mat = csr_matrix(find_connected(test), dtype = bool)
csr делает точечные продукты намного быстрее, поэтому c_mat = c_mat @ c_mat работает, но критерий остановки нарушается. Вы можете использовать превосходный ответ Анреаса К. здесь или просто сделать out = np.unique(c_mat.todense(), axis = 0).
РЕДАКТИРОВАТЬ 2:
Не удалось выкинь это из головы, пока я не решу это без создания плотной матрицы.
import numba as nb
import numpy as np
@nb.njit
def find_connected_semisort(data, dist = 1):
l = data.shape[0]
out = []
for x in range(l):
for y in range(x, l):
v = np.abs(data[x] - data[y])
if v.max() <= dist:
out.append(set([x, y]))
if v.min() > dist:
break
outlen = len(out)
for x in range(outlen):
for y in range(x + 1, outlen):
if len(out[x] & out[y]) > 0:
out[y] |= out[x]
out[x].clear()
return [list(i) for i in out if len(i) > 0]
[np.unique(test[i], axis = 0).squeeze() for i in find_connected_semisort(test)]
Out[]:
[array([ 1, 27]), array([ 1, 21]), array([ 2, 23]), array([[ 3, 25],
[ 4, 22],
[ 4, 23],
[ 4, 24]]), array([[ 4, 27],
[ 4, 28],
[ 5, 26]]), array([[ 6, 21],
[ 7, 20]]), array([[ 7, 26],
[ 8, 23],
[ 8, 24],
[ 8, 25]]), array([ 9, 28]), array([[ 9, 20],
[ 9, 21]])]
Возможно, есть какой-то способ сделать это без двух петель, но я не смог бы это сделать.