Быстрый алгоритм сравнения массива без обмена данными

Question

У меня есть два массива, созданных двумя разными системами, которые независимы друг от друга. Я хочу сравнить их сходства, сравнивая только несколько чисел, генерируемых из массивов.

Прямо сейчас, я только сравниваю min, max и суммы массивов, но мне было интересно, есть ли там лучший алгоритм? Любой тип алгоритма хэширования должен быть нечувствительным к малым разностям с плавающей запятой между массивами.

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

Answer 1

Я бы не попытался уменьшить это до одного числа; просто передайте значения tuple и напишите функцию close_enough, которая сравнивает кортежи.

Например, вы можете использовать (mean, stdev) как свое значение, а затем определить close_enough как «среднее значение для каждого массива находится в пределах 0.25 stdev от среднего значения другого массива».

def mean_stdev(a): 
    return mean(a), stdev(a) 

def close_enough(mean_stdev_a, mean_stdev_b): 
    mean_a, stdev_a = mean_stdev_a 
    mean_b, stdev_b = mean_stdev_b 
    diff = abs(mean_a - mean_b) 
    return (diff < 0.25 * stdev_a and diff < 0.25 * stdev_b) 

Очевидно, что правильное значение - это то, что вы хотите настроить на основе вашего прецедента. И, может быть, вы на самом деле хотите его обосновать, например, дисперсию (квадрат stdev), или дисперсию и перекос, или stdev и sqrt (перекос), или некоторую совершенно другую нормализацию, помимо среднего арифметического. Все зависит от того, что представляют ваши цифры, и что означает «достаточно близко».

Не зная ничего о вашей области применения, трудно дать что-то более конкретное. Например, если вы сравниваете звуковые отпечатки пальцев (или отпечатки пальцев ДНК или отпечатки пальцев), вам нужно что-то очень отличное от того, сравниваете ли вы JPEG-сжатые изображения ландшафтов.

---

В своем комментарии вы говорите, что хотите быть чувствительными к порядку значений. Чтобы справиться с этим, вы можете генерировать некоторую меру, как «вне порядка» последовательность. Например:

diffs = [elem[0] - elem[1] for elem in zip(seq, sorted(seq))] 

Это дает вам разницу между каждым элементом и элементом, который будет находиться в отсортированном положении. Вы можете построить из этого stdev-подобную меру (квадрат каждого значения, среднее значение, sqrt) или принять средний абсолютный разброс и т. Д.

Или вы можете сравнить, как далеко от фактического индекса от «правого», индекс. Или как далеко это значение от ожидаемого значения по его индексу на основе среднего и stdev. Или ... есть бесчисленные возможности. Опять же, это зависит в значительной степени от вашей области применения.

Answer 2

В зависимости от вашего определения «сравните их сходства».

Какие качества вы хотите сравнить? Какие функции вы можете определить? - их идентифицируемые образцы? т. е. в этом наборе имеется 6 критических точек, есть 2 разрыва ... и т. д.

Вы уже упомянули сравнение min/max/sum; и средства и стандартные отклонения обсуждались и в комментариях. Это все функции набора.

В конечном итоге вы сможете использовать все эти функции и создать n-мерный дескриптор. Например, [min, max, mean, std и т. Д. ...]

Затем вы можете сравнить эти n-мерные дескрипторы, чтобы определить, является ли это «меньше», «равно» или «больше», чем другое. Если вы хотите классифицировать другие наборы в том, являются ли они больше похожими на «set A» или больше похожими на «set B», вы можете посмотреть на классификаторы.

См:

Classifying High-Dimensional Patterns Using a Fuzzy Logic

Support Vector Machines