python - 识别由左侧的 delta 和右侧的不同 delta 链接的集群

Question

考虑排序数组a:

a = np.array([0, 2, 3, 4, 5, 10, 11, 11, 14, 19, 20, 20])

如果我指定左右增量，

delta_left, delta_right = 1, 1

那么这就是我希望分配集群的方式:

#   a = [ 0  .  2  3  4  5  .  .  .  . 10 11  .  . 14  .  .  .  . 19 20
#                                         11                         20
#
#                                     [10--|-12]                 [19--|-21]
#           [1--|--3]                 [10--|-12]                 [19--|-21]
#    [-1--|--1]   [3--|--5]         [9--|-11]                 [18--|-20]
#   +--+--|--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
#              [2--|--4]                       [13--|-15]
#
#         │    ╰──┬───╯                 ╰┬─╯        │              ╰┬─╯
#         │   cluster 2                Cluster 3    │           Cluster 5
#     Cluster 1                                 Cluster 4

注意:尽管区间 [-1, 1] 与 [1, 3] 共享边>，两个区间都不包含相邻点，因此不构成加入它们各自的簇。

假设集群分配存储在名为 clusters 的数组中，我希望结果看起来像这样

print(clusters)
[1 2 2 2 2 3 3 3 4 5 5 5]

---

但是，假设我将左右增量更改为不同:

delta_left, delta_right = 2, 1

这意味着对于 x 的值，它应该与区间 [x - 2, x + 1] 中的任何其他点相结合

#   a = [ 0  .  2  3  4  5  .  .  .  . 10 11  .  . 14  .  .  .  . 19 20
#                                         11                         20
#
#                                   [9-----|-12]              [18-----|-21]
#        [0-----|--3]               [9-----|-12]              [18-----|-21]
# [-2-----|--1][2-----|--5]      [8-----|-11]              [17-----|-20]
#   +--+--|--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
#           [1 ----|--4]                    [12-----|-15]
#
#         ╰─────┬─────╯                 ╰┬─╯        │              ╰┬─╯
#           cluster 1                Cluster 2      │           Cluster 4
#                                               Cluster 3

注意:尽管区间 [9, 12] 与 [12, 15] 共享边, 两个区间都不包含相邻点，因此不构成加入它们各自的簇。

假设集群分配存储在名为 clusters 的数组中，我希望结果如下所示:

print(clusters)
[1 1 1 1 1 2 2 2 3 4 4 4]

Answer 1

我们将利用 np.searchsorted和寻找聚类边缘的逻辑。

首先，让我们仔细看看 np.searchsorted 做了什么:

Find the indices into a sorted array a such that, if the corresponding elements in v were inserted before the indices, the order of a would be preserved.

我要做的是使用 a - delta_left 执行 np.searchsorted 和 a。让我们看看 delta_left = 1

# a =
# [ 0  2  3  4  5 10 11 11 14 19 20 20]
# 
# a - delta_left
# [-1  1  2  3  4  9 10 10 13 18 19 19]

• -1 将被插入到位置 0 以维持顺序
• 1 将被插入到位置 1 以维持顺序
• 2 也会插入位置 1，表明 2 可能与 1
• 3 将被插入到位置 2 表明 3 可能与 2 在同一簇中/li>
• 等等

我们注意到，只有当一个元素较少的增量插入到其当前位置时，我们才会考虑开始一个新的集群。

我们对右侧再次执行此操作，但有所不同。不同之处在于，默认情况下，如果一堆元素相同，np.searchsorted 假定插入到值的前面。为了识别簇的末端，我想在相同的元素之后插入。因此，我将使用参数 side='right'

If ‘left’, the index of the first suitable location found is given. If ‘right’, return the last such index. If there is no suitable index, return either 0 or N (where N is the length of a).

现在是逻辑。一个集群只有在前一个集群结束时才能开始，第一个集群除外。然后，我们将考虑第二个 np.searchsorted

结果的移位版本

---

现在让我们定义我们的函数

def delta_cluster(a, dleft, dright):
    # use to track whether searchsorted results are at correct positions
    rng = np.arange(len(a))

    edge_left = a.searchsorted(a - dleft)
    starts = edge_left == rng

    # we append 0 to shift
    edge_right = np.append(0, a.searchsorted(a + dright, side='right')[:-1])
    ends = edge_right == rng

    return (starts & ends).cumsum()

---

示范

左，右增量等于 1 和 1

print(delta_cluster(a, 1, 1))

[1 2 2 2 2 3 3 3 4 5 5 5]

左，右增量等于 2 和 1

print(delta_cluster(a, 2, 1))

[1 1 1 1 1 2 2 2 3 4 4 4]

额外学分
如果 a 没有排序怎么办？
我将利用从 this post 中学到的信息

def delta_cluster(a, dleft, dright):

    s = a.argsort()

    size = s.size

    if size > 1000:
        y = np.empty(s.size, dtype=np.int64)
        y[s] = np.arange(s.size)
    else:
        y = s.argsort()

    a = a[s]

    rng = np.arange(len(a))

    edge_left = a.searchsorted(a - dleft)
    starts = edge_left == rng

    edge_right = np.append(0, a.searchsorted(a + dright, side='right')[:-1])
    ends = edge_right == rng

    return (starts & ends).cumsum()[y]

示范

b = np.random.permutation(a)
print(b)

[14 10  3 11 20  0 19 20  4 11  5  2]

---

print(delta_cluster(a, 2, 1))

[1 1 1 1 1 2 2 2 3 4 4 4]

---

print(delta_cluster(b, 2, 1))

[3 2 1 2 4 1 4 4 1 2 1 1]

---

print(delta_cluster(b, 2, 1)[b.argsort()])

[1 1 1 1 1 2 2 2 3 4 4 4]