python - 遍历一维 Numpy 数组进行聚类

Question

我有一个一维 numpy 数组，其中每个元素的值 i 指向数组中的另一个索引。每个聚类中心都有一个唯一的负(整数)值。目标是将每个元素分配给一个集群。

例子

# Generated/pre-computed elsewhere
a = np.array([6, 8, 1, -1, 0, 3, -2, 4, -3, 10, 5])

因此，聚类中心是元素 3、6 和 8(因为它们具有负值)，它们分别标记为聚类 -1、-2 和 -3。所以，由于

a[0] = 6 --> a[6] = -2, 

那么a[0]可以被赋值为-2。同样，由于

a[5] = 3 --> a[3] = -1,

那么a[5]可以被赋值为-1。按照这个逻辑，所有元素都可以分配给一个聚类中心。结果数组将是:

[-2, -3, -3, -1, -2, -1, -2, -2, -3, -1, -1]

我知道如何在纸上实现这一点，但我不知道如何在代码中或在 numpy 中使用矢量化代码来实现这一点。

更新:根据下面 unutbu 的回答，我用 for 循环替换了 while 循环以避免无休止的 while 循环:

a = np.array([6, 8, 1, -1, 0, 3, -2, 4, -3, 10, 5])
for i in range(len(a)):
    mask = a >= 0
    if not mask.any(): break
    a[mask] = a[a[mask]]

Answer 1

我们先验不知道找到聚类中心需要多少“跃点”。所以我们必须进行一些迭代并检查我们是否已经落在聚类中心:

import numpy as np
a = np.array([6, 8, 1, -1, 0, 3, -2, 4, -3, 10, 5])

for i in a:
    mask = a>=0
    # We can stop when all the values in `a` are negative
    if not mask.any(): break
    # perform a hop
    a[mask] = a[a[mask]]

print(a)

产量

[-2 -3 -3 -1 -2 -1 -2 -2 -3 -1 -1]

---

要了解发生了什么，查看 a 的更简单值可能会更清楚:

a = np.arange(-1, 10)
print(a)
for i in a:
    mask = a>=0
    # We can stop when all the values in `a` are negative
    if not mask.any(): break
    # perform a hop
    a[mask] = a[a[mask]]
    print(a)

打印

[-1  0  1  2  3  4  5  6  7  8  9]
[-1 -1  0  1  2  3  4  5  6  7  8]
[-1 -1 -1 -1  0  1  2  3  4  5  6]
[-1 -1 -1 -1 -1 -1 -1 -1  0  1  2]
[-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]

在这里我们可以清楚地看到每个索引处的值(即输出)正在减少。您可能期望值减少 1，但是事实上，由于前一跳的影响。

更一般地，让 G 是跳到同一个集群的一系列索引值(value)。 循环的一个不变量是 G 中的值映射到 G 中的值。此外，在每个索引处，每次迭代的距离(即跳数)到聚类值减少(或为零)。 Banach fixed point theorem 这两个事实共同暗示那算法收敛于一个不动点。

还有每次迭代中用聚类值填充的位置数成倍增长。如果在一次迭代之前有 n 个位置填充了聚类值，那么在一个跃点之后将有 2n 个位置填充了聚类值。所以收敛是指数级的。

---

在 OP 的指导下，我将 while True 循环更改为 for-loop。不动点将在少于 len(a) 的步骤中找到，但是 for i in a 就足够了。

请注意，上面的代码假设每个索引都收敛到一个聚类值。如果这不是真的，那么原始的 while True 循环可能会永远循环下去。 for i in a 将结束，但可能根本不是所有簇值。 a = np.array([1,0]) 是说明该问题的一个简单示例。

---

有趣的是，“简单示例”np.arange(-1, 10) 也是最坏情况长度为 11 的数组所需的最大迭代次数的场景。由于聚类值的数量增长为 2**n，因此循环最多需要 log2(len(a)) 次迭代。因此，我们可以编写一个函数，当 a 包含无限循环时返回簇值或引发 ValueError:

def converge(a):
    for i in range(int(np.log2(len(a)))+1):
        mask = a>=0
        # We can stop when all the values in `a` are negative
        if not mask.any(): break
        # perform a hop
        a[mask] = a[a[mask]]
    else:
        # for-loop completed without reaching break
        mask = a>=0
        if mask.any(): 
            raise ValueError('{!r} contains infinite cycles'.format(a))
    return a