Jaki jest związek między grupowaniem k-średnich a PCA?

Powszechną praktyką jest stosowanie PCA (analiza głównego składnika) przed algorytmem grupowania (takim jak k-średnie). Uważa się, że poprawia to wyniki klastrowania w praktyce (redukcja hałasu).

Jestem jednak zainteresowany porównawczym i dogłębnym badaniem związku między PCA i k-średnich. Na przykład Chris Ding i Xiaofeng He, 2004, K-oznacza Clustering poprzez Principal Component Analysis pokazał, że „głównymi komponentami są ciągłe rozwiązania dyskretnych wskaźników członkostwa w klastrze dla klastrowania K-średnich”. Trudno mi jednak zrozumieć ten artykuł, a Wikipedia faktycznie twierdzi, że jest w błędzie .

Ponadto wyniki tych dwóch metod są nieco odmienne w tym sensie, że PCA pomaga zmniejszyć liczbę „cech” przy jednoczesnym zachowaniu wariancji, podczas gdy klastrowanie zmniejsza liczbę „punktów danych” poprzez podsumowanie kilku punktów według ich oczekiwań / środków (w przypadku k-średnich). Więc jeśli zestaw danych składa się z $N$ punktów z funkcjami $T$ , PCA dąży do kompresji funkcji $T$ podczas gdy grupowanie ma na celu kompresowanie $N$ punktów danych.

Szukam laikowskiego wyjaśnienia relacji między tymi dwiema technikami + kilka innych dokumentów technicznych dotyczących tych dwóch technik.

Prawdą jest, że K-klastrowanie i PCA wydają się mieć bardzo różne cele i na pierwszy rzut oka nie wydają się być powiązane. Jednak, jak wyjaśniono w artykule D- and & 2004 K-oznacza Clustering poprzez Principal Component Analysis , istnieje między nimi głęboki związek.

Intuicja jest taka, że ​​PCA stara się reprezentować wszystkie wektorów danych jako liniowe kombinacje niewielkiej liczby wektorów własnych i robi to, aby zminimalizować średni błąd kwadratowy rekonstrukcji. W przeciwieństwie do tego, K-średnie stara się reprezentować wszystkie n wektorów danych za pomocą niewielkiej liczby centroidów klastrowych, tj. Reprezentować je jako kombinacje liniowe małej liczby wektorów centroidów klastrowych, w których wagi kombinacji liniowej muszą być równe zeru, z wyjątkiem pojedynczego 1 . Odbywa się to również w celu zminimalizowania średniego kwadratu błędu rekonstrukcji.$n$$n$$1$

Tak więc środki K można postrzegać jako super-rzadkie PCA.

Co robi papier Ding & He, aby uczynić to połączenie bardziej precyzyjnym.

$(K-1)$

$K-1$

$K=2$

Jest to albo błąd, albo niechlujne pisanie; w każdym razie, biorąc dosłownie, to konkretne twierdzenie jest fałszywe.

$K=2$$100$

Widać wyraźnie, że chociaż centroidy klasowe są dość blisko pierwszego kierunku na PC, nie padają na nie dokładnie. Co więcej, mimo że oś PC2 doskonale oddziela klastry w podplotach 1 i 4, istnieje kilka punktów po niewłaściwej stronie w podplotach 2 i 3.

Tak więc zgodność między K-średnich a PCA jest całkiem dobra, ale nie jest dokładna.

$K=2$$n_1$$n_2$$n=n_1+n_2$ $\mathbf q\in\mathbb R^n$$q_i = \sqrt{n_2/nn_1}$$i$$q_i = -\sqrt{n_1/nn_2}$$\|\mathbf q\| = 1$$\sum q_i = 0$

Ding i He pokazują, że funkcja utraty K-średnich (że algorytm K-znaczy minimalizuje) może być w równym stopniu przepisana jako , gdzie jest Macierz Gramów produktów skalarnych między wszystkimi punktami: , gdzie jest macierzą danych i to wyśrodkowana macierz danych.$\sum_k \sum_i (\mathbf x_i - \boldsymbol \mu_k)^2$$-\mathbf q^\top \mathbf G \mathbf q$$\mathbf G$$n\times n$$\mathbf G = \mathbf X_c^\top \mathbf X_c$$\mathbf X$$n\times 2$$\mathbf X_c$

(Uwaga: używam notacji i terminologii, która nieco różni się od ich pracy, ale uważam ją za bardziej zrozumiałą).

Zatem rozwiązanie K-średnich jest wektorem jednostek centrowanych maksymalizującym . Łatwo jest wykazać, że pierwszy główny składnik (po znormalizowaniu w celu uzyskania sumy jednostkowej kwadratów) jest wiodącym wektorem własnym macierzy Grama, tj. Jest również centrowanym wektorem jednostek maksymalizującym . Jedyną różnicą jest to, że jest dodatkowo ograniczony do posiadania tylko dwóch różnych wartości, podczas gdy nie ma tego ograniczenia.$\mathbf q$$\mathbf q^\top \mathbf G \mathbf q$$\mathbf p$$\mathbf p^\top \mathbf G \mathbf p$$\mathbf q$$\mathbf p$

Innymi słowy, K-średnie i PCA maksymalizują tę samą funkcję celu , przy czym jedyną różnicą jest to, że K-średnie ma dodatkowe ograniczenie „kategoryczne”.

Jest oczywiste, że w większości przypadków rozwiązania K-średnie (ograniczone) i PCA (nieograniczone) będą dość blisko siebie, jak widzieliśmy powyżej w symulacji, ale nie należy oczekiwać, że będą identyczne. Biorąc i ustawiając wszystkie jego ujemne elementy na równe i wszystkie jego pozytywne elementy na ogół nie dają dokładnie .$\mathbf p$$-\sqrt{n_1/nn_2}$$\sqrt{n_2/nn_1}$$\mathbf q$

Wydaje się, że Ding i On dobrze to rozumieją, ponieważ formułują swoje twierdzenie w następujący sposób:

Twierdzenie 2.2. W przypadku K-klastrowania, gdzie , ciągłe rozwiązanie wektora wskaźnika klastrowego jest [pierwszym] głównym składnikiem$K= 2$

Zauważ, że słowa „ciągłe rozwiązanie”. Po udowodnieniu tego twierdzenia dodatkowo komentują, że PCA może być użyte do zainicjowania iteracji K-średnich, co ma sens, biorąc pod uwagę, że oczekujemy, że będzie zbliżone do . Ale nadal trzeba wykonywać iteracje, ponieważ nie są one identyczne.$\mathbf q$$\mathbf p$

Jednak Ding i He opracowali bardziej ogólne podejście do i ostatecznie sformułowali Twierdzenie 3.3 jako$K>2$

Twierdzenie 3.3. Podprzestrzeń środka ciężkości klastra jest rozłożona przez pierwsze główne kierunki [...].$K-1$

Nie przeszedłem przez matematykę z Rozdziału 3, ale uważam, że to twierdzenie faktycznie odnosi się również do „ciągłego rozwiązania” K-średnich, tj. Jego stwierdzenie powinno brzmieć „klaster centroid przestrzeni ciągłego rozwiązania K-średnich to rozpiętości [...] ".

Ding i On nie dokonują jednak tej ważnej kwalifikacji, a ponadto piszą w streszczeniu

Udowadniamy tutaj, że głównymi składnikami są ciągłe rozwiązania dyskretnych wskaźników członkostwa w klastrze dla klastrów K. Równolegle pokazujemy, że podprzestrzeń rozciągnięta przez centroidy gromadowe wynika z rozszerzenia widmowego macierzy kowariancji danych obciętej w kategoriach .$K-1$

Pierwsze zdanie jest całkowicie poprawne, ale drugie nie. Nie jest dla mnie jasne, czy jest to (bardzo) niechlujny tekst, czy prawdziwy błąd. Bardzo uprzejmie wysłałem e-mailem do obu autorów prośbę o wyjaśnienie. (Aktualizacja dwa miesiące później: nigdy nie otrzymałem od nich odpowiedzi).

Kod symulacyjny Matlaba

figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
    means = [0 0; i*2 0];

    rng(42)
    X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
         bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
    X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);
    [ind, centroids] = kmeans(X,2, 'Replicates', 100);

    subplot(2,4,i)
    scatter(X(:,1), X(:,2), [], [0 0 0])

    subplot(2,4,i+4)
    hold on
    scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
    scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
    plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
    plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)

    plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
    subplot(2,4,i)
    axis([-8 8 -8 8])
    axis square
    set(gca,'xtick',[],'ytick',[])
end    

PCA i K-znaczy robią różne rzeczy.

PCA służy do uczenia wymiarowości / wyboru cech / uczenia się reprezentacji, np. Gdy przestrzeń cech zawiera zbyt wiele nieistotnych lub nadmiarowych cech. Celem jest znalezienie wewnętrznej wymiarów danych.

Oto dwuwymiarowy przykład, który można uogólnić na przestrzenie o wyższych wymiarach. Zestaw danych ma dwie funkcje, i , każde koło jest punktem danych.$x$$y$

Na obrazie ma większą wielkość niż . To są wektory własne. Wymiar danych jest redukowany z dwóch wymiarów do jednego wymiaru (w tym przypadku nie ma dużego wyboru) i odbywa się to poprzez rzutowanie w kierunku wektora (po obrocie, w którym staje się równoległy lub prostopadły do ​​jednej z osi) . Wynika to z faktu, że jest prostopadła do kierunku największej wariancji. Jednym ze sposobów myślenia o tym jest minimalna utrata informacji. (Nadal występuje utrata, ponieważ jedna oś współrzędnych została utracona).$v1$$v2$$v2$$v2$$v2$

K-średnich to algorytm grupowania, który zwraca naturalne grupowanie punktów danych na podstawie ich podobieństwa. Jest to szczególny przypadek modeli mieszanki Gaussa .

Na poniższym obrazku zestaw danych ma trzy wymiary. Z wykresu 3D po lewej stronie widać, że wymiar można „upuścić” bez utraty dużej ilości informacji. PCA służy do wyświetlania danych na dwa wymiary. Na rysunku po lewej stronie pokazano również płaszczyznę rzutowania. Następnie można użyć K-średnich na rzutowanych danych do oznaczenia różnych grup, na rysunku po prawej stronie, zakodowanych w różnych kolorach.$X$

PCA lub inne techniki redukcji wymiarów są stosowane przed uczeniem maszynowym zarówno bez nadzoru, jak i nadzorowanych metod. Oprócz powodów przedstawionych przez ciebie i tych, o których wspomniałem powyżej, jest również używany do celów wizualizacji (projekcja do 2D lub 3D z wyższych wymiarów).

Jeśli chodzi o artykuł, nie sądzę, aby istniało jakieś połączenie, PCA nie ma informacji dotyczących naturalnego grupowania danych i działa na całych danych, a nie na podzbiorach (grupach). Jeśli niektóre grupy można wyjaśnić jednym wektorem własnym (tylko dlatego, że ta konkretna gromada jest rozproszona wzdłuż tego kierunku), to tylko zbieg okoliczności i nie należy jej traktować jako ogólnej zasady.

„PCA ma na celu kompresję funkcji T, podczas gdy klastrowanie ma na celu kompresję N punktów danych”.

Rzeczywiście, kompresja jest intuicyjnym sposobem myślenia o PCA. Jednak w K-średnich, aby opisać każdy punkt w stosunku do jego skupienia, nadal potrzebujesz co najmniej takiej samej ilości informacji (np. Wymiary) , gdzie jest odległością, a jest zapisywane zamiast . Musisz także zapisać aby wiedzieć, do czego odnosi się delta. Można sklepu oczywiście a jednak nie będzie można pobrać aktualne informacje w danych.$x_i = d( \mu_i, \delta_i)$$d$$\delta_i$$x_i$$\mu_i$$d$$i$

Klastrowanie dodaje informacje naprawdę. Myślę, że to podział danych na naturalne grupy (które niekoniecznie muszą być rozłączne) bez wiedzy, co oznacza etykieta dla każdej grupy (no cóż, dopóki nie spojrzysz na dane w grupach).

Zazwyczaj wybiela się dane przed użyciem k-średnich. Powodem jest to, że k-średnie jest niezwykle wrażliwe na skalę, a kiedy masz mieszane atrybuty, nie ma już „prawdziwej” skali. Następnie musisz znormalizować, ujednolicić lub wybielić swoje dane. Żadna z nich nie jest idealna, ale wybielanie usunie globalną korelację, która czasem może dać lepsze wyniki. PCA / wybielanie to ponieważ operujesz na macierzy kowariancji.$O(n\cdot d^2 + d^3)$

O ile mi wiadomo, związek k-średnich z PCA nie występuje w pierwotnych danych . Chodzi o użycie PCA na macierzy odległości (która ma wpisów, a wykonanie pełnego PCA jest więc - tj. Zbyt drogie, w szczególności w porównaniu do k-średnich, które są gdzie jest jedynym dużym terminem) i może tylko dla . Średnie K to problem optymalizacji najmniejszych kwadratów, podobnie jak PCA. k-znaczy próbuje znaleźć partycję danych o najmniejszych kwadratach. PCA znajduje wektor członkostwa w klastrze o najmniejszych kwadratach.$n^2$$O(n^2\cdot d+n^3)$$O(k\cdot n \cdot i\cdot d)$$n$$k=2$

Pierwszy wektor własny ma największą wariancję, dlatego podział na ten wektor (który przypomina członkostwo w klastrze, a nie współrzędne danych wejściowych!) Oznacza maksymalizację wariancji klastra . Maksymalizując wariancję między klastrami, minimalizujesz również wariancję wewnątrz klastra.

Ale w przypadku prawdziwych problemów jest to bezużyteczne. Ma to jedynie teoretyczne znaczenie.

Rozwiązanie k-średnich na jego przybliżeniu O (k / epsilon) niskiej rangi (tj. Rzutowanie na rozpiętość pierwszych największych wektorów pojedynczych jak w PCA) dałoby przybliżenie (1 + epsilon) pod względem błędu multiplikatywnego.

W szczególności rzutowanie na k-największy wektor dałoby przybliżenie 2.

W rzeczywistości suma kwadratów odległości dla KAŻDEGO zestawu k centrów może być przybliżona przez ten rzut. Następnie możemy obliczyć zestaw rdzeniowy na zredukowanych danych w celu zmniejszenia danych wejściowych do punktów poli (k / eps), które są zbliżone do tej sumy.

Zobacz: Dan Feldman, Melanie Schmidt, Christian Sohler: Przekształcanie dużych zbiorów danych w małe dane: zestawy rdzeniowe o stałej wielkości dla k-średnich, PCA i klastrów projekcyjnych. SODA 2013: 1434-1453

Intuicyjny związek PCA i KMeans

1. Teoretycznie analiza wymiarowa PCA (pierwszy zachowany wymiar K mówi, że 90% wariancji ... nie musi mieć bezpośredniego związku z gromadą K Znaczy), jednak wartość zastosowania PCA pochodzi z a) praktycznych rozważań, biorąc pod uwagę naturę obiektów, które analizujemy tendencję do naturalnego skupiania się wokół / ewolucji z (pewnego segmentu) ich głównych składników (wiek, płeć ...) b) PCA eliminuje te wymiary o niskiej wariancji (hałas), więc samo w sobie dodaje wartości (i tworzy poczucie podobne do grupowania ) poprzez skupienie się na tych kluczowych wymiarach Mówiąc prościej, to właśnie oś XY pomaga nam opanować dowolną abstrakcyjną koncepcję matematyczną, ale w bardziej zaawansowany sposób.

2. Środki K próbują zminimalizować całkowitą odległość w obrębie klastra dla danego K.

3. W przypadku zestawu obiektów o parametrach wymiaru N domyślnie podobne obiekty będą miały MOST parametry „podobne”, z wyjątkiem kilku kluczowych różnic (np. Grupa młodych studentów informatyki, młodych tancerzy, ludzi… będzie miała kilka bardzo podobnych cech (niska wariancja) ale kilka kluczowych cech jest wciąż dość różnorodnych, a uchwycenie tych „kluczowych głównych elementów” zasadniczo uchwyci większość wariancji, np. kolor, obszar zamieszkania… Stąd niskie zniekształcenie, jeśli zaniedbamy te cechy drobnych różnic lub konwersję do niższe komputery nie stracą dużo informacji
4. Jest zatem „bardzo prawdopodobne” i „bardzo naturalne”, że grupowanie ich w celu sprawdzenia różnic (wariantów) ma sens dla oceny danych (np. Jeśli wykonasz 1000 ankiet w ciągu tygodnia na głównej ulicy, grupując je w oparciu o pochodzenie etniczne , wiek lub wykształcenie, jak komputer ma sens) W ramach misji K Means staramy się ustalić znaczną liczbę K, aby te elementy grupy (w klastrze) miały ogólnie najmniejszą odległość (zminimalizowaną) między Centroidem, a jednocześnie koszt ustanowienie i uruchomienie klastrów K jest optymalne (każdy element jako klaster nie ma sensu, ponieważ jest to zbyt kosztowne do utrzymania i bez wartości)
5. Grupowanie K oznacza, że ​​można łatwo „wizualnie sprawdzić”, aby było optymalne, jeśli takie K jest zgodne z głównymi komponentami (np. Jeśli dla osób w różnym wieku, grupy etniczne / regresywne mają tendencję do wyrażania podobnych opinii, więc jeśli zgrupujesz te ankiety na podstawie te komputery osobiste, które osiągają cel minimalizacji (zob. 1) Również te komputery osobiste (etniczne, wiek, religia ...) dość często są ortogonalne, a zatem różnią się wizualnie, patrząc na PCA
6. Jednak ta intuicyjna dedukcja prowadzi do wystarczającego, ale nie koniecznego warunku. (Ref 2: Jednak to, że PCA jest użytecznym rozluźnieniem grupowania k-średnich, nie było nowym rezultatem (patrz na przykład [35]) i łatwo jest odkryć kontrprzykłady do stwierdzenia, że ​​podprzestrzeń centroid klastrów jest rozpięta według głównych kierunków [36])

Wybór klastrów na podstawie / wzdłuż CP może wygodnie prowadzić do wygodnego mechanizmu alokacji

Ten może być przykładem, jeśli x jest pierwszym komputerem PC wzdłuż osi X: (........... CC1 ............... CC2 ..... ....... CC3 oś X), gdzie oś X mówi, że przechwytuje ponad 9X% wariancji i mówi, że jest to jedyny komputer

6.Ponadto PCA służy również do wizualizacji po wykonaniu K środków (Ref 4)

Jeśli PCA wyświetla * nasz wynik grupowania K jako ortogonalny lub bliski, oznacza to, że nasze grupowanie jest prawidłowe, z których każda wykazuje unikalne cechy

(* ponieważ z definicji PCA znajduje / wyświetla te główne wymiary (od 1D do 3D), które mówią, że K (PCA) uchwyci prawdopodobnie znaczną większość wariancji.

Tak więc PCA jest zarówno użyteczny w wizualizacji i potwierdzeniu dobrego grupowania, jak i wewnętrznie użyteczny element w określaniu grupowania K oznacza - do użycia przed po K oznacza.

Odniesienie:

1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
2. https://en.wikipedia.org/wiki/Principal_component_analysis
3. KLASTROWANIE Z WYKORZYSTANIEM GŁÓWNEJ ANALIZY KOMPONENTÓW: STOSOWANIE AUTONOMII-NIEPEŁNOSPRAWNOŚCI OSÓB U OSÓB STARSZYCH (Combes & Azema)
4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng