Как вы можете сравнить, в какой степени два списка находятся в одном порядке?

Question

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

Метод, который я попробовал, не сработал. это было так:

Для каждого списка я построил матрицу, которая записывала для каждой пары элементов, были ли они выше или ниже друг друга в списке. Затем я вычислил коэффициент корреляции Пирсона для этих двух матриц. Это сработало крайне плохо. Вот тривиальный пример:

list 1:
1
2
3
4

list 2:
1
3
2
4

Метод, который я описал выше, производил матрицы, подобные этой (где 1 означает, что номер строки больше, чем столбец, а 0 наоборот):

list 1:
  1 2 3 4
1   1 1 1
2     1 1
3       1
4

list 2:
  1 2 3 4 
1   1 1 1
2     0 1 
3       1
4

Поскольку единственным отличием является порядок элементов 2 и 3, их следует считать очень похожими. Коэффициент корреляции Пирсона для этих двух матриц равен 0, что позволяет предположить, что они вообще не коррелированы. Я предполагаю, что проблема в том, что я ищу не коэффициент корреляции, а какой-то другой вид меры сходства. Редактировать расстояние, возможно?

Кто-нибудь может предложить что-нибудь лучше?

Answer 1

Среднеквадратичные различия показателей каждого элемента.

List 1: A B C D E
List 2: A D C B E

Индексы каждого элемента Списка 1 в Списке 2 (с нуля)

A B C D E
0 3 2 1 4

Индексы каждого элемента Списка 1 в Списке 1 (с нуля)

A B C D E
0 1 2 3 4

Различия:

A  B C D E
0 -2 0 2 0

Площадь различий:

A B C D E
  4   4

Средняя разница = 8 / 5.

Answer 2

Просто идея, но есть ли смысл в адаптации стандартного алгоритма сортировки для подсчета количества операций подкачки, необходимых для преобразования list1 в list2?

Я думаю, что определение функции сравнения может быть трудным, хотя (возможно, даже столь же сложным, как исходная проблема!), И это может быть неэффективным.

edit: если подумать немного об этом, функция сравнения будет определяться самим целевым списком. Так, например, если список 2:

1 4 6 5 3

... тогда функция сравнения должна привести к 1 <4 <6 <5 <3 (и вернуть равенство, если записи равны). </p>

Тогда нужно просто расширить функцию подкачки для подсчета операций подкачки.

Answer 3

Немного опоздал на вечеринку здесь, но для записи, я думаю, что у Бена почти было это ... если бы вы заглянули дальше в коэффициенты корреляции, я думаю, вы бы нашли, что ранг корреляции Спирмена коэффициент , возможно, был путь.

Интересно, что Джамеш, похоже, вывел аналогичную меру, но не нормализовал.

См. недавний SO-ответ .

Answer 4

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

См .: http://en.wikipedia.org/wiki/Levenshtein_distance

Хотя я не думаю, что l-расстояние учитывает вращение. Если вы разрешите вращение как операцию, то:

1, 2, 3, 4

и

2, 3, 4, 1

Очень похожи.

Answer 5

Если у вас два порядка, нужно взглянуть на два важных коэффициента корреляции ранжирования:

1. Коэффициент ранговой корреляции Спирмена: https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient Это почти так же, как ответ Jamesh, но масштабируется в диапазоне от -1 до 1. Он определяется как:
   1 - (6 * sum_of_squared_distances) / (n_samples * (n_samples ** 2 - 1)

2. Кендаллс тау: https://nl.wikipedia.org/wiki/Kendalls_tau

При использовании Python можно использовать:

 from scipy import stats

 order1 = [ 1, 2, 3, 4]
 order2 = [ 1, 3, 2, 4]
 print stats.spearmanr(order1, order2)[0]
 >> 0.8000
 print stats.kendalltau(order1, order2)[0]
 >> 0.6667

Answer 6

Другой подход, основанный на немного математики , заключается в подсчете количества инверсий для преобразования одного из массивов в другой. инверсия - это обмен двух соседних элементов массива. В рубине это делается так:

# extend class array by new method
class Array
  def dist(other)
    raise 'can calculate distance only to array with same length' if length != other.length
    # initialize count of inversions to 0
    count = 0
    # loop over all pairs of indices i, j with i<j
    length.times do |i|
      (i+1).upto(length) do |j|
        # increase count if i-th and j-th element have different order
        count += 1 if (self[i] <=> self[j]) != (other[i] <=> other[j])
      end
    end
    return count
  end
end
l1 = [1, 2, 3, 4]
l2 = [1, 3, 2, 4]
# try an example (prints 1)
puts l1.dist(l2)

Расстояние между двумя массивами длины n может быть между 0 (они одинаковы) и n * (n + 1) / 2 (при обращении первого массива один получает второй). Если вы предпочитаете иметь расстояния всегда между 0 и 1, чтобы иметь возможность сравнивать расстояния между парами массивов разной длины, просто разделите на n * (n + 1) /2.

Недостатком этого алгоритма является время выполнения n ^ 2. Также предполагается, что массивы не имеют двойных записей, но это можно адаптировать.

Замечание по поводу строки кода "count + = 1 if ...": счет увеличивается только в том случае, если i-й элемент первого списка на меньше , чем его j-й элемент и i-й элемент второго списка на больше , чем его j-й элемент, или наоборот (это означает, что i-й элемент первого списка больше, чем его j-й элемент и i -й элемент второго списка меньше его j-го элемента). Вкратце: (l1 [i] l2 [j]) или (l1 [i]> l1 [j] и l2 [i]

Answer 7

Я не уверен, какую именно формулу он использует под капотом, но difflib.SequenceMatcher.ratio() делает именно это:

ratio(self) method of difflib.SequenceMatcher instance:
    Return a measure of the sequences' similarity (float in [0,1]).

Пример кода:

from difflib import SequenceMatcher
sm = SequenceMatcher(None, '1234', '1324')
print sm.ratio()

>>> 0.75

Answer 8

Существует алгоритм ветвей и границ, который должен работать для любого набора операторов, который вам нравится. Это может быть не очень быстро. Псевдокод выглядит примерно так:

bool bounded_recursive_compare_routine(int* a, int* b, int level, int bound){
    if (level > bound) return false;
    // if at end of a and b, return true
    // apply rule 0, like no-change
    if (*a == *b){
        bounded_recursive_compare_routine(a+1, b+1, level+0, bound);
        // if it returns true, return true;
    }
    // if can apply rule 1, like rotation, to b, try that and recur
    bounded_recursive_compare_routine(a+1, b+1, level+cost_of_rotation, bound);
    // if it returns true, return true;
    ...
    return false;
}

int get_minimum_cost(int* a, int* b){
    int bound;
    for (bound=0; ; bound++){
        if (bounded_recursive_compare_routine(a, b, 0, bound)) break;
    }
    return bound;
}

Время, которое требуется, примерно равно экспоненциально в ответе, потому что в нем доминирует последняя сработавшая оценка.

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