Przeliczanie macierzy podobieństwa na macierz odległości (euklidesowa)

W algorytmie Losowy las Breiman (autor) konstruuje macierz podobieństwa w następujący sposób:

1. Wyślij wszystkie przykłady uczenia się w dół każdego drzewa w lesie

2. Jeśli dwa przykłady wylądują w tym samym przyrostu liścia, odpowiedni element w macierzy podobieństwa o 1

3. Normalizuj matrycę z liczbą drzew

On mówi:

Bliskości między przypadkami n i k tworzą macierz {prox (n, k)}. Z ich definicji łatwo jest wykazać, że macierz ta jest symetryczna, dodatnia określona i ograniczona powyżej przez 1, z elementami ukośnymi równymi 1. Wynika z tego, że wartości 1-prox (n, k) są kwadratowymi odległościami w euklidesowym przestrzeń wymiaru nie większa niż liczba przypadków. Źródło

W swojej implementacji używa sqrt (1-proxy) , gdzie proxy jest macierzą podobieństwa, aby przekonwertować ją na macierz odległości. Wydaje mi się, że ma to coś wspólnego z „kwadratowymi odległościami w przestrzeni euklidesowej” - cytowanym powyżej.

Czy ktoś może rzucić trochę światła na to, dlaczego wynika z tego, że 1-prox to kwadratowe odległości w przestrzeni euklidesowej i dlaczego używa kwadratowego pierwiastka do uzyskania macierzy odległości?

Zgodnie z twierdzeniem cosinusowym w przestrzeni euklidesowej (euklidesowa) kwadratowa odległość między dwoma punktami (wektorami) 1 i 2 wynosi . Kwadratowe długości i są sumami kwadratów współrzędnych odpowiednio punktów 1 i 2 (są to pitagorejskie przeciwprostokątne). Ilość nazywa się iloczynem skalarnym (= iloczyn skalarny , = iloczyn wewnętrzny) wektorów 1 i 2.$d_{12}^2 = h_1^2+h_2^2-2h_1h_2\cos\phi$$h_1^2$$h_2^2$$h_1h_2\cos\phi$

Iloczyn skalarny jest również nazywany podobieństwem typu kątowego między 1 a 2, aw przestrzeni euklidesowej jest geometrycznie najbardziej poprawną miarą podobieństwa , ponieważ łatwo można go przekonwertować na odległość euklidesową i odwrotnie (patrz również tutaj ).

Współczynnik kowariancji i korelacja Pearsona są produktami skalarnymi. Jeśli wyśrodkujesz dane wielowymiarowe (tak, aby początek znajdował się w środku chmury punktów), wówczas znormalizowane wartości to wariancje wektorów (nie zmiennych X i Y na powyższym rysunku), podczas gdy dla danych wyśrodkowanych to Pearson ; więc produktem skalarnym jest kowariancja. [Uwaga dodatkowa. Jeśli teraz myślisz o kowariancji / korelacji między zmiennymi , a nie punktami danych, możesz zapytać, czy można narysować zmienne tak, aby były wektorami, jak na powyższym rysunku. Tak, możliwe, nazywa się to „ przestrzenią tematyczną$h^2$$\cos\phi$$r$$\sigma_1\sigma_2r_{12}$„sposób reprezentacji. Twierdzenie cosinus pozostaje prawdziwe bez względu na to, co w tym przypadku przyjmuje się za„ wektory ”- punkty danych lub cechy danych.]

$h$$s$$d^2=2(1-s)$$d$$2$$d^2=1-s$$r$$r$

$s$$s$$h$$d$