Вот метрика сходства, основанная на числе инверсии.Сначала приведем несколько примеров:
['Jan' 'Feb' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec']
['Dec' 'Nov' 'Oct' 'Sep' 'Aug' 'Jul' 'Jun' 'May' 'Apr' 'Mar' 'Feb' 'Jan']
0.0
['Jan' 'Feb' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec']
['Jan' 'Feb' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec']
1.0
['May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec' 'Jan' 'Feb' 'Mar' 'Apr']
['Feb' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec' 'Jan']
0.5909090909090908
['Jan' 'Feb' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec']
['Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec' 'Jan' 'Feb' 'Mar' 'Apr' 'May' 'Jun']
0.4545454545454546
['Jan' 'Feb' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec']
['Feb' 'Jan' 'Mar' 'Apr' 'May' 'Jun' 'Jul' 'Aug' 'Sep' 'Oct' 'Nov' 'Dec']
0.9848484848484849
[10 3 2 1 4 5 0 7 9 8 11 6]
[ 2 10 1 3 4 0 11 9 7 5 8 6]
0.8333333333333334
['Nov' 'Jun' 'Dec' 'Oct' 'Feb' 'Mar' 'Jan' 'Jul' 'Sep' 'Aug' 'May' 'Apr']
['Dec' 'Nov' 'Oct' 'May' 'Jun' 'Sep' 'Jan' 'Jul' 'Mar' 'Feb' 'Aug' 'Apr']
0.7121212121212122
['Jan' 'Aug' 'May' 'Feb' 'Dec' 'Apr' 'Sep' 'Mar' 'Nov' 'Jul' 'Oct' 'Jun']
['May' 'Jun' 'Dec' 'Oct' 'Jan' 'Aug' 'Nov' 'Jul' 'Sep' 'Feb' 'Mar' 'Apr']
0.48484848484848486
['Nov' 'Oct' 'Jul' 'Feb' 'Dec' 'Sep' 'Apr' 'May' 'Mar' 'Aug' 'Jan' 'Jun']
['Apr' 'Jul' 'Dec' 'Jan' 'Aug' 'Jun' 'Feb' 'Sep' 'Nov' 'May' 'Oct' 'Mar']
0.4696969696969697
['Dec' 'Jul' 'May' 'Mar' 'Feb' 'Oct' 'Aug' 'Jun' 'Apr' 'Sep' 'Nov' 'Jan']
['Sep' 'Jan' 'Jul' 'Apr' 'Jun' 'Oct' 'May' 'Mar' 'Dec' 'Nov' 'Feb' 'Aug']
0.3787878787878788
['2033-03' '2025-07' '2013-10' '2013-02' '2018-01' '2068-07' '2054-06'
'2002-05' '2055-04' '2030-05' '2034-09' '2040-09' '2024-03' '2022-11'
'2007-07' '2034-09' '2077-11' '2026-03' '2072-12' '2070-06' '2054-12'
'2067-11' '2003-01' '2011-09' '2051-10' '2058-01' '2081-05' '2058-12'
'2000-10' '2018-09' '2060-05' '2050-05' '2015-04' '2034-12' '2017-03'
'2043-05' '2001-10' '2047-06' '2050-06' '2034-10']
['2002-05' '2051-10' '2007-07' '2018-01' '2043-05' '2050-06' '2034-12'
'2015-04' '2022-11' '2040-09' '2054-06' '2070-06' '2058-12' '2067-11'
'2077-11' '2017-03' '2050-05' '2011-09' '2072-12' '2025-07' '2013-02'
'2018-09' '2001-10' '2000-10' '2081-05' '2033-03' '2030-05' '2060-05'
'2013-10' '2026-03' '2034-09' '2034-10' '2054-12' '2003-01' '2024-03'
'2068-07' '2034-09' '2055-04' '2047-06' '2058-01']
0.4717948717948718
Количество инверсий - это минимальное количество соседних свопов, необходимое для переупорядочения одного ордера в другой.Это может быть что угодно от 0 до N (N-1) /2.
Код:
import numpy as np
def inversion_count_similarity(data1, data2):
N = len(data1)
o1 = np.argsort(data1, kind='mergesort')
o2 = np.argsort(data2, kind='mergesort')
o1inv = np.empty_like(o1)
o1inv[o1] = np.arange(N)
# pad to power of two
order = np.arange(1<<N.bit_length())
order[:N] = o2[o1inv]
sum_ = 0
for i in range(1, N.bit_length()+1):
order = np.reshape(order, (-1, 1<<i))
oo = np.argsort(order, axis = -1, kind='mergesort')
ioo = np.empty_like(oo)
ioo[np.arange(order.shape[0])[:, None], oo] = np.arange(1<<i)
order[...] = order[np.arange(order.shape[0])[:, None], oo]
hw = 1<<(i-1)
sum_ += ioo[:, :hw].sum() - order.shape[0] * (hw-1)*hw // 2
return 1 - (2*sum_)/((N-1)*N)
months = "Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec".split()
months = np.array(months)
upsidedown = months[::-1]
cycle = months[np.r_[1:12, 0]]
cycle4 = months[np.r_[4:12, :4]]
cycle6 = months[np.r_[6:12, :6]]
singleflip = months[np.r_[1, 0, 2:12]]
a = np.array([10, 3, 2, 1, 4, 5, 0, 7, 9, 8, 11, 6])
b = np.array([ 2, 10, 1, 3, 4, 0, 11, 9, 7, 5, 8, 6])
random = [[months[np.random.permutation(12)] for i in 'xx'] for j in 'xxxx']
a40 = np.random.randint(0, 1000, (40,)).view('m8[M]') + np.datetime64('2000-10')
b40 = a40[np.random.permutation(40)]
for m1, m2 in [(months, upsidedown), (months, months), (cycle4, cycle),
(months, cycle6), (months, singleflip), (a, b)] + random + [(a40, b40)]:
print(m1)
print(m2)
print(inversion_count_similarity(m1, m2))
print()
Попытка объяснения.
Сначала мы вычисляем относительный порядокпутем аргументирования обоих, а затем составления одной из результирующих перестановок с инверсией другой.Это дополняется степенью двойки, чтобы упростить реализацию следующего биссектрисового алгоритма.
Альтернативное эквивалентное определение числа инверсии приведенному выше является суммой по всем элементам числа меньших элементов, которыепомещенный над ним.
Используя это определение, мы можем рассмотреть специальный случай последовательности, которая разбивается на две отсортированные половины.Мы также предполагаем, что элементы - это просто индексы, то есть первые n чисел (вот почему нам нужно ioo в коде; ioo - обратная перестановка порядка сортировки oo, то есть расположение первых n чисел, которые необходимо переставитьпо oo сортироваться).Если бы он был полностью упорядочен, то элементы в левой половине были бы просто 0, 1, ... и суммировались бы в (n / 2) (n / 2-1) / 2.Нетрудно убедиться, что если вместо элемента i в позиции i у нас i + d в позиции i, то над ним должно быть d меньших элементов (потому что точно i + d меньших чисел и i из них слева, потому чтомы предположили, что половина была отсортирована).Таким образом, мы можем взять сумму по элементам в левой половине и вычесть (n / 2) (n / 2-1) / 2, чтобы получить число инверсии в этом особом случае.
Также легко проверитьчто, начиная с общего случая несортированных половин, числа инверсии каждой половины плюс номер инверсии всей последовательности после сортировки каждой половины суммы по полному числу инверсии.(Это снова легко увидеть, используя альтернативное определение числа инверсии.)
На основании этих наблюдений в коде реализована простая схема деления пополам.начиная с маленьких кусочков, сортируя их, а затем группируя их по два за один раз и снова сортируя, полностью отслеживая затраченные инверсии.
Обратите внимание, что сортировка двух отсортированных половинок фактически является O (n).Мы могли бы использовать heapq.merge для реализации O (n).На практике, однако, argsort почти наверняка будет быстрее, даже если это O (n log n).