Ранжируйте элементы в массиве с помощью Python / NumPy без двойной сортировки массива

103

У меня есть массив чисел, и я хотел бы создать еще один массив, представляющий ранг каждого элемента в первом массиве. Я использую Python и NumPy.

Например:

array = [4,2,7,1]
ranks = [2,1,3,0]

Вот лучший метод, который я придумал:

array = numpy.array([4,2,7,1])
temp = array.argsort()
ranks = numpy.arange(len(array))[temp.argsort()]

Есть ли более эффективные / более быстрые методы, позволяющие избежать двойной сортировки массива?

Джошайерс
источник
6
Ваша последняя строка эквивалентна ranks = temp.argsort().
Sven Marnach

Ответы:

68

Используйте нарезку слева на последнем шаге:

array = numpy.array([4,2,7,1])
temp = array.argsort()
ranks = numpy.empty_like(temp)
ranks[temp] = numpy.arange(len(array))

Это позволяет избежать двойной сортировки, инвертируя перестановку на последнем шаге.

Свен Марнах
источник
3
Отлично спасибо! Я знал, что решение есть, и когда я его увижу, оно станет очевидным. Я провел некоторое тестирование с timeit, и этот метод немного медленнее для небольших массивов. На моей машине они равны, когда в массиве 2000 элементов. При 20 000 элементов ваш метод примерно на 25% быстрее.
joshayers
какие-либо рекомендации о том, как это сделать по строкам?
Xaser
Если яркость больше 1, см. Ответ ниже.
mathtick
101

Используйте argsort дважды, сначала для получения порядка массива, а затем для получения ранжирования:

array = numpy.array([4,2,7,1])
order = array.argsort()
ranks = order.argsort()

При работе с двумерными (или более крупными) массивами не забудьте передать аргумент оси в argsort, чтобы упорядочить по правильной оси.

k.rooijers
источник
2
Обратите внимание, что если числа повторяются во входном массиве (например [4,2,7,1,1]), выходные данные будут ранжировать эти числа на основе их позиции в массиве ( [3,2,4,0,1])
rcoup
4
Сортировка дважды неэффективна. Ответ @Sven Marnach показывает, как достичь ранжирования с помощью одного вызова argsort.
Warren Weckesser
6
@WarrenWeckesser: я только что проверил разницу между ними, и вы правы для больших массивов, но для всех меньших (n <100) двойной argsort быстрее (примерно на 20% быстрее для n = 100 и примерно в 5 раз быстрее для n = 10). Так что, если вам нужно много ранжировать по множеству небольших наборов значений, этот метод намного лучше.
naught101
3
@WarrenWeckesser: На самом деле, я ошибаюсь, этот метод явно лучше. Оба метода намного быстрее, чем метод scipy.stats. Результаты: gist.github.com/naught101/14042d91a2d0f18a6ae4
naught101
1
@ naught101: В вашем скрипте есть ошибка. Строка array = np.random.rand(10)должна быть array = np.random.rand(n).
Уоррен Векессер,
89

Этому вопросу несколько лет, и принятый ответ отличный, но я думаю, что следующее все же стоит упомянуть. Если вы не против зависимости от scipy, вы можете использовать scipy.stats.rankdata:

In [22]: from scipy.stats import rankdata

In [23]: a = [4, 2, 7, 1]

In [24]: rankdata(a)
Out[24]: array([ 3.,  2.,  4.,  1.])

In [25]: (rankdata(a) - 1).astype(int)
Out[25]: array([2, 1, 3, 0])

Приятной особенностью rankdataявляется то, что methodаргумент предоставляет несколько вариантов обработки связей. Например, есть три вхождения 20 и два вхождения 40 в b:

In [26]: b = [40, 20, 70, 10, 20, 50, 30, 40, 20]

По умолчанию связанным значениям присваивается средний рейтинг:

In [27]: rankdata(b)
Out[27]: array([ 6.5,  3. ,  9. ,  1. ,  3. ,  8. ,  5. ,  6.5,  3. ])

method='ordinal' присваивает последовательные ранги:

In [28]: rankdata(b, method='ordinal')
Out[28]: array([6, 2, 9, 1, 3, 8, 5, 7, 4])

method='min' присваивает минимальный ранг связанных значений всем связанным значениям:

In [29]: rankdata(b, method='min')
Out[29]: array([6, 2, 9, 1, 2, 8, 5, 6, 2])

Дополнительные параметры см. В строке документации.

Уоррен Векессер
источник
1
да, это лучший ответ там, где важны крайние случаи.
naught101
Мне кажется интересным, что, rankdataпохоже, используется тот же механизм, что и в принятом ответе, для внутренней генерации начального рейтинга.
AlexV
5

Я попытался расширить оба решения для массивов A более чем одного измерения, предполагая, что вы обрабатываете свой массив построчно (ось = 1).

Я расширил первый код циклом по строкам; возможно это можно улучшить

temp = A.argsort(axis=1)
rank = np.empty_like(temp)
rangeA = np.arange(temp.shape[1])
for iRow in xrange(temp.shape[0]): 
    rank[iRow, temp[iRow,:]] = rangeA

А второй, следуя предложению k.rooijers, становится:

temp = A.argsort(axis=1)
rank = temp.argsort(axis=1)

Я произвольно сгенерировал 400 массивов с формой (1000,100); первый код занял около 7,5, второй 3,8.

Игорь Фобия
источник
5

Векторизованную версию усредненного ранга см. Ниже. Мне нравится np.unique, он действительно расширяет рамки того, какой код можно и нельзя эффективно векторизовать. Помимо отказа от циклов for в Python, этот подход также позволяет избежать неявного двойного цикла над 'a'.

import numpy as np

a = np.array( [4,1,6,8,4,1,6])

a = np.array([4,2,7,2,1])
rank = a.argsort().argsort()

unique, inverse = np.unique(a, return_inverse = True)

unique_rank_sum = np.zeros_like(unique)
np.add.at(unique_rank_sum, inverse, rank)
unique_count = np.zeros_like(unique)
np.add.at(unique_count, inverse, 1)

unique_rank_mean = unique_rank_sum.astype(np.float) / unique_count

rank_mean = unique_rank_mean[inverse]

print rank_mean
Eelco Hoogendoorn
источник
Кстати; Я сделал этот код таким же, как и другой код усредненного ранга, но я могу представить, что минимальный ранг группы повторяющихся чисел работает так же хорошо. Это может быть получено еще проще: >>> unique, index, inverse = np.unique (a, True, True) >>> rank_min = rank [index] [inverse]
Eelco Hoogendoorn
Я получаю следующую ошибку с вашим решением (numpy 1.7.1): AttributeError: объект 'numpy.ufunc' не имеет атрибута 'at'
Fear
Для этого требуется более свежая версия numpy; ваш довольно древний
Eelco Hoogendoorn
4

Помимо элегантности и краткости решений, существует еще вопрос производительности. Вот небольшой тест:

import numpy as np
from scipy.stats import rankdata
l = list(reversed(range(1000)))

%%timeit -n10000 -r5
x = (rankdata(l) - 1).astype(int)
>>> 128 µs ± 2.72 µs per loop (mean ± std. dev. of 5 runs, 10000 loops each)

%%timeit -n10000 -r5
a = np.array(l)
r = a.argsort().argsort()
>>> 69.1 µs ± 464 ns per loop (mean ± std. dev. of 5 runs, 10000 loops each)

%%timeit -n10000 -r5
a = np.array(l)
temp = a.argsort()
r = np.empty_like(temp)
r[temp] = np.arange(len(a))
>>> 63.7 µs ± 1.27 µs per loop (mean ± std. dev. of 5 runs, 10000 loops each)
Миша Лисовый
источник
1
Хорошая идея, но для честного сравнения вам следует использовать rankdata(l, method='ordinal') - 1.
Уоррен Векессер,
3

Дважды используйте argsort (), чтобы сделать это:

>>> array = [4,2,7,1]
>>> ranks = numpy.array(array).argsort().argsort()
>>> ranks
array([2, 1, 3, 0])
Квонг
источник
2
об этом уже упоминалось до того, как вы
изложили
2

Я пробовал описанные выше методы, но не смог, потому что у меня было много zeores. Да, даже с поплавками могут быть важны повторяющиеся элементы.

Итак, я написал модифицированное одномерное решение, добавив этап проверки связи:

def ranks (v):
    import numpy as np
    t = np.argsort(v)
    r = np.empty(len(v),int)
    r[t] = np.arange(len(v))
    for i in xrange(1, len(r)):
        if v[t[i]] <= v[t[i-1]]: r[t[i]] = r[t[i-1]]
    return r

# test it
print sorted(zip(ranks(v), v))

Я считаю, что это настолько эффективно, насколько это возможно.

h2kyeong
источник
0

Мне понравился метод k.rooijers, но, как писал rcoup, повторяющиеся числа ранжируются в соответствии с позицией массива. Для меня это было бесполезно, поэтому я изменил версию, чтобы постобработать ранги и объединить любые повторяющиеся числа в комбинированный средний ранг:

import numpy as np
a = np.array([4,2,7,2,1])
r = np.array(a.argsort().argsort(), dtype=float)
f = a==a
for i in xrange(len(a)):
   if not f[i]: continue
   s = a == a[i]
   ls = np.sum(s)
   if ls > 1:
      tr = np.sum(r[s])
      r[s] = float(tr)/ls
   f[s] = False

print r  # array([ 3. ,  1.5,  4. ,  1.5,  0. ])

Я надеюсь, что это может помочь и другим, я пытался найти другое решение, но не нашел ...

Мартин Ф. Томсен
источник
0

argsort и slice - это операции симметрии.

попробуйте дважды срезать вместо двух аргументов. поскольку срез быстрее, чем argsort

array = numpy.array([4,2,7,1])
order = array.argsort()
ranks = np.arange(array.shape[0])[order][order]
yupbank
источник
0

Более общий вариант одного из ответов:

In [140]: x = np.random.randn(10, 3)

In [141]: i = np.argsort(x, axis=0)

In [142]: ranks = np.empty_like(i)

In [143]: np.put_along_axis(ranks, i, np.repeat(np.arange(x.shape[0])[:,None], x.shape[1], axis=1), axis=0)

См. Раздел Как использовать numpy.argsort () в качестве индексов более чем в двух измерениях? обобщить на более тусклые.

математика
источник