Wybór siatki dla zadanych punktów

Borneq · Post autor: **Borneq** » 19 lip 2015, o 10:46

Mamy zadane n punktów na ograniczonej płaszczyźnie (0,0)-(max,max), niektóre mogą leżeć w tym samym miejscu co inny punkt. Wybieramy teraz znacznie mniejszą liczbę m punktów (nie z tych n, ale z płaszczyzny), takich że każdy z nich ma inne współrzędne oraz tych m punków dzieli płaszczyznę na klasy; każda klasa to punkty płaszczyzny najbliższe jednemu z punków m. Siatka Voronoi przedstawia ten podział. Teraz problemem jest: jak wybrać współrzędne tych m punktów, aby te n punków leżało dostatecznie blisko swoich reprezentantów. To znaczy, jeśli punkt byłby w danej klasie to musi leżeć blisko centrum. Można na przykład zminimalizować sumę kwadratów odległości.

Adifek · Post autor: **Adifek** » 19 lip 2015, o 14:29

Algorytm K-średnich. (K-means). Można dodatkowo dobierać różne jądra, żeby uzyskać pożądane efekty np. zamiast zwykłych odległości można brać gęstości rozkładu normalnego itd. -- 19 lipca 2015, 13:36 --Może dodam coś ważnego. Żeby złożoność nas nie zabijała nie przebiega się wszystkich \(\displaystyle{ {n \choose m}}\) wyborów punktów, tylko zwykle losuje się pewną liczbę takich \(\displaystyle{ m}\)-ek i wybiera spośród nich najlepszą. Wtedy złożoność jest ok, a średni wynik jest zwykle niewiele gorszy od od rzeczywiście optymalnego.

Borneq · Post autor: **Borneq** » 19 lip 2015, o 19:48

Czy losowania wystarczą? Czy też jedną wylosowaną m-kę da się doprowadzić do innego rozwiązania? Zastanawiałem się nad wersją trójwymiarową dla przestrzeni kolorów. Jeśli chodzi o kwantyzację kolorów, to bardzo dobre rezultaty daje algorytm NeuQuant, który uczy sieć Kohonena. Lepsze rezultaty niż algorytm Wu, który dzieli na prostopadłościany, choć być może jest to podział na prostopadłościany najlepszy. Ale może kryterium sumy odległości jest lepsze.

Adifek · Post autor: **Adifek** » 19 lip 2015, o 22:22

Czy losowania wystarczają możesz sprawdzić na youtube patrząc na sugerowane filmy W podanych przez Ciebie algorytmach także się losuje (czytałeś w ogóle co one robią?), bo to jest jedyna rozsądna droga dla dużych danych.

Zauważ, że jeśli chcielibyśmy przebiec wszystkie możliwości, złożoność wyskoczyłaby nam rzędu \(\displaystyle{ O(n^m T(n))}\), gdzie \(\displaystyle{ T(n)}\) to złożoność operacji jakie wykonujemy dla jakiejś wybranej \(\displaystyle{ m}\)-ki.

Wszystko zależy od tego, co dokładnie robisz. Zaproponowany przeze mnie pomysł jest najczęściej używaną metodą automatycznego klastrowania, często wykorzystywaną w szeroko pojętym machine learningu