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

27

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?

Uros K.
źródło

Odpowiedzi:

30

wprowadź opis zdjęcia tutaj

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.re122)=h12)+h2)2)-2)h1h2)sałataϕh12)h2)2)h1h2)sałataϕ

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 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ąh2)sałataϕrσ1σ2)r12„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.]

hsre2)=2)(1-s)re2)re2)=1-srr

sshre

ttnphns
źródło