Алгоритм проверки на похожесть графиков двух функций

← →
Blind Guardian (2007-12-24 19:31) [0]

Здравствуйте. Такая вот задача:
У меня есть два множества функций (дискретно заданных). Заданы в виде
TFunc=record values:array of double; Xmin,Xmax:integer; end;

Xmin..Xmax - это интервал на котором задана функция. Получается length(values)=Xmax-Xmin+1.
Нужно сопоставить наиболее похожие друг на друга функции или их части (одна функция может быть очень похожа только на часть другой функции, это тоже нужно учесть)

Я сделал вот так: брал две функции, находил пересечение интервалов, на которых они заданы (получал интервал a..b). Далее делал примерно так:
// func1,func2:TFunc; result:=0; for x:=a to b do result:=result+abs(func1.values[x-func1.Xmin]-func2.values[x-func2.Xmin]; result:=result/(b-a+1);
То есть, посчитал площадь зоны между графиками двух функций, потом нашел среднее значение этой площади по интервалу a..b. Таким образом, я получал некоторый коэффициент отличия.

Может, кто-нибудь подскажет чего умнее?

← →
Юрий Зотов © (2007-12-24 20:53) [1]

Попробовал бы подсказать... если бы знал, что понимается под словом "похожесть".

Допустим, точки близки, но одна линия плавная, а другая ломаная - они похожи? Или среднеквадратичное отклонение точек минимально - но по сравнению с чем оно должно быть минимально? И т.д.

Это и есть главный вопрос - что такое "похожесть". И ответить на него может только тот, кто знает конечную задачу. То есть, Вы и никто другой.

← →
Германн © (2007-12-25 00:52) [2]

Я тоже в первую бы очередь заинтересовался бы "физическим смыслом" такого сравнения. Вряд ли ведь это "искусство ради искусства".

← →
Jeer © (2007-12-25 09:36) [3]

> Blind Guardian (24.12.07 19:31)

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

Собственно, алгоритмы кластеризации:
- иерархический (дендрограммы);
- двухвходовой;
- К-средних;
- etc > 100 алгоритмов.

← →
Blind Guardian (2007-12-25 17:12) [4]

Юрий Зотов © (24.12.07 20:53) [1]
вот, что я имею ввиду под похожестью. К примеру: вы взяли несколько (5 к примеру) белых проводков (пластичных), погнули их так, как будто бы они - это графики функций y=f(x). Расместили их на черном столе. Сфотографировали. Потом поменяли их местоположение на столе (не вращая, а перемещая поступательно). Задача программы : по фотографиям сопоставить проводки. Может быть, проводки помялись самую малость, пока вы их перемещали =) , да и шум присутствует, то есть, стопроцентного совпадения каждого проводка с первой фотографии с проводком со второй фотографии не будет. Этап выделения белых линий на черном фоне в данном случае меня не интересует. А вот проверка на эту самую похожесть - интересует.
Примечание: функций намного больше чем 5 (примерно 2000), длины варьируются от 1 до 500 (в общем-то, очень короткие функци можно не рассматривать даже) И функция скорее всего разное количество в обоих множествах сопоставления.

← →
Blind Guardian (2007-12-25 17:17) [5]

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

← →
Jeer © (2007-12-26 09:31) [6]

Если известны исходные и слегка искаженные y=f(x), то сопоставление можно вести методами корреляционного анализа.

а проводки двигаются только по вертикали или по горизонтали тоже?

я бы нашел среднее расстояние между графиками, а затем рассматривал среднеквадратичные отклонения по каждой точке

А нельзя проще: взять и "проводок" просто размыть. Попадает в него другой, неразмытый - он похож.

> Blind Guardian (25.12.07 17:12) [4]
>
>

Эээ. Это вроде уже как бы было. Только с другим ником.
Модератора на тебя нет!

Алгоритм проверки на похожесть графиков двух функций Найти похожие ветки