遍历一维 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

我们不知道先验需要多少 "hops" 才能找到聚类中心。所以我们必须进行一些迭代并检查我们是否已经落在集群中心：

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 是跳到同一个集群的一系列索引价值。 循环的一个不变量是 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])。

有趣的是，"simple example" np.arange(-1, 10) 也是最坏的情况长度为 11 的数组所需的最大迭代次数的场景。由于聚类值的数量增长为 2**n，因此循环最多需要 log2(len(a)) 次迭代。因此，我们可以编写一个函数来 return 簇值，或者在 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

遍历一维 Numpy 数组进行聚类

Traversing a 1D Numpy Array for Clustering

python

arrays

numpy

traversal