Wykonywanie PCA tylko z matrycą odległości

12

Chcę utworzyć klaster ogromnego zestawu danych, dla którego mam tylko pary odległości. Wdrożyłem algorytm k-medoidów, ale jego uruchomienie trwa zbyt długo, dlatego chciałbym zacząć od zmniejszenia wymiaru mojego problemu przez zastosowanie PCA. Jednak jedynym sposobem, w jaki znam tę metodę, jest zastosowanie macierzy kowariancji, której nie mam w swojej sytuacji.

Czy istnieje sposób na zastosowanie PCA, znając tylko pary odległości?

pca dimensionality-reduction multidimensional-scaling

— wielkie drzewo
źródło

1

Tak więc masz dużą kwadratową macierz odległości między punktami, które chcesz połączyć. (BTW, jaką odległość? Euklidesa?) Co sprawia, że myślisz, że to liczba wymiarów tych punktów, a nie liczba samych punktów (liczność), utrudnia grupowanie?

— ttnphns

1

Liczba punktów nie jest „bardzo duża” (kilka tysięcy). Odległość, której używam, jest korelacją Pearsona między tymi punktami

— bigTree

2

Ale moje pytanie brzmiało: czy naprawdę chcesz zmniejszyć wymiarowość (a jeśli tak, dlaczego?) Czy liczność (liczbę punktów)? Ponieważ twoje pytanie jest niejasne .

— ttnphns

1

@ttnphns: Oh chłopcze, oczywiście, że po prostu źle wpisałem swój poprzedni komentarz. Aby usunąć ewentualne zamieszanie, usunę teraz ten komentarz i powtórzę to, co tu powiedziałem, z poprawnym sformułowaniem: „Zmniejszenie liczności w tym przypadku oznacza zmniejszenie macierzy odległości (zmniejszenie ). Zmniejszenie wymiarów oznacza zmniejszenie jej niższa ranga, bez zmiany PCA równa się temu drugiemu i tak naprawdę nie pomaga w pierwszym celu ".

N \times N

$N \times N$

N

$N$

N

$N$

— ameba

1

Myślę, że najłatwiejszym sposobem jest skorzystanie z takiej (a) metody klastrowania lub (b) takiej jej implementacji lub (c) tak mocnego (wystarczającej ilości pamięci RAM) komputera, który weźmie i sklasyfikuje 6000 obiektów (nie wiem, dlaczego program medoid ma trudności. 6000 jest duży, ale niezbyt duży.). Niektóre metody (takie jak K-średnie) wymagają danych obiektów X. Możesz tworzyć takie dane z macierzy odległości obiektów za pomocą metrycznego MDS (jeśli ponownie twój komputer / program MDS zezwoli na 6000 obiektów).

— ttnphns

8

Aktualizacja: Całkowicie usunąłem swoją pierwotną odpowiedź, ponieważ była oparta na pomieszaniu odległości euklidesowych i produktów skalarnych. To jest nowa wersja mojej odpowiedzi. Przeprosiny.

Jeśli przez odległości parami masz na myśli odległości euklidesowe, to tak, istnieje sposób na wykonanie PCA i znalezienie głównych składników. Algorytm opisuję w odpowiedzi na następujące pytanie: Jaka jest różnica między analizą głównych składników a skalowaniem wielowymiarowym?

Krótko mówiąc, macierz odległości euklidesowych można przekształcić w wyśrodkowaną macierz Gram, która może być bezpośrednio wykorzystana do wykonania PCA poprzez skład eigendide. Ta procedura jest znana jako [klasyczne] skalowanie wielowymiarowe (MDS) .

Jeśli twoje pary odległości nie są euklidesowe, nie możesz wykonać PCA, ale nadal możesz wykonać MDS, który nie będzie już równoważny PCA. Jednak w tej sytuacji MDS może być jeszcze lepszy dla twoich celów.

— ameba
źródło

Odległość, której używam, jest korelacją (korelacja Pearsona), a zatem nie jest odległością euklidesową. Czy to działałoby podobnie?

— bigTree

1

@bigTree: Jeśli nie jest to odległość euklidesowa, nie ma możliwości uruchomienia PCA. Można jednak użyć skalowania wielowymiarowego, które jest techniką redukcji wymiarowości, która wykorzystuje dokładnie macierz odległości parowych (może to być dowolna odległość). Inna uwaga: przy pewnych założeniach dotyczących oryginalnych punktów danych (których nie masz) korelacje można przekształcić w odległości euklidesowe. Założenia są następujące: (1) mający zerową średnią, (2) mający ustaloną, np. Jednostkę, długość. Czy to przypadek dotyczy twoich danych?

— ameba

Żadne z tych danych nie jest prawdziwe ani moje dane, ale spróbuję dzięki MDS

— bigTree

1

nie możesz użyć jądra PCA? Wyobrażam sobie, że potrzebowałoby to tylko kropkowych produktów, ale niewiele wiem o tym problemie, więc nie wiem, czy to ma sens

— rep_ho,

4

Istnieje PCA z macierzą odległości, która nazywa się skalowaniem wielowymiarowym (MDS). Możesz dowiedzieć się więcej na wikipedii lub w tej książce .

Możesz to zrobić za Rpomocą funkcji mds cmdscale. Na przykład xmożesz to sprawdzić prcomp(x)i cmdscale(dist(x))dać ten sam wynik (gdzie prcompPCA i distpo prostu oblicza odległości euklidesowe między elementami x)

— Muzyka pop
źródło

3

Wygląda to na problem, do którego można zastosować klastrowanie spektralne. Ponieważ dysponujesz parą macierzy odległości, możesz zdefiniować w pełni połączony wykres, w którym każdy węzeł ma N połączeń, odpowiadających jego odległości od każdego innego węzła na wykresie. Na tej podstawie możesz obliczyć wykres Laplaciana (jeśli to brzmi przerażająco, nie martw się - to łatwe obliczenie), a następnie weź wektory własne najmniejszychwartości własne (tutaj różni się od PCA). Jeśli na przykład weźmiesz 3 wektory własne, uzyskasz macierz Nx3. W tej przestrzeni punkty powinny (miejmy nadzieję) być dobrze oddzielone ze względu na pewną zgrabną teorię graficzną, która sugeruje, że jest to optymalne cięcie dla maksymalizacji przepływu (lub w tym przypadku odległości) między skupieniami. Stamtąd możesz użyć k-średnich lub podobnego algorytmu do klastra w 3-przestrzeni. Polecam przejrzenie tego niesamowitego przewodnika, aby uzyskać więcej informacji:

http://arxiv.org/abs/0711.0189

— Christopher Krapu
źródło

0

Odległości w parach również tworzą macierz kwadratową, podobnie jak macierz współwariancji. PCA to po prostu SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ) zastosowane do macierzy korelacji. Nadal powinieneś być w stanie redukować wymiary za pomocą SVD na swoich danych. Nie jestem do końca pewien, jak interpretować wyniki, ale zdecydowanie warto spróbować. Możesz użyć metod klastrowania, takich jak k-średnich lub klastrowanie hierarchiczne. Zobacz także inne techniki redukcji wymiarów, takie jak skalowanie wielowymiarowe. Co próbujesz wydostać się ze swoich klastrów?

— Andrew Cassidy
źródło

Odpowiedź Andrew Cassidy'ego jest rzeczywiście ważna. Jeśli twoją miarą odległości jest korelacja Pearsona, jesteś po prostu czynnikiem standaryzującym „zbyt daleko” od faktycznego posiadania macierzy kowariancji. Zatem stosowanie SVD jest w zasadzie tym samym, co robienie PCA.

— Matthew Anthony