Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Statystyka II – 4. Skalowanie wielowymiarowe – MIM UW

Zagadnienia

4. Skalowanie wielowymiarowe

Skalowanie wielowymiarowe pozwala na redukcję wymiaru cech. Dla macierzy danych:

X=\left(\begin{array}[]{c}X_{1}^{T}\\
X_{2}^{T}\\
\ldots\\
X_{n}^{T}\\
\end{array}\right)_{{n\times p}}

będziemy chcieli zrzutować ,,optymalnie” dane na \mathbb{R}^{k}, czyli zmniejszyć macierz X do \hat{Z} o wymiarch n\times k, k<p.

Optymalność zdefiniujemy w kategoriach macierzy odległości lub podobieństwa dla n obiektów. Zadaniem będzie znalezienie optymalnej reprezentacji obiektów w \mathbb{R}^{k}.

Definicja 4.1

Macierz odległości to taka macierz, która spełnia własności:

D=(d_{{ij}})_{{i,j=1}}^{n},\quad d_{{ij}}\geq 0,\quad d_{{ij}}=d_{{ji}},\quad d_{{ii}}=0.

Macierz podobieństwa jest macierzą konstruowaną w sposób przeciwstawny do macierzy odległości o własnościach:

C=(c_{{ij}})_{{i,j=1}}^{n},\quad c_{{ij}}=c_{{ji}},\quad c_{{ii}}\geq c_{{ij}}\text{ }\forall i,j.

4.1. Metody skalowania danych

Dla macierzy danych X o wymiarach n\times p, zdefiniujmy D jako macierz odległości euklidesowych pomiędzy obiektami:

d_{{ij}}^{2}=||X_{i}-X_{j}||^{2}.
  1. Classical multidimensional scaling:

    (\widehat{Z}_{1},\ldots,\widehat{Z}_{n})=\min _{{Z_{1},\ldots,Z_{n}\in\mathbb{R}^{k}}}\text{ }\sum _{{i\neq j}}(d_{{ij}}^{2}-||Z_{i}-Z_{j}||^{2});
  2. Sammon scaling:

    (\widehat{Z}_{1},\ldots,\widehat{Z}_{n})=\min _{{Z_{1},\ldots,Z_{n}\in\mathbb{R}^{k}}}\text{ }\frac{1}{\sum _{{k\neq l}}d_{{kl}}}\sum _{{i\neq j}}\frac{(d_{{ij}}-||Z_{i}-Z_{j}||)^{2}}{d_{{ij}}}=
    =\min _{{Z_{1},\ldots,Z_{n}\in\mathbb{R}^{k}}}\text{ }\sum _{{i\neq j}}\left(\frac{d_{{ij}}-||Z_{i}-Z_{j}||}{d_{{ij}}}\right)^{2}\frac{d_{{ij}}}{\sum _{{k\neq l}}d_{{kl}}};
  3. Kruskal-Shepard scaling:

    (\widehat{Z}_{1},\ldots,\widehat{Z}_{n})=\min _{{Z_{1},\ldots,Z_{n}\in\mathbb{R}^{k}}}\text{ }\sum _{{i\neq j}}(d_{{ij}}-||Z_{i}-Z_{j}||)^{2}.

4.2. Własności

Niech L oznacza macierz ortogonalną p\times p, L=(L_{1},L_{2}), L_{1} o wymiarze p\times k. Oznaczmy \widehat{Z}=XL_{1}, czyli rzut X na \mathbb{R}^{k}. Zdefiniujmy macierz odległości dla \widehat{Z} jako \widehat{D}=(\widehat{d}_{{rs}}). Zauważmy, że:

d_{{rs}}^{2}=||X_{r}-X_{s}||^{2}=||L^{T}(X_{r}-X_{s})||^{2},

ponieważ mnożenie wektora przez macierz ortogonalną nie zmienia jego normy. Mamy więc:

d_{{rs}}^{2}=\sum _{{j=1}}^{p}(X_{{rj}}-X_{{sj}})^{2}=\sum _{{j=1}}^{p}[l_{j}^{T}(X_{{r}}-X_{{s}})]^{2}\geq\sum _{{j=1}}^{k}[l_{j}^{T}(X_{{r}}-X_{{s}})]^{2}=\widehat{d}_{{rs}}^{2}.
Stwierdzenie 4.1

Rzut X na k pierwszych składowych głównych minimalizuje wyrażenie \sum _{{r\neq s}}(d_{{rs}}^{2}-\widehat{d}_{{rs}}^{2}) wśród wszystkich rzutów XL_{1}. Jest więc rozwiązaniem zadania classical multidimensional scaling.

Przyjrzyjmy się następującej macierzy:

\sum _{{r,s=1}}^{n}(X_{r}-X_{s})(X_{r}-X_{s})^{T}=

dla \overline{X}=\frac{1}{n}\sum _{{i=1}}^{n}X_{i},

=2n\sum _{{r=1}}^{n}(X_{r}-\overline{X})(X_{r}-\overline{X})^{T}-2\sum _{{r=1}}^{n}(X_{r}-\overline{X})\underbrace{\sum _{{s=1}}^{n}(X_{s}-\overline{X})^{T}}_{{=0_{p}^{T}}}=
=2n\text{ }\left(\begin{array}[]{ccc}\sum _{{r=1}}^{n}(X_{{r1}}-\overline{X}_{{.1}})^{2}&\ldots&\sum _{{r=1}}^{n}(X_{{r1}}-\overline{X}_{{.1}})(X_{{rp}}-\overline{X}_{{.p}})\\
\ldots&\ldots&\ldots\\
\sum _{{r=1}}^{n}(X_{{rp}}-\overline{X}_{{.p}})(X_{{r1}}-\overline{X}_{{.1}})&\ldots&\sum _{{r=1}}^{n}(X_{{rp}}-\overline{X}_{{.p}})^{2}\\
\end{array}\right)+0=
=2nnS,

gdzie S jest macierzą kowariancji próbkowej (estymator obciążony).

Wróćmy do minimalizacji wyrażenia:

\sum _{{r,s=1}}^{n}(d_{{rs}}^{2}-\widehat{d}_{{rs}}^{2})=\underbrace{\sum _{{r,s=1}}^{n}d_{{rs}}^{2}}_{{p\text{ współczynników}}}-\underbrace{\sum _{{r,s=1}}^{n}\widehat{d}_{{rs}}^{2}}_{{k\text{ współczynników}}}=
=\underbrace{\sum _{{r,s=1}}^{n}\sum _{{j=k+1}}^{p}[l_{j}^{T}(X_{r}-X_{s})]^{2}}_{{\text{zostaje }p-k\text{ współczynników}}}.

Ponieważ \sum _{{r,s=1}}^{n}d_{{rs}}^{2} jest stałą, zadanie minimalizacji wyrażenia \sum _{{r,s=1}}^{n}(d_{{rs}}^{2}-\widehat{d}_{{rs}}^{2}) jest równoważne zadaniu maksymalizacji \sum _{{r,s=1}}^{n}\widehat{d}_{{rs}}^{2}. Maksymalizujemy po ortogonalnym układzie wektorów l_{1},\ldots,l_{k} wyrażenie:

\sum _{{r,s=1}}^{n}\sum _{{j=1}}^{k}l_{j}^{T}(X_{r}-X_{s})(X_{r}-X_{s})^{T}l_{j}=
=\sum _{{j=1}}^{k}l_{j}^{T}\left[\sum _{{r,s=1}}^{n}(X_{r}-X_{s})(X_{r}-X_{s})^{T}\right]l_{j}=
=2n^{2}\sum _{{j=1}}^{k}l_{j}^{T}Sl_{j}=

korzystając z rozkładu spektralnego S,

=2n^{2}\sum _{{j=1}}^{k}l_{j}^{T}(\sum _{{i=1}}^{p}\lambda _{i}v_{i}v_{i}^{T})l_{j}=
=2n^{2}\sum _{{j=1}}^{k}\sum _{{i=1}}^{p}\lambda _{i}(v_{i}^{T}l_{j})^{2}.

Dalszy dowód przebiega analogicznie do dowodu stwierdzenia 3.6. Można zauważyć związek pomiędzy własnościami składowych głównych dla podejścia populacyjnego i próbkowego.

4.3. Przykłady w programie R

Skalowanie wielowymiarowe:

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.