识别左侧由 delta 链接的簇，右侧由不同 delta 链接的簇

考虑排序后的数组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

NOTE:尽管有间隔[-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

NOTE:尽管有间隔[9, 12]与 共享优势[12, 15]，两个区间都不包含相邻点，因此不构成连接它们各自的簇。

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

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

我们将利用np.searchsorted https://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html和寻找簇边缘的逻辑。

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

查找排序数组 a 中的索引，这样，如果 v 中的相应元素插入到索引之前，则 a 的顺序将被保留。

我要做的是执行np.searchsorted with a using a - delta_left。 Let's look at that fordelta_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
• 等等等等

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

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

如果“left”，则给出找到的第一个合适位置的索引。如果“正确”，则返回最后一个此类索引。如果没有合适的索引，则返回 0 或 N（其中 N 是 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没有排序吗？
我将利用从中学到的信息这个帖子 https://stackoverflow.com/q/41394595/2336654

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]