2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Многомерное шкалирование
Сообщение15.11.2011, 03:15 


25/10/11
23
Собственно, вопрос также по многомерному шкалированию.
Однако меня интересует не классическая модель, а неметрическое многомерное шкалирование (NMDS) по методу Крускала (Kruskal)
какими формулами можно получить:

1) новую кофнигурацию
2) градиент спуска (negative gradient)
3) "step size" - то есть шаг ($\alpha$), на который следует сместить конфигурацию текущей итерации


P.S. вроде как, это все должно называться "stepest descent". Нашел в интернете следующие формулы. однако, подходят ли они к Non-metric MDS по методу Крускала? и вообще верны ли они? (pda'ка (стр 90 и далее)с этими формулами была очень низкого разрешения, так что переписывать их пришлось чуть ли не наугад)

1) новая конфигурация:
$$x_{is}^{new}=x_{is}+\frac {\alpha} {mag(g)}  g_{is}$$
где:
$x_{is}$ - объект текущей конфигурации
${\alpha}$ - сдвиг (шаг или step-size)
$g_{is}$ - градиент
$mag(g)$ - магнитуда градиента, высчитываемая по формуле $((\sum\limits_{i,s} g^{2}_{is})/n)^{1/2}$

2) градиент спуска (для Евклидового пространства):
$$g_{kl}=S \sum\limits_{i,j} (\delta^{ki}-\delta^{kj})(\frac {d_{ij}-\hat{d}_{ij}} {S^{*}} - {\frac {d_{ij}} {T^{*}}})(\frac {x_{il}-x_{jl}} {d_{ij}})$$
где:
$x_{il}$ - объект текущей конфигурации
$d_{ij}$ - элемент метрицы расстояний (distance) между объектами
$\hat{d}_{ij}$ - диспаритет (disparity) - результат приведения функции к монотонности (используется так называемый weak monotonicity)
$S^{*}$ - "сырой стресс" (raw stress), рассчитываемый по формуле $S^{*}=\sum({d_{ij}-\hat{d}_{ij}})^{2}$
$T^{*}$ - сумма квадратов всех расстояний $T^{*}=\sum{d_{ij}}^2$
$S$ - нормализованный стресс, рассчитываемый по формуле $S=({S^{*}/T^{*}})^{1/2}$
$\delta^{ki}$ и $\delta^{kj}$ - символы Кронекера (равны 1 или 0)

3)сдвиг (step size)
на первой итерации берется $\alpha$ равный 0.2 (при высоком показателе стресса), и менее (при низком)
на последующих шагах:
$$\alpha_{new}=\alpha_{previous}\cdot (angle factor)\cdot (relaxation factor)\cdot (good luck factor)$$
где:
$\alpha_{previous}$ - сдвиг на предыдущей итерации
$angle factor=(4.0)^{({\cos\theta})^{2.0}}$
${\cos\theta}$ - угол между текущим градиентом и градиентом предыдущей итерации, высчитываемый по формуле: $${\cos\theta}=\frac {\sum\limits_{i,s} g_{is} g''_{is}} {(\sum\limits_{i,s} g_{is}^{2})^{1/2}(\sum\limits_{i,s} g''_{is}^{2})^{1/2}}$$
где $g_{is}$ - градиент текущей итерации, а $g''_{is}$, соответственно, градиент предыдущей итерации
$relaxation factor = \frac {1.3} {1+({5 step ratio})^{5.0}}$
$5 step ratio =\min \Bigl[ 1,{\frac {(present stress)} {(stress 5 iterations ago)}} \Bigl] $, где: $(present stress)$ - текущий стресс; $(stress 5 iterations ago)$ - стресс 5 итераций назад (если 5 итераций еще не было совершено, то берется самый первый высчитанный стресс)
$good luck factor =\min \Bigl[ 1,{\frac {(present stress)} {(previous stress)}} \Bigl] $, где: $(present stress)$ - текущий стресс; $(previous stress)$ - стресс на предыдущей итерации (если она вообще была)

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

 Профиль  
                  
 
 Re: Многомерное шкалирование
Сообщение15.11.2011, 09:41 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
 i  Отделено из другой темы

 Профиль  
                  
 
 Re: Многомерное шкалирование
Сообщение16.11.2011, 10:06 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Посмотрите в сборнике "Статистические методы для ЭВМ", М., "Наука", 1986. Там есть статья Крускала "Многомерное шкалирование и другие методы поиска структуры" с подробным объяснением.
Вообще же расхождение может быть обусловлено тем, что это не единый метод, а семейство методов, различающихся, в частности, функцией, преобразующей "различия объектов" в "расстояния между точками" (линейная, полином, монотонная общего вида и т.п.)

 Профиль  
                  
 
 Re: Многомерное шкалирование
Сообщение16.11.2011, 12:30 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Есть, например, здесь:
http://www.twirpx.com/file/357477/

 Профиль  
                  
 
 Re: Многомерное шкалирование
Сообщение16.11.2011, 13:48 


25/10/11
23
большое спасибо! это то что нужно

 Профиль  
                  
 
 Re: Многомерное шкалирование
Сообщение26.12.2011, 03:57 


25/10/11
23
Вцелом, данная книга очень помогла. В MDS разобрался практически полностью.
Однако, осталась одна маленькая недопонятка.

Итак, на каждой итерации шкалирования необходимо производить регрессию, дабы получать псевдорастояния (также упоминается как pseudodistances, disparities или $\hat_{d}$). Если выбирать монотонную регрессию (неметрическое шкалирование), то мы всегда будем получать положительные псевдорасстояния. Однако, в случае линейной или полиномиальной (метрическое шкалирование) регрессии через метод наименьших квадратов, мы можем получить отрицательные псевдорасстояния.
Собственно, с этим и связан вопрос. А могут ли псевдорасстояния быть отрицательными? Ведь, как никак, это тоже расстояния, а также они нужны для рассчета стресса и градиента (формулы представлены выше). В сборнике "Статистические методы для ЭВМ" об этом ничего не сказано, также как не сказано и в мануале к алгоритму KYST (данный алгоритм и описан в сбонике). По этому вопросу нашел только описание и решение проблемы для другого MDS алгоритма - SMACOF, но он сам по себе совершенно иной.
Буду весьма признателен, если кто-нибудь разъяснит мне данный вопрос.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group