Numpy 按元素之间的差异范围进行分组

Question

我有一个角度数组，我想将它们分组为数组，它们之间的最大差异为 2 度。

例如：输入：

angles = np.array([[1],[2],[3],[4],[4],[5],[10]])

输出

('group', 1)
[[1]
 [2]
 [3]]
('group', 2)
[[4]
 [4]
 [5]]
('group', 3)
[[10]]

numpy.diff获取下一个元素与当前元素的差异，我需要下一个元素与组中第一个元素的差异

itertools.groupby对不在可定义范围内的元素进行分组

numpy.digitize按预定义范围对元素进行分组，而不是按数组元素指定的范围。（也许我可以通过获取角度的唯一值、按差异对它们进行分组并将其用作预定义范围来使用它？）

。

我的方法有效，但似乎效率极低且非Pythonic：（我使用expand_dims和vstack，因为我正在使用一维数组（不仅仅是角度），但我已经减少了它们以简化这个问题）

angles = np.array([[1],[2],[3],[4],[4],[5],[10]])

groupedangles = []
idx1 = 0
diffAngleMax = 2

while(idx1 < len(angles)):
    angleA = angles[idx1]
    group = np.expand_dims(angleA, axis=0)
    for idx2 in xrange(idx1+1,len(angles)):
        angleB = angles[idx2]
        diffAngle = angleB - angleA
        if abs(diffAngle) <= diffAngleMax:
            group = np.vstack((group,angleB))
        else:
            idx1 = idx2
            groupedangles.append(group)
            break
    if idx2 == len(angles) - 1:
        if idx1 == idx2:
            angleA = angles[idx1]
            group = np.expand_dims(angleA, axis=0)
        groupedangles.append(group)
        break

for idx, x in enumerate(groupedangles):
    print('group', idx+1)
    print(x)

有什么更好更快的方法来做到这一点？

Answer 1

更新这是一些 Cython 处理

\n\n

In [1]: import cython\n\nIn [2]: %load_ext Cython\n\nIn [3]: %%cython\n   ...: import numpy as np\n   ...: cimport numpy as np\n   ...: def cluster(np.ndarray array, np.float64_t maxdiff):\n   ...:     cdef np.ndarray[np.float64_t, ndim=1] flat = np.sort(array.flatten())\n   ...:     cdef list breakpoints = []\n   ...:     cdef np.float64_t seed = flat[0]\n   ...:     cdef np.int64_t int = 0\n   ...:     for i in range(0, len(flat)):\n   ...:         if (flat[i] - seed) > maxdiff:\n   ...:             breakpoints.append(i)\n   ...:             seed = flat[i]\n   ...:     return np.split(array, breakpoints)\n   ...: \n

\n\n

稀疏性测试

\n\n

In [4]: angles = np.random.choice(np.arange(5000), 500).astype(np.float64)[:, None]\n\nIn [5]: %timeit cluster(angles, 2)\n422 \xc2\xb5s \xc2\xb1 12.6 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n

\n\n

重复测试

\n\n

In [6]: angles = np.random.choice(np.arange(500), 1500).astype(np.float64)[:, None]\n\nIn [7]: %timeit cluster(angles, 2)\n263 \xc2\xb5s \xc2\xb1 14.6 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n

\n\n

两项测试均显示出显着的改善。该算法现在对输入进行排序，并对排序后的数组进行一次运行，这使其稳定为 O(N*log(N))。

\n\n

预更新

\n\n

这是种子聚类的一种变体。不需要排序

\n\n

def cluster(array, maxdiff):\n    tmp = array.copy()\n    groups = []\n    while len(tmp):\n        # select seed\n        seed = tmp.min()\n        mask = (tmp - seed) <= maxdiff\n        groups.append(tmp[mask, None])\n        tmp = tmp[~mask]\n    return groups\n

\n\n

例子：

\n\n

In [27]: cluster(angles, 2)\nOut[27]: \n[array([[1],\n        [2],\n        [3]]), array([[4],\n        [4],\n        [5]]), array([[10]])]\n

\n\n

500、1000 和 1500 角度的基准：

\n\n

In [4]: angles = np.random.choice(np.arange(500), 500)[:, None]\n\nIn [5]: %timeit cluster(angles, 2)\n1.25 ms \xc2\xb1 60.3 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n\nIn [6]: angles = np.random.choice(np.arange(500), 1000)[:, None]\n\nIn [7]: %timeit cluster(angles, 2)\n1.46 ms \xc2\xb1 37 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n\nIn [8]: angles = np.random.choice(np.arange(500), 1500)[:, None]\n\nIn [9]: %timeit cluster(angles, 2)\n1.99 ms \xc2\xb1 72.5 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n

\n\n

虽然该算法在最坏情况下为 O(N^2)，在最好情况下为 O(N)，但上面的基准清楚地显示了接近线性的时间增长，因为实际运行时间取决于数据的结构：稀疏性和重复率。在大多数实际情况下，您不会遇到最坏的情况。

\n\n

一些稀疏性基准

\n\n

In [4]: angles = np.random.choice(np.arange(500), 500)[:, None]\n\nIn [5]: %timeit cluster(angles, 2)\n1.06 ms \xc2\xb1 27.9 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n\nIn [6]: angles = np.random.choice(np.arange(1000), 500)[:, None]\n\nIn [7]: %timeit cluster(angles, 2)\n1.79 ms \xc2\xb1 117 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n\nIn [8]: angles = np.random.choice(np.arange(1500), 500)[:, None]\n\nIn [9]: %timeit cluster(angles, 2)\n2.16 ms \xc2\xb1 90.3 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n\nIn [10]: angles = np.random.choice(np.arange(5000), 500)[:, None]\n\nIn [11]: %timeit cluster(angles, 2)\n3.21 ms \xc2\xb1 139 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n

\n