Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нелинеарная паралллельная проекция

Автор: sergejzr 5.6.2007, 13:22

Пришёл в выводы, что именно она мне нужна.
Смысл:

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

Как проще всего реализовать такую проекцию?

Поясняю в картинках smile

Это обычная параллельная проекция С отрезка А на отрезок В
http://img507.imageshack.us/my.php?image=projectvg6.gif

Это на кривую.

http://img254.imageshack.us/my.php?image=curvell3.gif

Таким образом хочу добиться, чтобы на "выпрямленной" кривой расстояния между спроецированными точками было одинакого
http://img507.imageshack.us/my.php?image=straightat8.gif

Это так была оттренирована система. Теперь приходит новая точка и мне надо найти её спроецированное положение
вот новая тут - красная линия
http://img404.imageshack.us/my.php?image=resultva5.gif

Нужную кривую я создам сам (думаю колоколами интерполировать проецируемые точки). Вопрос, как легчае всего определять положение новых точек?

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

Автор: kali 5.6.2007, 13:40

кривая между двумя оттренированными точками будет задана функционально?

Автор: sergejzr 5.6.2007, 13:59

Думаю кривую интерполировать колоколами. Это будет функция.

Чтото вроде:

Сумма_по_всем_тренированным_точкам(е^(si*x^2) )

Где коефф Si надо будет подобрать. Пока ещё точно не решил, что да как, но думаю в этом направлении ждёт удача.

Если возникнут другие предложения - буду рад!

Добавлено через 1 минуту и 57 секунд

http://img300.imageshack.us/my.php?image=interpoluj4.gif

Автор: maxim1000 5.6.2007, 14:06

можно воспользоваться тем же подходом, который используется для выравнивания распределения генераторов случайных чисел:
берём функцию распределения: F(x)=кол-во точек < x / общее количество точек
сглаживаем её как-нибудь (а то она ступенчатая будет)
и для каждой точки делаем преобразование: a -> F(a)
получившиеся точки будут равномерно распределены на [0,1]

Автор: kali 5.6.2007, 14:46

Длина кривой F(x) на интервале от a до b равна

L=Интеграл от a до b ( Sqrt( 1+F'(x)^2 ) dx )

Если найдешь такую интерполяционную функцию, что будет аналитически считаться интеграл, то будет тебе счастье, иначе придется сумму в цикле по точкам гонять.

P.S.

Цитата

(IMG:http://img300.imageshack.us/img300/9885/interpoluj4.th.gif)

ИМХО утебя получается обратный эффект. Между соседними точками с малым расстоянием между собой расстояние остается небольшим, а между точками большим расстояним между собой расстояние еще больше увеличивается.

Автор: sergejzr 2.7.2007, 09:17

kali, да, всё верно, спасибо.

Короче я подумал и нашёл решение проблемы. Оно как всегда оказалось довольно простым...

новая координата равна интегралу функции от начала до старой координаты.

Вопрос, чему равен интеграл функции: $user posted image$ ? (http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 )
Для этого вопроса я создал http://forum.vingrad.ru/forum/act-ST/f-13/t-161614/unread-1.html:

Автор: ivashkanet 4.7.2007, 09:49

Цитата(sergejzr @ 2.7.2007, 09:17

)

Вопрос, чему равен интеграл функции:

sergejzr, в аналитичеких функциях этот интеграл не берется. Только приближенно.
У тебя вариантов два:
Либо создать таблицу значений (нужных размеров) для интеграла N(0,1), (ню = 0, сигма =1), а потом получить значение для N(m,sigma) (кста в в вики про это написано).
Либо считать все самому, что менее рационально, но точнее.

Добавлено @ 09:51

Цитата(sergejzr @ 2.7.2007, 09:17

)

Для этого вопроса я создал спецтему:

Не заметил, звиняюсь.

Добавлено @ 09:57

Цитата(sergejzr @ 5.6.2007, 13:22

)

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

Есть такое понятие как "Естественное задание прямой".
Суть в том, что в качестве x используется длина кривой p (ро)от начала до этой точки.

Код

x =x(p)
y = y(p)

в твоем случае можно проще:

Код

y = y(x(p))

Так вот, если ты получишь формулу своей кривой в естественных координатах, то для определения новой точки ты просто подбираешь нужное значение p, а потом вычисляешь координаты этой точки.

Автор: sergejzr 4.7.2007, 12:16

У меня получилось то что хотел (в той теме отписал немного).
Смысл в том, что регрессирую колоколами точки и в качестве новой координаты беру нормализованное значение интеграла в старой точке.
Работает "на удивление" хорошо.

Т.е грубо говоря использую не длину кривой (кривая - интеграл), а её градиент. где Градиент большой - разброс большой, где маленький - разброса почти нет.

Сейчас в картинках отображу, вдруг кому понадобится. А ещё лучше, если кто нибудь сможет сказать, что такое уже в научной литературе есть. Тогда мне не надо будет мучатся в публикации smile

По X - старые значения от 0 - 10, которые надо "растянуть" на интервал респектируя ожидание новых точек.
Y - не важен для всех графиков кроме последнего.

Собственно алгоритм smile

1) Берём тренировочные точки и каждой присваиваем колокол
http://img176.imageshack.us/my.php?image=1gaussforeachpointma9.png

2) Суммарно колокола дадут нам функцию распределения (чем больше плотность - тем больше значение функции)
http://img207.imageshack.us/my.php?image=2summedupgaussgg8.png

3) Новая функция базируется на интеграле суммарной. Идея - чем выше точка в суммарной - тем больше её интеграл и наоборот.
Интеграл суммарной, в свою очередь - сумма интегралов колоколов (которые апроксимируем 1/(1+ехп(-х)) )
http://img265.imageshack.us/my.php?image=3integralforeachpointqe1.png

4) ну вот и ответ smile

. Здесь значения по Y - то, что мы ищем
http://img149.imageshack.us/my.php?image=4mappingfunctionjm2.png

Как видим, чем больше градиент- тем больше разброс. В принципе - элементарно smile

Т.е чем ближе изначальные точки друг к другу - тем выше значение суммарной функции - тем больше интеграл - тем "круче" градиент суммарного интеграла - тем дальше полученные точки друг от друга. smile

Напомню, искали мы функцию, которая из первого делает последнее.

Осталось доказать, что разброс действительно равномерный, но это уже дело техники smile

Автор: maxim1000 4.7.2007, 12:37

собственно это можно описать так:

Цитата(maxim1000 @ 5.6.2007, 14:06

)

только здесь ещё использование "колоколов" привело к некоторому сглаживанию функции распределения, возможно, нелишнему...

Автор: sergejzr 4.7.2007, 12:50

maxim1000, возможно я твой ответ неправильно понял smile

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

Автор: maxim1000 4.7.2007, 13:06

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

Автор: sergejzr 29.7.2007, 00:19

Цитата(maxim1000 @ 5.6.2007, 13:06

)

Где можно про это почитать? Куда ссылаться? smile

Автор: maxim1000 29.7.2007, 00:31

да, честно говоря, даже и не помню, откуда узнал
свойство простое: если x - случайная величина, F - её функция распределения, то F(x) - величина, равномерно распределённая на [0,1] (ну с некоторыми допущениями)