python - 按多列对数据框中的连续条目进行聚类/分组

Question

题

假设我有 k 个标量列，如果它们沿着每列彼此在一定距离内，我想对它们进行分组。

假设简单 k 是 2 并且它们是我唯一的列。

pd.DataFrame(list(zip(sorted(choices(range(0,10), k=20)), choices(range(20,29), k=20))), columns=['a','b'])

产量

[(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)]

我想要分组，以便组包含列 a 中的条目最多 m分开AND列 b最多 n分开。如果 m = n = 1，则聚类为:

(1, 27), (1, 27)
(1, 21)
(2, 23)
(3, 25), (4, 23), (4, 22), (4, 24)
(4, 28), (4, 27), (5, 26)
(6, 21), (7, 20)
(7, 26), (8, 24), (8, 25), (8, 23)
(9, 20), (9, 21)
(9, 28),

笔记

实现此目的的一种方法是使用 pdist ，但这不是一个好的解决方案，因为:

我有很多数据——不想做平方运算。

数据已经排序，m，n相对于列的范围

较小

m =/= n(不总是)否则 m+n 的曼哈顿距离阈值会起作用

我相信这可能是一个非常相关的问题，但它没有一个通用的答案:

Group by continuous indexes in Pandas DataFrame

可能让您找到答案的方法草图:

a, b, c, d, e = tee(range(10), 5)
next(b, None)
next(c, None);next(c, None)
next(d, None);next(d, None);next(d, None)
next(e, None);next(e, None);next(e, None);next(e, None)
list(zip(a, b, c, d, e))

[(0, 1, 2, 3, 4),
 (1, 2, 3, 4, 5),
 (2, 3, 4, 5, 6),
 (3, 4, 5, 6, 7),
 (4, 5, 6, 7, 8),
 (5, 6, 7, 8, 9)]

Answer 1

首先，我们做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

要找到完整的不连通图，您可能可以在 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是所有单独组的 bool 索引。现在返回结果:

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

您还可以使用这些 bool 索引来访问原始 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有效，但停止标准中断。您可以使用 Anreas K. 的出色回答 here ，或者只是做 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]])]

可能有一些方法可以在没有两个循环的情况下做到这一点，但我无法理解。