Ранжирование элементов в массиве с использованием Python/NumPy
У меня есть массив чисел, и я хотел бы создать еще один массив, который представляет ранг каждого элемента в первом массиве. Я использую 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()]
Есть ли лучшие / более быстрые методы, которые избегают сортировки массива дважды?
9 ответов
Используйте нарезку слева на последнем шаге:
array = numpy.array([4,2,7,1])
temp = array.argsort()
ranks = numpy.empty_like(temp)
ranks[temp] = numpy.arange(len(array))
Это позволяет избежать сортировки дважды путем инверсии перестановки на последнем шаге.
Используйте argsort дважды, сначала для получения порядка массива, затем для ранжирования:
array = numpy.array([4,2,7,1])
order = array.argsort()
ranks = order.argsort()
При работе с двумерными (или многомерными) массивами обязательно передайте аргумент оси в argsort для упорядочения по правильной оси.
Этому вопросу уже несколько лет, и принятый ответ великолепен, но я думаю, что стоит упомянуть следующее. Если вы не возражаете против зависимости от 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])
Посмотрите строку документации для большего количества вариантов.
Используйте argsort() дважды, чтобы сделать это:
>>> array = [4,2,7,1]
>>> ranks = numpy.array(array).argsort().argsort()
>>> ranks
array([2, 1, 3, 0])
Векторизованная версия усредненного ранга приведена ниже. Я люблю 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
Я попытался расширить оба решения для массивов A более чем одного измерения, предполагая, что вы обрабатываете свой массив строка за строкой (axis=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.
Помимо элегантности и краткости решений, существует также вопрос производительности. Вот небольшой тест:
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)
Я попробовал вышеупомянутые методы, но потерпел неудачу, потому что у меня было много zeores. Да, даже с поплавками дубликаты могут быть важны.
Поэтому я написал модифицированное решение 1D, добавив этап проверки связи:
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))
Я считаю, что это настолько эффективно, насколько это возможно.
Argsort и slice - операции симметрии.
попробуйте дважды срезать вместо двух аргументов. поскольку срез быстрее, чем argsort
array = numpy.array([4,2,7,1])
order = array.argsort()
ranks = np.arange(array.shape[0])[order][order]
Мне понравился метод 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. ])
Я надеюсь, что это может помочь и другим, я пытался найти другое решение, но не мог найти...
Более общий вариант одного из ответов:
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() в качестве индексов более чем в двух измерениях? обобщить на более тусклые.