通过多列对数据帧中的连续项进行群集/分组

Question

问题

假设我有k个标量列，并且我想将条目分组，如果它们沿着每列彼此之间的距离在一定范围内

假设simpicity 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的条目和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

首先，我们用metric = 'chebyshev'做pdist

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基本上是一个节点图，如果它们是<；每个方向都有一个间隔

要找到完整的未连接图，在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可以工作，但停止条件中断。您可以使用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]])]

也许有办法不用两个循环就能完成，但我无法摸索

Answer 2

你的问题让我想起了lag操作和cumsum。这里有一个答案。如果您的数据很大，我认为使用python list和tuple是可以的，默认模块必须有函数来完成我们的任务

步骤1：获取数据

# generate data
import pandas as pd
import numpy as np
from random import choices,seed
seed(1245)
data = pd.DataFrame(list(zip(sorted(choices(range(0,10), k=20,)), choices(range(20,29), k=20))), columns=['a','b'])

第2步：滞后1个长度

# lag opertion
data_shift = data.shift(1,fill_value = -999)
data_shift.columns = ["a_last","b_last"]

# conbine them together to apply. If your data is huge, just call function on these 2 pieces of data
data_flat = pd.concat([data,data_shift],axis = 1)
data_flat.head()

输出：

   a   b  a_last  b_last
0  1  26    -999    -999
1  1  27       1      26
2  1  28       1      27
3  2  22       1      28
4  2  24       2      22

步骤3：定义custum函数，然后将观察结果分组

# define your function with args m,n
def your_func(x,m,n):
    cond1 = (abs(x.a - x.a_last) <= m)
    cond2 = (abs(x.b - x.b_last) <= n)
    if cond1 & cond2:
        return 0
    else: 
        return 1
# calculate per row and get the group_id of samples
groups = data_flat.apply(your_func,axis = 1,m=1,n=1).cumsum()
# get the result
data.groupby(groups).apply(lambda x:list(map(tuple,x.values)))

输出：

1     [(1, 26), (1, 27), (1, 28)]
2                       [(2, 22)]
3                       [(2, 24)]
4                       [(3, 20)]
5                       [(3, 26)]
6              [(4, 21), (4, 20)]
7                       [(5, 28)]
8              [(5, 26), (5, 26)]
9                       [(6, 28)]
10                      [(6, 24)]
11                      [(6, 28)]
12                      [(7, 23)]
13                      [(7, 26)]
14             [(8, 28), (8, 28)]
15                      [(9, 26)]
dtype: object