查找具有容忍度的重复项并分配给 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。这相当于单链接聚类，但无需计算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(from 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，并返回结果。