Алгоритм сравнения множеств?

Question

[kot-samolet]

Как можно сравнить 2 множества что бы выяснить на сколько они похожи или различаются?

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

1-2
2-9
3-6
4-3
5-1

Предположим у нас есть 2 и более таких множеств в каждом из которых не 5 а 100 элементов. Как их сравнить и найти похожие?

Comments

[Therapyx]

А само сравнение, то как должно происходить для каждого "х" со значение "y" найти идеентичное "y" на ЛЮБОЙ точке "х" других графиков?

[kot-samolet]

Therapyx: Ну мы сравниваем множества одинакового размера, поэтому x везде одинаковые - это просто порядковый номер, от 0 до 100 например. Т.е. мы сравниваем x[0] у всех множеств, потом x[1] у мех множеств, множества у которых совпали Y у всех Х это абсолютно одинаковые, равные друг другу множества. А если x[0] != x[0] в другом множестве то надо куда-то записать величину разности, т.к. например x[0] = 599 и x[0] = 600 очень похожи, если макс. значение 650 а вот x[0] = 5 x[0] = 10 очень не похожи если максимальное значение всего 10. Но заранее минимальное значение Y известно это 0, а вот максимальное не известно.

[Денис Загаевский]

kot-samolet: чего? Ты вообще определение множества знаешь?

[Therapyx]

kot-samolet: ну а в чем проблема тогда просто перебирать обычным линейным поиском? Ибо тут надо же все комбинации проверять, это не бинарный поиск в сортированном массиве.
А при поиске просто задавать нужные коеффициенты разницы в %. Проблема тут в том, что тебе надо найти "все" возможные совпадения, а не остановится на одном.
График можно представить как тот же map, где ключ это время, а величина это значение, а дальше сделать (массив, вектор, эррейлист) этих map'ov итерируя друг с другом.
Или ты ищешь какие-то специфические методы или библиотеки для такой задачи?

[kot-samolet]

Денис Загаевский: неудивительно что Яндекс так деградировал в последнее время )))

[kot-samolet]

Therapyx: нет я именно ищу алгоритмы и любые методы, напишу сам, библиотеки не нужны. Меня интересует только одно: есть ли классическое решение, классический алгоритм (как например расстояние левенштейна при поиске похожих слов) а то я буду писать свой велик а потом окажется что он не оптимальный и всё уже придумано до нас (скорее всего в данном случае так и есть, т.к. задача распространённая)

[Therapyx]

kot-samolet: понимаешь, в этой ситуации прямая взаимосвязь (NxM) или по другому O(n^2), и если обычно алгоритмы можно оптимировать на какой-нибудь O(log(N)), то тут никак. Тебе нужны "ВСЕ" возможные комбинации.
Можно конечно схитрить конечно, но это опять же "предработа". Например как я уже и говорил разложить каждый х и y как пару, и отсортировать ее по value. И только тогда, когда они будут все отсортированны - то можно будет использовать например индексацию, бинарное дерево. Что конечно же сократит время поиска. Только вот поиск будет происходить не х(1) для всех х(y), а рандомно х(100), х(352), х(2).. Но такой подход все равно проверит все возможные комбинации ))
Надеюсь понятно выразился, а то сижу с полузакрытыми глазами уже.

И да, на сколько огромное кол-во данных с этих графиков?

[kot-samolet]

Therapyx: спасибо, надо попробовать, смотря для чего применять )) Есть области где немного, а есть области где в одном графике 620 элементов и таких графиков миллионы

[Therapyx]

kot-samolet: тут много нюансов может быть. Мы ж тут не видим всех данных. А эт дело такое... на словах наилучший вариант не выбрать )
То из того, что ты привел в пример, вот и первое, что пришло в голову. Но опять же. Нюансы по типу, ищутся ли сначала первые 100, а потом добавляются еще 100 и надо сравнивать их всех, или после каждого поиска они уже становятся не нужными и удаляются, или или или... И от таких факторов и будут делать выводы в пользу того или иного подхода )
Но это так, может и вправду для таких задач есть свои специальные алгоритмы. Если проблема или сама задача довольно распространенная, то навернка что-то уже более оптимально придумали ))

Answer 1

[xmoonlight]

Пусть даны значения, идущие в определённом порядке (из примера): 2,9,6,3,1
Пусть максимально возможное значение одного показателя: 9
Тогда:
Суммарный показатель одного графика: S=10^4*2+10^3*9+10^2*6+10^1*3+10^0*1
Затем, считаем такие же суммы для всех графиков и находим наименьшую разницу между всеми парами.

Comments

[kot-samolet]

Да похожее пришло мне в голову когда коммент под вопросом писал, вопроса только 3:
1) почему наоборот, не с 0 до 4, а с 4 до 0
2) это 10 в степени порядкового номера N? В чём смысл, почему не просто S = 4*2 + 3*9 ...
3) так где 10^0*1 число 0 всегда будет приводить любое значение к нулю?, надо тогда от 1 считать

[xmoonlight]

kot-samolet:
1. проверка более строгая от начала вектора к концу (вектор здесь - шкала времени)
2. 10 - это предел разряда числа (от 0 до 9 - это 10 значений). N - порядковый номер разряда.
3. X^0 =1 любое число в 0-й степени - равно 1-це. Вначале исполняется возведение в степень, затем - перемножение: 10^0*1 = 1

[Николай]

1. проверка более строгая от начала вектора к концу (вектор здесь - шкала времени) ....почему это? 1111111111111 и 911111111111111 - совершенно разные, 111111111111111 и 1111111111119 - почти идентичные. При этом очевидно что у этих сигналов должна быть одинаковая "степень подобия"

[xmoonlight]

Николай:

При этом очевидно что у этих сигналов должна быть одинаковая "степень подобия"

Очевидно, что нет, т.к. 9-ка была в разное время (в начале и в конце!), т.к. то, что мы отслеживаем - растянуто во времени.

Ну если так надо - используйте бинарный XOR и получите 1-ые биты, где есть несовпадения. Посчитаете кол-во 1-ых различающихся битов и всё.

Answer 2

[Дмитрий Дарт]

Конкретный алгоритм сильно от задачи зависит, в данном случае вам Therapyx уже подсказал. Можете так же ознакомиться:

Поиск похожих документов, но основано на матрицах
https://netpeak.net/ru/blog/algoritm-lsa-dlya-pois...

Похожие множества
https://habrahabr.ru/post/115147/

Поиск похожих изображений (алгоритм там не фонтан, но статья доступная)
https://habrahabr.ru/post/122372/

Применительно к строкам
https://habrahabr.ru/sandbox/101202/

Answer 3

[Владимир Олохтонов]

Если данных немного (а 1к списков по 100 элементов - это немного) или работа разовая, то можно просто MSE между всеми списками посчитать.
Для каждого из списков минимум MSE - самый похожий список.
Сложность O(m*n^2), где m - длина списка, n - число списков.

MSE - сумма квадратов разностей соответствующих элементов сравниваемых списков.

Answer 4

[dom1n1k]

Во-первых, звуковая волна - это не множество, а функция.
Во-вторых, в лоб звук не сравнивают. Его нужно преобразовать из амплитудного в частотный вид (гуглить по словам fast fourier transform) и сравнивать сонограммы.

Comments

[kot-samolet]

Ладно опустим звук, это просто пример, представим 2 множества это количество людей в метро в зависимости от часа суток:

7 - 200 тыс. чел.
8 - 250 тыс. чел.
9 - 180 тыс. чел.
10 - 120 тыс. чел.
11 - 100
12 - 90
13 - 110

И таких рядов у нас например 900 - по всем городам мира с метро, надо их сравнить и найти максимально похожие друг на друга

[Labunsky]

kot-samolet: капитан говорит, что это тоже функция, функция зависимости количества людей в метро от времени

[kot-samolet]

Labunsky: ок, пусть будет функция зависимости, как сравнить-то мне 900 таких штук и найти похожие? ))

[Денис Загаевский]

kot-samolet: учить матчасть.

[dom1n1k]

Можно попробовать посчитать корреляцию. Но там тоже не всё так просто, есть много нюансов.

[Николай]

Ну просто метрику взять, rss например, и считать. Если из совсем тупых и прямолинейных способов