python - 查找具有公差的重复项并分配给 Pandas 中的一个集合

Question

输入

  Name         A    B     C
0   aa  0.002667  2.5  13.5
1   bb  0.003400  2.5  13.7
2   cc  0.003600  1.0  13.6
3   dd  0.003667  1.0  13.6
4   aa  0.003667  1.0  13.6
5   bb  0.007600  1.0  13.6
6   cc  0.007000  1.0  13.6
7   dd  0.007000  1.0  13.6

允许的公差:

        A    B   C
0   0.003   0.2 0.2

我必须找到具有上述公差表的重复项，并且需要将重复项映射到下面的集合中

预期输出:

   Name     A        B   C     Set
0   aa  0.002667    2.5 13.5    1
1   bb  0.003400    2.5 13.7    1
2   cc  0.003600    1.0 13.6    2
3   dd  0.003667    1.0 13.6    2
4   aa  0.003667    1.0 13.6    2
5   bb  0.007600    1.0 13.6    3
6   cc  0.007000    1.0 13.6    3
7   dd  0.007000    1.0 13.6    3

Answer 1

这是一种相对较快的方法，并且可以适用于其他邻近查询类型(例如，查找彼此之间在欧氏距离内的点集)。它以传递的方式处理接近度:如果 a 在 b 的公差范围内，并且 b 在 c 的公差范围内>，那么所有的a，b，c都被分配给同一个set_id，不管是否>a 在 c 的公差范围内。这相当于 single-linkage clustering ，但无需计算 O[n^2] 距离矩阵即可完成。

它使用了两个重要的工具:

1. scipy.spatial.KDTree加快寻找给定距离内的邻居。

2. networkx在邻居中找到孤立的子图。

注意 p-范数:我们对这个问题的理解是标记所有中彼此接近的点对的尺寸。相反，如果目标是在任何 维度中找到容差范围内的邻居，则改用p=1。对于轴 tol 彼此位于椭圆体内的点(即缩放问题中的球体)，则使用 p=2。

关于速度的注意事项:如果邻居的总数(彼此容差范围内的点对数)很小，这是有效的。在所有点彼此接近的极端情况下，那么这里介绍的方法是O[n^2]，其他方法(例如装箱)会更快。

解决方案

import networkx as nx
from scipy.spatial import KDTree


def group_neighbors(df, tol, p=np.inf, show=False):
    r = np.linalg.norm(np.ones(len(tol)), p)
    kd = KDTree(df[tol.index] / tol)
    g = nx.Graph([
        (i, j)
        for i, neighbors in enumerate(kd.query_ball_tree(kd, r=r, p=p))
        for j in neighbors
    ])
    if show:
        nx.draw_networkx(g)
    ix, id_ = np.array([
        (j, i)
        for i, s in enumerate(nx.connected_components(g))
        for j in s
    ]).T
    id_[ix] = id_.copy()
    return df.assign(set_id=id_)

示例1(OP的描述)

df = pd.DataFrame({
    'Name': ['aa', 'bb', 'cc', 'dd', 'aa', 'bb', 'cc', 'dd'],
    'A': [0.002667, 0.0034, 0.0036, 0.003667, 0.003667, 0.0076, 0.007, 0.007],
    'B': [2.5, 2.5, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0],
    'C': [13.5, 13.7, 13.6, 13.6, 13.6, 13.6, 13.6, 13.6]},
)
tol = pd.Series([0.003, 0.2, 0.2], index=list('ABC'))

>>> group_neighbors(df, tol)
  Name         A    B     C  set_id
0   aa  0.002667  2.5  13.5       0
1   bb  0.003400  2.5  13.7       0
2   cc  0.003600  1.0  13.6       1
3   dd  0.003667  1.0  13.6       1
4   aa  0.003667  1.0  13.6       1
5   bb  0.007600  1.0  13.6       2
6   cc  0.007000  1.0  13.6       2
7   dd  0.007000  1.0  13.6       2

奖励:显示邻居图:

_ = group_neighbors(df, tol, show=True)

例子2:一长串邻居

在此示例中，我们将 A 替换为单调序列 [0, 0.1, 0.2, ...]，这样每对连续点的距离为 0.1。我们还给出了 A=0.12 的公差:

>>> group_neighbors(
...     df.assign(A=np.arange(0, df.shape[0]) * 0.1),
...     tol=pd.Series([0.12], index=['A']), show=True)

  Name    A    B     C  set_id
0   aa  0.0  2.5  13.5       0
1   bb  0.1  2.5  13.7       0
2   cc  0.2  1.0  13.6       0
3   dd  0.3  1.0  13.6       0
4   aa  0.4  1.0  13.6       0
5   bb  0.5  1.0  13.6       0
6   cc  0.6  1.0  13.6       0
7   dd  0.7  1.0  13.6       0

例子3:更多的邻居，没有孤立的子图

>>> group_neighbors(
...     df.assign(A=np.arange(0, df.shape[0]) * 0.1),
...     tol=pd.Series([0.21], index=['A']), show=True)

  Name    A    B     C  set_id
0   aa  0.0  2.5  13.5       0
1   bb  0.1  2.5  13.7       0
2   cc  0.2  1.0  13.6       0
3   dd  0.3  1.0  13.6       0
4   aa  0.4  1.0  13.6       0
5   bb  0.5  1.0  13.6       0
6   cc  0.6  1.0  13.6       0
7   dd  0.7  1.0  13.6       0

解释

以下是该算法采取的各个步骤:

1. 缩放所有坐标，使公差在每个坐标中变为 1维度；
2. 将这些转换后的点制作成 KDTree；
3. 一次性查询距离r=1 内的所有点对； 注意:我们使用 p-norm Infinite，所以区域是超立方体；这对应于在彼此的 tol 边界框内找到所有点；
4. 制作一个图，其中所有边都表示相邻的点；
5. 找到所有孤立的子图:这些是我们要将每个成员分配给的集合；
6. 用唯一的 int 标记集合(来自 enumerate())。

实例

让我们逐步检查 OP 示例中发生的情况。

首先，选择单位公差的相关尺寸和刻度:

>>> df[tol.index] / tol

          A     B     C
0  0.889000  12.5  67.5
1  1.133333  12.5  68.5
2  1.200000   5.0  68.0
3  1.222333   5.0  68.0
4  1.222333   5.0  68.0
5  2.533333   5.0  68.0
6  2.333333   5.0  68.0
7  2.333333   5.0  68.0

在这种缩放之后，任务变成了寻找在任何维度上的差异最多为 1 的任何一对点。

使用 KDTree 可以快速找到邻居。 注意:我们使用 kd.query_ball_tree 而不是 kd.query_pairs 因为我们也想保留单例(例如:仅与他们自己)，以便他们可以在最终输出中获得自己的 set_id:

kd = KDTree(df[tol.index] / tol)
>>> kd.query_ball_tree(kd, r=1, p=np.inf)

[[0, 1],
 [0, 1],
 [2, 3, 4],
 [2, 3, 4],
 [2, 3, 4],
 [5, 6, 7],
 [5, 6, 7],
 [5, 6, 7]]

然后从所有这些对构建图。

我们使用connected_components 来获取g 的所有相互隔离的子图:

>>> list(nx.connected_components(g))

[{0, 1}, {2, 3, 4}, {5, 6, 7}]

所以，我们有三个集合(孤立的子图)。然后我们可以为每个分配一个 ID，并返回结果。