将行按重叠范围分组

Question

我有一个数据框，其中left列是对象最左边的位置，right列是对象最右边的位置。如果它们重叠，或者它们与重叠的对象重叠（递归），我需要对这些对象进行分组。

因此，例如，如果这是我的数据框：

     left  right
0      0    4
1      5    8
2      10   13
3      3    7
4      12   19      
5      18   23
6      31   35

所以行0和行3重叠 - 因此它们应该在同一组中，而且行1与行3重叠 - 因此它加入了这个组。

因此，对于这个示例，输出应该是这样的：

     left  right    group
0      0    4         0
1      5    8         0
2      10   13        1
3      3    7         0
4      12   19        1
5      18   23        1
6      31   35        2

我想了很多方向，但是没有想出来（不用丑陋的for）。任何帮助都将不胜感激！

- Binyamin Even

Answer 1

我发现被接受的解决方案（更新：已删除）是误导性的，因为它无法推广到类似的情况。例如，对于以下示例：

df = pd.DataFrame({'left': [0,5,10,3,12,13,18,31], 
    'right':[4,8,13,7,19,16,23,35]})
df

建议的聚合函数输出以下数据框（请注意，18-23应与12-19一起分组为组1）。

一种解决方案是使用以下方法（基于一种合并区间的方法由@CentAu发布）：

# Union intervals by @CentAu
from sympy import Interval, Union
def union(data):
    """ Union of a list of intervals e.g. [(1,2),(3,4)] """
    intervals = [Interval(begin, end) for (begin, end) in data]
    u = Union(*intervals)
    return [u] if isinstance(u, Interval) \
        else list(u.args)

# Create a list of intervals
df['left_right'] = df[['left', 'right']].apply(list, axis=1)
intervals = union(df.left_right)

# Add a group column
df['group'] = df['left'].apply(lambda x: [g for g,l in enumerate(intervals) if 
l.contains(x)][0])

...它输出：

- tomp

---

基于你的想法，为什么13、16和18、23有重叠区间？你能解释一下吗？所以你认为这是网络问题？ - BENY

如果您正在尝试合并重叠的范围，则有三个组：0（0-8），1（10-23）和2（31-35）。回答您的问题，13-16和18-23重叠，因为它们由12-19连接。尝试查看区间树：https://en.wikipedia.org/wiki/Interval_tree - tomp

Answer 2

你可以尝试使用 rolling max 和 rolling min，来找到范围的交集：

df=df.sort_values(['left','right'])
df['Group']=((df.right.rolling(window=2,min_periods=1).min()-df.left.rolling(window=2,min_periods=1).max())<0).cumsum()


df.sort_index()
Out[331]: 
   left  right  Group
0     0      4      0
1     5      8      0
2    10     13      1
3     3      7      0
4    12     19      1
5    18     23      1
6    31     35      2

例如，(1,3)和(2,4)。要找到交集。

mix(3,4)-max(1,2)=1；1大于0；那么两个区间有交集。

- BENY

---

你对 sort_values 的想法很有启发性。 - cs95

这是一个很好的答案，我希望我能接受两个答案。不幸的是我不能，@COLDSPEED的答案似乎更加直接。无论如何，非常感谢！ - Binyamin Even

@BinyaminEven 没问题，愉快编码。 - BENY

这种方法无法推广到类似的数据集（例如对于 pd.DataFrame({'left': [0,5,10,3,12,13,18,31], 'right':[4,8,13,7,19,16,23,35]})，18-23与12-19不属于同一组）。 - tomp

Answer 3

您可以对样本进行排序并利用累计函数cummax和cumsum。让我们看看您的例子：

   left  right
0     0      4
3     3      7
1     5      8
2    10     13
4    12     19
5    13     16
6    18     23
7    31     35

首先，您需要对值进行排序，以便较长的范围首先出现：

df = df.sort_values(['left', 'right'], ascending=[True, False])

结果：

   left  right
0     0      4
3     3      7
1     5      8
2    10     13
4    12     19
5    13     16
6    18     23
7    31     35

然后，您可以通过比较“left”和前一个“right”值来找到重叠的组：

df['group'] = (df['right'].cummax().shift() <= df['left']).cumsum()
df.sort_index(inplace=True)

结果：

   left  right  group
0     0      4      0
1     5      8      0
2    10     13      1
3     3      7      0
4    12     19      1
5    13     16      1
6    18     23      1
7    31     35      2

一句话概括：

- Mykola Zotko