检查并索引numpy数组中的非唯一/重复值

Question

我有一个数组traced_descIDs，其中包含对象ID，我想确定在这个数组中哪些项不是唯一的。然后，对于每个唯一的重复（小心），我需要确定与之相关联的traced_descIDs索引。

举个例子，如果我们看一下这里的traced_descIDs，我希望进行以下过程：

traced_descIDs = [1, 345, 23, 345, 90, 1]
dupIds = [1, 345]
dupInds = [[0,5],[1,3]]

我当前正在查找有超过1个条目的对象：

mentions = np.array([len(np.argwhere( traced_descIDs == i)) for i in traced_descIDs])
dupMask = (mentions > 1)

然而，由于len(traced_descIDs)大约为150,000，这需要太长时间。有没有更快的方法来实现相同的结果呢？

非常感谢任何帮助。谢谢。

- Carl M

Answer 1

尽管字典是O(n)的，但Python对象的开销有时会使使用numpy函数更加方便，这些函数使用排序且是O(n*log n)的。在您的情况下，起点将是：

a = [1, 345, 23, 345, 90, 1]
unq, unq_idx, unq_cnt = np.unique(a, return_inverse=True, return_counts=True)

如果您使用的是早于1.9版本的numpy，则最后一行应为：

unq, unq_idx = np.unique(a, return_inverse=True)
unq_cnt = np.bincount(unq_idx)

我们创建的三个数组的内容为：

>>> unq
array([  1,  23,  90, 345])
>>> unq_idx
array([0, 3, 1, 3, 2, 0])
>>> unq_cnt
array([2, 1, 1, 2])

获取重复的项：

cnt_mask = unq_cnt > 1
dup_ids = unq[cnt_mask]

>>> dup_ids
array([  1, 345])

获取索引需要一些复杂的操作，但相当直接:

cnt_idx, = np.nonzero(cnt_mask)
idx_mask = np.in1d(unq_idx, cnt_idx)
idx_idx, = np.nonzero(idx_mask)
srt_idx = np.argsort(unq_idx[idx_mask])
dup_idx = np.split(idx_idx[srt_idx], np.cumsum(unq_cnt[cnt_mask])[:-1])

>>> dup_idx
[array([0, 5]), array([1, 3])]

- Jaime

---

我对这个答案感到更加舒适，而且似乎并不比上面的字典答案花费更多时间。谢谢你的时间。 - Carl M

Answer 2

有一个叫做scipy.stats.itemfreq的函数，可以给出每个项的频率：

>>> xs = np.array([1, 345, 23, 345, 90, 1])
>>> ifreq = sp.stats.itemfreq(xs)
>>> ifreq
array([[  1,   2],
       [ 23,   1],
       [ 90,   1],
       [345,   2]])
>>> [(xs == w).nonzero()[0] for w in ifreq[ifreq[:,1] > 1, 0]]
[array([0, 5]), array([1, 3])]

- behzad.nouri

---

我之前不知道有这个函数。谢谢你提醒我。 - Carl M

Answer 3

您当前的方法是O(N**2)，使用字典可以在O(N)时间内完成：

>>> from collections import defaultdict
>>> traced_descIDs = [1, 345, 23, 345, 90, 1]
>>> d = defaultdict(list)
>>> for i, x in enumerate(traced_descIDs):
...     d[x].append(i)
...     
>>> for k, v in d.items():
...     if len(v) == 1:
...         del d[k]
...         
>>> d
defaultdict(<type 'list'>, {1: [0, 5], 345: [1, 3]})

获取元素和索引：

>>> from itertools import izip
>>> dupIds, dupInds = izip(*d.iteritems())
>>> dupIds, dupInds
((1, 345), ([0, 5], [1, 3]))

请注意，如果您希望保留dupIds中项目的顺序，则可以使用collections.OrderedDict和dict.setdefault()方法。

- Ashwini Chaudhary

---

个人而言，我更喜欢numpy的解决方案，但如果你想这样做，标准库也可以满足你的需求：从collections中导入Counter。 - Eelco Hoogendoorn

你能详细说明一下，如果不使用OrderedDict会导致哪些内容无法被保留吗？ - Carl M

请注意，这个解决方案会创建大量的Python对象，因此内存使用量会急剧增加；所以如果你处理的是大型数据集，最好还是保持在NumPy内部。 - Eelco Hoogendoorn

@CarlM 这里的输出本来可能是 [345, 1], 因为字典没有顺序。使用 OrderedDict 将确保输出为 [1, 345]。 - Ashwini Chaudhary

Answer 4

td = np.array(traced_descIDs)
si = np.argsort(td)
td[si][np.append(False, np.diff(td[si]) == 0)]

这将为您提供：

array([  1, 345])

我还没有完全想清楚第二部分，但也许这已经足够激发你的灵感了，或者我会回来继续思考。:)

- John Zwinck

Answer 5

Jaime提出的同样具有向量化效率的解决方案已经嵌入到numpy_indexed包中（免责声明：我是它的作者）：

import numpy_indexed as npi
print(npi.group_by(traced_descIDs, np.arange(len(traced_descIDs))))

这让我们完成了大部分工作；但是如果我们还想过滤掉单例组，同时避免任何Python循环并完全向量化，我们可以降低一些级别，做到：

g = npi.group_by(traced_descIDs)
unique = g.unique
idx = g.split_array_as_list(np.arange(len(traced_descIDs)))
duplicates = unique[g.count>1]
idx_duplicates = np.asarray(idx)[g.count>1]
print(duplicates, idx_duplicates)

- Eelco Hoogendoorn

Answer 6

np.unqiue 用于 Ndims

我有一个类似的问题，需要在 ndArray 中找出重复的行。

x = np.arange(60).reshape(5,4,3)
x[1] = x[0]

在轴0中，0和1应该是重复的。我使用了np.unique并返回了所有选项。然后使用Jaime的方法来定位重复项。

_,i,_,c = np.unique(x,1,1,1,axis=0)
x_dup = x[i[1<c]]

我为了清晰起见不必要地使用了return_inverse。这是结果：

>>> print(x_dupilates)
[[[ 0  1  2]
  [ 3  4  5]
  [ 6  7  8]
  [ 9 10 11]]]

- A. West