Jak „inteligentnie” skumulować zbiór posortowanych danych?

11

Staram się inteligentnie bin posortować kolekcję. Mam kolekcję fragmentów danych. Ale wiem, że te dane wpisuje się nierówno wielkości pojemników. Nie wiem, jak inteligentnie wybrać punkty końcowe, aby odpowiednio dopasować dane. na przykład:nm

Powiedzmy, że mam w mojej kolekcji 12 produktów i wiem, że dane zmieszczą się w 3 pojemnikach:

Index:  1 2 3 4 5 6 7 8 9 10 11 12
Value:  1 1 1 3 3 3 3 3 3 5  5  6

Jak inteligentnie wybrać moje punkty przerwania dla pojemników ?i={13},{49},{1012}

Obecna implementacja, którą mam, dzieli dane na pojemniki o równej wielkości, a następnie bierze średnią punktów końcowych, aby znaleźć indeksy na końcu pojemników. Działa to tak:

Index:  1 2 3 4 5 6 7 8 9 10 11 12
Value:  1 1 1 3 3 3 3 3 3 5  5  6

first break evenly: i = 1-4, 5-8, 9-12
mean endpoints:  between 4 and 5: (3+3)/2 = 3
                 between 8 and 9: (3+3)/2 = 3

Więc teraz wszystko poniżej 3 mieści się w bin 1, wszystko powyżej 3, ale poniżej 3 pasuje do bin 2, a wszystko powyżej 3 mieści się w bin 3. Możesz zobaczyć, na czym polega mój problem. Jeśli dane mają nierówne pojemniki, moja metoda zawodzi.

Znajomy wspomniał o algorytmie k-najbliższego sąsiada, ale nie jestem pewien.

Matthew Kemnetz
źródło
1
Czy możesz wyjaśnić, co oznacza „inteligentnie”? Co próbujesz osiągnąć dzięki binowaniu? Dlaczego przede wszystkim binningujesz?
whuber
<3bin13&<4bin24bin3
Mam na myśli inteligentnie, jak nie naiwnie, jak to robiłem, zakładając, że pojemniki są równomiernie rozmieszczone. jeśli fragment danych wpada do określonego pojemnika, co mówi mi coś bardzo ważnego o tym fragmencie danych. Sortuję dane w celu ustalenia wskaźników przerwania bin, a następnie decyduję, który bin każdy kawałek danych przypada indywidualnie.
Matthew Kemnetz
chyba że zrobiłem coś złego w uśrednianiu, myślę, że mam rację. wybierając parzyste; y pojemniki z odstępami wszystkie moje punkty końcowe to 3. Więc właściwie nie mogę bin moich danych. Dlatego moja implementacja psuje się bez równomiernie rozłożonych pojemników.
Matthew Kemnetz
Oto coś, co zrobiłem w nieco innym otoczeniu.
Makro

Odpowiedzi:

9

Myślę, że to, co chcesz zrobić, nazywa się klastrowaniem. Chcesz zgrupować swoje „Wartości” w taki sposób, aby podobne wartości były zbierane w tym samym pojemniku, a liczba wszystkich pojemników była wstępnie ustawiona.

Możesz rozwiązać ten problem za pomocą algorytmu klastrowania k-średnich . W MATLAB możesz to zrobić poprzez:

bin_ids = kmeans(Values,3); 

Powyższe wywołanie Valuesgrupuje wartości w trzy grupy, dzięki czemu wariancja wewnątrz grupy jest minimalna.

emrea
źródło
1
Też to odkryłem. Właśnie to wdrożyłem i działało doskonale. Przyszedłem tutaj, aby odpowiedzieć na moje pytanie, ale pobiłeś mnie! Grupowanie było tym, co próbowałem zrobić.
Matthew Kemnetz
8

k-średnie jest opcją, ale nie jest zbyt sensowne dla danych 1-wymiarowych. W danych jednowymiarowych masz jedną ogromną zaletę: dane można w pełni posortować.

Zamiast tego spójrz na optymalizację naturalnych przerw :
http://en.wikipedia.org/wiki/Jenks_natural_breaks_optimization

Ma ZAKOŃCZENIE - Anony-Mus
źródło
To jest bardzo interesujące. Czy mógłbyś bardziej szczegółowo wyjaśnić, dlaczego może to być lepsze niż oznacza k?
Matthew Kemnetz
Głównym powodem, dla którego pytam, jest to, że używam MATLAB-a dla mojego algorytmu i nie mogłem znaleźć optymalizacji naturalnych przerw w Jenks w żadnych zestawach narzędzi itp., Więc będę musiał zaimplementować własne. Chciałem tylko wiedzieć, ile to może być lepsze / szybsze, zanim zmienię biegi i zastosuję to.
Matthew Kemnetz
1
k-znaczy jest całkiem głupi. Ma środki i zawsze dzieli się na środek dwóch środków. Biorąc pod uwagę np. 0 1 2 3 4 5 7 7 7, k-średnie wolą podzielić między 4 a 5. Czasami nawet podzieli się między 3 i 4.
Ma ZAKOŃCZENIE - Anony-Mousse