Czym jest ta struktura / koncepcja danych, w której wykres punktów definiuje podział na przestrzeń

15

Zetknąłem się z algorytmem rozwiązywania rzeczywistego problemu i pamiętam klasę, w której wziąłem udział, gdzie zrobiłem coś bardzo podobnego dla niektórych na zadanie domowe. To wygląda tak

Zasadniczo jest to wykres punktów, a linie są rysowane tak, aby były w równej odległości między dwoma punktami. Tworzy idealną przegrodę, w której linie wokół punktu tworzą kształt obszaru najbliższego temu punktowi. Czy to komukolwiek dzwoni? Trudno mi było przeglądać opisy i uzyskiwać wyniki. I nie wiem, jak inaczej to opisać. Mam nadzieję, że obraz pomaga.

— Brian
źródło

Oglądane 1667 razy od wczoraj? Czy SE jest hakowany?

— HEKTO

@HEKTO zostało wyświetlone jako jedno z „Gorących pytań sieciowych”.

— John L.,

31

Co opisane jest diagram woronoja .

Oto fragment Wikipedii.

${p_1, \cdots, p_n}$ $p_k$ $R_k$ $p_k$ jest mniejsza lub równa jego odległości do jakichkolwiek innych punktów. Każda taka komórka jest uzyskiwana ze przecięcia półprzestrzeni, a zatem jest wypukłym wielokątem. Segmenty linii na diagramie Voronoi to wszystkie punkty na płaszczyźnie, które są w równej odległości od dwóch najbliższych miejsc. Wierzchołki (węzły) Voronoi są punktami w równej odległości od trzech (lub więcej) miejsc.

— John L.
źródło

4

+1. Powstrzymałem się od wspominania o nich i poszedłem do implementacji, ponieważ pamiętam, że moi profesorowie wspominali o nich z przypisem, że diagramy Voronoi są skomplikowane obliczeniowo do wdrożenia w większych wymiarach. Dzięki prostym implementacjom kNN praca jest wykonywana znacznie lepiej. Jednak warunek, że „linie są narysowane tak, aby były w równej odległości między dwoma punktami” może nie być spełniony.

— Sagnik

3

Szukasz algorytmu klasyfikacji wieloklasowej. Proponuję spojrzeć na:

Algorytm K-Nearest Neighbors (lub KNN). Oto wprowadzający post na blogu .
Obsługa maszyn wektorowych. Możesz zacząć czytać o tym tutaj .

— Sagnik
źródło