Wypukły kadłub w wyższych wymiarach, znajdowanie wierzchołków polytopy

Question

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).

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):

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):

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)?

Answer 1

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.