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
źródło
Odpowiedzi:
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.
źródło
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 mdscmdscale. Na przykładxmożesz to sprawdzićprcomp(x)icmdscale(dist(x))dać ten sam wynik (gdzieprcompPCA idistpo prostu oblicza odległości euklidesowe między elementami x)źródło
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
źródło
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?
źródło