Wypukłe kadłuby hierarchicznego grupowania w Pythonie - python, analiza skupień, geometria obliczeniowa, wypukły kadłub, hierarchiczne grupowanie

Używam hierarchicznego łączenia w klastry, aby spróbowaćwizualizuj duży zestaw danych spłaszczonych do dwóch wymiarów. Chciałbym stworzyć wizualizację, która pozwoli mi spojrzeć na dane z różnych wysokości w hierarchii, przez uczynienie z klastrów wypukłych kadłubów ich punktów składowych. Najtrudniejszą częścią tego problemu jest to, że potrzebuję algorytmu, który może wydajnie łączyć wypukłe kadłuby klastrów, kiedy poruszam się w górę hierarchii. Widziałem wiele algorytmów do obliczania wypukłych kadłubów punktów w czasie O (n log n), ale wydaje się, że byłoby znacznie wydajniej w tym przypadku wykorzystać podstrukturę problemu, ale ja jestem nie do końca pewny jak.

Edytować:

Aby uzyskać więcej informacji, struktura danych totablica, która zaczyna się od oryginalnych punktów grupowania, a następnie mówi, które punkty / klastry są połączone w celu utworzenia następnego skupienia. Jest to trochę jak struktura drzewa / wskaźnika, ale zawarta w jednej dużej tablicy, ważną rzeczą jest to, że efektywnie jest zobaczyć, jakie dwa klastry stanowią jakąkolwiek superklazję, ale nie jest ona wydajna zestaw wszystkich punktów należących do klastra, więc każdy rozsądny algorytm musi działać od dołu do góry.

Powiedzmy więc, że jesteśmy w środku hierarchiigdzieś, a wstępna hierarchia mówi, że klastry A i B są połączone w celu utworzenia klastra C. Oddajemy się od dołu do góry, więc obliczyliśmy już wypukłe kadłuby punktów w klastrach A i B, więc musimy po prostu połączyć je, aby uzyskać wypukły kadłub klastra. Wypukły kadłub w klastrze A może w rzeczywistości być pojedynczym punktem, parą lub pełnym poligonem. To samo dotyczy gromady B. Tak więc istnieje kilka przypadków, w których powinny one zostać połączone w celu utworzenia wypukłego kadłuba gromady C, ale założę się, że istnieje sprytne rozwiązanie, które prawdopodobnie traktowałoby pojedyncze i pary w taki sam sposób, jak wielokąty.

Najbardziej oczywistym rozwiązaniem byłoby obliczeniewypukły kadłub z połączonym zbiorem punktów z wypukłych kadłubów klastrów A i B. Ale muszę to zrobić w hierarchii 100k punktów, więc zastanawiam się, czy istnieje skuteczniejszy sposób połączenia wypukłych kadłubów A i B.

Edytuj 2:

         /----5
1---/    / 
/       / B 8
2 A 3  C 6   /
 /       /
4--------7

Okej, więc spróbowałem zrobić ASCII ilustracjęo co mi chodzi. Wypukły kadłub gromady A to 1-2-3-4, wypukły kadłub B wynosi 5-6-7-8, a wypukły kadłub C to 1-2-4-7-8-5. Przypuszczalnie, klastry A i B zawierają dodatkowe punkty wewnątrz swoich kadłubów, ale te wyraźnie nie mogą stać się częścią kadłuba C, więc problemem jest algorytm, który określa, gdzie "splecić" kadłuby klastra A i B w celu utworzenia kadłub C, na podstawie współrzędnych punktów. Jest to indukcyjny krok całego procesu. (Ostatecznie C będzie połączone z klastrem D i tak dalej, aż algorytm zakończy się najwyższą gromadą, która będzie miała wypukły kadłub wypukłego kadłuba wszystkich punktów).

Odpowiedzi:

Istnieją co najmniej dwa wypukłe algorytmy scalania kadłuba, o których jestem świadomy - obrotowe zaciski Toussaint (sekcja 5 artykułu) i algorytm mostkowania Preparata i Hong (patrz sekcja 3 artykułu). Oba te algorytmy wymagają czasu liniowego h = h₁ + godz₂, gdzie h₁ i h₂ to liczba wierzchołków kadłuba odpowiednio w pierwszym i drugim wypukłym kadłubie.

Istnieją różne metody, które umożliwiają"zaktualizuj" wypukły kadłub podczas dodawania nowego punktu. Również niektóre metody wypukłego kadłuba i triangulacji Delauneya dobrze działają już na wylot, co powinno dobrze się z tym bawić. Spójrz na algorytm s-kadłuba.

Jednakże, ponieważ mówimy o hierarchicznym grupowaniu, wypukły kadłub jest prawdopodobnie najmniejszym z twoich problemów jeśli chodzi o złożoność.

Hierarchiczne grupowanie nie skaluje się dobrze do dużych zestawów danych, ponieważ algorytmy są zwykle O(n^3) w naturze (co czyni je jednym z najwolniejszych algorytmów grupowania, które można znaleźć w praktyce). Więc dodatkowo należy obliczyć liczbę wypukłych kadłubów nie sprawiają tak wiele różnicy, biorąc pod uwagę, że tworzenie klastrów było droższe. Prawdopodobnie potrzebujesz szybkiej, przyrostowej implementacji O(n log n) Algorytm wypukłego kadłuba.