Многомерное шкалирование

[wizardofnothing]

Собственно, вопрос также по многомерному шкалированию.
Однако меня интересует не классическая модель, а неметрическое многомерное шкалирование (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. еще нашел такую страничку, где формулы рассчета сдвига отличаются. собственно, вот и не знаю как правильнее получать новую конфигурацию, при каждой итерации.
поэтому, прошу помощи (правильны ли представленные формулы, либо в какой литературе их вообще искать). заранее спасибо

[PAV]

Отделено из другой темы

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

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

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

Есть, например, здесь:
http://www.twirpx.com/file/357477/

[wizardofnothing]

большое спасибо! это то что нужно

[wizardofnothing]

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

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