Методы сравнения набора цифр

greekdom

каким образом их можно сравнить, учитывая место каждой из них, какие есть вообще методы?

agroprom

а по-конкретней?

greekdom

Ну есть 2 набора цифр и есть ли какой математический способ определить насколько они схожи, учитывая местоположения каждой цифры.

HEPBAP

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

greekdom

Это из статистики что ли?
Да нет просто имеется два набора, порядок зависит, и нужно определить насколько они похожи ака 1 3 2 4 6, 1 3 2 4 6 = 100%, ну и т.д.Мне бы формулу какую.

zuzaka

Поищи, мы что-то такое проходили, когда нас с биоинформатикой знакомили:
Courses\Biopolymers\Vasilevskaya
Этот комп сейчас не пашет. Вернусь домой - попробую свои конспекты найти.

dysh

От тебя хотят метрику. Например, 13248 отличается от твоей последовательности сильнее чем 13247 или как? Как соотносятся штрафы за пропуск числа, вставку лишнего и замену?
Одна из стандартных метрик --- количество опечаток, где опечатка --- это удаление, вставка, замена (часто еще обмен местами). При этом если замена то все равно на какое число.
З.Ы. Алгоритмы которые считают число опечаток очень неэффективные.

parfum74

Самое стандартное - посчитать расстояние по метрике в l2 - те r = (a1-b1)^2 + (a2-b2)^2 +.., где ai и bi - числа на i-й позиции. А похожесть можно определить как d = 1 - c/r , где c - некий коэффициент, например c=1. Если последовательности совпадают, то d = 1, если сильно различаются, то d будет далеко от 1.
Но мне кажется, что основная проблема будет в другом. Там, где это тебе нужно, кроме чисел в последовательностях могут стоять пропуски, причем их заведомо больше , чем самих чисел. И вот тогда вопрос: насколько считать похожими последовательности 1, _, 3, _, 5 и _, 2, _, 4, _ ?

filippov2005

Может поподробнее расскажешь о том, как такой вопрос возник?
Пока непонятно:
Могут ли быть наборы разной длины?
Должна ли функция расстояния быть аддитивной (например, р(abcd, efgh) = p(a, e) + p(b, f) + p(c, g) + p(d, h?
Верно ли, что p(5, 6) < p(5, 7)?
И т.п.
Простые функции схожести - количество совпадающих позиций, длина наибольшей общей подпоследовательности.
Словом, нужен источник проблемы, а то получается слишком общая задача.

greekdom

Если последовательности совпадают, то d = 1,
Чёт я не понял, r = 0, d = INF.
Там, где это тебе нужно, кроме чисел в последовательностях могут стоять пропуски, причем их заведомо больше , чем самих чисел.
Нет, пропуски там не к чему.

greekdom

От тебя хотят метрику. Например, 13248 отличается от твоей последовательности сильнее чем 13247 или как?
Ну в этом то и вопрос, как сравнить наиболее эфективно.

greekdom

Верно ли, что p(5, 6) < p(5, 7)?
Да.
Могут ли быть наборы разной длины?
Нет.
Должна ли функция расстояния быть аддитивной (например, р(abcd, efgh) = p(a, e) + p(b, f) + p(c, g) + p(d, h?
Необязательно.
а то получается слишком общая задача.
Ну так оно и есть, просто нужет какой нибуть метод, так сказать наиболее адекватный и общий.

parfum74

Согласен, ерунду написал. Уровень совпадения можно определить как d = 1/(1+c*r) или d = exp(-c*r) . Тогда при r = 0, d=1, а при r->\infty, d->0.
Нет, пропуски там не к чему.
Пропуск = отсутствие оценки. В большинстве случаев как раз оценки нет

filippov2005

Еще вопрос.
Как тебе кажется какие из этих пар должны быть ближе в требуемой метрике:
(191919 и 919191) или (191919 и 282919)
- первая пара отличается тем, что удалив первый элемент из первой и последний из второй получим одинаковые последовательности, но при этом цифры в одинаковых позициях отличаются сильно (на 8);
- во второй не сильно отличаются (на 1) первые три цифры.
?
Если тебе кажется, что в твоей задаче сдвинутые последовательности не должны быть близки, а надо смотреть на различие в каждой позиции, то тебе подойдет обычная евклидова метрика, которую тебе написал (только там принято еще квадратный корень из суммы извлекать).
А уж из метрики r (т.е. меры различия) получить меру сходства d легко. Кроме тех, что предложил (d = exp(-c*r d = 1/(1 + c*r:
Если у тебя последовательности фиксированной длины (например, 4 то можно просто с помощью линейной функции:
d = A - B*r, где коэффициенты A и B ищутся из начальных условий. Например положим d(0000, 9999) = 0, d(X, X) = 100%.
A - B*18 = 0,
A - B*0 = 100;
A = 100,
B = 100/18.
В итоге получаем d( (a1, a2, a3, a4 (b1, b2, b3, b4) ) = 100 - 100/18*( (a1 - b1)^2 + ... (a4 - b4)^2 )^0.5
Если последовательности переменной длины, то можно взять такую почти линейную (линейную при фиксированном n) функцию:
d( (a1, ..., a_n (b1,..., b_n) ) = 100 - 100/(9 *(n^0.5*( (a1 - b1)^2 + ... (a_n - b_n)^2 )^0.5
Для такой функции 100 достигается только на совпадающих последовательностей, а 0 на парах типа (00...0, 99...9 )

naami_moloko

Есть прекрасная метрика p({a1, ..., an}, {b1, ..., bn})=max(|a1-b1|, ...,|an-bn|). Норма соответственно |{a1, ..., an}|=p({a1, ..., an}, {0, ...,0})=max(|a1|, ...,|an|)

greekdom

В большинстве случаев как раз оценки нет
Не ну мы берем только пересечение множеств оценок.

greekdom

Спасибо, метод принет к рассмотрению.

greekdom

Тоже хорошая идея, спасибо.
Оставить комментарий
Имя или ник:
Комментарий: