"Метрика" на вещественных массивах

[zcorvid]

Добрый день.

Пытаюсь решить следующую задачу. Нужно определить степень похожести двух массивов $A$ и $B$, причём меряется это похожесть довольно хитро (из-за специфики их происхождения — массивы берутся из реальных данных, измеряемых приборами).

Оба массива являются массивами расстояний до целей, в идеальных условиях они должны были бы попросту совпасть поэлементно (может только отличаться порядок следования чисел). Но получены они разным способом, каждый из которых имеет тенденцию к ошибкам, которые нужно попытаться обнаружить путём сравнения массивов.

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

Массив $B$ может иметь ошибку другого рода. В нём может появиться большое количество фиктивных целей, которые появились как шум (то есть помимо записей, соответствующих реальным целям, массив $B$ содержит также данные, которые в общем-то можно считать случайными). При этом массив $B$ не может содержать две записи об одной и той же цели (шумовые записи тоже не могут совпасть с каким-то "полезным" сигналом, так как $B$ это на самом деле данные от радара, и если он увидит две записи с одинаковыми значениями дальности, он их просто запишет как одну запись).

Таким образом, массив $B$ должен быть признан близким к массиву $A$, если $A$ можно преобразовать в $B$ посредством сопоставления некоторым записям массива $B$ набора записей из массива $A$, причём одна запись из $A$ не может быть приписана к двум различным записям из $B$, также нужно учесть возможность погрешности измерения, то есть если некоторая запись из $A$ приписывается некоторой записи из $B$, то разница соответствующих чисел (расстояний) должна быть мала (на самом деле тут имеет смысл брать квадрат этой разницы и суммировать его к невязке, которая и будет мерой отклонения массивов).

Сейчас эту задачу я решаю дурацким образом. Просто сортирую оба массива по возрастанию, затем считаю расстояние Левенштейна от $B$ до $A$, задав цены операций так: вставка — нуль, удаление — бесконечность, замена — квадрат разности чисел (то есть разрешено неограниченное число вставок — решает проблему шума, запрещены удаления — каждая запись получит соответствие, цена замены просто некоторая весовая функция, можно в принципе и другую было взять, это уже не важно). Такой подход не решает последнюю проблему — одному объекту может соответствовать несколько записей из $A$ (при указанном подходе каждому числу из $A$ будет сопоставлено число из $B$, причём разным элементам сопоставляются разные элементы). Если реальные данные будут иметь такую коллизию, то мы получим огромную невязку, хотя в действительности массивы очень похожи (просто некоторые элементы продублированы). Например если таким образом посчитать разницу между массивами $\{1, 2, 3, 4, 5\}$ и $\{3, 1000002, 1000003, 1000004, 1000005\}$, то невязку будет огромная, так как они будут сопоставлены как $1 \mapsto 1, 2 \mapsto 2, 3 \mapsto 3, 4 \mapsto 4, 5 \mapsto 5$ (по индексам), в действительности же видно, что скорее всего набор чисел $\{1, 2, 3, 4, 5\}$ это всё число $3$, измеренное с погрешностью.

Подскажите, пожалуйста, как можно попытаться устранить этот недостаток?

У меня есть идея — выполнить предобработку массива $A$, попытавшись предсказать группы записей, относящиеся к одной цели, и затем склеить их, заменив, скажем, средним значением, но тут можно по-разному делать, наивный способ — ввести порог $\varepsilon$, и если в отсортированном массиве соседние элементы отстоят не более чем на $\varepsilon$, то записываем их в одну группу, но тогда в одной группе могут оказаться элементы с очень большим разбросом, при этом нельзя разумно ограничить разброс, так как тогда при равномерно распределённых данных мы можем распределить элементы совсем неправильно, например пусть массив представляет собой последовательность $1, 2, 3, 4, 5, 6, \dots$, тогда при максимально допустимом разбросе равном $1.5$ допустимы разбиения $\{1, 2\}, \{3, 4\}, \dots$ и $\{1\}, \{2, 3\}, \{4, 5\}, \dots$ , причём оба они могут быть реальными, но нет никакого способа предпочесть одно разбиение другому.

Другой способ выполнить разбиение основан на анализе массива $A$ с помощью данных из массива $B$. Сортируем $B$, затем наносим точки массива $B$ на числовую прямую и применяем к $A$ правило ближайшего соседа — каждую точку $A$ относим к той записи из $B$, к которой она наиболее близка. Такой подход мне кажется намного корректнее, но я пока не уверен в его правильности.

Ещё можно пытаться считать расстояние Левенштейна, но ввести дополнительную операцию — клонирование элемента массива $B$, приписав ей цену нуль. Но этот подход я пока не очень хорошо продумал.

Может есть какие-то ещё разумные способы найти степень различия массивов?

Возможно эта задача относится больше к анализу данных, а не к программированию. Если тут как-то могут сработать методы машинного обучения, это тоже будет очень хорошо — в там, где эта задача будет применяться, есть возможность накапливать статистику таких массивов, а значит можно как-то со временем уточнять какие-нибудь параметры метода...

PS. В тексте я упомянул радар, скорее всего кто-то это заметит, и скажет, что радар обычно даёт помимо дистанции до цели ещё и её скорость. Это правда, в моих данных скорость также присутствует, то есть в действительности массив $B$ представляет собой множество пар расстояние-скорость, но во-первых для массива $A$ скорость установить весьма проблематично, а во-вторых, если бы она и была, то задача просто повысила бы размерность с $1$ до $2$, и скорее всего метод обработки был бы аналогичным (просто мерить расстояние между точками на плоскости, а не на прямой, или же ещё проще — сначала выполнить обработку по расстояниям, затем для групп одинаковых расстояний сделать обработку по скоростям, это кстати по-моему соответствует какой-то метрике на плоскости, что-нибудь типа $|x_1 - x_2| + k \cdot |y_1 - y_2|$ при достаточно большом $k$, учитываем тот факт, что для реальных данных значения координат $x, y$ ограничены сверху, и поэтому нам реально нужна метрика не на всей плоскости, а лишь на ограниченной её области, для которой достаточно большое $k$ в указанной выше формуле вполне сгодится).

-- 31.05.2016, 14:27 --

Цитата:

Программирование

Обсуждение вопросов, связанных с программированием на языках общего назначения, таких как C/C++, Pascal/Delphi, Java, C#, Perl, Python и т.д. Обсуждение алгоритмов без привязки к языку программирования ведется НЕ ЗДЕСЬ, а в корне раздела Computer Science

Прошу модераторов переместить тему в корень раздела Computer Science, тема относится к алгоритмике (и скорее даже к анализу данных), а не к языкам программирования. Извините за оплошность.

[Karan]

Тема перемещена из форума «Программирование» в форум «Computer Science»

[slavav]

Я не специалист, но думаю что вам нужны кластеры (https://ru.wikipedia.org/wiki/%D0%9A%D0 ... 0%B8%D0%B7).

1. Смешайте массивы, выделите кластеры. Проанализируйте каждый кластер. В хорошем кластере должны быть элементы из обоих массивов, кластер не должен быть слишком велик. Плохие кластеры задают меру непохожести двух массивов.

2. Выделите кластеры до смешивания. Смешайте массивы кластеров и кластеризуйте ещё раз. Снова выделите плохие кластеры.

[Евгений Машеров]

Примитивный, но, возможно, могущий сработать подход.
Раз массивы уже отсортированы - идём по ним параллельно. Для каждого элемента В находим все элементы А, которые ближе к нему, чем к соседним элементам В. Если таковых нет - считаем элемент В фиктивной целью, если несколько - находим средние значения по всем таким элементам А и отклонение среднего от элемента В. Ну и сумма квадратов отклонений (или средний квадрат, скорее)

[NO.]

Сначала провести кластеризацию. Не до уровня уникальных экзепляров, где нет дублей, а до обобщений. То есть выделить группы точек. Потом отождествлять объекты внутри кластеров, а из разных кластеров даже не пытаться. Это порежет пространство по самым выразительным участкам. Далее можно предположить, что внутри класса объекты расположены на равных расстояниях, тогда как классы были на разных. Внутри кластера можно посчитать дистанции между точками и найти среднее и выбросы. Так можно прикинуть количество точек в кластере или форму случайного распеделения. Ещё найти хорошие совпадения, от них тоже можно отталкиваться разбирая остальные. Построить график сходимости, действительно ли перебор вариантов что-то дает. Если хороших мало можно оценить общее качество информации. В общем набрать как можно больше оценок, осмыслить их значимость, абсолютную и локальную в зависимости от значений других. Потом обсудить это с людьми, кто понимает проч что числа, это самое полезное, что можно в этой задаче сделать. Люди может узнают что-то знакомое и подтвердят, что такое есть, или хотя бы получится их разговорить. Посчитать статистику с графиками и пусть объяснят там каждую особенность, тут ровно тут шум, тут плавно тут ступенька. Математик не должен вносить в данные свои приоритеты, поэтому если остается неопределенность её нужно так явно и описать, что вот тут такая-то область, тут такой-то класс, а определить что внутри мне не хватает информации. Если же начальство пытается переложить ответственность за принятие решения или экспериментирует то это отдельная тема и тоже желательно определиться в полномочиях.
Можно погуглить про какой-нибудь unexact pattern matching.
Коэффициенты 0 и бесконечность говорят только о том, что метрика Левенштейна не подходит.
Очень хорошая реальная задача, учителя и теоретики обломаются.

[Dmitriy40]

zcorvid в сообщении #1127578 писал(а):

Другой способ выполнить разбиение основан на анализе массива $A$ с помощью данных из массива $B$. Сортируем $B$, затем наносим точки массива $B$ на числовую прямую и применяем к $A$ правило ближайшего соседа — каждую точку $A$ относим к той записи из $B$, к которой она наиболее близка. Такой подход мне кажется намного корректнее, но я пока не уверен в его правильности.

На мой взгляд этот алгоритм решает задачу вполне корректно.
Для контроля можно ужесточить условие "наиболее близка" до скажем "расстояния до ближайшей точки $B$ и до любой другой (на самом деле она одна такая другая) отличаются не менее чем вдвое" - и при его невыполнении выдавать предупреждение о слишком высокой зашумлённости данных.

[Mihaylo]

zcorvid в сообщении #1127578 писал(а):

$\{1, 2, 3, 4, 5\}$ и $\{3, 1000002, 1000003, 1000004, 1000005\}$, то невязку будет огромная

Почему Вы увидели в данном примере проблему? Ведь массивы действительно сильно различаются! Степень непохожести равна 4 при максимуме 5. С нашей колокольни все норм.
Если же Вас не устраивает результат, то действительно надо провести кластеризацию. Грубо говоря, из массива $\{1, 2, 3, 4, 5\}$ получить массив $\{[3, 5]\}$ (усредненное число 3, в кластере 5 чисел). Из массива $\{3, 1000002, 1000003, 1000004, 1000005\}$ получится массив $\{[3, 1], [1000003.5, 4]\}$. Такие массивы могут оказаться в одной из метрик более похожими.

[zcorvid]

Mihaylo в сообщении #1128864 писал(а):

Почему Вы увидели в данном примере проблему? Ведь массивы действительно сильно различаются!

Не согласен, эти два массива очень похожи - я в первом посте описал, какие массивы считаются похожими. У меня прикладная задача, и похожие массивы это те, которые были получены из одного и того же набора реальных данных (но, например, разными физическими устройствами, как в моей ситуации). В данном примере явно видно, что числа 1,2,3,4,5 являются приближением числа 3, а числа за миллион - шум (пример искуственный, если нужно - могу написать пример двух массивов, которые были получены с реальных устройств, и суть их "отличия" была ровно такая же, при том что они были сняты с ситуации в один и тот же момент).

Mihaylo в сообщении #1128864 писал(а):

Степень непохожести равна 4 при максимуме 5. С нашей колокольни все норм.

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

Mihaylo в сообщении #1128864 писал(а):

Если же Вас не устраивает результат, то действительно надо провести кластеризацию. Грубо говоря, из массива $\{1, 2, 3, 4, 5\}$ получить массив $\{[3, 5]\}$ (усредненное число 3, в кластере 5 чисел). Из массива $\{3, 1000002, 1000003, 1000004, 1000005\}$ получится массив $\{[3, 1], [1000003.5, 4]\}$. Такие массивы могут оказаться в одной из метрик более похожими.

После кластеризации мы получим следующий результат:

$\{[1, 2, 3, 4, 5]\}$ и $\{[3], [\dots]\}$

Сопоставляя эти массивы мы как раз и получим требуемый результат в этом конкретном случае. Так что техника с кластеризацией очень интересная и многообещающая. Вообще отдельное спасибо NO. за подробное описание того, что можно сделать.

Сейчас я сделал отбор по ближайшему соседу, результат для конкретного набора данных неплохой - хорошо сопоставляет, отбрасывает шум, собирает разделившиеся цели (как и хотелось), но возникли другие проблемы. А именно, эта задача лишь часть более общей, общая задача - изучение этих массивов в динамике, и очень не радует то, как скачет результат в зависимости от времени. В общем результат получается такой, словно это просто набор случайных данных, то есть по факту в динамике никакой информации у нас не прибавилось.

ps. NO. , ваши труды не пропадут, я непременно попытаюсь воплотить ваши идеи в программу, может чуть позже, но обязательно они будут использованы по назначению

В общей задаче у меня возникли серьёзные трудности, поэтому создам по ней тему в корне раздела Computer Science, чтобы не разводить в этой теме оффтоп.

Тема:

http://www.dxdy.ru/topic109248.html