时间戳

首页 > 解决方案 > Python - 比较两个 numpy 数组

metrics - Python - 比较两个 numpy 数组

问题描述

我有两个 numpy 数组：

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])

每个 numpy 数组对应于一年中月份的排名。因此，在a阵列上，第 10 个月（11 月）是最好的。第二好的月份对应于第 3 个月（4 月），依此类推。

我的目标是比较排名b和排名a，考虑到每个月在每个排名中的位置。是否有任何指标可以帮助我解决这个问题（如果可能的话，某种介于 0 和 1 之间的标准化分数可以量化这两个排名的接近程度）？

标签： metrics

解决方案

这是基于反转数的相似性度量。先举几个例子：

['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()

尝试解释。

我们首先通过对两者进行 argsorting 来计算相对顺序，然后将结果排列中的一个与另一个排列的倒数组合起来。将其填充为 2 的幂，以使以下二等分算法更易于实现。

反转数的另一种等效定义与上面给出的定义是放在它上面的较小元素的数量的所有元素的总和。

使用这个定义，我们可以查看一个序列的特殊情况，该序列分为两个已排序的部分。我们还假设元素只是索引，即前 n 个数字（这就是我们在代码中需要 ioo 的原因；ioo 是排序顺序 oo 的逆排列，即需要置换的前 n 个数字的排列按 oo 进行排序）。如果它是完全有序的，那么左半部分的元素将只是 0, 1, ... 并且总和为 (n/2)(n/2-1)/2。很容易验证，如果不是位置 i 处的元素 i，而是位置 i 处的 i+d，它上面必须有 d 个更小的元素（因为正好有 i+d 个更小的数字，其中 i 个在左边，因为我们假设一半已排序）。

也很容易验证从未排序的一半的一般情况开始，每一半的反转数加上排序后的整个序列的反转数总和为完整的反转数。（使用反转数的替代定义也很容易看到这一点。）

基于这些观察，代码实现了一个简单的二等分方案。从小块开始，对它们进行排序，然后一次将它们分组并再次排序，一直跟踪所花费的反转。

请注意，对两个已排序的一半进行排序实际上是 O(n)。我们可以heapq.merge用于 O(n) 实现。然而，在实践中，argsort几乎肯定会更快，即使它是 O(n log n)。

推荐阅读