考虑排序数组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]
最佳答案
我们将利用 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可能与13将被插入到位置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]
关于python - 识别由左侧的 delta 和右侧的不同 delta 链接的集群，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41464177/