Stressmajorisering

Stressmajorisering är en optimeringsstrategi som används i multidimensionell skalning (MDS) där, för en uppsättning av $n$$m$ -dimensionella dataobjekt, en konfiguration $X$ av $n$ punkter i $r$$(\ll m)$ -dimensionellt utrymme eftersträvas som minimerar den så kallade spänningsfunktionen ${\displaystyle \sigma (X)$ } . Vanligtvis är $r$$2$ eller $3$ , dvs $(n\times r)$ matrisen $X$ listar punkter i $2-$ eller $3-$ dimensionellt euklidiskt utrymme så att resultatet kan visualiseras (dvs. en MDS-plot ). Funktionen $\sigma$ är en kostnads- eller förlustfunktion som mäter de kvadratiska skillnaderna mellan ideala ( $m$ -dimensionella) avstånd och faktiska avstånd i r -dimensionellt rum. Det definieras som:

$\sigma (X)=\summa _{i<j\leq n}w_{ij }(d_{ij}(X)-\delta _{ij})^{2}$

där $w_{ij}\geq 0$ är en vikt för mätningen mellan ett par punkter $(i,j)$ , ${\ displaystyle d_{ij}(X)}$ är det euklidiska avståndet mellan $i$ och $j$ och $\delta _{ij}$ är det ideala avståndet mellan punkterna (deras separation) i det $m$ -dimensionella datautrymmet. Observera att $w_{ij}$ kan användas för att specificera en grad av tillförlitlighet i likheten mellan punkter (t.ex. 0 kan anges om det inte finns någon information för ett visst par).

En konfiguration $X$ som minimerar $\sigma (X)$ ger en plot där punkter som ligger nära varandra motsvarar punkter som också ligger nära varandra i den ursprungliga $m$ -dimensionellt datautrymme.

Det finns många sätt som $\sigma (X)$ kan minimeras. Till exempel rekommenderade Kruskal ett iterativt tillvägagångssätt för brantaste nedstigning . En betydligt bättre metod (när det gäller garantier för och konvergenshastighet) för att minimera stress introducerades dock av Jan de Leeuw . De Leeuws iterativa majoriseringsmetod vid varje steg minimerar en enkel konvex funktion som både begränsar $\sigma$ ovanifrån och berör ytan av $\sigma$ i en punkt $Z$ , kallad den stödjande punkt . I konvex analys kallas en sådan funktion en majoriserande funktion. Denna iterativa majoriseringsprocess kallas också för SMACOF-algoritmen ("Skalning genom att MAjorisera en komplicerad funktion").

SMACOF-algoritmen

Spänningsfunktionen $\sigma$ kan utökas enligt följande:

$\sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij }(X)-\delta _{ij})^{2}=\summa _{i<j}w_{ij}\delta _{ij}^{2}+\summa _{i<j}w_{ ij}d_{ij}^{2}(X)-2\sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)$

Observera att den första termen är en konstant $C$ och den andra termen är kvadratisk i $X$ (dvs för den hessiska matrisen $V$ är den andra termen ekvivalent med tr $X'VX$ ) och därför relativt lätt att lösa. Den tredje termen begränsas av:

$\displaystyle \sum _{i<j}w_{ij}\ delta _{ij}d_{ij}(X)=\,\operatörsnamn {tr} \,X'B(X)X\geq \,\operatörsnamn {tr} \,X'B(Z)Z}$

där $B(Z)$ har:

$b_{ij}=-{\frac {w_{ij}\delta _{ij}}{d_{ij}(Z)} }$ för $d_{ij}(Z)\neq 0,i\neq j$

och $b_{ij}=0$ för $d_{ij}(Z)=0,i\neq j$

och $b_{ii}=-\summa _{j=1,j\neq i}^{n}b_{ij}$ .

Bevis på denna ojämlikhet är Cauchy-Schwarz- ojämlikheten, se Borg (s. 152–153).

Således har vi en enkel kvadratisk funktion $\tau (X,Z)$ som majoriserar stress:

$\sigma (X)=C+\,\operatörsnamn {tr} \,X'VX-2\,\operatörsnamn {tr} \,X'B(X)X$

$\leq C+\,\operatörsnamn {tr } \,X'VX-2\,\operatörsnamn {tr} \,X'B(Z)Z=\tau (X,Z)$

Den iterativa minimeringsproceduren är då:

• vid ${\displaystyle k^{th}}-$ steget sätter vi $Z\leftarrow X^{k-1}$
• $X^{k}\leftarrow \min _{X}\tau (X,Z)$
• stoppa om $\sigma (X^{k-1})-\sigma (X^{k})<\epsilon$ upprepa annars.

Denna algoritm har visat sig minska stressen monotont (se de Leeuw).

Använd i grafritning

Stressmajorisering och algoritmer som liknar SMACOF har också tillämpning inom området för grafritning . Det vill säga att man kan hitta en någorlunda estetiskt tilltalande layout för ett nätverk eller en graf genom att minimera en stressfunktion över nodernas positioner i grafen. I det här fallet $\delta _{ij}$ vanligtvis inställda på de grafteoretiska avstånden mellan noderna $i$ och $j$ och vikterna ${\ displaystyle w_{ij}}$ tas som $\delta _{ij}^{-\alpha }$ . Här $\alpha$ vald som en avvägning mellan att bevara lång- eller kortdistans idealavstånd. Goda resultat har visats för $\alpha =2$ .