Mam pogrupować obiekty na płaszczyźnie w taki sposób, aby odległość pomiędzy poszczególnymi grupami nie była większa niż jakaś zadana liczba n. Obiekty są wyrażone w postaci listy punktów, np. kwadrat [(0, 0), (1, 0), (0, 1), (1, 1)]. W sieci są przykłady jak pogrupować takie pojedyncze punkty, ale nijak nie wiem jak to przełożyć na figury. Może ktoś miał już do czynienia z podobnymi rzeczami i mógłby podrzucić jakiś przykład, albo nakierować jak się za to zabrać?
0
1
Odległość między poszczególnymi grupami czy wewnątrz pojedynczej grupy?
Może np. K-means clustering lub coś podobnego, tu jest artykulik na ten temat
@komuher powinien być w stanie coś więcej powiedzieć
0
Odległość między poszczególnymi grupami. K-means ma chyba z góry założone na ile grup podzielić a u mnie tego nie wiadomo, więc chyba odpada.
0
kiyo napisał(a):
Odległość między poszczególnymi grupami.
Czyli mając np. tak rozsiane dane:
Ideałem dla Ciebie będzie, jeśli granice grup będą przebiegać po granicach komórek?
Przejrzałem te algorytmy z artykułu, który wygrzebałem (pomijając jeden krótki epizod na pograniczu, zupełnie nie siedzę w DS/ML, fajnie by było jakby komuher jednak tu zajrzał bo prędzej coś sensownego wymóżdży) i mam takie podejrzenie, że gdybyś wykorzystał etap sprawdzania sąsiedztwa z DBSCAN i zmodyfikował go tak, by zamiast budować grupę tyczył przyszłe granice pomiędzy nimi, to może coś by z tego wyszło?
K-means ma chyba z góry założone na ile grup podzielić a u mnie tego nie wiadomo, więc chyba odpada.
To byś jeszcze obszedł np. dodatkowo sterując docelową liczbą grup, ale jak chcesz uzyskać minimalne odległości grup to raczej się nie nada.
0
kiyo napisał(a):
Nie muszę mieć minimalnych odległości pomiędzy grupami. Po prostu ta odległość nie może być większa od n.
To może jakaś wariacja na temat np. divisive clustering + odległość między grupami jako warunek zaakceptowania pod-podziału? Ewentualnie - przy czym nie powiedziałeś w sumie ile będzie tych danych, czy to idzie w dziesiątki, tysiące czy ile, ani jak te maksymalne odległości mają się do rozmiaru całej przestrzeni - przychodzi mi do głowy jeszcze inna alternatywa, jeśli danych jest na tyle, by to przeszło:
- najpierw zrobić wstępny clustering by wytypować mniejsze grupy
- łączyć powstałe grupy tak, by wyeliminować niedopuszczalnie długie odległości
I jeszcze jedno, chcesz aby każda grupa miała po prostu co najmniej jedną inną grupę nie dalej od siebie, niż o n, a nie żadne dwie grupy nie mogą być dalej od siebie, niż n, tak?
0
przy czym nie powiedziałeś w sumie ile będzie tych danych, czy to idzie w dziesiątki, tysiące czy ile, ani jak te maksymalne odległości mają się do rozmiaru całej przestrzeni
Tego nie mam sprecyzowanego. Wiem tylko, że na wejściu dostaję zbiór tych figur jako listę punktów, czyli tutaj jest widzimisię testującego bo może być 5, albo 5 milionów.
I jeszcze jedno, chcesz aby każda grupa miała po prostu co najmniej jedną inną grupę nie dalej od siebie, niż o n, a nie żadne dwie grupy nie mogą być dalej od siebie, niż n, tak?
W wynikowych grupach odległość dwóch najbliższych figur nie może być większa od n. Dokładnie tak ma być
0
Nie wiem czy dobrze zrozumiałem ale wydaje sie to byc w miare proste i nie trzeba nawet zbytnio uderzac w k-meansy ani bardziej skomplikowane metody klasteryzacji.
"Obiekty są wyrażone w postaci listy punktów np. kwadrat [(0, 0), (1, 0), (0, 1), (1, 1)]. " -> Jesli chodzi o jakies zaliczenie na studiach to pewnie wystarczy napisac algorytm wyszukajacy czy w pozycjach maksymalnie oddalony o n znajduje sie jakis inny objekt (klaster) jesli tak to grupujemy je po tym. (https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.norm.html tym wyliczasz odleglosc)
0
Dobra doczytałem tutaj pewnie chodziło o klasteryzacje hierarchiczna -> https://towardsdatascience.com/machine-learning-algorithms-part-12-hierarchical-agglomerative-clustering-example-in-python-1e18e0075019 poczytaj sobie i mozesz to w prosty sposób połaczyć z informacją o tych swoich "figurach" czy obiektach (musisz je gdzies storowac po prostu i bedziesz wiedzial w ktorym klastrze sie znajda) Wiecej nie pomoge jesli chodzi o hierarchiczne algorytmy bo jedyny raz kiedy robilem cos z klasteryzacja hierarchiczna to sam poczatek mojej nauki :D