识别由左侧的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它的作用:

将索引查找到排序数组a中,如果在索引之前插入v中的相应元素,则将保留a的顺序.

我要做的是执行np.searchsorted与a使用a - delta_left.让我们来看看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
• 等等等等

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

我们再次为右侧做同样的事情.不同之处在于,默认情况下,如果一堆元素相同,则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没有排序怎么办？
我将利用从这篇文章中学到的信息

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]