7

Załóżmy, że mam chmurę punktów podaną w 6-wymiarowej przestrzeni, którą mogę uczynić tak gęstą, jak potrzeba. Punkty te okazują się leżeć na powierzchni niższego wymiaru politytu (tj. Wektory punktowe (x1, x2, ... x6) wydają się być współpłaszczyznowe).Wypukły kadłub w wyższych wymiarach, znajdowanie wierzchołków polytopy

Chciałbym znaleźć wierzchołki tej nieznanej polytopy, a moja obecna próba korzysta z algorytmu qhull, poprzez interfejs scipy w Pythonie. Na początku otrzymywałbym tylko komunikaty o błędach, najwyraźniej spowodowane wprowadzeniem niższego wymiaru i/lub wieloma zdegenerowanymi punktami. Próbowałem kilku metod brutalnej siły, aby wyeliminować zdegenerowane punkty, ale niezbyt udane, a więc w końcu przypuszczam, że wszystkie te punkty muszą leżeć na wypukłym kadłubie.

This question był bardzo pomocny, ponieważ sugeruje zmniejszenie wymiarów za pomocą analizy głównych składników. Jeśli rzutuję punkty na hyperplane 4D, algorytm qhull działa bezbłędnie (dla dowolnego wyższego wymiaru nie działa).

from scipy.spatial import ConvexHull 
from sklearn.decomposition import PCA 

model = PCA(n_components=4).fit(initial_points) 
proj_points = model.transform(initial_points) 
hull = ConvexHull(proj_points, qhull_options = "Qx") 

Odpowiedź na powyższe pytanie wspomina, że ​​simplices muszą zostać przekształcone z powrotem po jednym oblicza wypukłej prognozowanego punktów. Ale wynik khull składa się tylko z indeksów i dlaczego nie odpowiadają one indeksom początkowych punktów?

Teraz mój problem polega na tym, że nie wiem, którą precyzję użyć, aby uzyskać właściwe wierzchołki. Bez względu na to, jak gęsto wykonuję chmurę punktów, uzyskane wierzchołki różnią się od siebie różnymi szczegółami. Na przykład, dla pierwszych punktów w (10000, 6) tablica dostać (gdzie E0.03 jest maksymalna, dla której pracuje ten):

hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03") 
print len(hull1.vertices) 
print hull1.vertices 

5 
[ 437 2116 3978 7519 9381] 

I wykreślenie go w niektórych (nie strasznie informacyjny) projekcję osiach 0,1,2 (gdzie niebieskie punkty stanowią wybór punktu początkowego chmurze):

enter image description here Ale dla większej precyzji (oczywiście) I dostać inny zestaw:

hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003") 
print len(hull2.vertices) 
print hull2.vertices 

29 
[ 74 75 436 437 756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979 
4340 4561 4657 4659 4924 5338 5797 6336 7519 7882 8200 9381 9427 9470] 

samej projekcji (tylko trochę inny kąt):

enter image description here

Podejrzewam, że pierwszy obraz nie ma wystarczającej liczby wierzchołków i że drugi obraz ewentualnie ma zbyt wielu. Chociaż oczywiście nie mogę wyciągnąć rygorystycznych informacji z tych wątków. Ale czy istnieje dobry sposób sprawdzenia, której precyzji użyć? A może zupełnie inne podejście do tego problemu (próbowałem już kilku)?

+1

Fascynujące pytanie. Nie mam gotowej odpowiedzi, ale zgadzam się, że pierwszy przykład z pewnością wygląda (na oko), że ma zbyt mało wierzchołków. Wydaje mi się, że ten ostatni zawsze będzie miał wiele wierzchołków wzdłuż "krawędzi" (przepraszam, jeśli jest to zła terminologia, a nie moja dziedzina wiedzy) projektowanej polytopy tylko dlatego, że początkowe punkty są losowe - prawdopodobnie nie dostać jeden na "prawdziwym" wierzchołku polytopy, o którym mówisz, że istnieje. Jeśli masz czas na eksperymentowanie - wypróbowałeś opcję [Q8] (http://www.qhull.org/html/qh-optq.htm#Q8), która wydaje się zignorować punkty "prawie w środku". –

+0

Dzięki za komentowanie. Okazuje się, że większość różnych opcji w Qhull daje te same (zmienne) odpowiedzi, podobnie jak Q8. Jedynym, który daje nieco inną liczbę (ale wciąż niestabilną z różnymi dokładnościami) jest Q9. Prawdą jest, że zestaw prawdopodobnie nie będzie zawierał oczekiwanych "prawdziwych" wierzchołków, ale ponieważ są one tak blisko, wydaje mi się, że powinien istnieć sposób ich uzyskania. – Denor

+0

Im więcej myślę, tym bardziej jestem zaintrygowany. Wydaje się, że jest to wciąż tematem prac w matematyce. [This] (http://cran.r-project.org/web/packages/alphahull/vignettes/alphahull.pdf) pokazuje podejście (2D), w którym ich parametr alfa wydaje się mieć podobny efekt do twojej precyzji. Problem polega na tym, że kadłub jest z definicji * najmniejszym * polytopem, który może zawierać punkty, a jednak zakładamy, że "prawdziwe" wierzchołki mogą leżeć poza zestawem próbek i że w pewnym sensie polytop ma "prostszy kształt" "niż wyprodukowany przez precyzyjne oszacowanie.Oko, OK, algorytmicznie, trudne. –

Odpowiedz

2

W tej odpowiedzi zakładam, że już użyłeś PCA do prawie bezstratnego kompresowania danych do danych 4-wymiarowych, gdzie zredukowane dane znajdują się w czterowymiarowej polityce z koncepcyjnie mało powierzchniami. Opiszę podejście do rozwiązania dla twarzy tej polytopy, która z kolei da ci wierzchołki.

Niech x i w R , i = 1, ..., K, być PCA obniżone punkty danych.

Niech K = (a, b) jest twarz, w której znajduje się R i z kulą; a = 1 i b jest w R.

Definiujemy twarz stratę funkcja L jak następuje, gdzie & lambda; + & lambda; -> 0 to parametry, które wybierzesz. λ + powinna być bardzo małą liczbą dodatnią. λ - powinna być bardzo dużą liczbą dodatnią.

l (F) = suma i (i lambda, + i kula, max (0, A i kula X i + B) - i N; - i kula, min (0, A i kuli; x i + b))

Chcemy znaleźć minimalny twarze F względem funkcji straty L. niewielki zbiór wszystkich minimalnych twarze opisze swój Polytope. Możesz rozwiązać minimalne twarze, losowo inicjując F, a następnie wykonując pochylenie gradientowe, używając pochodnych cząstkowych ∂L/∂a j, j = 1, 2, 3, 4 i ∂L/∂b. Na każdym kroku spadku gradientu a & bullet; a za 1 przez normalizację.

∂L/∂a J = suma i (i lambda, + i kula X J i kula, [A-kula X i + b> 0] - i N; - i kula x J i kula, [A-kula x i + b < 0]) dla j = 1, 2, 3, 4

∂L/∂b = suma ı (i lambda, + & bullet; [pocisk; x i + b> 0] - & lambda; - & bullet; [pocisk; x i + b < 0])

Uwaga Iverson brackets [P] = 1, jeśli P jest prawdziwe, [P] = 0, jeżeli P jest fałszywa.

+0

Jest kilka szczegółów, które wciąż mnie omijają w odniesieniu do faktycznego zastosowania, ale teoretycznie bardzo podoba mi się ten pomysł. Na wstępie muszę przyznać, że nie jest dla mnie jasne, jak zdobyć twarze. Czy możesz wyjaśnić (lub wskazać mi jakieś źródło), skąd bierze się stan a • a = 1? – Denor

+0

Wektor a jest normalny dla (skierowanej) powierzchni F. Warunek a • a = 1 ogranicza tylko normę a do długości 1; to znaczy, || a || = 1. –

+0

Ah, racja. To ma sens. Czym dokładnie jest b określona przez? Nie udało mi się w pełni zrealizować tego pomysłu, ale wydaje mi się, że warto to zaakceptować. – Denor